HashMap uses LinkedList internally

Question

public V get(Object key) {
if (key == null)
    return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

What I knew is, if you want to get a object from HashMap, first of all it searches the hash bucket based on hashcode/hash value and then iterates through the LinkedList in that hashbucket(suppose the diff objects have same hash code, thus in the same hash bucket).

But after looking at the code above, I am not able to understand when it iterates through the LinekedList(and where is the LinkedList)

Solution 1

The bucket is the linked list, effectively. The table array is an array of Entry elements, and each Entry is a linked list, in that each entry knows about the next one in the list, until you reach the end when the next reference is null. The for loop you've shown iterates over the linked list.

It's not a LinkedList as in a java.util.LinkedList - it's a separate (simpler) implementation just for the map.

Solution 2

It does use linked list, but not java.util.LinkedList class.

Basically e.next is something you're looking for. Each entry has a reference to next entry in bucket - it's a linked list implementation.

Solution 3

e.next is what you're looking for. Each entry has a reference to next entry in the bucket; it's a linked list implementation.