HashMap

一、JDK 1.7 的HashMap

1. 数据结构

1
2
3

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

HashMap 继承了 AbstractMap 抽象类，实现了 Cloneable、Serializable接口。HashMap的拷贝是一种浅拷贝，即拷贝对象的改变会影响到原对象；HashMap是线程不安全的，不保证插入的键值对有序，但是允许存储键为null的值；HashTable是线程安全的，但是不能存储键为 null的值。
jdk 1.7 中的HashMap 是基于数组+链表的模式构建的。虽然 HashMap定义了hash函数来避免冲突，但是还是会存在两个 key在计算后桶的位置一样，因此考虑使用链表的方式解决冲突；

结构： Entry节点(包括键、值、next、hash)

static class Entry implements Map.Entry {
    /** 键对象*/
    final K key;
    /** 值对象*/
    V value;
    /** 指向下一个Entry对象*/
    Entry next;
    /** 键对象哈希值*/
    int hash;
}

由于是数组组成，因此 O(1)的平均查找、插入、删除时间；

结构	描述	备注
数组（主）	（1）底层的核心是数组(table[]) ，数组中存储的是结点Entry。（2）数组的下标是经过处理的键Key的hash值。（3）数组元素 = 1个Entry结点 = hash值+key+value+next指针 = 1个链表头结点（4）数组大小 = HashMap的容量
单链表（辅）	（1）每个链表 = 哈希表的桶（bucket）（2）链表的结点值 = 1个键值对（3）链表长度 = 桶的大小	链表的主要作用是用来解决Hash冲突的。发生冲突时，新元素插入到链表头中；新元素总是添加到数组中，旧元素移动到单链表中。
	HashMap的键值对数量 = 数组中的键值对数量 + 链表中的键值对数量

2. 重要参数

重要参数包括三个：容量、负载因子、扩容阈值

容量：

容量（Capicity）是指 HashMap中的数组长度；而 Size 指的是HashMap中存储的键值对的数量；

容量的范围必须是 2的整数次幂；最大容量是 2^30；初始容量是 16；

负载因子：

负载因子是用来描述 HashMap在扩容前能够存储达到多满的一种程度；

负载因子越大，说明能够填满的元素越多，空间利用率就越高，但是相对应的Hash冲突的概率就会越大；

负载因子越小，说明能填满的元素越少，空间利用率越低，对应Hash越不容易冲突，查找效率更高。

扩容阈值：

当容量 > 扩容阈值时需要进行扩容操作。

扩容是将当前容量扩大为原容量的2倍，从而使哈希表具有2倍的桶数；

扩容阈值 = 容量大小 × 负载因子，默认为 12

3. 构造方法分析

构造方法包括四种，默认构造方法、根据容量进行初始化、根据容量和负载因子进行初始化、根据子Map进行初始化。

/**
     * 指定容量及负载因子构造方法
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //校验初始容量
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity:" +
                                               initialCapacity);
        //当初始容量超过最大容量，初始容量为最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //校验初始负载因子    
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        //设置负载因子
        this.loadFactor = loadFactor;
        //设置扩容阈值
        threshold = initialCapacity;
        //空方法，让其子类重写例如LinkedHashMap
        init();
    }
    
    /**
     * 默认构造方法，采用默认容量16，默认负载因子0.75
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    
    /**
     * 指定容量构造方法，负载因子默认0.75
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 根据子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);
    }

重点：构造方法初始化只是设置了初始容量大小（capicity）、负载因子（Load factor），并没有真正的初始化哈希表。哈希表中数组的初始化，必须等到第一次 put()操作时进行。

4. 插入 put() 方法分析

    /**
     * 源码分析：主要分析： HashMap的put函数
     */

    public V put(K key, V value)
（分析1）// 1. 若 哈希表未初始化（即 table为空) 
        // 则使用 构造函数时设置的阈值(即初始容量) 初始化 数组table  
        if (table == EMPTY_TABLE) { 
        inflateTable(threshold); 
    }  
        // 2. 判断key是否为空值null
（分析2）// 2.1 若key == null，则将该键-值 存放到数组table 中的第1个位置，即table [0]
        // （本质：key = Null时，hash值 = 0，故存放到table[0]中）
        // 该位置永远只有1个value，新传进来的value会覆盖旧的value
        if (key == null)
            return putForNullKey(value);

（分析3） // 2.2 若 key ≠ null，则计算存放数组 table 中的位置（下标、索引）
        // a. 根据键值key计算hash值
        int hash = hash(key);
        // b. 根据hash值 最终获得 key对应存放的数组Table中位置
        int i = indexFor(hash, table.length);

        // 3. 判断该key对应的值是否已存在（通过遍历 以该数组元素为头结点的链表 逐个判断）
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
（分析4）// 3.1 若该key已存在（即 key-value已存在 ），则用 新value 替换 旧value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue; //并返回旧的value
            }
        }

        modCount++;

（分析5）// 3.2 若 该key不存在，则将“key-value”添加到table中
        addEntry(hash, key, value, i);
        return null;
    }

分析一、哈希表为空时进行初始化

    private void inflateTable(int toSize) {  
    
    // 1. 将传入的容量大小转化为：>传入容量大小的最小的2的次幂
    // 即如果传入的是容量大小是19，那么转化后，初始化容量大小为32（即2的5次幂）
    // 初始时传入的是阈值12，大于它的最小的2的整数次幂就是16，即默认容量
    int capacity = roundUpToPowerOf2(toSize);->>分析1   

    // 2. 重新计算阈值 threshold = 容量 * 加载因子  
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  

    // 3. 使用计算后的初始容量（已经是2的次幂） 初始化数组table（作为数组长度）
    // 即 哈希表的容量大小 = 数组大小（长度）
    table = new Entry[capacity]; //用该容量初始化table  

    initHashSeedAsNeeded(capacity);  
}  

    /**
     * 分析1：roundUpToPowerOf2(toSize)
     * 作用：将传入的容量大小转化为：>传入容量大小的最小的2的幂
     * 特别注意：容量大小必须为2的幂，该原因在下面的讲解会详细分析
     */

     private static int roundUpToPowerOf2(int number) {  
   
       //若 容量超过了最大值，初始化容量设置为最大值 ；否则，设置为：>传入容量大小的最小的2的次幂
       return number >= MAXIMUM_CAPACITY  ? 
            MAXIMUM_CAPACITY  : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;  
     }

分析二、当key为null时，将key-value插入到数组的第一个位置 table[0]

      private V putForNullKey(V value) {  
        // 遍历以table[0]为首的链表，寻找是否存在key==null 对应的键值对
        // 1. 若有：则用新value 替换 旧value；同时返回旧的value值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
          if (e.key == null) {   
            V oldValue = e.value;  
            e.value = value;  
            e.recordAccess(this);  
            return oldValue;  
        }  
    }  
    modCount++;  

    // 2 .若无key==null的键，那么调用addEntry（），将空键 & 对应的值封装到Entry中，并放到table[0]中
    addEntry(0, null, value, 0); 
    // 注：
    // a. addEntry（）的第1个参数 = hash值 = 传入0
    // b. 即 说明：当key = null时，也有hash值 = 0，所以HashMap的key 可为null
    // c. 对比HashTable，由于HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
    // d. 此处只需知道是将 key-value 添加到HashMap中即可，关于addEntry（）的源码分析将等到下面再详细说明，
    return null;  

}

分析三、计算键值对实际在哈希表中应该存储的位置

 /**
     * 函数使用原型
     * 主要分为2步：计算hash值、根据hash值再计算得出最后数组位置
     */
        // a. 根据键值key计算hash值 ->> 分析1
        int hash = hash(key);
        // b. 根据hash值 最终获得 key对应存放的数组Table中位置 ->> 分析2
        int i = indexFor(hash, table.length);

   /**
     * 源码分析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次异或运算
     */

     // JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
     static final int hash(int h) {
        h ^= k.hashCode(); 
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
     }

      // JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
      // 1. 取hashCode值： h = key.hashCode() 
     //  2. 高位参与低位的运算：h ^ (h >>> 16)  
      static final int hash(Object key) {
           int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
            // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
            // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
            // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
     }

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

关键点：计算哈希码，通过扰动函数去二次处理哈希码，最后用 h&(length-1) 来计算最终的存储位置。

问题（1）：为什么不采用经过扰动处理的 hashcode 作为最终的存储位置？

因为经过扰动处理的哈希码的范围可能与数组长度不匹配，这样存储就会出现错误。因此要想办法将哈希码的范围约束在数组长度范围内。

一般想到的解决方案就是将 hash值对数组范围取模（求余运算）。但是 JDK7中并没有这么做，而是采用了与运算（&）：h & (length-1)来得到最终的存储下标。

问题（2）：为什么采用哈希码和数组长度-1 与运算来计算数组的下标？

我认为关键有两点：

1. 提高运算效率：

与运算的实质是采用取模运算，即用 Hash值对数组长度取模 h % length，但是由于求余运算的效率很低，因此采用与运算来提高效率。而且由于数组的长度为2的整数次幂，那么 h & (length-1)实质上是用 哈希码与length-1 个1进行与运算，结果就是哈希码对应长度为 length-1 低位的部分。

2. 保证哈希码的均匀性：

因为下标的求解方法是：将hash值和数组长度-1 进行与运算。当长度为2^n时，数组长度减1后得到的所有位都为1，那么与运算的结果就是 hash值，一定程度上减小了碰撞的几率；

而如果不是 2^n，那么数组长度-1 后一定会产生0位，0 和任何数求与都为0，那么无论hash值为何值，对应该位为1时的那个位置的桶会一直空着。

问题（3）：为什么在计算数组下标前，需要对哈希码进行二次处理(扰动处理)？

扰动处理的目的就是为了让哈希码分布的更加均匀，使得存储在hashmap中的数组位置更加均匀，从而避免出现 hash冲突。

问题（4）：为什么数组的长度一定为 2^n ？

因为下标的求解方法是：将hash值和数组长度-1 进行与运算。当长度为2^n时，数组长度减1后得到的所有位都为1，那么与运算的结果就是 hash值，一定程度上减小了碰撞的几率；

而如果不是 2^n，那么数组长度-1 后一定会产生0位，0 和任何数求与都为0，那么无论hash值为何值，对应该位为1时的那个位置的桶会一直空着。

分析四、若对应的key已经存在，就使用新value去替换旧value

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    // 2.1 若该key已存在（即 key-value已存在 ），则用 新value 替换 旧value
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue; //并返回旧的value
    }
}

modCount++;

// 2.2 若 该key不存在，则将“key-value”添加到table中
addEntry(hash, key, value, i);
return null;

方法很简单，就是顺序查找链表，找到对应值进行覆盖即可。

分析五、若对应的key不存在，就将该key-value添加到数组对应位置

   //若 该key对应的值不存在，则将“key-value”添加到table中
        addEntry(hash, key, value, i);

   /**
     * 源码分析：addEntry(hash, key, value, i)
     * 作用：添加键值对（Entry ）到 HashMap中
     */
      void addEntry(int hash, K key, V value, int bucketIndex) {  
          // 参数3 = 插入数组table的索引位置 = 数组下标
          
          // 1. 插入前，先判断容量是否足够
          // 1.1 若不足够，则进行扩容（2倍）、重新计算Hash值、重新计算存储数组下标
          if ((size >= threshold) && (null != table[bucketIndex])) {  
            resize(2 * table.length); // a. 扩容2倍  --> 分析1
            hash = (null != key) ? hash(key) : 0;  // b. 重新计算该Key对应的hash值
            bucketIndex = indexFor(hash, table.length);  // c. 重新计算该Key对应的hash值的存储数组下标位置
    }  

    // 1.2 若容量足够，则创建1个新的数组元素（Entry） 并放入到数组中--> 分析2
    createEntry(hash, key, value, bucketIndex);  
}  

 /**
   * 分析1：resize(2 * table.length)
   * 作用：当容量不足时（容量 > 阈值），则扩容（扩到2倍）
   */ 
   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); 
} 

 /**
   * 分析1.1：transfer(newTable); 
   * 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
   * 过程：按旧链表的正序遍历链表、在新链表的头部依次插入
   */ 
void transfer(Entry[] newTable) {
      // 1. src引用了旧数组
      Entry[] src = table; 

      // 2. 获取新数组的大小 = 获取新容量大小                 
      int newCapacity = newTable.length;

      // 3. 通过遍历 旧数组，将旧数组上的数据（键值对）转移到新数组中
      for (int j = 0; j < src.length; j++) { 
      	  // 3.1 取得旧数组的每个元素  
          Entry<K,V> e = src[j];           
          if (e != null) {
              // 3.2 释放旧数组的对象引用（for循环后，旧数组不再引用任何对象）
              src[j] = null; 

              do { 
                  // 3.3 遍历 以该数组元素为首 的链表
                  // 注：转移链表时，因是单链表，故要保存下1个结点，否则转移后链表会断开
                  Entry<K,V> next = e.next; 
                 // 3.4 重新计算每个元素的存储位置
                 int i = indexFor(e.hash, newCapacity); 
                 // 3.5 将元素放在数组上：采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
                 // 即 扩容后，可能出现逆序：按旧链表的正序遍历链表、在新链表的头部依次插入
                 e.next = newTable[i]; 
                 newTable[i] = e;  
                 // 3.6 访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
                 e = next;             
             } while (e != null);
             // 如此不断循环，直到遍历完数组上的所有数据元素
         }
     }
 }

 /**
   * 分析2：createEntry(hash, key, value, bucketIndex);  
   * 作用： 若容量足够，则创建1个新的数组元素（Entry） 并放入到数组中
   */  
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++;  
}

创建新结点时会检查是否需要进行扩容(阈值12)；如果需要就将容量扩大为原来的2倍，然后将旧数组中的值转移到新数组(会重新计算hash和下标点进行插入)，数据转移过程使用的是头插法(头插法在多线程环境下会造成死锁问题)。

问题（1）：transfer 为什么采用头插而不是尾插？为什么不用二维数组解决冲突？

因为后插入的数据被使用的频次更高，而单链表无法随机访问只能从头开始遍历查询，所以采用头插.突然又想为什么不采用二维数组的形式利用线性探查法来处理冲突，数组末尾插入也是O(1)，可数组其最大缺陷就是在于若不是末尾插入删除效率很低，其次若添加的数据分布均匀那么每个桶上的数组都需要预留内存.

问题（2）：头插法为什么造成死锁问题？

// transfer() 方法重要部分
do {
    Entry<K,V> next = e.next; // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

单线程下：当HashMap 被扩容后，key值为 7和3的节点分别插入到了下标为3的位置。

多线程下：如果线程1执行到第一句被挂起了；此时线程2将整个插入操作执行完了（key:7 放在了 key:3的前面）；此时如果线程1又被调度，执行e.next= newTable[i]又会将7连接在3的尾部，这样就形成了环。那么如果对环进行查找时(找一个不存在的量)就会造成死锁。

5. 扩容操作 resize()分析

  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); 
}

扩容操作首先会复制出一个大小为原数组大小二倍的新数组。然后需要遍历旧数组中的每个值，采用和put()方法相同的方式，重新计算每个数据在新数组中的存储位置h & (length-1)，然后将旧数组的值转移到新数组中。对于旧数组的链表结点，在新数组中采用头插法进行插入。最后重新计算扩容阈值，重新计算需要插入数据对应的hash值，然后进行插入。

JDK7 中为了防止 hash 碰撞引起的拒绝服务攻击，在计算 hash 的过程中引入了随机种子。以增强 hash 的随机性，使得键值对均匀分布在桶数组中。在扩容过程中，相关方法会根据容量判断是否需要生成新的随机种子，并重新计算所有节点的hash。

6. 获取数据 get() 方法分析

get() 方法原理和put() 方法类似，都是根据 key计算hash值，然后扰乱处理，结合数组长度计算最终的存放位置。然后到该存放位置去查找，如果找到了就返回，否则就没有找到。

 /**
   * 分析1：getForNullKey()
   * 作用：当key == null时，则到 以哈希表数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
   */ 
private V getForNullKey() {  

    if (size == 0) {  
        return null;  
    }  

    // 遍历以table[0]为头结点的链表，寻找 key==null 对应的值
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {  

        // 从table[0]中取key==null的value值 
        if (e.key == null)  
            return e.value; 
    }  
    return null;  
}  
 
 /**
   * 分析2：getEntry(key)
   * 作用：当key ≠ null时，去获得对应值
   */  
final Entry<K,V> getEntry(Object key) {  

    if (size == 0) {  
        return null;  
    }  

    // 1. 根据key值，通过hash（）计算出对应的hash值
    int hash = (key == null) ? 0 : hash(key);  

    // 2. 根据hash值计算出对应的数组下标
    // 3. 遍历 以该数组下标的数组元素为头结点的链表所有节点，寻找该key对应的值
    for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  

        Object k;  
        // 若 hash值 & key 相等，则证明该Entry = 我们要的键值对
        // 通过equals（）判断key是否相等
        if (e.hash == hash &&  
            ((k = e.key) == key || (key != null && key.equals(k))))  
            return e;  
    }  
    return null;  
}

7. 总结

HashMap的关键点主要包括：数据结构+重要参数+重点方法

数据结构和核心参数

添加、查询数据操作

二、JDK 1.8 的HashMap

JDK8 中的 hashMap相较于 JDK7做出了很大的改变，主要包括数据结构、插入查找方法、扩容操作这三个方面。

1. 数据结构

JDK8 采用的是数组+链表+红黑树来实现的。

为什么要引入红黑树？

因为如果像 JDK7 那样，采用链地址法解决哈希冲突，那么当链表长度过长时查找是非常耗时的。因此引入红黑树的结构来加快查找过程，并且根据链表的长度来控制链表和红黑树之间的转化，这样一方面提高了查找的效率（时间复杂度从 O(n) 减少为了 O(logn)）；另一方面又不至于浪费很多资源空间。

如何转化？

没有冲突时，完全采用数组存储；
当出现冲突时，优先使用链表进行存储，如果此时链表长度 <8 ，会一直使用链表存储；
当出现冲突，并且链表长度 >=8 时，存储结构转化为红黑树；当链表长度小于6时又会变回链表存储。

红黑树的特点？

红黑树本质上是一棵二叉搜索树，因此查找的时间复杂度为 O(logn)，效率很高。
红黑树每个结点不是红色就是黑色，而且父子结点必须是不同的颜色。根节点和叶子节点都是黑色。
从1个结点到该子孙结点的所有路径上包含相同数量的黑色结点，因此红黑树是相对接近平横二叉树。

2. 重要结构

主要看一下 Node结点和 TreeNode结点

Node结点：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //哈希值
        final K key;       //key值
        V value;           //value值
        Node<K,V> next;    //链表下一个结点

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

Node结点和 JDK7 中的结点结构完全类似。

TreeNode 结点：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // 父结点
    TreeNode<K,V> left;    // 左子树
    TreeNode<K,V> right;   // 右子树
    TreeNode<K,V> prev;    // 前一个结点
    boolean red;           // 结点颜色
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

3. 重要变量

由于引入了红黑树，因此也引入了一些与红黑树相关的临界变量。

（1）桶的树化阈值，即链表转化为红黑树的阈值，当链表长度大于该值时，将链表转化为红黑树

static final int TREEIFY_THRESHOLD = 8;

（2）桶的还原阈值，当原有红黑树中的结点数小于6时，转换回链表

static final int UNTREEIFY_THRESHOLD = 6;

（3）最小树化容量阈值，当哈希表中的容量大于该值时，才允许进行树化。为树化阈值的4倍

static final int MIN_TREEIFY_CAPACITY = 64;

4. 插入 put() 方法分析

1
2
3

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

4.1 哈希的计算方式

//JDK8 中的 hash计算方法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//JDK7 中的 hash计算方法
static final int hash(int h) {
    h ^= k.hashCode(); 
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
 }

JDK7 中总共采用了9次扰动处理，包括4次位运算、5次异或运算；

JDK8 中总共采用了2次扰动处理，包括1次位运算、1次异或运算；

问题（1）：这里计算 hash值为什么采用 key.hashcode() ^ h>>>16 这种方式？

因为如果直接使用 hashcode 去进行 index = key.hashcode() & (n-1)运算来计算最终的存储位置，那么相当于 hashcode 的高位都没有用到 (因为n为2的整数次幂，减一后低位都1，高位都为0，0和任何数与运算都为0)；简单的来说，直接使用 hashcode 去计算最终位置会使得取余的计算结果只对低位有效，当hash 值高位变化时低位不变，取余结果仍然一样，容易发生哈希冲突。

因为哈希值为32位，那么如果我将整个hash 值右移16位，得到的结果就是哈希值的高16位；再将高16位和低16位进行异或运算，那就相当于用到了整个 hash部分。无论此时是 hash的高位还是低位发生改变，最终的 hash求余结果一定会发生改变，巧妙地避免了哈希冲突。

4.2 putVal() 方法分析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //tab:旧的数组   i:根据hash计算后的存储位置  p:存储位置对应的结点   n:数组长度
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 如果数组未初始化，先进行数组初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
  
    // 如果对应存储位置没有值，生成一个结点插入
 // i = (n-1) & hash  操作类似于 JDK7 中的 indexFor()函数，都是根据hash值和数组长度计算最终位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
  
    // 否则存在hash冲突
    else {
        Node<K,V> e; K k;
        
        // 如果对应位置的key相同，用新值覆盖旧值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 否则判断当前的数据结构，如果是红黑树的结构
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 否则是链表存储的结构,那么需要遍历的同时记录节点个数，如果大于了8就要转化为红黑树的结构
        else {
            // binCount 就是用来记录结点个数	
            for (int binCount = 0; ; ++binCount) {
                
                // 遍历到了链表末尾，说明没有找到，就在末尾插入新结点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 判断结点个数是否大于8
                    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;
                // 更新p指向下一个结点，继续遍历
                p = e;
            }
        }
        
        // 对于i情况的后续操作，发现key已存在，就用新value覆盖旧value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    
    // 检查是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

JDK8 与 JDK7 的插入操作有了很大的不同：

第一步都是判断数组是否被初始化，没有初始化就进行初始化（容量大小为大于输入数值的最小的2的整数次幂）；
第二步就是根据 key 计算应该存放的位置，这里的计算方法和JDK7 也不相同，主要体现在扰动函数上，只进行了2次扰动处理；
如果该位置没有值就生成一个新的结点插入；否则有值但是 key可能相同，这样的话进行覆盖就可以了。
但是如果 key不相同却有值，说明存在hash冲突（不同的key经过计算得到相同的存储位置）；就需要根据此时的存储数据结构进行判断，如果是红黑树就采用红黑树的方式插入然后调整；如果是链表就查找链表中是否已经存在，存在就覆盖，不存在就在链表尾插入一个新的。

但是注意链表超过一定长度是需要转化为红黑树进行存储的，因此遍历链表的过程中还需要记录链表的位置，源码中使用binCount进行记录。记录完毕后判断是否需要变换结构。
最后判断是否需要进行扩容处理，如果当前键值对的数量大于扩容阈值，就采用 resize() 方法进行扩容。扩容操作接下来分析。

5. 扩容操作 resize() 分析

// 该方法会在数组初始化和扩容时被调用 
final Node<K,V>[] resize() {
      //oldTab：旧表    oldThr：旧的阈值    oldCap：旧的容量  
    
      Node<K,V>[] oldTab = table;
      int oldCap = (oldTab == null) ? 0 : oldTab.length;
      int oldThr = threshold;
      int newCap, newThr = 0;
    
      // 数组已经进行了初始化
      if (oldCap > 0) {
          // 如果旧容量大于最大容量，则不能进行扩容处理
          if (oldCap >= MAXIMUM_CAPACITY) {
              threshold = Integer.MAX_VALUE;
              return oldTab;
          }
          // 否则容量扩大为之前的2倍
          else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)
              newThr = oldThr << 1; // double threshold
      }
    
      // 初始化数组
      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);
      }
    
      // 新的扩容阈值为空，就进行重新计算并初始化
      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) {
          for (int j = 0; j < oldCap; ++j) {
              Node<K,V> e;
              if ((e = oldTab[j]) != null) {
                  oldTab[j] = null;
                
                  // 原数组中单个结点重新计算hash值存储
                  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 { // preserve order
                      Node<K,V> loHead = null, loTail = null;
                      Node<K,V> hiHead = null, hiTail = null;
                      Node<K,V> next;
                      do {
                          next = e.next;
                          
                          // 原hash值的最高位的上一位如果为0，则采用原索引
                          if ((e.hash & oldCap) == 0) {
                              //采用尾插法
                              if (loTail == null)
                                  loHead = e;
                              else
                                  loTail.next = e;
                              loTail = e;
                          }
                          // 否则为1，采用新索引
                          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;
                          newTab[j + oldCap] = hiHead;
                      }
                  }
              }
          }
      }
      return newTab;
  }

重点在重新计算数组中元素在新数组中的位置：

// 原hash值的最高位的上一位如果为0，则采用原索引
if ((e.hash & oldCap) == 0) {
  if (loTail == null)
    loHead = e;
  else
    loTail.next = e;
  loTail = e;
}
// 否则为1，采用新索引
else {
  if (hiTail == null)
    hiHead = e;
  else
    hiTail.next = e;
  hiTail = e;
}

根据代码，这里只存在两种情况，要么仍然是原位置，要么是原位置+原数组的长度作为新位置。

因为扩容后容量为原来的2倍，相当于把容量的2进制值往左移动1位。在计算存储位置 i = (n-1) & hash时，n-1 的二进制比原来的二进制高位多了一个1，那么原hash 值与这个1相与结果就可能是1或者0了。如果是0，则新计算的存储位置和原存储位置相同；如果是1，新存储位置 = 原长度+原来的存储位置。

6. 获取数据 get() 方法分析

获取数据类似于插入操作，包括计算存储位置，判断存储的数据结构然后去对应位置查找。

7. 总结

数据结构

添加、查询数据流程

扩容机制

三、JDK7 和 JDK8 HashMap的区别

3.1 数据结构不同

JDK7 的数据结构为数组+链表，当发生哈希冲突时采用链地址法解决冲突；缺点是当冲突过多导致链表过长时，对链表中数据的查询效率非常低；

JDK8 的数据结构为数组+链表+红黑树，当发生哈希冲突时优先采用链表解决冲突，但是如果链表的长度大于8，就要将结构转换为红黑树，红黑树的查找时间复杂度为 O(logn) 比链表的 O(n) 在结点很多的情况下要好很多。如果链表长度低于6时，就没必要使用红黑树了，此时将红黑树转换回链表结构。

3.2 插入数据、获取数据

JDK7 的插入数据首先会检查数组是否初始化，初始化完毕后判断key是否为空，为空直接插在数组第一个位置；然后根据 key对应的哈希值进行扰动处理，这里的扰动处理包括4次位运算和5次异或运算；紧接着根据 index = h & (length-1) 计算出最终的插入位置；如果该位置没有冲突，直接插入；否则需要插入到单链表中，这就涉及到了扩容操作，在扩容之后又重新计算需要插入的数据的位置进行插入。是先扩容后计算插入位置进行插入

JDK8 的插入数据首先也会检查数据是否初始化，初始化完毕后紧接着计算哈希值，哈希值的计算与JDK7不同，是通过采用 hashcode & (hashcode>>>16)计算得到hash值，然后根据 index=h&(length-1)得出最终插入位置。没有冲突直接插入，如果有冲突，判断当前数据结构的类型进行冲突解决，对于链表而言需要特别注意当结点数大于8时需要转化为红黑树的结构。最后插入完毕后判断是否需要进行扩容操作。是先插入后判断是否需要扩容