[ Data Structures with Java ] Section 21.6 : An Unordered Map Collection (HashMap)

Preface : 
In the previous section, we used a hash table as the underlying storage structure for the Hash class. We extend this notion to create an implementation of an unordered map, called HashMap. A HashMap is not ordered because the position of elements depends on hashing the keys. This affect the method toString(), which returns a listing of the elements based on the iterator order. 
The HashMap class stores elements, which are key-value pairs. The storage structure for a HashMap object is a hash table of Entry objects that reference nodes in a linked list. The objects (nodes) are instances of the inner class Entry, which declares variables for the key and value components. It also defines the variable next to reference the subsequent pair in the current list. A hash value is computed once when a new entry enters the map. The integer value is stored as a field in the node : 
 

The inner class Entry implements the Map.Entry interface, which defines the method getKey() to access the key field and the methods getValue() and setValue() to access and update the value component. A toString() method in the Entry class returns a representation of an entry in the format key=value. The constructor has arguments for each fields in the node : 

- Inner class Entry in class HashMap :

view plaincopy to clipboardprint?

1. static class Entry implements Map.Entry {  
2.     K key;  
3.     V value;  
4.     Entry next;  
5.     int hashValue;  
6.       
7.     public Entry(K k, V v, int h, Entry n) {  
8.         key = k;  
9.         value = v;  
10.         hashValue = h;  
11.         next = n;  
12.     }  
13.       
14.     @Override  
15.     public K getKey() {  
16.         return key;  
17.     }  
18.   
19.     @Override  
20.     public V getValue() {  
21.         return value;  
22.     }  
23.   
24.     @Override  
25.     public V setValue(V v) {  
26.         V tmp = value;  
27.         value = v;  
28.         return tmp;  
29.     }         
30. }  

Accessing Entries in a HashMap : 
The methods get() and containskey() take a key reference argument and must locate a corresponding entry in the map. This task is performed by the private method getEntry(), which searches for an element in the hash table. The implementation of getEntry() takes a key as an argument, applies the hash function to the key, and searches the resulting list for a key-value pair with the same key : 

- Method getEntry() in class HashMap :

view plaincopy to clipboardprint?

1. ...  
2.     private Entry getEntry(K key) {  
3.         for(int i=0; i
4.             Entry entry = table[i];  
5.             while(entry!=null) {  
6.                 if(entry.key.equals(key)) return entry;  
7.                 entry = entry.next;  
8.             }  
9.         }  
10.         return null;  
11.     }  
12. ...  

The public method get() takes a key as the argument and uses getEntry() to obtain low-level access to an Entry node. The return value is the value component of the node or null if an entry matching the key is not found : 

- Method get() in class HashMap :

view plaincopy to clipboardprint?

1. ...  
2.     @Override  
3.     public V get(Object key) {  
4.         Entry p = getEntry((K)key);  
5.         if(p==null) return null;  
6.         else return p.value;  
7.     }  
8. ...  

Updating Entries in a HashMap : 
The method put() first searches the collection by applying the hash function for the key to obtain the table index and then scans the corresponding linked list for a match with the key. If a match occurs, the method calls setValue() to update the entry and returns the original value. If the key does not occur in the list, put() inserts a new Entry object at the front of the linked list. Note that we record the hash value as we did in the Hash class. If the hash map size has reached the table threshold, we apply rehashing so the new table size is 2*table.lenght + 1 and conclude by returning null : 

- Method put() in class HashMap :

view plaincopy to clipboardprint?

1. ...  
2.     @Override  
3.     public V put(K key, V value) {  
4.         int hashValue = key.hashCode();  
5.         int index = hashValue % table.length;  
6.         Entry entry = table[index];  
7.         if(entry!=null) {  
8.             while(entry!=null) {  
9.                 if(entry.key.equals(key)) {  
10.                     return entry.setValue(value);                     
11.                 }  
12.                 entry = entry.next;  
13.             }  
14.         }  
15.         entry = new Entry(key, value, hashValue, table[index]);  
16.         table[index] = entry;  
17.         modCount++;  
18.         hashMapSize++;  
19.         if(hashMapSize >= tableThreshold) rehash(2*table.length+1);  
20.         return value;  
21.     }  
22. ...  

For more implementation detail, please refer to the Section 20.2 : Implementing the TreeMap Class which has the similar algorithm.