[数据结构与算法]HashMap 1.7和1.8添加流程

1.8 HashMap

声明构造函数

1. 此处仅用于接收初始容量大小（capacity）、加载因子(Load factor)，但仍无真正初始化存储数组table
2. 此处先给出结论：真正初始化哈希表（初始化存储数组table）是在第1次添加键值对时，即第1次调用put（）时。

添加数据

1. 计算Hash值、

   * JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算 * JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算

2. 判断数组是否已经初始化，没有初始化则resize设置容量，加载因子，扩容阈值；已经初始化则计算位置

   所以，初始化哈希表的时机 = 第1次调用put函数时，即调用resize() 初始化创建

3. 判断数组位置中是否存在数据，若不存在则直接在该位置新建节点=插入完毕；否则:视为发生Hash冲突
   则继续判断:当前位置的key是否与需插入的key相同，若相同则直接用新value覆盖旧value， 更新数据完毕；
   否则视为插入数据到数组中失败

4. 插入成功后，将需要插入的数据数组table[i]

5. 未插入成功，代表Hash冲突；判断数据结构是红黑树还是链表

6. 如果是链表，遍历table[i]，equals判断key是否存在，若存在新替换旧；不存在则在链表尾插入；

   1. 插入后判断是否需要树化，当链表长度>8,链表转红黑树

   2. 插入后判断是否需要扩容，当前键值数量>扩容阈值；转化后容量变二倍，按结论规则重新计算存储位置

      1.8扩容机制：

      1. 判断是否需要初始化（若当前容量》最大值不扩容），否则根据新容量2倍创建数组，保存旧的数组；

      2. 遍历旧的数组数据，重新计算在新数组的位置

         情况1:扩容后，若hash值的新增参与运算的位= 0,那么元素在扩容后的位置=原始位置；

         情况2:扩容后，若hash值的新增参与运算的位= 1，那么元素在扩容后的位置=原始位置+扩容前的旧容量

      3. 将旧数组逐个专业新数组（尾插法）

      4. 新数组table引用到hashmap的table属性上

      5. 重新设置阈值

      6. 结束

7. 如果是红黑树，遍历判断节点Key是否与需要插入key相等；

   相等则新覆盖旧的，不相等则新建节点=插入数据
   
   
   参考:
   1.8HashMap
   1.7HashMap

* resize()扩容：1.初始化哈希表 2.当前数组容量过小，需扩容
     */
   final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table; // 扩容前的数组（当前数组）
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的数组的容量 = 长度
    int oldThr = threshold;// 扩容前的数组的阈值
    int newCap, newThr = 0;

    // 针对情况2：若扩容前的数组容量超过最大值，则不再扩充
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }

        // 针对情况2：若无超过最大值，就扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 通过右移扩充2倍
    }

    // 针对情况1：初始化哈希表（采用指定 or 默认值）
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;

    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 计算新的resize上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    if (oldTab != null) {
        // 把每个bucket都移动到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;

                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                else { // 链表优化重hash的代码块
                    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;
                        }
                        // 原索引 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1.7 HashMap

过程：

1. 判断是否初始化table，

2. 未初始化：将传入容量转化为2的次幂
   计算阈值threshold =容量*加载因子
   初始化数组table (使用初始容量)

   // 1. 将传入的容量大小转化为：>传入容量大小的最小的2的次幂    // 即如果传入的是容量大小是19，那么转化后，初始化容量大小为32（即2的5次幂）
   
   // 2. 重新计算阈值 threshold = 容量 * 加载因子  
   
   // 3. 使用计算后的初始容量（已经是2的次幂） 初始化数组table（作为数组长度）    // 即 哈希表的容量大小 = 数组大小（长度）
   

3. 已经初始化，判断key是否为空，key空放在table第一个位置table [0]；key不空则计算hashcode值

   - `HashMap`的键`key` 可为`null`（区别于 `HashTable`的`key` 不可为`null`）
   - HashMap`的键`key` 可为`null`且只能为1个，但值`value`可为null且为多个
   

4. 将hashcode进行扰动处理，得到hash值

   ? 源码分析1：hash(key)
   ? 该函数在JDK 1.7 和 1.8 中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）
   ? JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
   ? JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算

   // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null

   	/**
        * 函数源码分析2：indexFor(hash, table.length)
        * JDK 1.8中实际上无该函数，但原理相同，即具备类似作用的函数
        */
         static int indexFor(int h, int length) {  
             return h & (length-1); 
             // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
   }
   

   计算存放在数据中的位置：

   1.计算哈希码：h=key.hashCode();

   2.再次处理哈希码：1.8将 键key 转换成 哈希码（hash值）操作 = 用hashCode() + 1次位运算 + 1次异或运算（2次扰动）

   3.最终确定下标：h&(length-1)相当于取模操作

   • ? a % b == a & (b - 1) 前提数组长度b是2的次幂
     • 数组长度为什么是2^n？因为在h&(length-1)如果length是奇数，减一后是偶数最后一位是0 ，会导致最后计算的结果都在偶数位置

5. 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）

6. 判断该位置key是否存在

7. 若存在则新值替换旧值；不存在则添加数组

8. 添加之前判断容量是否足够，容量不够则需要扩容

   void resize(int newCapacity) {  
    
    // 1. 保存旧数组（old table） 
    Entry[] oldTable = table;  
   
    // 2. 保存旧容量（old capacity ），即数组长度
    int oldCapacity = oldTable.length; 
   
    // 3. 若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，退出    
    if (oldCapacity == MAXIMUM_CAPACITY) {  
        threshold = Integer.MAX_VALUE;  
        return;  
    }  
   
    // 4. 根据新容量（2倍容量）新建1个数组，即新table  
    Entry[] newTable = new Entry[newCapacity];  
   
    // 5. 将旧数组上的数据（键值对）转移到新table中，从而完成扩容 ->>分析1.1 
    transfer(newTable); 
   
    // 6. 新数组table引用到HashMap的table属性上
    table = newTable;  
   
    // 7. 重新设置阈值  
    threshold = (int)(newCapacity * loadFactor); 
   } 
   
   

   在扩容resize（）过程中，在将旧数组上的数据 转移到 新数组上时，转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况

   此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现 环形链表，从而在获取数据、遍历链表时 形成死循环（Infinite Loop），即 死锁的状态 = 线程不安全

9. 如果容量够则直接插入，原头节点位置后移，新节点头插法

        createEntry(hash, key, value, bucketIndex); 
              void createEntry(int hash, K key, V value, int bucketIndex) { 
   
       // 1. 把table中该位置原来的Entry保存  
       Entry<K,V> e = table[bucketIndex];
       // 2. 在table中该位置新建一个Entry：将原头结点位置（数组上）的键值对 放入到（链表）后1个节点中、将需插入的键值对 放入到头结点中（数组上）-> 从而形成链表
       // 即 在插入元素时，是在链表头插入的，table中的每个位置永远只保存最新插入的Entry，旧的Entry则放入到链表中（即 解决Hash冲突）
       table[bucketIndex] = new Entry<>(hash, key, value, e);  
       // 3. 哈希表的键值对数量计数增加
       size++;  
   }