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 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.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+ 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 >MAXIMUM_CAPACITY )
40+ this .capacity =MAXIMUM_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+ @ Override /** Remove all of the entries from this map */
51+ public void clear () {
52+ size =0 ;
53+ removeEntries ();
54+ }
55+
56+ @ Override /** Return true if the specified key is in the map */
57+ public boolean containsKey (K key ) {
58+ if (get (key ) !=null )
59+ return true ;
60+ else
61+ return false ;
62+ }
63+
64+ @ Override /** Return true if this map contains the value */
65+ public boolean containsValue (V value ) {
66+ for (int i =0 ;i <capacity ;i ++) {
67+ if (table .get (i ) !=null &&table .get (i ).getValue () ==value )
68+ return true ;
69+ }
70+
71+ return false ;
72+ }
73+
74+ @ Override /** Return a set of entries in the map */
75+ public java .util .Set <MyMap .Entry <K ,V >>entrySet () {
76+ java .util .Set <MyMap .Entry <K ,V >>set =
77+ new java .util .HashSet <>();
78+
79+ for (int i =0 ;i <capacity ;i ++) {
80+ if (table .get (i ) !=null ) {
81+ set .add (table .get (i ));
82+ }
83+ }
84+
85+ return set ;
86+ }
87+
88+ @ Override /** Return the value that matches the specified key */
89+ public V get (K key ) {
90+ int index =hash (key .hashCode ());
91+ int i =index -1 ;// One cycle of the arraylist
92+
93+ // While index is empty or a collision occurs check the next index
94+ while (index !=i && (table .get (index ) ==null ||
95+ table .get (index ).getKey () !=key )) {
96+ index ++;
97+ index %=capacity ;
98+ }
99+
100+ if (table .get (index ).getKey () ==key ) {
101+ return table .get (index ).getValue ();
102+ }
103+
104+ return null ;
105+ }
106+
107+ @ Override /** Return true if this map contain no entries */
108+ public boolean isEmpty () {
109+ return size ==0 ;
110+ }
111+
112+ @ Override /** Return a set consisting of the keys in this map */
113+ public java .util .Set <K >keySet () {
114+ java .util .Set <K >set =new java .util .HashSet <K >();
115+
116+ for (int i =0 ;i <capacity ;i ++) {
117+ if (table .get (i ) !=null )
118+ set .add (table .get (i ).getKey ());
119+ }
120+
121+ return set ;
122+ }
123+
124+ @ Override /** Add an entry (key, value) into the map */
125+ public V put (K key ,V value ) {
126+ int index =hash (key .hashCode ());
127+
128+ while (table .get (index ) !=null ) {
129+ // Add a new entry (key, value)
130+ if (table .get (index ).getKey () ==key ) {
131+ Entry <K ,V >entry =table .get (index );
132+ V oldvalue =entry .getValue ();
133+ // Replace old value with new value
134+ entry .value =value ;
135+ table .set (index ,entry );
136+ // Return the old value for the key
137+ return oldvalue ;
138+ }
139+
140+ // Collision check if the next index is available
141+ index ++;
142+ index %=capacity ;
143+ }
144+
145+ // Check load factor
146+ if (size >=capacity *loadFactorThreshold ) {
147+ if (capacity ==MAXIMUM_CAPACITY )
148+ throw new RuntimeException ("Exceeding maximum capacity" );
149+ rehash ();
150+ }
151+
152+ // Add a new entry (key, value) to hashtable
153+ table .set (index ,new MyMap .Entry <K ,V >(key ,value ));
154+
155+ size ++;// Increase size
156+
157+ return value ;
158+ }
159+
160+ @ Override /** Remove the entry for the specified key */
161+ public void remove (K key ) {
162+ int index =hash (key .hashCode ());
163+ int i =index -1 ;// One cycle of the arraylist
164+
165+ // While index is empty or there is a
166+ // collision check the next index in cycle
167+ while ((table .get (index ) ==null ||
168+ table .get (index ).getKey () !=key ) &&i !=index ) {
169+ index ++;
170+ index %=capacity ;
171+ }
172+
173+ // Remove the entry that matches the key
174+ if (table .get (index ).getKey () ==key ) {
175+ table .remove (index );
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 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+ /** Return a power of 2 for initialCapacity */
209+ private int trimToPowerOf2 (int initialCapacity ) {
210+ int capacity =1 ;
211+ while (capacity <initialCapacity ) {
212+ capacity <<=1 ;
213+ }
214+
215+ return capacity ;
216+ }
217+
218+ /** Remove all entries from map */
219+ private void removeEntries () {
220+ table .clear ();
221+ }
222+
223+ /** Rehash the map */
224+ private void rehash () {
225+ capacity <<=1 ;// Same as capacity *= 2. <= is more efficient
226+ for (int i = (size +1 );i <capacity ;i ++) {
227+ table .add (null );
228+ }
229+ }
230+
231+ @ Override /** Return a string repesentation for this map */
232+ public String toString () {
233+ StringBuilder builder =new StringBuilder ("[" );
234+
235+ for (Entry <K ,V >entry :table ) {
236+ if (entry !=null &&table .size () >0 )
237+ builder .append (entry );
238+ }
239+
240+ builder .append ("]" );
241+ return builder .toString ();
242+ }
243+ }
