1+ import java .util .LinkedList ;
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 MAXIMUM_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.75f ;
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 array with each cell being a linked list
23+ LinkedList <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 >MAXIMUM_CAPACITY )
40+ this .capacity =MAXIMUM_CAPACITY ;
41+ else
42+ this .capacity =trimToPowerOf2 (initialCapacity );
43+
44+ this .loadFactorThreshold =loadFactorThreshold ;
45+ table =new LinkedList [capacity ];
46+ }
47+
48+ @ Override /** Remove all of the entries from this map */
49+ public void clear () {
50+ size =0 ;
51+ removeEntries ();
52+ }
53+
54+ @ Override /** Return true if the specified key is in the map */
55+ public boolean containsKey (K key ) {
56+ if (get (key ) !=null )
57+ return true ;
58+ else
59+ return false ;
60+ }
61+
62+ @ Override /** Return true if this map contains the value */
63+ public boolean containsValue (V value ) {
64+ for (int i =0 ;i <capacity ;i ++) {
65+ if (table [i ] !=null ) {
66+ LinkedList <Entry <K ,V >>bucket =table [i ];
67+ for (Entry <K ,V >entry :bucket )
68+ if (entry .getValue ().equals (value ))
69+ return true ;
70+ }
71+ }
72+
73+ return false ;
74+ }
75+
76+ @ Override /** Return a set of entries in the map */
77+ public java .util .Set <MyMap .Entry <K ,V >>entrySet () {
78+ java .util .Set <MyMap .Entry <K ,V >>set =
79+ new java .util .HashSet <>();
80+
81+ for (int i =0 ;i <capacity ;i ++) {
82+ if (table [i ] !=null ) {
83+ LinkedList <Entry <K ,V >>bucket =table [i ];
84+ for (Entry <K ,V >entry :bucket )
85+ set .add (entry );
86+ }
87+ }
88+
89+ return set ;
90+ }
91+
92+ @ Override /** Return the value that matches the specified key */
93+ public V get (K key ) {
94+ int bucketIndex =hash (key .hashCode ());
95+ if (table [bucketIndex ] !=null ) {
96+ LinkedList <Entry <K ,V >>bucket =table [bucketIndex ];
97+ for (Entry <K ,V >entry :bucket )
98+ if (entry .getKey ().equals (key ))
99+ return entry .getValue ();
100+ }
101+
102+ return null ;
103+ }
104+
105+ @ Override /** Return true if this map contains no entries */
106+ public boolean isEmpty () {
107+ return size ==0 ;
108+ }
109+
110+ @ Override /** Return a set consisting of the keys in this map */
111+ public java .util .Set <K >keySet () {
112+ java .util .Set <K >set =new java .util .HashSet <>();
113+
114+ for (int i =0 ;i <capacity ;i ++) {
115+ if (table [i ] !=null ) {
116+ LinkedList <Entry <K ,V >>bucket =table [i ];
117+ for (Entry <K ,V >entry :bucket ) {
118+ set .add (entry .getKey ());
119+ }
120+ }
121+ }
122+
123+ return set ;
124+ }
125+
126+ @ Override /** Add and entry (key, value) into the map */
127+ public V put (K key ,V value ) {
128+ if (get (key ) !=null ) {// The key is already in the map
129+ int bucketIndex =hash (key .hashCode ());
130+ LinkedList <Entry <K ,V >>bucket =table [bucketIndex ];
131+ for (Entry <K ,V >entry :bucket )
132+ if (entry .getKey ().equals (key )) {
133+ V oldValue =entry .getValue ();
134+ // Replace old value with new value
135+ entry .value =value ;
136+ // Return the old value for the key
137+ return oldValue ;
138+ }
139+ }
140+
141+ // Check load factor
142+ if (size >=capacity *loadFactorThreshold ) {
143+ if (capacity ==MAXIMUM_CAPACITY )
144+ throw new RuntimeException ("Exceeding maximum capacity" );
145+
146+ rehash ();
147+ }
148+
149+ int bucketIndex =hash (key .hashCode ());
150+
151+ // Create a linked list for the bucket if not already created
152+ if (table [bucketIndex ] ==null ) {
153+ table [bucketIndex ] =new LinkedList <Entry <K ,V >>();
154+ }
155+
156+ // Add a new entry (key, value) to hashtable[index]
157+ table [bucketIndex ].add (new MyMap .Entry <K ,V >(key ,value ));
158+
159+ size ++;// Increase size
160+
161+ return value ;
162+ }
163+
164+ @ Override /** Remove the entries for the specifie key */
165+ public void remove (K key ) {
166+ int bucketIndex =hash (key .hashCode ());
167+
168+ // Remove the first entry that matches the key from a bucket
169+ if (table [bucketIndex ] !=null ) {
170+ LinkedList <Entry <K ,V >>bucket =table [bucketIndex ];
171+ for (Entry <K ,V >entry :bucket )
172+ if (entry .getKey ().equals (key )) {
173+ bucket .remove (entry );
174+ size --;// Decrease size
175+ break ;// Remove just one entry that matches the key
176+ }
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 the 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 [i ] !=null ) {
191+ LinkedList <Entry <K ,V >>bucket =table [i ];
192+ for (Entry <K ,V >entry :bucket ) {
193+ set .add (entry .getValue ());
194+ }
195+ }
196+ }
197+
198+ return set ;
199+ }
200+
201+ /** Hash function */
202+ private int hash (int hashCode ) {
203+ return supplementalHash (hashCode ) & (capacity -1 );
204+ }
205+
206+ /** Ensure the hashing is evenly distributed */
207+ private int supplementalHash (int h ) {
208+ h ^= (h >>>20 ) ^ (h >>>12 );
209+ return h ^ (h >>>7 ) ^ (h >>>4 );
210+ }
211+
212+ /** Return a power of 2 for initialCapacity */
213+ private int trimToPowerOf2 (int initialCapacity ) {
214+ int capacity =1 ;
215+ while (capacity <initialCapacity ) {
216+ capacity <<=1 ;// Same as capacity *= 2. <= is more efficient
217+ }
218+
219+ return capacity ;
220+ }
221+
222+ /** Remove all entries from each bucket */
223+ private void removeEntries () {
224+ for (int i =0 ;i <capacity ;i ++) {
225+ if (table [i ] !=null ) {
226+ table [i ].clear ();
227+ }
228+ }
229+ }
230+
231+ /** Rehash the map */
232+ private void rehash () {
233+ java .util .Set <MyMap .Entry <K ,V >>set =entrySet ();// Get entries
234+ capacity <<=1 ;// Same as capacity *= 2. <= is more efficient
235+ table =new LinkedList [capacity ];// Crate a new hash table
236+ size =0 ;
237+
238+ for (Entry <K ,V >entry :set ) {
239+ put (entry .getKey (),entry .getValue ());// Store to new table
240+ }
241+ }
242+
243+ @ Override /** Return a string representation for this map */
244+ public String toString () {
245+ StringBuilder builder =new StringBuilder ("[" );
246+ for (int i =0 ;i <capacity ;i ++) {
247+ if (table [i ] !=null &&table [i ].size () >0 )
248+ for (Entry <K ,V >entry :table [i ]) {
249+ builder .append (entry );
250+ }
251+ }
252+
253+ builder .append ("]" );
254+ return builder .toString ();
255+ }
256+ }
