How do java implement hash map chain collision resolution

Question

I know that we can use a linked list to handle chain collision for hash map. However, in Java, the hash map implementation uses an array, and I am curious how java implements hash map chain collision resolution. I do find this post: Collision resolution in Java HashMap . However, this is not the answer I am looking for.

Thanks a lot.

Answer 1

HashMap contains an array of Entry class. Each bucket has a LinkedList implementation. Each bucket points to hashCode, That being said, if there is a collision, then the new entry will be added at the end of the list in the same bucket.

Look at this code :

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length); // get table/ bucket index
        for (Entry<K,V> e = table[i]; e != null; e = e.next) { // walk through the list of nodes
            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;         // return old value if found
            }
        }

        modCount++;
        addEntry(hash, key, value, i); // add new value if not found
        return null;
    }