0

My understanding of the HashMap JDK implementation is that the Key of the Entry object to be put in the HashMap bucket is used to find a place in the Entry[] table field of the HashMap object. If this is the case, why is that hashcode used as a starting point for a for loop? What is the rationale for looping through the array of Entry objects if the Entry is not found in the expected location based on the computed Hash from the Key?

The code for this method from OpenJDK is below. 

public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            for (Entry<k , V> 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++;
            addEntry(hash, key, value, i);
            return n
aruuuuu
  • 1,605
  • 2
  • 22
  • 32

1 Answers1

2

It's how the hash table deals with hash collisions. There can be multiple objects whose hash codes map to the same bucket. Each bucket holds a linked list of objects.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578