Rehashing in HashMap in Java

Question

I have a small doubt with the concept of Rehashing in HashMap.

Lets say I have a HashMap with size 8 and within that I have an Object(E1) present at index 7. So when we put multiple elements, forcing the HashMap to increase its internal Array size, which will lead to rehashing.

So my question goes, After the rehashing, will my Object(E1) be placed at 7th index or will it get a different bucket.

Appreciate useful response and references.

Wondering: why do you care? In other words: in which way is this information relevant at all? (not saying that this is a bad question; I am just wondering about the practical relevance) — GhostCat, Apr 15 '15 at 06:26
It will go in a different bucket (unless, by chance, the new computed bucket is the 7th one again) Why don't you read the source code? It comes with the JDK. — JB Nizet, Apr 15 '15 at 06:26

score 3 · Accepted Answer · answered Apr 15 '15 at 06:27

3

The bucket your key is placed in is a function of its hashCode modulus the size of the array used to hold the HashMap (which is the number of buckets), so re-hashing can move a key to a different bucket.

answered Apr 15 '15 at 06:27

Eran

387,369
54
702
768

Nir Alfasi · Answer 2 · 2015-04-15T06:37:52.693

OpenJDK implementation shows that each new bucket will be re-indexed to a (potentially) different index in the new table:

 void More ...transfer(Entry[] newTable) {
489         Entry[] src = table;
490         int newCapacity = newTable.length;
491         for (int j = 0; j < src.length; j++) {
492             Entry<K,V> e = src[j];
493             if (e != null) {
494                 src[j] = null;
495                 do {
496                     Entry<K,V> next = e.next;
497                     int i = indexFor(e.hash, newCapacity); // <-- new index is calculated here
498                     e.next = newTable[i];
499                     newTable[i] = e; // <-- and assigned
500                     e = next;
501                 } while (e != null);
502             }
503         }
504     }

score 2 · Answer 3 · answered Jun 24 '18 at 15:29

It will be placed at a different index. I am posting the answer to highlight the point that the term Re-Hashing doesn't represent the operation properly. It should be Re-Indexing.

Unfortunately oracle docs also has used the same terminology and called it "rehashing". But it described the process as to rebuilt the internal data structure - the array.. This array is called hash table by them, and I think that's the reason, creating the hash table newly is being called rehashing.

Rehashing in HashMap in Java

3 Answers3

Linked