底层数据结构

• 由数组和链表组合构成的数据结构

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

插入节点

java8 之前是头插法； java8之后是尾插法。

扩容

• Capacity：HashMap当前长度。

• LoadFactor：负载因子，默认值0.75f。

• 扩容：创建一个新的Entry空数组，长度是原数组的2倍。

• ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

扩容后每个key Hash到的index不一致，所以需要重新Hash。

头插法

在多线程中会导致循环链表。

插入一个元素需要进行扩容时，当一个线程完成扩容，另一个线程将节点添加到新数组时就会产生指向问题，导致循环指向。

重写equal 方法但不重写 hashcode方法

保证两个前提

1. 如果两个对象相同（即用equals比较返回true），那么它们的hashCode值一定要相同；
2. 如果两个对象的hashCode相同，它们并不一定相同(即用equals比较返回false) 。

如果重写了equal方法，使得两个对象相同，但是hashcode不同，这时将他们插入到不重复集合Map或者Set中，就会插入成功，与预期不符。