/**
 * @description: jdk1.7中的HashMap 扩容造成死循环分析过程
 * @author: Silince
 * @create: 2021-01-17 20:26
 **/
public class HashMapTest {
    public static void main(String[] args) {
        HashMapThread thread0 = new HashMapThread();
        HashMapThread thread1 = new HashMapThread();
        HashMapThread thread2 = new HashMapThread();
        HashMapThread thread3 = new HashMapThread();
        HashMapThread thread4 = new HashMapThread();
        thread0.start();
        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();
    }
}

class HashMapThread extends Thread{
    private static AtomicInteger ai = new AtomicInteger();
    private static Map<Integer,Integer> map = new HashMap<>();

    @Override
    public void run() {
        map.put(ai.get(),ai.get());
        ai.incrementAndGet();
    }
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length; // 获取新Entry数组的容量
    // 遍历旧的Entry数组
    for (Entry<K,V> e : table) {
    // e的下一个entry不为null则循环（链表上的循环）
      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的hash值和容量计算出index值
        e.next = newTable[i]; // e的下一个Entry为新数组i位置上的值
        newTable[i] = e; // e添加到新数组的i位置上
        e = next; // next赋值给e
       }
     }
 }

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /**
     *1）transient Node<K,V>[] table; 表示存储Map集合中元素的数组。
     *2）(tab = table) == null 表示将空的table赋值给tab,然后判断tab是否等于null，第一次肯定是null
     *3）(n = tab.length) == 0 表示将数组的长度0赋值给n,然后判断n是否等于0，n等于0
     *由于if判断使用双或，满足一个即可，则执行代码 n = (tab = resize()).length; 进行数组初始化。
     *并将初始化好的数组长度赋值给n.
     *4）执行完n = (tab = resize()).length，数组tab每个空间都是null
     */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /**
     *1）i = (n - 1) & hash 表示计算数组的索引赋值给i，即确定元素存放在哪个桶中
     *2）p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给节点p
     *3) (p = tab[i = (n - 1) & hash]) == null 判断节点位置是否等于null，如果为null，则执行代码：tab[i] = newNode(hash, key, value, null);根据键值对创建新的节点放入该位置的桶中
     *  小结：如果当前桶没有哈希碰撞冲突，则直接把键值对插入空间位置
     */ 
6    if ((p = tab[i = (n - 1) & hash]) == null)
        //创建一个新的节点存入到桶中
        tab[i] = newNode(hash, key, value, null);
    else {
         // 执行else说明tab[i]不等于null，表示这个位置已经有值了。
        Node<K,V> e; K k;
        /**
         *比较桶中第一个元素(数组中的结点)的hash值和key是否相等
         *	1）p.hash == hash ：p.hash表示原来存在数据的hash值  hash表示后添加数据的hash值 比较两个hash值是否相等
         *    说明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象。
         *    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) 
         *    {
         *       return new Node<>(hash, key, value, next);
         *    }
         *    而在Node类中具有成员变量hash用来记录着之前数据的hash值的
         *  2）(k = p.key) == key ：p.key获取原来数据的key赋值给k  key 表示后添加数据的key 比较两个key的地址值是否相等
         *  3）key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等，那么先判断后添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等
         */
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 说明：两个元素哈希值相等，并且key的值也相等
                // 将旧的元素整体对象赋值给e，用e来记录
                e = p;
        // ⚠️ hash值不相等或者key不相等；判断p是否为红黑树结点
        else if (p instanceof TreeNode)
            // 说明是该桶中是红黑树的头节点，把新节点放入红黑树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 说明是链表节点
        else {
            /**
            *	1)如果是链表的话需要遍历到最后节点然后插入
            *	2)采用循环遍历的方式，判断链表中是否有重复的key
            */
            for (int binCount = 0; ; ++binCount) {
                /**
                 *	1)e = p.next 获取p的下一个元素赋值给e
                 *	2)(e = p.next) == null 判断p.next是否等于null，等于null，说明p没有下一个元素，那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键；将该键值对插入链表中
                 */
                if ((e = p.next) == null) {
                    /**
                     * 1）创建一个新的节点插入到尾部  ⚠️⚠️⚠️ 尾插法！
                     * p.next = newNode(hash, key, value, null);
                     * Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) 
                     * {
                     *          return new Node<>(hash, key, value, next);
                     *   }
                     * 注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个节点肯定是null
                     * 2）这种添加方式也满足链表数据结构的特点，每次向后添加新的元素
                     */
                    p.next = newNode(hash, key, value, null);
                    /**
                     *1)节点添加完成之后判断此时节点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于
                     * 则将链表转换为红黑树
                     *2）int binCount = 0 ：表示for循环的初始化值。从0开始计数。记录着遍历节点的个数。值是0表示第一个节点，1表示第二个节点...
                     * TREEIFY_THRESHOLD - 1 = 7;
                     * 如果binCount的值是7(加上数组中的的一个元素，元素个数是8),此时转换红黑树
                     */
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //转换为红黑树
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                 
                /**
                 *执行到这里说明e = p.next 不是null，不是最后一个元素。继续判断链表中结点的key值与插入的元素的key值是否相等
                 */
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    /**
                     *要添加的元素和链表中的存在的元素的key相等了，则跳出for循环。不用再继续比较了
                     *	直接执行下面的if语句去替换去 if (e != null) 
                     */
                    break;
                    /**
                     *说明新添加的元素和当前节点不相等，继续查找下一个节点。
                     *用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                     */
                    p = e;
            }
        }
        /**
         *表示在桶中找到key值、hash值与插入元素相等的结点
         *也就是说通过上面的操作找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值
         *这里完成了put方法的修改功能
         */
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                //e.value 表示旧值  value表示新值 
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    //修改记录次数
    ++modCount;
    // 判断实际大小是否大于threshold阈值，如果超过则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}