How does HashMap work in Java? (HashMap internals)
http://howtodoinjava.com/2012/10/09/working-with-hashcode-and-equals-methods-in-java/
https://www.youtube.com/watch?v=iinE6ZBNBjw
https://www.youtube.com/watch?v=iinE6ZBNBjw
HashMaps are probably one of the most used and definitely one of the least understood Java classes. In this post let's look at the source code of HashMap.java to understand how is data inserted and retrieved from a HashMap.
We know that HashMaps work on the principle of 'hashing' and put(key, value) is used to store a key and corresponding value and get(key) is used to retrieve the value for given key.
Below image shows how HashMap stores the data. The blue squares represent the 'bucket' or indexes in the array, determined on the basis of hash value for each key. (We will see later, exactly how the hash value is calculated) At each index of the array, is stored a linked list which has nodes of the type 'Map.Entry'. Each node stores the key/value pair.
Why is the linked list needed? Because two unequal objects can have same hash value (read more about equals and hashcode here). Remember that a HashMap will store values as long as different keys are used so if those different keys result in same hash value they will reside at the same index in the table, in different nodes of the linked list.
Let's look at the default implementation of HashMap in Java.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int bucketIndex = (hash & (table.length-1));
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
return null;
}
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
int bucketIndex = (hash & (table.length-1));
for (Entry e = table[bucketIndex]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
Now let's analyze the code:
int hash = hash(key.hashCode());
int bucketIndex = (hash & (table.length-1));
('hash' function could be anything that ensures that hash value will be as unique as possible. You can implement your own HashMap with your own hash function. HashTable.java has got a different hash function.)
Note that get() and put() have lot of code in common because before putting any key/value pair it checks if it already exists. When you do get(key) the key is hashed and thenbucketIndex is calculated using this hash value. The linkedList at this index will be traversed till a 'key' with matching hash value and also being 'equal' to the input parameter.
In above image K9, K19, K29 all give same hash value H9. So if you give get(K19), it will start traversing starting with K9. Same hashCode but "K9".equals("K19") is false, so it proceeds to "K19" where both conditions are satisfied.
Implementation of HashTable is similar except the fact that methods are synchronized.
A word about the keys. Immutable objects make best keys because this ensures that hash value will remain same when putting in the value and when retrieving it.String objects are the best because of this, also they implement equals and hashCode methods.
We know that HashMaps work on the principle of 'hashing' and put(key, value) is used to store a key and corresponding value and get(key) is used to retrieve the value for given key.
Below image shows how HashMap stores the data. The blue squares represent the 'bucket' or indexes in the array, determined on the basis of hash value for each key. (We will see later, exactly how the hash value is calculated) At each index of the array, is stored a linked list which has nodes of the type 'Map.Entry'. Each node stores the key/value pair.
Why is the linked list needed? Because two unequal objects can have same hash value (read more about equals and hashcode here). Remember that a HashMap will store values as long as different keys are used so if those different keys result in same hash value they will reside at the same index in the table, in different nodes of the linked list.
Let's look at the default implementation of HashMap in Java.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int bucketIndex = (hash & (table.length-1));
for (Entry
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
Entry
table[bucketIndex] = new Entry<>(hash, key, value, e);
}
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
int bucketIndex = (hash & (table.length-1));
for (Entry
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
Now let's analyze the code:
int hash = hash(key.hashCode());
int bucketIndex = (hash & (table.length-1));
('hash' function could be anything that ensures that hash value will be as unique as possible. You can implement your own HashMap with your own hash function. HashTable.java has got a different hash function.)
Note that get() and put() have lot of code in common because before putting any key/value pair it checks if it already exists. When you do get(key) the key is hashed and thenbucketIndex is calculated using this hash value. The linkedList at this index will be traversed till a 'key' with matching hash value and also being 'equal' to the input parameter.
In above image K9, K19, K29 all give same hash value H9. So if you give get(K19), it will start traversing starting with K9. Same hashCode but "K9".equals("K19") is false, so it proceeds to "K19" where both conditions are satisfied.
Implementation of HashTable is similar except the fact that methods are synchronized.
A word about the keys. Immutable objects make best keys because this ensures that hash value will remain same when putting in the value and when retrieving it.String objects are the best because of this, also they implement equals and hashCode methods.
