HashMap in JDK 7

1. Questions

1.1. Hand-Written HashMap

1.1.1. Entry

class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;// Separate chaining
    }

1.1.2. put Operation

public V put(K key, V value) {
    // Calculate the hash and the array index
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    // First traverse the linked list to see whether an equal key exists; if so, replace the value
    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;
        }
    }
    // If not, use head insertion
    addEntry(hash, key, value, i);
    return null;
}

1.1.3. get Operation

final Entry<K,V> getEntry(Object key) {
                // Calculate the hash value
    int hash = (key == null) ? 0 : hash(key);
            // Calculate the array index
            // Traverse every element in the linked list and compare keys for equality
    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 != null && key.equals(k))))
            return e;
    }
    return null;
}

1.1.4. remove Operation

final Entry<K,V> removeEntryForKey(Object key) {
            // Find the corresponding linked list
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

            // Traverse the linked list and delete (this is simply a linked-list deletion operation and needs a prev and a current)
    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

1.2. Why Does the Constructor Need to Convert capacity to a Power of 2?

This is related to how indexFor calculates the array index.

static int indexFor(int h, int length) {
    return h & (length-1);
}

It does not calculate the hash and then take modulo table.length; it uses a bitwise AND operation.

h:          1001 1001
length:     0001 0000
length-1:   0000 1111
&:          0000 1001

As shown above, the result of & preserves the last 4 bits of h.

1.3. Resize Operation

When does resizing occur?

// Resize when the number of entries in the current HashMap (including those in linked lists) has exceeded the threshold
if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// Twice the array length
    }

1.3.1. Resize Logic

Reference:

An infinite loop occurs on get after concurrent puts.

1.4. How Are Hash Collisions Resolved?

Separate chaining, that is, array + linked list.

1.5. When a Hash Collision Occurs, Is Insertion at the Head or the Tail?

Head insertion. This gives the highest efficiency.

void createEntry(int hash, K key, V value, int bucketIndex) {
            // Save the old linked-list head
    Entry<K,V> e = table[bucketIndex];
            // Create a new entry and point next to the old linked-list head.
            // Point the new linked-list head to this new entry
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

1.6. Does get Enter an Infinite Loop After Concurrent puts?

In 1.7, the put operation uses head insertion. When two threads perform put and resize at the same time, a circular linked list may occur, so the get operation may enter an infinite loop.

There is a transfer method inside resize, which needs to move all elements in the old array to the new array.

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
                // Traverse each element in the array (linked list)
    for (Entry<K,V> e : table) {
                        // Traverse each element in the linked list
        while(null != e) {
            Entry<K,V> next = e.next;
                                    // Recalculate the hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
                                // Calculate the new index
            int i = indexFor(e.hash, newCapacity);
                                // Head insertion
            e.next = newTable[i];
            newTable[i] = e;

            e = next;
        }
    }
}

1.6.1. Reference

https://blog.csdn.net/zhuqiuhui/article/details/51849692

1.7. Can key Be NULL?

Yes. In 1.7, it is stored in the first element of table.

When put determines that the key is NULL, it calls putForNullKey.

private V putForNullKey(V value) {
            // Traverse the linked list at the first array element; if a null key is found, replace the value and return the old value
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
            // If not found, insert into the first array position
    addEntry(0, null, value, 0);
    return null;
}

1.8. ConcurrentModificationException

Reference: fail-fast.md

Performing a deletion operation (remove) while traversing (get) throws this exception. This is called the fast-fail mechanism.

It is caused by modCount and expectedCount being unequal.

2. References

• java - Why is a ConcurrentModificationException thrown and how to debug it - Stack Overflow
• Avoiding the ConcurrentModificationException in Java | Baeldung