Java7 HashMap

概述

之所以把HashSet和HashMap放在一起讲解，是因为二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap。

**

HashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素；除该类未实现同步外，其余跟Hashtable大致相同；跟TreeMap不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个HashMap的顺序可能会不同。 根据对冲突的处理方式不同，哈希表有两种实现方式，一种开放地址方式(Open addressing)，另一种是冲突链表方式(Separate chaining with linked lists) 。Java7 HashMap 采用的是冲突链表方式。

从上图容易看出，如果选择合适的哈希函数，put()和get()方法可以在常数时间内完成。但在对HashMap进行迭代时，需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景，不宜将HashMap的初始大小设的过大。

有两个参数可以影响HashMap的性能: 初始容量(inital capacity)和负载系数(load factor)。 初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。

将对象放入到HashMap或HashSet中时，有两个方法需要特别关心: hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象” 。所以，如果要将自定义的对象放入到HashMap或HashSet中，需要hashCode()和equals()方法。

构造函数源码

    public class HashMap<K,V>
      extends AbstractMap<K,V>
      implements Map<K,V>, Cloneable, Serializable{

    // 省略上节阐述的参数
    
    /*
      构造函数1：默认构造函数（无参）
      加载因子和容量为默认，分别是0.75和16
     */
    public HashMap() {
        /*
         实际上是调用构造函数3：指定"容量大小"和"加载因子"的构造函数
         传入的指定容量和加载因子均为默认
        */
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 
    }

    /*
      构造函数2：指定"容量大小"的构造函数
      加载因子是默认的0.75 、容量为指定大小
     */
    public HashMap(int initialCapacity) {
        // 实际上是调用的也是构造函数3，只是在传入的加载因子参数为默认加载因子
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
        
    }

    /*
      构造函数3：指定“容量大小”和“加载因子”的构造函数
      加载因子和容量都是程序员自己指定
     */
    public HashMap(int initialCapacity, float loadFactor) {

        // HashMap的最大容量只能是MAXIMUM_CAPACITY，哪怕传入的 > 最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        // 设置加载因子
        this.loadFactor = loadFactor;
        
        /*
        设置扩容阈值 = 初始容量
        1、注意：此处不是真正的阈值，仅是为了接收参数初始容量大小（capacity）、加载因子(Load factor)，
        并没有真正初始化哈希表，即初始化存储数组table
        2、真正初始化哈希表（初始化存储数组table）是在第1次添加键值对时，即第1次调用put()时，下面会
        详细说明。
        */
        threshold = initialCapacity;   

        init(); // 一个空方法用于未来的子对象扩展
    }

    /*
      构造函数4：包含“子Map”的构造函数
      即构造出来的HashMap包含传入Map参数
      加载因子和容量均为默认
     */
    public HashMap(Map<? extends K, ? extends V> m) {

        // 设置容量大小和加载因子为默认值
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);

        // 该方法用于初始化数组和阈值
        inflateTable(threshold);

        // 将传入的子Map中的全部元素逐个添加到HashMap中
        putAllForCreate(m);
    }
}

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{

    /*
    名词介绍：
    1、容量（capacity）： HashMap中数组【强调一下是数组，不是元素个数】的长度
    2、容量范围：必须是2的幂并且小于最大容量（2的30次方）
    3、初始容量 = 哈希表创建时的容量
    */
    
    //默认初始容量 = 哈希表创建时的容量。默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 十进制的2^4=16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	
    // 最大容量 =  2的30次方（若传入的容量过大，将被最大值替换）
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /*
    1、加载因子(Load factor)：HashMap在其容量自动增加前的一种尺度。
    2、加载因子越大、填满的元素越多 = 空间利用率高、但hash冲突的机会加大、查找效率变低（因为链表变长了）
    3、加载因子越小、填满的元素越少 = 空间利用率小、hash冲突的机会减小、查找效率高（链表不长）
    */
    
    // 实际加载因子
    final float loadFactor;
    
    // 默认加载因子 = 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
	
    //就是上面说的数组，hashmap用Entry数组储存k-v键值对
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    
    static final Entry<?,?>[] EMPTY_TABLE = {};

	
    // HashMap的大小，即HashMap中存储的键值对的数量。注意：和容量区分开，容量是数组Entry的长度
    transient int size;
	

    /*
    1、扩容阈值（threshold）：当哈希表的大小【就是上面的size】 ≥ 扩容阈值时，就会扩容哈希表
    （即扩充HashMap的容量） 
    2、扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
    3、扩容阈值 = 容量 x 加载因子
    */
    int threshold;

数组-Entry

/** 
 * Entry类实现了Map.Entry接口
 * 即 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
**/  
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;  // 键
    V value;  // 值
    Entry<K,V> next; // 指向下一个节点 ，也是一个Entry对象，从而形成解决hash冲突的单链表
    int hash;  // hash值
  
    /** 
     * 构造方法，创建一个Entry 
     * 参数：哈希值h，键值k，值v、下一个节点n 
     */  
    Entry(int h, K k, V v, Entry<K,V> n) {  
        value = v;  
        next = n;  
        key = k;  
        hash = h;  
    }  
  
    // 返回 与 此项 对应的键
    public final K getKey() {  
        return key;  
    }  

    // 返回 与 此项 对应的值
    public final V getValue() {  
        return value;  
    }  
  
    public final V setValue(V newValue) {  
        V oldValue = value;  
        value = newValue;  
        return oldValue;  
    }  
    
   /** 
     * equals（）
     * 作用：判断2个Entry是否相等，必须key和value都相等，才返回true  
     */ 
      public final boolean equals(Object o) {  
        if (!(o instanceof Map.Entry))  
            return false;  
        Map.Entry e = (Map.Entry)o;  
        Object k1 = getKey();  
        Object k2 = e.getKey();  
        if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
            Object v1 = getValue();  
            Object v2 = e.getValue();  
            if (v1 == v2 || (v1 != null && v1.equals(v2)))  
                return true;  
        }  
        return false;  
    }  
    
    /** 
     * hashCode（） 
     */ 
    public final int hashCode() { 
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());  
    }  
  
    public final String toString() {  
        return getKey() + "=" + getValue();  
    }  
  
    /** 
     * 当向HashMap中添加元素时，即调用put(k,v)时， 
     * 对已经在HashMap中k位置进行v的覆盖时，会调用此方法 
     * 此处没做任何处理 
     */  
    void recordAccess(HashMap<K,V> m) {  
    }  
  
    /** 
     * 当从HashMap中删除了一个Entry时，会调用该函数 
     * 此处没做任何处理 
     */  
    void recordRemoval(HashMap<K,V> m) {  
    } 

}

get()

get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.getValue()。因此getEntry()是算法的核心。 算法思想是首先通过hash()函数得到对应bucket的下标，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否是要找的那个entry。

上图中hash(k)&(table.length-1)等价于hash(k)%table.length，原因是HashMap要求table.length必须是2的指数，因此table.length-1就是二进制低位全是1，跟hash(k)相与会将哈希值的高位全抹掉，剩下的就是余数了。

假设我们有一个哈希表，其长度table.length = 8，这是一个2的幂次方(2^3)。那么table.length - 1就等于7，转换成二进制就是0111。现在我们有一个哈希值hash(k) = 45，它的二进制表示为00101101。

• hash(k) & (table.length - 1) = 45 & 7 = 00101101 & 00000111 = 00000101，转换回十进制就是5。
• hash(k)%table.length = 45 % 8 = 5

可以看到，两种方式得到的结果是一样的，但是位运算的方式更快，因为它只涉及到简单的逻辑运算，而取模运算可能需要更多的计算步骤。

这就是为什么在设计像HashMap这样的数据结构时，会选择让table.length为2的幂次方，并使用位运算来代替取模运算的原因。

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
	......
	int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[hash&(table.length-1)];//得到冲突链表
         e != null; e = e.next) {//依次遍历冲突链表中的每个entry
        Object k;
        //依据equals()方法判断是否相等
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于getEntry()方法；如果没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry，插入方式为头插法。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    // 计算键key的哈希值。hash()方法会对key.hashCode()的结果进行一定的处理，以减少哈希冲突。
    int hash = hash(key.hashCode());
    // 定位桶索引：利用哈希值和哈希表当前长度，通过indexFor(hash, table.length)计算出桶（bucket）的索引位置。
    int i = indexFor(hash, table.length);
    //遍历桶中链表：从对应索引的桶开始，遍历链表中的每个Entry（键值对节点）
    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;
        }
    }

    modCount++;
    // 未找到匹配项时插入新项：如果遍历完链表都没有找到匹配的键值对，
    // 则创建一个新的Entry对象，并使用addEntry方法将其添加到数组位置i的链表头部
    addEntry(hash, key, value, i);
    return null;
}



//addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 检查哈希表的当前大小（size）是否达到了扩容阈值（threshold）
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//自动扩容，并重新哈希
        //重新计算哈希值
        hash = (null != key) ? hash(key) : 0;
        //重新计算桶索引
        bucketIndex = hash & (table.length-1);//hash%table.length
    }
    // 获取当前桶中链表的第一个元素（头结点）
    Entry<K,V> e = table[bucketIndex];
    // 将新创建的Entry对象设置为table[bucketIndex]，并让新创建的Entry对象的下一个引用指向原来的头节点。
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}


static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
     /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    //...
}

头插法

假设刚开始hashMap有这些数据

此时插入 e2

    // 对e2<k,v> k.hashCode()的进行求hashcode
    int hash = hash(key.hashCode());
    // 通过indexFor(hash, table.length)计算出桶的索引位置。假设i=1
    int i = indexFor(hash, table.length);

    //遍历桶中链表：从对应索引的桶开始，遍历链表中的每个Entry（键值对节点）
    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;
        }
    }

    modCount++;
    // 未找到匹配项时插入新项：如果遍历完链表都没有找到匹配的键值对，
    // 则创建一个新的Entry对象，并使用addEntry方法将其添加到数组位置i中
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 检查哈希表的当前大小（size）是否达到了扩容阈值（threshold） 不成立
    // 此时size=1 ,扩容阈值为1.5 不成立
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//自动扩容，并重新哈希
        //重新计算哈希值
        hash = (null != key) ? hash(key) : 0;
        //重新计算桶索引
        bucketIndex = hash & (table.length-1);//hash%table.length
    }
    // 获取当前桶中链表的第一个元素（头结点） e= e4
    Entry<K,V> e = table[bucketIndex];
    // 将新创建的Entry对象该对象为e2的实例，将e2插入链表，e2.next = e4
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}


static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
     /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    //...
}

remove()

remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry，然后删除该entry(修改链表的相应引用)。查找过程跟getEntry()过程类似。

//removeEntryForKey()
final Entry<K,V> removeEntryForKey(Object key) {
	......
	int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);//hash&(table.length-1)
    Entry<K,V> prev = table[i];//得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {//遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry
            modCount++; size--;
            if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry
            else prev.next = next;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

Java8 HashMap

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。

根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。

为了降低这部分的开销，在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

来一张图简单示意一下吧：

注意，上图是示意图，主要是描述结构，不会达到这个状态的，因为这么多数据的时候早就扩容了。

下面，我们还是用代码来介绍吧，个人感觉，Java8 的源码可读性要差一些，不过精简一些。

Java7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。

我们根据数组元素中，第一个节点数据类型是 Node 还是 TreeNode 来判断该位置下是链表还是红黑树的。

put 过程分析

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

// 第一个hash值
// 第四个参数 onlyIfAbsent 如果是 true，那么只有在不存在该 key 时才会进行 put 操作，
// 第五个参数 evict 我们这里不关心，可以不用管，使用默认的即可
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 第一次 put 值的时候，会触发下面的 resize()，类似 java7 的第一次 put 也要初始化数组长度
    // 第一次 resize 和后续的扩容有些不一样，因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 尝试直接在空位插入新节点(p==null)
    // 首先计算出哈希表中的索引位置i，然后通过索引i访问哈希表中的元素p。
    // 如果该元素为空，则说明指定键值对不存在于哈希表中。那么直接初始化一下 Node 并放置在这个位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    //发生哈希冲突的几种情况(p!=null)
    else {
        // e 临时节点的作用， k 存放该当前节点的key 
        Node<K,V> e; K k;
        
        //第一种,需要插入的key-value的hash值，key都与当前节点p的相等，e = p，
        // 则表示需要插入的key-value与首节点相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        //第二种，hash值不等于首节点，判断该p是否属于红黑树的节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        //第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点
        else {
            //遍历该链表
            for (int binCount = 0; ; ++binCount) {
                
                // 插入到链表的最后面(Java7 是插入到链表的最前面)
                // 判断当前节点的下一个节点是否为空，如果为空，则表示遍历到了链表的末尾
                if ((e = p.next) == null) {
                    // 在链表的末尾插入新的节点
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 8 个
                    // 如果当前链表的节点个数超过了阈值（TREEIFY_THRESHOLD-1），则将链表转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }

                // 如果当前节点的哈希值和键值与要插入的键值对相等，则表示找到了已存在的键值对，退出循环。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node
                    break;
                p = e;
            }
        }
        // 如果e不为空，说明找到了现有节点，进行值的更新或返回旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

和 Java7 稍微有点不一样的地方就是，Java7 是先扩容后插入新值的，Java8 先插值再扩容，不过这个不重要。

resize() 数组扩容

resize() 方法用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移。

final Node<K,V>[] resize() {
    // 把当前底层数组赋值给oldTab，为数据迁移工作做准备
    Node<K,V>[] oldTab = table;
    // 获取当前数组的大小，等于或小于0表示需要初始化数组，大于0表示需要扩容数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 获取扩容的阈值（容量*负载系数）
    int oldThr = threshold;
    // 定义并初始化新数组长度和目标阈值
    int newCap, newThr = 0;
    
    // 判断是初始化数组还是扩容，等于或小于0表示需要初始化数组，大于0表示需要扩容数组。
    // 若  if(oldCap > 0)=true 表示需扩容而非初始化
    if (oldCap > 0) { 
        // 判断数组长度是否已经是最大
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
    
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 目标阈值扩展2倍，数组长度扩展2倍
            newThr = oldThr << 1; // double threshold
    }
    // 表示需要初始化数组而不是扩容    
    else if (oldThr > 0) // 
        newCap = oldThr;
    // 表示需要初始化数组而不是扩容，零初始阈值表示使用默认值        
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 当目标阈值为0时需重新计算，公式：容量（newCap）*负载系数（loadFactor）
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        // 计算目标阈值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

    // 根据以上计算结果将阈值更新
    threshold = newThr;

    // 用新的数组大小初始化新的数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 将新数组赋值给底层数组
    table = newTab;


    // --------------------------------------------------------------------
    // 此时已完成初始化数组或扩容数组，但原数组内的数据并未迁移至新数组（扩容后的数组），
    // 之后的代码则是完成原数组向新数组的数据迁移过程
    // --------------------------------------------------------------------

    // 判断原数组内是否有存储数据，有的话开始迁移数据
    if (oldTab != null) {
        // 开始遍历原数组，进行数据迁移。
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 将数组内此下标中的数据赋值给Node类型的变量e，并判断非空
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 1 - 普通元素判断：判断数组内此下标中是否只存储了一个元素，是的话表示这是一个普通元素，并开始转移
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 2 - 红黑树判断：判断此下标内是否是一颗红黑树，是的话进行数据迁移
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 3 - 链表判断：若此下标内包含的数据既不是普通元素又不是红黑树，则它只能是一个链表，进行数据转移    
                else { 
                    // 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序
                    // loHead、loTail 对应一条链表
                    // hiHead、hiTail 对应另一条链表
                    // 代码还是比较简单的
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        // 第一条链表
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 第二条链表的新的位置是 j + oldCap，这个很好理解
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

get 过程分析

相对于 put 来说，get 真的太简单了。

• 计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)
• 判断数组该位置处的元素是否刚好就是我们要找的，如果不是，走第三步
• 判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据，如果不是，走第四步
• 遍历链表，直到找到相等(==或equals)的 key

public V get(Object key) {
    Node<K,V> e;
    // 调用getNode方法来完成
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}


final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    // 头结点也就是数组下标的节点
    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) != null) {
            
            // 判断是否是红黑树
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            // 链表遍历
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //找不到，表示不存在该节点
    return null;
}

遍历

    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        
        //一般我们用到EntrySet，都是为了获取iterator
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator();
        }
        
        //最终还是调用getNode方法
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        
        //最终还是调用removeNode方法
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        //。。。
    }

abstract class HashIterator {
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot
 
        HashIterator() {
            //因为hashmap也是线程不安全的，所以要保存modCount。用于fail-fast策略
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            //next 初始时，指向 哈希桶上第一个不为null的链表头
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }
 
        public final boolean hasNext() {
            return next != null;
        }
 
        //由这个方法可以看出，遍历HashMap时，顺序是按照哈希桶从低到高，链表从前往后，依次遍历的。属于无序集合。
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            //fail-fast策略
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            //依次取链表下一个节点，
            if ((next = (current = e).next) == null && (t = table) != null) {
                //如果当前链表节点遍历完了，则取哈希桶下一个不为null的链表头
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }
 
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            fail-fast策略
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            //最终还是利用removeNode 删除节点
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

树化

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // 首先判断哈希表是否为空或者容量是否小于 64
        // 如果是则调用resize()方法进行扩容操作。
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        // 如果哈希表不为空且容量满足要求，则获取链表的头节点和尾节点
        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);
        }
    }

链表变红黑树之前，会进行数组扩容。数组数量较小时，应该避开红黑树结构，这种情况下变为红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡 。同时数组长度小于64时，搜索时间相对要快些。所以为了提高性能和减少搜索时间，底层在阈值大于8并且数组长度不小于64时，链表才转换为红黑树。

JDK7 扩容出现的死循环链表

 /**
   * 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
   * 过程：按旧链表的正序遍历链表、在新链表的头部依次插入。但是这样会导致扩容完成后，链表逆序
   */ 	
void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //通过遍历 旧数组，将旧数组上的数据（键值对）转移到新数组中
        for (Entry<K,V> e : table) {
            while(null != e) {
                /*
                 1、遍历以该数组元素为首的链表
                 2、转移链表时，因是单链表，故要保存下1个结点，否则转移后链表会断开
                 */
                Entry<K,V> next = e.next; //pos_1
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                 //重新计算每个元素的存储位置
                int i = indexFor(e.hash, newCapacity);
                
                //这个地方暂时先放着，后面讲死循环链表的时候会讲到
                e.next = newTable[i];
                //讲当前元素，赋给新数组的对应下标位置。
                newTable[i] = e;
                // 访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
                e = next;
            }
        }
    }

前置条件

1、为了演示方便，初始状态时，hashmap容量为2，加载因子为默认的0.75.

步骤1

hashmap初始状态

1. 此时只有一个元素，扩容阈值为2*0.75 = 1.5。
2. 此时假设有两个线程，线程a和线程b同时put，并且都没有进入到addEntry()方法里的if逻辑【因为此时size都没有++，size == 1   1 < 1.5  所以if判断不成立。】。两个线程都准备同时调用createEntry()方法。

	void addEntry(int hash, K key, V value, int bucketIndex) {

        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

3、线程a put的是 e3 = <k3,v3>。线程b put的是e2 = <k2,v2>。两个都调用了createEntry()方法。

步骤2

两个线程调用完毕之后，hashmap目前是这样的。

此时size==3。下次再进行put的时候，addEntry()方法里的if判断就会成立。

步骤3

接下来重点看看死循环是如何产生的？

假设数据跟元素数据一致，有两个线程：线程1 和 线程2，同时执行put方法，最后同时调用transfer方法。

1. 假设线程1 put的是e1，线程2 put的是e0。
2. 两个线程都同时调用resize()方法，新数组已经扩容完毕，准备转移旧数组上的数据到新数组里。也就是准备调用resize()里的下面这个方法。

//addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 检查哈希表的当前大小（size）是否达到了扩容阈值（threshold）
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // pos_1
        resize(2 * table.length);//自动扩容，并重新哈希
        //重新计算哈希值
        hash = (null != key) ? hash(key) : 0;
        //重新计算桶索引
        bucketIndex = hash & (table.length-1);//hash%table.length
    }
    // 获取当前桶中链表的第一个元素（头结点）
    Entry<K,V> e = table[bucketIndex];
    // 将新创建的Entry对象设置为table[bucketIndex]，并让新创建的Entry对象的下一个引用指向原来的头节点。
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

void resize(int newCapacity) {
     Entry[] oldTable = table;
     int oldCapacity = oldTable.length;
     if (oldCapacity == MAXIMUM_CAPACITY) {
     threshold = Integer.MAX_VALUE;
     return;
     }
     // pos_2
     // 创建2倍大小的新数组
     Entry[] newTable = new Entry[newCapacity];
     // pos_3
     // 将旧数组的链表转移到新数组，就是这个方法导致的hashMap不安全，等下我们进去看一眼
     transfer(newTable, initHashSeedAsNeeded(newCapacity));
     table = newTable;
     // 重新计算扩容阈值(容量*加载因子)
     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

1. 此时线程1 线程2 都执行到pos_2, 来看下此时内存里的状态

接下里线程1 线程2 都执行pos_3，调用transfer()方法

步骤4

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];
             //这行才是真正把数据插入新数组中，前面那行代码只是设置当前节点的next
             //这两行代码决定了倒序插入
             //比如：以前同一个位置上是:3，7，后面可能变成了：7、3
             newTable[i] = e;
             //将下一个元素赋值给当前元素，以便遍历下一个元素
             e = next;  
         }  
     }
}

线程1 先执行，到 Entry<K,V> next = e.next; 这一行，被挂起了。

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;

        for (Entry<K,V> e : table) {
            while(null != e) {
				//pos_1
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);   
                //pos_2
                e.next = newTable[i];
                //pos_3
                newTable[i] = e;
                //pos_4
                e = next;
            }
        }
    }

1. 假设线程1执行完代码pos_1位置后，暂时挂起。此时e == e3  e.next == e2

1. 线程2直接扩容完毕，那么完成后的状态是这样【假设e2和e3还是hash到同一个位置】

1. 线程1还是原来的状态

强调一点：线程2已经扩容完毕

步骤5

目前两个线程里的新数组是这样的

步骤6

线程1开始继续执行

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
				//pos_1
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);   
                //pos_2
                e.next = newTable[i];
                //pos_3
                newTable[i] = e;
                //pos_4
                e = next;
            }
        }
    }

之前说过：假设线程1执行完代码pos_1位置后，暂时挂起。此时e == e3   e.next == e2【也就是next == e2】

1. 线程1唤醒后，继续执行pos_2，pos_3，pos_4
2. 执行pos_2：意思是e3的next指针指向了线程1的新hash表【也就是线程1的newTable】，因为线程1的newTable是新的所以为null，所以e3.next = null。
3. 执行pos_3：线程1的newTable[3] = e2,将e2放入数组3中（头插法）
4. 执行pos_4：e = next,next==e2,则e = e2;

也就变成了下面这个样子。

步骤7

1. 线程1继续执行循环体

注意之前强调过线程2已经扩容完毕，那么table就已经被指向了newTable2，也就是说第二次循环时，线程1所循环的table变量就是线程2中的newTable

while(null != e) {
    //pos_1
    Entry<K,V> next = e.next;
    if (rehash) {
        e.hash = null == e.key ? 0 : hash(e.key);
    }
    int i = indexFor(e.hash, newCapacity);   
    //pos_2
    e.next = newTable[i];
    //pos_3
    newTable[i] = e;
    //pos_4
    e = next;
}

1. 执行pos_1：此时e == e2，那么next就是 e2.next，此时next == e3；
2. 执行pos_2：经过第一轮循环，线程1中的newTable[3] == e2。那么执行完这行代码后，e2.next还是等于e3【相当于没执行】
3. 执行pos_3：newTable1[3] == e3。
4. 执行pos_4：e = e2

执行完，变成这样。

步骤8

线程1继续执行循环体

while(null != e) {
    //pos_1
    Entry<K,V> next = e.next;
    if (rehash) {
        e.hash = null == e.key ? 0 : hash(e.key);
    }
    int i = indexFor(e.hash, newCapacity);   
    //pos_2
    e.next = newTable[i];
    //pos_3
    newTable[i] = e;
    //pos_4
    e = next;
}

1. 执行pos_1：next = e3.next得到  next == null。
2. 执行pos_2： e.next = newTable[i]     e3.next == newTable[3]。也就是相当于 e3.next == e2
3. 执行pos_3： newTable[i] = e得到  newTable1[3] == e3

这样就形成了循环链表，再get()数据就会陷入死循环。

死循环造成 CPU 100%

HashMap 有可能会发生死循环并且造成 CPU 100% ，这种情况发生最主要的原因就是在扩容的时候，也就是内部新建新的 HashMap 的时候，扩容的逻辑会反转散列桶中的节点顺序，当有多个线程同时进行扩容的时候，由于 HashMap 并非线程安全的，所以如果两个线程同时反转的话，便可能形成一个循环，并且这种循环是链表的循环，相当于 A 节点指向 B 节点，B 节点又指回到 A 节点，这样一来，在下一次想要获取该 key 所对应的 value 的时候，便会在遍历链表的时候发生永远无法遍历结束的情况，也就发生 CPU 100% 的情况。

所以综上所述，HashMap 是线程不安全的，在多线程使用场景中如果需要使用 Map，应该尽量避免使用线程不安全的 HashMap。同时，虽然 Collections.synchronizedMap(new HashMap()) 是线程安全的，但是效率低下，因为内部用了很多的 synchronized，多个线程不能同时操作。推荐使用线程安全同时性能比较好的 ConcurrentHashMap。

在Java中，HashMap作为一种常用的数据结构，提供了高效的键值对存储和检索能力。然而，其设计并非考虑线程安全性，这在高并发环境下可能导致严重的性能问题，甚至死锁。当多个线程同时尝试修改HashMap，尤其是在执行扩容操作时，这种线程不安全性尤为突出。扩容过程中，HashMap需要重新计算每个键的哈希值，并将元素重新分配到新的桶中，这一过程涉及对现有链表或红黑树结构的调整。如果多个线程并发进行此操作，没有适当的同步机制，很容易产生链表循环引用，即所谓的“死循环”，这会导致CPU占用率飙升至100%，严重影响系统响应和稳定性。

为了避免这类问题，开发人员在设计多线程应用时应谨慎选择数据结构。尽管HashMap提供了良好的单线程性能，但在并发场景下，其线程不安全性成为显著短板。虽然Collections.synchronizedMap(new HashMap<>())可以创建线程安全的Map，但由于其实现方式依赖于大量的synchronized关键字，这不仅降低了并发性能，还可能引入不必要的锁竞争，从而限制了系统的吞吐量。

鉴于上述分析，ConcurrentHashMap作为Java并发包中的明星成员。ConcurrentHashMap在Java 8及后续版本中进一步优化了内部实现，采用了更高效的数据结构和算法，如基于CAS的非阻塞算法，以及在高负载下自动转换为红黑树的链表，进一步增强了其在高并发环境下的表现。

因此，在多线程环境中，建议优先考虑使用ConcurrentHashMap，以充分利用其优秀的并发性能和线程安全性，确保应用的稳定运行和高效处理。

论证HashMap是线程不安全的

modCount 赋值错误

在 HashMap 的 put() 方法中，可以看出里面进行了很多操作，那么在这里，我们把目光聚焦到标记出来的 ++modCount 这一行代码中，相信有经验的小伙伴一定发现了，这相当于是典型的“i++”操作。从表面上看 i++ 只是一行代码，但实际上它并不是一个原子操作，它的执行步骤主要分为三步，而且在每步操作之间都有可能被打断。

• 第一个步骤是读取；
• 第二个步骤是增加；
• 第三个步骤是保存。

那么我们接下来具体看一下如何发生的线程不安全问题。

我们根据箭头指向依次看，假设线程 1 首先拿到 i=1 的结果，然后进行 i+1 操作，但此时 i+1 的结果并没有保存下来，线程 1 就被切换走了，于是 CPU 开始执行线程 2，它所做的事情和线程 1 是一样的 i++ 操作，但此时我们想一下，它拿到的 i 是多少？实际上和线程 1 拿到的 i 的结果一样都是 1，为什么呢？因为线程 1 虽然对 i 进行了 +1 操作，但结果没有保存，所以线程 2 看不到修改后的结果。

然后假设等线程 2 对 i 进行 +1 操作后，又切换到线程 1，让线程 1 完成未完成的操作，即将 i + 1 的结果 2 保存下来，然后又切换到线程 2 完成 i = 2 的保存操作，虽然两个线程都执行了对 i 进行 +1 的操作，但结果却最终保存了 i = 2 的结果，而不是我们期望的 i = 3，这样就发生了线程安全问题，导致了数据结果错误，这也是最典型的线程安全问题。

所以，从源码的角度，或者说从理论上来讲，这完全足以证明 HashMap 是线程非安全的了。因为如果有多个线程同时调用 put() 方法的话，它很有可能会把 modCount 的值计算错。

扩容期间取出的值不准确

刚才我们分析了源码，你可能觉得不过瘾，下面我们就打开代码编辑器，用一个实验来证明 HashMap 是线程不安全的。

为什么说 HashMap 不是线程安全的呢？我们先来讲解下原理。HashMap 本身默认的容量不是很大，如果不停地往 map 中添加新的数据，它便会在合适的时机进行扩容。而在扩容期间，它会新建一个新的空数组，并且用旧的项填充到这个新的数组中去。那么，在这个填充的过程中，如果有线程获取值，很可能会取到 null 值，而不是我们所希望的、原来添加的值。所以我们程序就想演示这种情景，我们来看一下这段代码：

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

public class HashMapNotSafe {

    public static void main(String[] args) {
        final Map<Integer, String> map = new HashMap<>();
        final Integer targetKey = 0b1111_1111_1111_1111; // 65 535
        final String targetValue = "v";

        map.put(targetKey, targetValue);

        new Thread(() -> {
            IntStream.range(0, targetKey).forEach(key -> map.put(key, "someValue"));
        }).start();

        while (true) {
            if (null == map.get(targetKey)) {
                throw new RuntimeException("HashMap is not thread safe.");
            }
        }
    }
}

代码中首先建立了一个 HashMap，并且定义了 key 和 value， key 的值是一个二进制的 1111_1111_1111_1111，对应的十进制是 65535。之所以选取这样的值，就是为了让它在扩容往回填充数据的时候，尽量不要填充得太快，便于我们能捕捉到错误的发生。而对应的 value 是无所谓的，我们随意选取了一个非 null 的 "v" 来表示它，并且把这个值放到了 map 中。

接下来，我们就用一个新的线程不停地往我们的 map 中去填入新的数据，我们先来看是怎么填入的。首先它用了一个 IntStream，这个 range 是从 0 到之前所讲过的 65535，这个 range 是一个左闭右开的区间，所以会从 0、1、2、3……一直往上加，并且每一次加的时候，这个 0、1、2、3、4 都会作为 key 被放到 map 中去。而它的 value 是统一的，都是 "someValue"，因为 value 不是我们所关心的。

然后，我们就会把这个线程启动起来，随后就进入一个 while 循环，这个 while 循环是关键，在 while 循环中我们会不停地检测之前放入的 key 所对应的 value 还是不是我们所期望的字符串 "v"。我们在 while 循环中会不停地从 map 中取 key 对应的值。如果 HashMap 是线程安全的，那么无论怎样它所取到的值都应该是我们最开始放入的字符串 "v"，可是如果取出来是一个 null，就会满足这个 if 条件并且随即抛出一个异常，因为如果取出 null 就证明它所取出来的值和我们一开始放入的值是不一致的，也就证明了它是线程不安全的，所以在此我们要抛出一个 RuntimeException 提示我们。

下面就让我们运行这个程序来看一看是否会抛出这个异常。一旦抛出就代表它是线程不安全的，这段代码的运行结果：

Exception in thread "main" java.lang.RuntimeException: HashMap is not thread safe.
	at com.thread.basic.HashMapNotSafe.main(HashMapNotSafe.java:24)

很明显，很快这个程序就抛出了我们所希望看到的 RuntimeException，并且我们把它描述为：HashMap is not thread safe，一旦它能进入到这个 if 语句，就已经证明它所取出来的值是 null，而不是我们期望的字符串 "v"。

通过以上这个例子，也证明了HashMap 是线程非安全的。

put 碰撞导致数据丢失

比如，有多个线程同时使用 put 来添加元素，而且恰好两个 put 的 key 是一样的，它们发生了碰撞，也就是根据 hash 值计算出来的 bucket 位置一样，并且两个线程又同时判断该位置是空的，可以写入，所以这两个线程的两个不同的 value 便会添加到数组的同一个位置，这样最终就只会保留一个数据，丢失一个数据。

可见性问题无法保证

我们再从可见性的角度去考虑一下。可见性也是线程安全的一部分，如果某一个数据结构声称自己是线程安全的，那么它同样需要保证可见性，也就是说，当一个线程操作这个容器的时候，该操作需要对另外的线程都可见，也就是其他线程都能感知到本次操作。

可是 HashMap 对此是做不到的，如果线程 1 给某个 key 放入了一个新值，那么线程 2 在获取对应的 key 的值的时候，它的可见性是无法保证的，也就是说线程 2 可能可以看到这一次的更改，但也有可能看不到（原因在于线程2可以使用CPU中的缓存，如果使用CPU中缓存的数据则表示无法看到线程1的操作，实际上是非原子性导致的）。所以从可见性的角度出发，HashMap 同样是线程非安全的。

为什么选择8作为树化阈值？

	//Java8代码官方解释的原因
   * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

由于treenodes的大小大约是常规节点的两倍，因此我们仅在容器包含足够的节点以保证使用时才使用它们，当它们变得太小（由于移除或调整大小）时，它们会被转换回普通的node节点，容器中节点分布在hash桶中的频率遵循泊松分布，桶的长度超过8的概率非常非常小，作者是根据概率统计而选择了8作为阀值。

为什么选择6和8作为链表化和树化的阈值?

1. 首先就是遵循泊松分布概率选了6和8
2. 其次：如果选择6和8（如果链表小于等于6树还原转为链表，大于等于8转为树），中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

package com.core.Collection;

import java.util.HashMap;

public class HashMapDemo12 {

    private int i;


    public HashMapDemo12(int i) {
        this.i = i;
    }

    public static void main(String[] args) {

        HashMap map = new HashMap<HashMapDemo12, Integer>(1);

        HashMapDemo12 hashMapDemo = null;
        for (int i = 0; i < 1000; i++) {
            HashMapDemo12 hashMapDemo1 = new HashMapDemo12(i);
            if (i==500){
                hashMapDemo = hashMapDemo1;
            }
            map.put(hashMapDemo1, null);
        }

        System.out.println(map.get(hashMapDemo));


        System.out.println("运行结束");

    }

    @Override
    public int hashCode() {
        return 1;
    }
}

在这个例子中，我们建了一个 HashMap，并且不停地往里放入值，所放入的 key 的对象，它的 hashCode 是被重写过得，并且始终返回 1。这段代码运行时，如果通过 debug 查看map.get(hashMapDemo) 的执行逻辑，我们观察 map 内的节点，可以发现已经变成了 TreeNode。