Internals of how the HashMap put() and get() methods work (basic logic only )

Question

When we put a key instance say "key" and a Value instance say "value" in a HashMap class using put() method , what does the HashMap class do internally . How does it retrieve the value back when we say hashMap.get(key) ?

Edit: I do not want details here , basically trying to understand the bigger picture and the role of equals() and hashcode() method in put() and get() operations.

Solution 1

If you talk about higher picture it is just like below.Here i refer item as a key of Map

While Putting items.

1. Calculate hashcode of key
2. If basket with that hashcode is present then use the equals method on the key search the keys i that basket to determine if the element is to be added or replace.
3. If not there then create new basket (rehashing) and add that element to that.

Get:

1. Get the hashcode of key
2. Go to that basket
3. Iterate using equals on the key will return you that element from that basket.

Solution 2

This is what is done in IBM jdk 1.6 (i believe it is pretty much the same for all vendors)

EDIT

Regarding equals and hashcode you might be interested in seeing this post.

END of EDIT

 /**
 * Maps the specified key to the specified value.
 * 
 * @param key
 *            the key
 * @param value
 *            the value
 * @return the value of any previous mapping with the specified key or null
 *         if there was no mapping
 */
@Override
public V put(K key, V value) {
    return putImpl(key, value);
}

V putImpl(K key, V value) {
    Entry<K,V> entry;
    if(key == null) {
        entry = findNullKeyEntry();
        if (entry == null) {
            modCount++;
            if (++elementCount > threshold) {
                rehash();
            }
            entry = createHashedEntry(null, 0, 0);
        }
    } else {
        int hash = key.hashCode();
        int index = hash & (elementData.length - 1);
        entry = findNonNullKeyEntry(key, index, hash);
        if (entry == null) {
            modCount++;
            if (++elementCount > threshold) {
                rehash();
                index = hash & (elementData.length - 1);
            }
            entry = createHashedEntry(key, index, hash);
        }
        if ((cache != null) && (hash >> CACHE_BIT_SIZE == 0)
                && (key instanceof Integer)) {
            cache[hash] = value;
        }
    }

    V result = entry.value;
    entry.value = value;
    return result;
}

Solution 3

From java 8 onwords, there is a performance improvement for HashMap objects where there are lots of collisions in the keys by using balanced trees rather than linked lists to store map entries. The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold, that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).

Basically when a bucket becomes too big (currently: TREEIFY_THRESHOLD = 8), HashMap dynamically replaces it with an ad-hoc implementation of tree map. This way rather than having pessimistic O(n) we get much better O(log n).

Bins (elements or nodes) of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. However, since the vast majority of bins in normal use are not overpopulated, checking for existence of tree bins may be delayed in the course of table methods.

Tree bins (i.e., bins whose elements are all TreeNodes) are ordered primarily by hashCode, but in the case of ties, if two elements are of the same “class C implements Comparable<C>“, type then their compareTo() method is used for ordering.

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes. And when they become too small (due to removal or resizing) they are converted back to plain bins (currently: UNTREEIFY_THRESHOLD = 6). In usages with well-distributed user hashCodes, tree bins are rarely used.

Link to java doc

Collection framework enhancements