Hashmap Internal Implementation Analysis in Java
Note: Based on the response from my technical blog I am posting this article here so that it would be visible to wider audience.
java.util.HashMap.java
1./**2.* The maximum capacity, used if a higher value is implicitly specified3.* by either of the constructors with arguments.4.* MUST be a power of two <= 1<<30 .="" code="">5.*/6.static final int MAXIMUM_CAPACITY = 1 << 30;
java.util.HashMap.java
01./**02.* The default initial capacity - MUST be a power of two.03.*/04.static final int DEFAULT_INITIAL_CAPACITY = 16;05. 06./**07.* The load factor used when none specified in constructor.08.*/09.static final float DEFAULT_LOAD_FACTOR = 0.75f;
It says default size of an array is 16 (always power of 2, we will understand soon why it is always power of 2 going further) and load factor means whenever the size of the hashmap reaches to 75% of its current size, i.e, 12, it will double its size by recomputing the hashcodes of existing data structure elements.
Hence to avoid rehashing of the data structure as elements grow it is the best practice to explicitly give the size of the hashmap while creating it.
Do you foresee any problem with this resizing of hashmap in java? Since java is multi threaded it is very possible that more than one thread might be using same hashmap and then they both realize the need for re-sizing the hashmap at the same time which leads to race condition.
What is race condition with respect to hashmaps? When two or more threads see the need for resizing the same hashmap, they might end up adding the elements of old bucket to the new bucket simultaneously and hence might lead to infinite loops. FYI, in case of collision, i.e, when there are different keys with same same hashcode, internally we use single linked list to store the elements. And we store every new element at the head of the linked list to avoid tail traversing and hence at the time of resizing the entire sequence of objects in linked list gets reversed, during which there are chances of infinite loops.
For example, lets assume there are 3 keys with same hashcode and hence stored in linked list inside a bucket [below format is in object_value(current_address, next_address) ]
Initial structure: 1(100, 200) –> 2(200, 300) –> 3(300, null)
After resizing by thread-1: 3(300, 200) –> 2(200, 100) –> 1(100, null)
When thread-2 starts resizing, its again starts with 1st element by placing it at the head:
1(100, 300) –> 3(300, 200) –> 2(200, 100) ==> which becomes a infinite loop for next insertion and thread hangs here.
Initial structure: 1(100, 200) –> 2(200, 300) –> 3(300, null)
After resizing by thread-1: 3(300, 200) –> 2(200, 100) –> 1(100, null)
When thread-2 starts resizing, its again starts with 1st element by placing it at the head:
1(100, 300) –> 3(300, 200) –> 2(200, 100) ==> which becomes a infinite loop for next insertion and thread hangs here.
java.util.HashMap.java
01./**02.* Associates the specified value with the specified key in this map.03.* If the map previously contained a mapping for the key, the old04.* value is replaced.05.*06.* @param key key with which the specified value is to be associated07.* @param value value to be associated with the specified key08.* @return the previous value associated with key, or09.* null if there was no mapping for key.10.* (A null return can also indicate that the map11.* previously associated null with key.)12.*/13.public V put(K key, V value) {14.if (key == null)15.return putForNullKey(value);16.int hash = hash(key.hashCode());17.int i = indexFor(hash, table.length);18.for (Entry e = table[i]; e != null; e = e.next) {19.Object k;20.if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {21.V oldValue = e.value;22.e.value = value;23.e.recordAccess(this);24.return oldValue;25.}26.}27. 28.modCount++;29.addEntry(hash, key, value, i);30.return null;31.}
Here it
1. re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument
2. generates index based on the re-generated hashcode and length of the data structure.
3. if key exists, it over-rides the element, else it will create a new entry in the hashmap at the index generated in STEP-2
1. re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument
2. generates index based on the re-generated hashcode and length of the data structure.
3. if key exists, it over-rides the element, else it will create a new entry in the hashmap at the index generated in STEP-2
Steps3 is straight forward but Steps1&2 needs to have deeper understanding. Let us dive into the internals of these methods…
Note: These two methods are very very important to understand the internal working functionality of hashmap in openjdk
java.util.HashMap.java
01./**02.* Applies a supplemental hash function to a given hashCode, which03.* defends against poor quality hash functions. This is critical04.* because HashMap uses power-of-two length hash tables, that05.* otherwise encounter collisions for hashCodes that do not differ06.* in lower bits. Note: Null keys always map to hash 0, thus index 0.07.*/08.static int hash(int h) {09.// This function ensures that hashCodes that differ only by10.// constant multiples at each bit position have a bounded11.// number of collisions (approximately 8 at default load factor).12.h ^= (h >>> 20) ^ (h >>> 12);13.return h ^ (h >>> 7) ^ (h >>> 4);14.}15. 16./**17.* Returns index for hash code h.18.*/19.static int indexFor(int h, int length) {20.return h & (length-1);21.}
here:
‘h’ is hashcode(because of its int data type, it is 32 bit)
‘length’ is DEFAULT_INITIAL_CAPACITY(because of its int data type, it is 32 bit)
‘h’ is hashcode(because of its int data type, it is 32 bit)
‘length’ is DEFAULT_INITIAL_CAPACITY(because of its int data type, it is 32 bit)
Comment from above source code says…
Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits. What do this means???
Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits. What do this means???
It means that if in case the algorithm we wrote for hashcode generation does not distribute/mix lower bits evenly, it will lead to more collisions. For example, we have hashcode logic of “empId*deptId” and if deptId is even, it would always generate even hashcodes because any number multiplied by EVEN is always EVEN. And if we directly depend on these hashcodes to compute the index and store our objects into hashmap then
1. odd places in the hashmap are always empty
2. because of #1, it would leave us to use only even places and hence double the number of collisions
1. odd places in the hashmap are always empty
2. because of #1, it would leave us to use only even places and hence double the number of collisions
For example,
01.I am considering some hash codes which our code might generate, which are very valid as they are different, but we will prove these to be useless soon02.111111011101101010110101011111003.110011011101101010101101011111004.110000011101101010111001011111005.I am considering these sequences directly (without using hash function) and pass it for indexFor method, where we do AND operation between'hashcode' and 'length-1(which will always give sequence of 1's as length is always power of 2)'06.As we are considering the length as default length, i.e, 16, binary representation of 16-1 is 111107.this is what happens inside indexFor method08.1111110111011010101101010111110 & 0000000000000000000000000001111 = 111009.1100110111011010101011010111110 & 0000000000000000000000000001111 = 111010.1100000111011010101110010111110 & 0000000000000000000000000001111 = 1110
What is bucket and what can be maximum number of buckets in hashmap? A bucket is an instance of the linked list (Entry Inner Class in my previous post) and we can have as many number of buckets as length of the hashmap at maximum, for example, in a hashmap of length 8, there can be maximum of 8 buckets, each is an instance of linked list.
From this we understand that all the objects with these different hascodes would have same index which means they would all go into the same bucket, which is a BIG-FAIL as it leads to arraylist complexity O(n) instead of O(1)
Comment from above source code says…
that otherwise encounter collisions for hashCodes that do not differ in lower bits.
that otherwise encounter collisions for hashCodes that do not differ in lower bits.
Notice this sequence of 0-15 (2-power-4), its the default size of Hashtable
1.0000 - 0 1000 - 82.0001 - 1 1001 - 93.0010 - 2 1010 - 104.0011 - 3 1011 - 115.0100 - 4 1100 - 126.0101 - 5 1101 - 137.0110 - 6 1110 - 148.0111 - 7 1111 - 15
If we notice here, hashmap with power-of-two length 16(2^4), only last four digits matter in the allocation of buckets, and these are the 4 binary lower bit digit variations that play prominent role in identifying the right bucket.
Keeping the above sequence in mind, we re-generated the hashcode from hash(int h) by passing the existing hascode which makes sure there is enough variation in the lower bits of the hashcode and then pass it to indexFor() method , this will ensure the lower bits of hashcode are used to identify the bucket and the rest higher bits are ignored.
For example, taking the same hascode sequences from above example
For example, taking the same hascode sequences from above example
01.this is what happens inside indexFor method02.1111110111011010101101010111110 (our hash code) when regenerated with hash(int h) method, it generates new hashcode111100111111001110011011101101003.1100110111011010101011010111110 ==> 110000001001000010110111001100104.1100000111011010101110010111110 ==> 110011000100100001101111000101105. 06.passing these set of new hashcodes to indexFor() method07.1111001111110011100110111011010 & 0000000000000000000000000001111 = 101008.1100000010010000101101110011001 & 0000000000000000000000000001111 = 100109.1100110001001000011011110001011 & 0000000000000000000000000001111 = 1011
so here it is clear that becase of regenerated hashcode, the lower bits are will distributed/mixed leading to unique index which leads to different buckets avoiding collisions.
Why only these magic numbers 20, 12, 7 and 4. It is explained in the book: “The Art of Computer Programming” by Donald Knuth.
>> Here we are XORing the most significant bits of the number into the least significant bits (20, 12, 7, 4). The main purpose of this operation is to make the hashcode differences visible in the least significant bits so that the hashmap elements can be distributed evenly across the buckets.
>> Here we are XORing the most significant bits of the number into the least significant bits (20, 12, 7, 4). The main purpose of this operation is to make the hashcode differences visible in the least significant bits so that the hashmap elements can be distributed evenly across the buckets.
java.util.HashMap.java
01./**02.* Associates the specified value with the specified key in this map.03.* If the map previously contained a mapping for the key, the old04.* value is replaced.05.*06.* @param key key with which the specified value is to be associated07.* @param value value to be associated with the specified key08.* @return the previous value associated with key, or09.* null if there was no mapping for key.10.* (A null return can also indicate that the map11.* previously associated null with key.)12.*/13.public V put(K key, V value) {14.if (key == null)15.return putForNullKey(value);16.int hash = hash(key.hashCode());17.int i = indexFor(hash, table.length);18.for (Entry e = table[i]; e != null; e = e.next) {19.Object k;20.if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {21.V oldValue = e.value;22.e.value = value;23.e.recordAccess(this);24.return oldValue;25.}26.}27. 28.modCount++;29.addEntry(hash, key, value, i);30.return null;31.}
Going back to previous steps:
1. re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument
2. generates index based on the re-generated hashcode and length of the data structure.
3. if key exists, it over-rides the element, else it will create a new entry in the hashmap at the index generated in STEP-2
1. re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument
2. generates index based on the re-generated hashcode and length of the data structure.
3. if key exists, it over-rides the element, else it will create a new entry in the hashmap at the index generated in STEP-2
Steps1&2 must be clear by now.
Step3:
What happens when two different keys have same hascode?
1. if the keys are equal, i.e, to-be-inserted key and already-inserted key’s hashcodes are same and keys are same (via reference or via equals() method) then over-ride the previous key-value pair with the current key-value pair.
2. if keys are not equal, then store the key-value pair in the same bucket as that of the existing keys.
What happens when two different keys have same hascode?
1. if the keys are equal, i.e, to-be-inserted key and already-inserted key’s hashcodes are same and keys are same (via reference or via equals() method) then over-ride the previous key-value pair with the current key-value pair.
2. if keys are not equal, then store the key-value pair in the same bucket as that of the existing keys.
When collision happens in hashmap? it happens in case-2 of above question.
How do you retrieve value object when two keys with same hashcode are stored in hashmap? Using hashcode wo go to the right bucket and using equals we find the right element in the bucket and then return it.
How does different keys with same hascode stored in hashmap? Usual answer is in bucket but technically they are all stored in a single linked list. Little difference is that insertion of new element to the linked list is made at the head instead of tail to avoid tail traversal.
java.util.HashMap.java
01./**02.* Returns the value to which the specified key is mapped,03.* or {@code null} if this map contains no mapping for the key.04.*05.* More formally, if this map contains a mapping from a key06.* {@code k} to a value {@code v} such that {@code (key==null ? k==null :07.* key.equals(k))}, then this method returns {@code v}; otherwise08.* it returns {@code null}. (There can be at most one such mapping.)09.*10.* A return value of {@code null} does not necessarily11.* indicate that the map contains no mapping for the key; it's also12.* possible that the map explicitly maps the key to {@code null}.13.* The {@link #containsKey containsKey} operation may be used to14.* distinguish these two cases.15.*16.* @see #put(Object, Object)17.*/18.public V get(Object key) {19.if (key == null)20.return getForNullKey();21.int hash = hash(key.hashCode());22.int i = indexFor(hash, table.length);23.for (Entry e = table[i]; e != null; e = e.next) {24.Object k;25.if (e.hash == hash && ((k = e.key) == key || key.equals(k)))26.return e.value;27.}28.return null;29.}
1. re-generates the hashcode using hash(int h) method by passing user defined hashcode as an argument
2. generates index based on the re-generated hashcode and length of the data structure.
3. point to the right bucket, i.e, table[i], and traverse through the linked list, which is constructed based on Entry inner class
4. when keys are equal and their hashcodes are equal then return the value mapped to that key
2. generates index based on the re-generated hashcode and length of the data structure.
3. point to the right bucket, i.e, table[i], and traverse through the linked list, which is constructed based on Entry inner class
4. when keys are equal and their hashcodes are equal then return the value mapped to that key
No comments:
Post a Comment