ThinkerQAQ

NOTE

HashMap in JDK 8

What HashMap is, usage, source analysis of construction, put, resize, treeification, get, containsKey, remove, containsValue, and differences from JDK 7.

JavaCreated Updated 3 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

1. What It Is

A key-value data structure that provides O(1) access efficiency.

2. How to Use It

public class HashMapTest
{
    public static void main(String[] args)
    {
        HashMap<String, Object> map = new HashMap<>();
        map.put("key1", "value1");

        System.out.println(map.get("key1"));
        map.remove("key1");

        map.containsKey("key1");
    }
}

3. Principle Analysis

3.1. UML

Cloneable, serializable, and implements Map.

3.2. Constructor

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // Implemented using a Node array; separate chaining is used to resolve hash collisions
    transient Node<K,V>[] table;
    // Default initial capacity
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // Maximum capacity
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // Default load factor
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // Linked-list length at which it is converted into a tree
    static final int TREEIFY_THRESHOLD = 8;
    // Tree length at which it is converted back into a linked list
    static final int UNTREEIFY_THRESHOLD = 6;

    static final int MIN_TREEIFY_CAPACITY = 64;

    public HashMap() {
    // Set the default load factor
    // Number of existing elements in table / total number of table elements.
    // When this ratio >= 0.75, resizing is required
    // In other words, when used capacity reaches 16 * 0.75 = 12, resizing is required
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
}

3.3. put Method

The overall pseudo-algorithm is as follows:

  • Calculate the key’s hash value.

  • Use the hash value & array length - 1 to calculate position i.

    • If table is empty, resize.
    • If position i is empty, store (key, value) there.
    • If position i is not empty:
      • Compare the key at that position with the new key. If equal, replace the value.
      • Otherwise:
        • If it is a tree node, call the red-black tree insertion operation.
        • If it is a linked-list node, traverse the linked list.
          • If a node with the same key is found, replace the value.
          • Otherwise insert at the end of the linked list.

  • After insertion, compare whether size is greater than capacity * load factor. If so, resize.

    • Capacity becomes twice the original.
    • Create a new Node array and migrate the elements from the old array into it.

  • put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

3.3.1. Calculate the Key’s Hash Value

  • hash
// Hash function
static final int hash(Object key) {
    int h;
    // hashCode XOR hashCode shifted right by 16 bits
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table is null or length is 0
    if ((tab = table) == null || (n = tab.length) == 0)
        // First resize
        n = (tab = resize()).length;
    // Use the hash value and array length to calculate the index.
    // If table[index] is empty, assign directly
    if ((p = tab[i = (n  1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // Otherwise table[index] already has an element
    else {
        Node<K,V> e; K k;
        // The head node has the same hash and equal key
        // (that is, the head node is the desired node), so save it for later use
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // The head node is not the desired node and is a TreeNode, so delegate to the tree operation
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // The head node is not the desired node and is an ordinary linked list
        else {
            // Traverse the linked list while counting how many elements have been traversed in binCount
            for (int binCount = 0; ; ++binCount) {
                // Reached the end of the linked list
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // Determine whether binCount has reached the treeification threshold
                    if (binCount >= TREEIFY_THRESHOLD  1) // 1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // Found an equal node
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // If an equal node was found, e contains its reference; simply replace value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // If adding this node exceeds threshold, resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

3.3.2. On the First Entry, table Must Be Empty, So Resize

  • resize
final Node<K,V>[] resize() {
    // Save the old table, capacity, and threshold
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    // Initialize the new capacity and threshold to 0
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // If the old capacity is at least int MAXIMUM_CAPACITY = 1 << 30,
        // update threshold to Integer.MAX_VALUE and directly return the old table
        // (that is, do not resize)
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // The new capacity is twice the old capacity (16 * 2 = 32)
        // If 32 < MAXIMUM_CAPACITY and oldCap >= DEFAULT_INITIAL_CAPACITY
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // Also double threshold (12 * 2 = 24)
            newThr = oldThr << 1; // double threshold
    }
    // New capacity is threshold
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // First initialization
    else { // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // Create a new table with size newCapacity
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // Traverse every linked list in the old table
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // Set it to null so GC can reclaim it promptly.
                // oldTab[j] has already been saved in local variable e
                oldTab[j] = null;
                // Case 1: there is only one node in the linked list
                if (e.next == null)
                    // Recalculate its position (e.hash & (newCap - 1)) and put it into the new table
                    newTab[e.hash & (newCap - 1)] = e;
                // Case 2: there are multiple nodes and the first one is a TreeNode, delegate to tree logic
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // Case 3: there are multiple nodes and it is an ordinary linked list
                else { // preserve order
                    // After rehash, the old table's linked-list nodes are positioned in the new table either:
                    // (1) at the same position as in the old table
                    // (2) at the old position + oldCap
                    // This effectively splits the original linked list into two parts:
                    // loXXX represents (1)
                    // hiXXX represents (2)
                    Node<K,V> loHead = null, loTail = null;

                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // High bit is 0, so this element's position in the new table is the same as before
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // High bit is 1, so this element's position is old position + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // The loop above has split the linked list; now assign the two parts to the new table
                    if (loTail != null) {
                        loTail.next = null;
                        // (1)
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // (2)
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

3.3.3. Use Hash Value & Array Length - 1 to Calculate Position i

i = (n - 1) & hash

3.3.4. On the Second Entry, If Position i Is Empty, Store (key, value) There

// Use hash and array length to calculate the index.
// If table[index] is empty, assign directly
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

3.3.5. On the Third Entry, If Position i Is Not Empty, Traverse the Linked List or Red-Black Tree and Replace value When an Equal Key Is Found

// table[index] already contains an element
else {
    Node<K,V> e; K k;
    // The head node has the same hash and equal key
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    // The head node is not the desired node and is a TreeNode
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // The head node is not the desired node and is an ordinary linked list
    else {
        // Traverse the linked list and count elements in binCount
        for (int binCount = 0; ; ++binCount) {
            // Reached the end
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                // Determine whether binCount reaches the treeification threshold
                // Here binCount is TREEIFY_THRESHOLD - 1, namely 7
                // That means the number of nodes in this linked list excluding the head is 8
                if (binCount >= TREEIFY_THRESHOLD - 1) // 1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            // Found an equal node
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    // If an equal node was found, e holds its reference; directly replace value
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}
3.3.5.1. How Is It Converted into a Red-Black Tree?
  • treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // If table length < 64, do not treeify; resize instead
    // In other words, a linked list becomes a red-black tree when it has 8 elements
    // and table length is 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)// MIN_TREEIFY_CAPACITY is 64
        resize();
    // Convert nodes (Node) in the linked list into tree nodes (TreeNode)
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // Traverse the linked list
        do {
            // Pass the current linked-list node and next node, converting it into TreeNode
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // tail is null, so this is the first element in the tree
            if (tl == null)
                // Initialize head to the current node
                hd = p;
            // Not the first element; insert it at the end
            else {
                // Why does this tree node look like a doubly linked list here???
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // Above only constructs a doubly linked list whose nodes are TreeNodes.
            // The actual treeification happens here
            hd.treeify(tab);
    }
}
3.3.5.1.1. Node -> TreeNode
  • replacementTreeNode
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    // Initialize TreeNode's hash, key, and value with the current node's hash, key, and value
    // Initialize TreeNode.next with the next node
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
  • TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    // This constructor is essentially HashMap.Node's constructor; nothing special
    TreeNode(int hash, K key, V val, Node<K,V> next) {
    // LinkedHashMap.Entry
        super(hash, key, val, next);
    }
  • LinkedHashMap.Entry
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
    // HashMap.Node
        super(hash, key, value, next);
    }
}
  • HashMap.Node
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
3.3.5.1.2. Treeification
  • treeify

A bit complicated, skip it for now…

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}

3.4. get Method

Overall pseudo-algorithm:

  • Calculate the key’s hash value.
  • Use hash value & array length - 1 to calculate position i.
    • If position i is not empty, compare whether the key is equal; if so, return it.
      • Otherwise, if it is a tree, delegate to red-black tree lookup.
      • If it is a linked list, traverse it to find the node with an equal key.
    • Otherwise return null.
public V get(Object key) {
    Node<K,V> e;
    // Find a node by the key's hash value + the key itself
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

3.4.1. Calculate the Key’s Hash Value

  • hash
// Hash function
static final int hash(Object key) {
    int h;
    // hashCode XOR hashCode shifted right by 16 bits
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • getNode
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // Calculate the index using hash & (table length - 1)
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n  1) & hash]) != null) {
        // Found it: current node is table[index], hash is equal, and key is equal
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // Continue searching
        if ((e = first.next) != null) {
            // TreeNode: delegate to tree
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // Traverse the linked list to find an equal node
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

3.4.2. Use Hash Value & Array Length - 1 to Calculate Position i

i = (n - 1) & hash

3.4.3. The First Node Is the Desired Node

if ((tab = table) != null && (n = tab.length) > 0 &&
    (first = tab[(n  1) & hash]) != null) {
    // Found: the current node equals table[index], hash is equal, and key is equal
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))
        return first;

3.4.4. Delegate to Tree or Linked-List Lookup to Find the Node

// Continue searching
if ((e = first.next) != null) {
    // TreeNode, delegate to tree
    if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    do {
        // Traverse the linked list to find an equal node
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    } while ((e = e.next) != null);
}

3.4.5. Return null If Not Found

return null;

3.5. containsKey Method

public boolean containsKey(Object key) {
    // Also calls getNode and checks whether the result is null
    return getNode(hash(key), key) != null;
}

3.6. remove Method

Overall pseudo-algorithm:

  • Calculate the key’s hash value.

  • Use hash value & array length - 1 to calculate position i.

  • If position i is not empty, compare whether the keys are equal. If equal, make the head node point to the next node.

  • Otherwise:

    • If it is a tree node, delegate to the red-black tree deletion interface.
    • If it is a linked-list node, traverse the linked list to find an equal key and point the previous node’s next to that node’s next.

  • remove

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

3.6.1. Calculate the Key’s Hash Value

  • hash
// Hash function
static final int hash(Object key) {
    int h;
    // hashCode XOR hashCode shifted right by 16 bits
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • removeNode
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // Calculate the position of the first node
        (p = tab[index = (n  1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // The first node is the desired node
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // Otherwise continue searching
        else if ((e = p.next) != null) {
            // It is a TreeNode; delegate to tree
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // Traverse the linked list until an equal node is found
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // A node was found
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // Delegate to tree
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // First element of the linked list
            else if (node == p)
                tab[index] = node.next;
            // Non-first element of the linked list
            else
                p.next = node.next;
            ++modCount;
            size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

3.6.2. Use Hash Value & Array Length - 1 to Calculate Position i

i = (n  1) & hash

3.6.3. Use Linked-List or Red-Black Tree Lookup to Find the Node with an Equal Key

Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // Calculate the position of the first node
        (p = tab[index = (n  1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // The first node is the desired node
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // Otherwise continue searching
        else if ((e = p.next) != null) {
            // It is a TreeNode; delegate to tree
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // Traverse the linked list until an equal node is found
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }

3.6.4. Call Linked-List or Red-Black Tree Deletion

// A node was found
if (node != null && (!matchValue || (v = node.value) == value ||
                     (value != null && value.equals(v)))) {
    // Delegate to tree
    if (node instanceof TreeNode)
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
    // First element of the linked list
    else if (node == p)
        tab[index] = node.next;
    // Non-first element of the linked list
    else
        p.next = node.next;
    ++modCount;
    size;
    afterNodeRemoval(node);
    return node;
}

3.7. containsValue

  • Complexity O(N²)
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
    // Traverse every array element
    for (int i = 0; i < tab.length; ++i) {
        // Traverse every element of the linked list
        for (Node<K,V> e = tab[i]; e != null; e = e.next) {
            if ((v = e.value) == value ||
                (value != null && value.equals(v)))
                return true;
        }
    }
}
return false;
}

4. Questions

4.1. Differences from JDK 1.7

  • Red-black trees are used.

Therefore, JDK 1.8’s internal implementation is array + linked list + red-black tree.

Before 1.8, it used array + linked list. For a key, its hash value is calculated first, then modulo the array size determines which element it is placed in, and separate chaining resolves collisions.

If many keys map to the same element, efficiency degrades to O(N). Therefore, in 1.8, when the linked list exceeds a threshold it is converted into a red-black tree, with O(log N) efficiency.

  • The infinite-loop problem during concurrent resize was solved.

Order is preserved, using tail insertion instead of head insertion.

4.2. How Is the Infinite-Loop Problem During Concurrent resize Solved?

Order is preserved by changing head insertion to tail insertion.

4.3. When Does Resizing Happen?

When the number of Entry objects in the map >= threshold, where threshold = capacity * load factor.

4.4. How Does Resizing Work?

See:

3.3.2. On the First Entry, table Must Be Empty, So Resize

5. References

Discussion

Sign in with GitHub to comment. Discussions are stored as GitHub Issues.View on GitHub