HashMap的实现

0x00 背景知识
首先HashMap是基于hash表的，hash表的相关知识及其存储原理，可以参考我之前写的一篇文章：查找算法总结，要着重看此文章关于冲突处理所讲述的拉链法。
我们仅在这稍微明确一点概念：首先对于拉链式的hash表，其是由数组和链表共同组成的，当然Java中还引入了红黑树，当链表长度大于8时，将链表转为红黑树以提高查找效率。我们先来看上面的这个图，保存这个hash表的数组称之为桶（bucket），而每个桶中保存了一系列的数据入口（entries）。
同理，我们在这明确一个概念“等同”：我们假定如果两个对象其hashCode相同，且任一一个调用equals方法与另一个返回true，即认为两个对象等同。
同时，在HashMap中有如下几个量需要注意，代码如下：
/**
 * The number of key-value mappings contained in this map.
 */
// MAP中所包含的键值对的数量
transient int size;
​
/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
// 阈值，超过此阈值就会诱发桶的扩容操作，值为：桶的容量乘以装填因子
int threshold;
​
/**
 * The load factor for the hash table.
 *
 * @serial
 */
// 装填因子
final float loadFactor;
HashMap和HashTable的区别
首先，HashMap是非线程安全的，而HashTable则是线程安全的，也因此，HashMap的效率较高。除此之外，在HashMap中null可以用来作为键，而HashTable则不可以，否则抛出NullPointerException。
HashMap和HashSet的区别
HashSet底层基于HashMap实现，其实现了Set接口，仅用来存储对象而不是键值对。而且HashSet较HashMap效率低。
HashMap的长度为什么是2的幂次方
因为经计算出来的hash值需要对数组长度进行取余运算，然后用余数定位其在hash表中的位置，为了优化取余运算的效率，人们发现取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(\&)操作，即：hash%length​等价于hash\&(length-1)，前提是length是2的n次方，采用二进制位操作\&，相对于%能够提高运算效率。
0x01 put方法
先来看一张流程图：
图片非原创，来自文章：HashMap原理深入理解​
正好我们就着源代码来说说这张图，首先我们来看put方法的源代码：
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
其直接将工作转交至了putVal方法中，我们直接来看putVal的代码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    // 如果桶为空或者长度为0的话，那么调用resize方法对其进行扩容
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 通过(n - 1) & hash计算当前元素对应在table数组（桶）中的下标
    // 其中n为桶的长度，hash为依据key所计算的hash码值
    // 如果table数组中此项为空，意味着没有冲突发生
    // 那就直接在此项处新建一个Node直接将其插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果桶中已经有了至少一个元素
    else {
        Node<K,V> e; K k;
        // 首先判断链表的第一个结点与当前所插入的结点的`key`是否等同
        // 其中key的hash相同并且equals方法返回true被认为等同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 如果等同的话，则将标记e指向p
            e = p;
        // 如果桶的entry类型为TreeNode的话
        else if (p instanceof TreeNode)
            // 那就调用红黑树的插入方法，将此键值对插入
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 
        // 否则调用链表的插入方法，目标在链表尾部插入此结点
        else {
            for (int binCount = 0; ; ++binCount) {
                // 如果抵达链表尾部
                if ((e = p.next) == null) {
                    // 插入新结点
                    p.next = newNode(hash, key, value, null);
                    // 如果插入后链表的长度大于TREEIFY_THRESHOLD
                    // 即调用treeifyBin方法将链表变为红黑树
                    // 注：TREEIFY_THRESHOLD默认为8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在链表中找到了和插入键值对key等同的结点则退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果标记e不为null的话
        // 即在当前hash表中找到了与所要插入的键值对的key相同的结点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent即为是否仅在oldValue为null的情况下更新键值对
            // 这个参数在put方法中被默认给定为false
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; 
    // 键值对数量超过阈值时，调用resize方法进行扩容对桶进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
在上述两个代码中，我们可以看到两个方法afterNodeAccess和afterNodeInsertion这两个方法在HashMap里面的实现是空的，在此处什么都不做，其注释中写道：Callbacks to allow LinkedHashMap post-actions，即适用于LinkedHashMap实现一些后置功能的回调函数。
JDK7 put方法为什么线程不安全
以下内容仅适用于JDK7之前的版本，即对链表的插入方法为头插法，JDK8以后，链表的插入方法改为了尾插法，从此之后就不存在这个问题了。
众所周知，HashMap不是线程安全的，多线程的情况下操作HashMap的put操作有可能导致死循环，原因在于HashMap扩容使用的resize方法，由于扩容是新建一个数组，然后复制原数据到数组，由于数组下标挂有链表，所以需要复制链表，但多线程操作有可能导致环形链表。
我们先来看JDK7 HashMap实现中的transfer方法：
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i]; // 才用头插入，在链表头部插入元素
            newTable[i] = e; // 线程执行完上一行后，在此处挂起
            e = next; // 循环遍历链表内元素
        }
    }
}
我们假设没有执行resize之前Entry数组的结构如下：
则其在单线程的情况下，正确执行扩容操作后的样子如下：
好了，现在我们来看多线程的情况，假设线程A执行扩容操作，在上述代码片中标记部分线程A被挂起，则目前线程A内的状态如下：
这个时候线程B介入了，线程B也想进行扩容操作，而且恰好线程B的扩容操作还操作完了，则线程B内的状态如下：
这是对于值为3, 7, 5的这三个对象来说，其状态为：
tab[1]=5, 5.next=null
tab[3]=7, 7.next=3, 3.next=null
然后CPU又切换时间片到线程A，线程A继续运行，在Java中代码中的临时变量e和next实际上都为引用类型变量。线程A继续操作，线程A的newTable变为了如下状态：
继续循环：
e=7
next=e.next ----> next=3【从主存中取值】
e.next=newTable[3] ----> e.next=3（7.next=3）【从主存中取值】
newTable[3]=e ----> newTable[3]=7
e=next ----> e=3
此时状态如下：
e=3于是又再一次进入循环：
e=3
next=e.next ----> next=null
e.next=newTable[3] ----> e.next=7（3.next=7）
newTable[3]=e ----> newTable[3]=3
e=next ----> e=null
此时线程状态如下，并结束循环：
此时newTable[3]中所保存的链表即成了循环链表，当查找一个元素，假设说8，经计算indexOf(8) = 3，那么将会在table[3]所存储链表中查找，此时get(8)操作即为一个死循环。
JDK8之后的put方法为什么线程不安全？
JDK8中链表的插入方法由JDK7中的头插入改为了尾插入，所以上面会导致死循环的那个问题在JDK8中已经不复存在了。但HashMap依旧是线程不安全的，因为写入丢失。
现在考虑一种情况，2个线程同时要向一个HashMap中插入元素，而这两个元素恰好又有相同的hash值，假设这个hash值所对应的数组下标所在位置原先是没有元素的，那线程1直接进行赋值，然后CPU切换到了线程2，线程2又进行了一次直接复制，线程2赋的值覆盖了线程1的值，导致了写入丢失的问题。
其次，如果线程1和2向HashMap插入元素时，需要进行扩容操作的话，线程1和线程2都会各自生成各自的newTab，然后最后tab = resize()，到最后table里面只保存了最后一个线程的newTab，其余线程的均会丢失。
0x02 get方法
先来看一下get方法：
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
其主要工作在getNode方法中，用于通过键值hash和键值对象获取Node，如果其得到的值为null那就返回null，否则返回Node对象的value，我们着重来看getNode方法：
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 首先检查桶是否为空，如果不为空的话，检查键值所在桶的位置是否为空
    // 如果二者均为空的话，返回null查找失败
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 检查第一个是否等同
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next