Environment to prepare

  • Java8_221 version
  • The Idea of the Debug configuration

Introduction to HashMap

  • A HashMap stores data in key-value pairs;
  • The key cannot be repeated, but the value can be repeated, allowing null keys and null values.
  • If the same key is added, the original key-value is overwritten, which is equivalent to modification (the key is not replaced, but the value is replaced).
  • As with a HashSet, the order of the mapping is not guaranteed because the underlying store is hash;
  • HashMap does not implement synchronization and is therefore thread-unsafe;

Underlying structure of HashMap

Expansion mechanism

  1. The underlying HashMap maintains an array table of type Node, which is null by default.
  2. When creating an object, initialize the loading factor loadfactor to 0.75;
  3. When a key-value is added, the hash value of the key is added to the index of the table. Then determine if the index has an element, if no element is added directly. If there is an element at the index, proceed to determine whether the element’s key is equal to the intended key. If so, replace val. If it’s not equal and you need to decide whether it’s a tree or a linked list, do different things. If the capacity is insufficient, expand the capacity.
  4. If the table is added for the first time, the table capacity needs to be expanded to 16 and the threshold is 12.
  5. In the future expansion, the table capacity needs to be expanded by 2 times, and the critical value is 2 times, that is, 24, and so on.
  6. In Java8, if the number of elements in a linked list exceeds TREEIFY_THRESHOLD(default: 8) and the table size >= MIN_TREEIFY_CAPACITY (default: 64), tree evolution (red-black tree) occurs.

Source code analysis

@SuppressWarnings("all")
public class HashMapSource {
  public static void main(String[] args) {
    HashMap map = new HashMap();
    map.put("java".10);
    map.put("php".10);
    map.put("java".20); }}Copy the code

1. Execute constructor new HashMap();

Initialize the loading factor this.loadFactor = DEFAULT_LOAD_FACTOR 0.75

​ Node<K,V>[] table = null

2. Execute put and invoke hash(key) first.

public V put(K key, V value) {
    return putVal(// hash(key), key, value, false, true);
}
// Compute the hash value of Kay
static final int hash(Object key) {
    int h;
    return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

3. Perform 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;
    // If the underlying table array is null, or length == 0, expand to 16
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Select a Node from the hash table index. If null, add k-v to newNode
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // If the hash of the key at the index position of the table is the same as that of the newly added hash, and the object is the same or equals() is the same
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        // Already treed
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // Compare in an infinite loop until the list is inserted and the loop stops
            for (int binCount = 0; ; ++binCount) {
                // If the whole list is not the same as it, it is added to the end of the list
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // After the list is added, check whether the number of current lists has reached 8. When the list reaches 8, the treeifyBin will determine whether to expand or tree
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // Check if there is the same, if so break to update
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    break; p = e; }}// Update operation
        if(e ! =null) { // existing mapping for key
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value; / / replace
            afterNodeAccess(e);
            returnoldValue; }}// Every time newNode is added ++
    ++modCount;
    // When the threshold is reached, expand the capacity
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

treeifyBin

It turns into a red black tree

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // If table == null, or the size does not reach 64, do not tree, expand array first!
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    / / tree
    else if ((e = tab[index = (n - 1) & hash]) ! =null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while((e = e.next) ! =null);
        if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the code

Test capacity

1. Put the first element to perform the first expansion, size=16;

2. Put the 9th element to perform the second expansion, size=32, the linked list already has 9 elements;

3. When the 10th element is put, the third expansion is performed, size=64, and the tree condition is satisfied.

4. Put the 11th element to tree, HashMap$Node => HashMap$TreeNode

import java.util.HashMap;

/ * *@author Strive */
@SuppressWarnings("all")
public class HashMapSource2 {
  public static void main(String[] args) {
    HashMap map = new HashMap();

    for (int i = 1; i <= 12; i++) {
      map.put(new A(i), "hello");
    }

    System.out.println("hashMap="+ map); }}class A {
  private int num;

  public A(int num) {
    this.num = num;
  }

  @Override
  public int hashCode(a) {
    return 100;
  }

  @Override
  public String toString(a) {
    return "\nA{" + "num=" + num + '} '; }}Copy the code