CODEWITHSUNDEEP
javahashmap
WideVision Technologies
WideVision Technologies

Reputation: 29

Internal structure of Hashmap

I was going through the internal structure of HashMap and got stuck in the concept of how a bucket stores multiple objects.

As HashMap is an array of Entry objects, every index of array is a bucket. The Entry class is like

static class Entry<K,V> implements Map.Entry<K,V> {  
    K key;  
    V  value;  
    Entry<K,V> next_entry;  
    int hash;  
}

On Adding a new key-value pair

So how can a bucket store multiple object as per the 2nd point?

Upvotes: 2

Views: 3253

Answers (3)

SpaceTrucker
SpaceTrucker

Reputation: 13556

This is about HashMap in Oracle JDK 1.7.0.55.

Creating a new entry is done through:

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

which clearly shows that the already existing element is stored as next element of the new element. So the array contains the buckets. Buckets themselves are single linked lists made up of Entry elements.

And when a get operation is performed, then this single linked list is iterated as can be seen in the for loop of (comment by me)

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) { // <- see here
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

So the Entry elements of the single linked list all have keys with the same hash. But by the contract of hashCode objects not equal to each other may have the same hash codes. So using key.equals(k) in the above for loop will not be true for the first round in the loop in every case. So the loop may be traversed until the end of the linked list.

Upvotes: 2

Mike Sokolov
Mike Sokolov

Reputation: 7054

HashMap maintains an array: Entry[]; each element of that array represents a "bucket". The remainder of the entries in the bucket are accessed by traversing a linked list maintained in by Entry.next.

Upvotes: 0

Elliott Frisch
Elliott Frisch

Reputation: 201537

Java HashMap uses a linkedlist for buckets (but not a java.util.LinkedList). If a class hard codes the hashCode() method to a single value; instances of such a class loaded into a HashMap the structure will degenerate into a linkedlist. You override equals() to support replace in the "bucket".

Upvotes: 0

Related Questions