1+ import java .util .ArrayList ;
2+
3+ public class MyHashMap <K ,V >implements MyMap <K ,V > {
4+ // Define the default hash-table size. Must be a power of 2
5+ private static int DEFAULT_INITIAL_CAPACITY =4 ;
6+
7+ // Define the maximum hash-table size. 1 << 30 is same as 2 ^ 30
8+ private static int MAMIMUM_CAPACITY =1 <<30 ;
9+
10+ // Current hash-table capacity. Capacity is a power of 2
11+ private int capacity ;
12+
13+ // Define default load factor
14+ private static float DEFAULT_MAX_LOAD_FACTOR =0.5f ;
15+
16+ // Specify a load factor used in the hash table
17+ private float loadFactorThreshold ;
18+
19+ // The number of entries in the map
20+ private int size =0 ;
21+
22+ // Hash table is an ArrayList
23+ private ArrayList <MyMap .Entry <K ,V >>table ;
24+
25+ /** Construct a map with the default capacity and load factor */
26+ public MyHashMap () {
27+ this (DEFAULT_INITIAL_CAPACITY ,DEFAULT_MAX_LOAD_FACTOR );
28+ }
29+
30+ /** Construct a map with the specified initial capacity and
31+ * default load factor */
32+ public MyHashMap (int initialCapacity ) {
33+ this (initialCapacity ,DEFAULT_MAX_LOAD_FACTOR );
34+ }
35+
36+ /** Construct a map with the specified initial capacity
37+ * and load factor */
38+ public MyHashMap (int initialCapacity ,float loadFactorThreshold ) {
39+ if (initialCapacity >MAMIMUM_CAPACITY )
40+ this .capacity =MAMIMUM_CAPACITY ;
41+ else
42+ this .capacity =trimToPowerOf2 (initialCapacity );
43+
44+ this .loadFactorThreshold =loadFactorThreshold ;
45+ table =new ArrayList <>();
46+ for (int i =0 ;i <capacity ;i ++) {
47+ table .add (null );
48+ }
49+ }
50+
51+ @ Override /** Remove all of the entries from this map */
52+ public void clear () {
53+ size =0 ;
54+ removeEntries ();
55+ }
56+
57+ @ Override /** Return true if the specified key is in the map */
58+ public boolean containsKey (K key ) {
59+ if (get (key ) !=null )
60+ return true ;
61+ else
62+ return false ;
63+ }
64+
65+ @ Override /** Return true if this map contains the value */
66+ public boolean containsValue (V value ) {
67+ for (int i =0 ;i <capacity ;i ++) {
68+ if (table .get (i ) !=null &&
69+ table .get (i ).getValue () ==value )
70+ return true ;
71+ }
72+
73+ return false ;
74+ }
75+
76+ @ Override /** Return a set of entries in the map */
77+ public java .util .Set <Entry <K ,V >>entrySet () {
78+ java .util .Set <Entry <K ,V >>set =new java .util .HashSet <>();
79+
80+ for (int i =0 ;i <capacity ;i ++) {
81+ if (table .get (i ) !=null ) {
82+ set .add (table .get (i ));
83+ }
84+ }
85+
86+ return set ;
87+ }
88+
89+ @ Override /** Return the value that matches the specified key */
90+ public V get (K key ) {
91+ int hash1 =hash (key .hashCode ());
92+ int index =hash1 ;
93+ int j =0 ;
94+
95+ while (table .get (index ) ==null ) {
96+ // Secondary hash: (k + j * h'(key)) % N
97+ index =hash1 +j ++ *hash2 (hash1 );
98+ index %=capacity ;
99+ }
100+
101+ if (table .get (index ).getKey () ==key ) {
102+ return table .get (index ).getValue ();
103+ }
104+
105+ return null ;
106+ }
107+
108+ @ Override /** Return true if this map contains no entries */
109+ public boolean isEmpty () {
110+ return size ==0 ;
111+ }
112+
113+ @ Override /** Return a set consisting of the keys in this map */
114+ public java .util .Set <K >keySet () {
115+ java .util .Set <K >set =new java .util .HashSet <>();
116+
117+ for (int i =0 ;i <capacity ;i ++) {
118+ if (table .get (i ) !=null )
119+ set .add (table .get (i ).getKey ());
120+ }
121+
122+ return set ;
123+ }
124+
125+ @ Override /** Add an entry (key, value) into the map */
126+ public V put (K key ,V value ) {
127+ int hash1 =hash (key .hashCode ());
128+ int index =hash1 ;
129+ int j =0 ;
130+
131+ while (table .get (index ) !=null ) {
132+ // Add a new entry (key, value)
133+ if (table .get (index ).getKey () ==key ) {
134+ Entry <K ,V >entry =table .get (index );
135+ V oldValue =entry .getValue ();
136+ // Replace old value with new value
137+ entry .value =value ;
138+ table .set (index ,entry );
139+ // Return the old value for the key
140+ return oldValue ;
141+ }
142+
143+ // Secondary hash: (k + j * h'(key)) % N
144+ index =hash1 +j ++ *hash2 (hash1 );
145+ index %=capacity ;
146+ }
147+
148+ // Check load factor
149+ if (size >=capacity *loadFactorThreshold ) {
150+ if (capacity ==MAMIMUM_CAPACITY )
151+ throw new RuntimeException ("Exceeding maximum capacity" );
152+ rehash ();
153+ }
154+
155+ // Add a new entry(key, value) to hashtable
156+ table .set (index ,new MyMap .Entry <K ,V >(key ,value ));
157+
158+ size ++;// Increase size;
159+
160+ return value ;
161+ }
162+
163+ @ Override /** Remove the entry for the specified key */
164+ public void remove (K key ) {
165+ int hash1 =hash (key .hashCode ());
166+ int index =hash1 ;
167+ int j =0 ;
168+
169+ while (table .get (index ) ==null ) {
170+ // Secondary hash: (k + j * h'(key)) % N
171+ index =hash1 +j ++ *hash2 (hash1 );
172+ index %=capacity ;
173+ }
174+
175+ if (table .get (index ).getKey () ==key ) {
176+ table .remove (index );
177+ }
178+ }
179+
180+ @ Override /** Return the number of entries in this map */
181+ public int size () {
182+ return size ;
183+ }
184+
185+ @ Override /** Return a set consisting of values in this map */
186+ public java .util .Set <V >values () {
187+ java .util .Set <V >set =new java .util .HashSet <>();
188+
189+ for (int i =0 ;i <capacity ;i ++) {
190+ if (table .get (i ) !=null )
191+ set .add (table .get (i ).getValue ());
192+ }
193+
194+ return set ;
195+ }
196+
197+ /** Hash function */
198+ private int hash (int hashCode ) {
199+ return supplementalHash (hashCode ) & (capacity -1 );
200+ }
201+
202+ /** Ensure the hashing is evenly distributed */
203+ private static int supplementalHash (int h ) {
204+ h ^= (h >>>20 ) ^ (h >>>12 );
205+ return h ^ (h >>>7 ) ^ (h >>>4 );
206+ }
207+
208+ /** Secondary hash function */
209+ private int hash2 (int hash ) {
210+ return (7 -hash ) & (7 -1 );
211+ }
212+
213+ /** Return a power of 2 for initialCapacity */
214+ private int trimToPowerOf2 (int initialCapacity ) {
215+ int capacity =1 ;
216+ while (capacity <initialCapacity ) {
217+ capacity <<=1 ;
218+ }
219+
220+ return capacity ;
221+ }
222+
223+ /** Remove all entries from map */
224+ private void removeEntries () {
225+ table .clear ();
226+ }
227+
228+ /** Rehash the map */
229+ private void rehash () {
230+ capacity <<=1 ;// Same as capacity *= 2. <= is more efficient
231+ for (int i =size +1 ;i <capacity ;i ++) {
232+ table .add (null );
233+ }
234+ }
235+
236+ @ Override /** Return a string repersentation of this map */
237+ public String toString () {
238+ StringBuilder builder =new StringBuilder ("[" );
239+
240+ for (Entry <K ,V >entry :table ) {
241+ if (entry !=null &&table .size () >0 ) {
242+ builder .append (entry );
243+ }
244+ }
245+
246+ builder .append ("]" );
247+ return builder .toString ();
248+ }
249+ }
