集合 - HashMap

JDK 评论

前言

HashMap 是基于哈希表实现的，外层是一个数组，数组中的每个元素封装了一个 key-value 及其他元数据信息，这些元数据信息是为了更好的管理数组中某个位置中的元素，如使用单链表或红黑树组织元素，元数据信息就是对应的指针等信息。对 HashMap 进行增、删、改、查都需要经历两个必须的步骤，先计算 key 的 hash 值，接着根据 hash 值计算出当前键值对位于数组的哪个位置。HashMap 虽然基础，但是其中的思想值得学习。本篇文章将分别对 JDK 7、8 版本下的 HashMap 进行介绍。

JDK 7 HashMap

JDK 1.7 的 HashMap 结构如上图所示。内部存储结构是数组和链表的结合，在实例化 HashMap 时会创建一个长度为 Capacity 的 Entry 数组，这个长度被称为容量，数组中可以存放元素的位置我们称为桶（bucket），每个 bucket 都有自己的索引下标，系统可以根据索引下标快速查找 bucket 中的元素。每个 bucket 中存储一个元素，即一个 Entry 对象，但每一个 Entry 对象都可以通过指针链接下一个元素，因此，在一个 bucket 中就有可能生成一个 Entry 链。

关键属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//默认初始化化容量, 16  
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

//最大容量，即2的30次方  
static final int MAXIMUM_CAPACITY = 1 << 30;  

// 默认负载因子  
static final float DEFAULT_LOAD_FACTOR = 0.75f;  

// HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态  
static final Entry<?,?>[] EMPTY_TABLE = {};  

// 空的存储实体  
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  

//实际存储的 key-value 键值对的个数。注意和容量的区分。
transient int size;

// 扩容阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold 可以为下列值：
// 1 等于 capacity * loadFactory 「默认构造方法」
// 2 2 倍增大「正常扩容过程」
// 3 Integer.MAX_VALUE「数组容量达到最大值」
// HashMap在进行扩容时需要参考threshold
int threshold;

//负载因子，代表了table的填充度有多少，默认是0.75。
// 为什么是 0.75 ，是根据 泊松统计定义的
final float loadFactor;

//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;

//默认的 threshold 值  
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

注意，HashMap 数组的每一个元素不止是一个 Entry 对象，也是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到冲突的数组位置时，只需要插入到对应的链表中即可。

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 通过初始容量和负载因子构造HashMap  
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 初始值为初始容量
    threshold = initialCapacity;  
    //init方法在HashMap中没有实际实现
    init();
}  

// 通过扩容阈值构造 HashMap,容量是默认值 16  
public HashMap(int initialCapacity) {  
    this(initialCapacity, DEFAULT_LOAD_FACTOR);  
}  

// 负载因子取0.75，容量取16，构造HashMap  
public HashMap() {  
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);  
}  

// 通过其他 Map 来初始化HashMap,容量通过其他Map的size来计算，装载因子取0.75  
public HashMap(Map<? extends K, ? extends V> m) {  
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  
    //初始化HashMap底层的数组结构  
    inflateTable(threshold);
    //添加m中的元素  
    putAllForCreate(m);
}

Put方法原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public V put(K key, V value) {
    // 当插入第一个元素的时候，根据情况先初始化数组大小
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果 key 为 null，最终会将这个 entry 放到 table[0] 中
    if (key == null)
        return putForNullKey(value);

    // 1. 求 key 的 hash 值
    // 对 key 的 hashcode 进一步计算，确保散列均匀
    int hash = hash(key);

    // 2. 找到对应的数组下标
    // i = h & (table.length-1)，效果同取模运算
    int i = indexFor(hash, table.length);

    // 3. 遍历一下对应下标处的链表，看是否有重复的 key 已经存在， 如果有，直接覆盖，put 方法返回旧值就结束了
    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;
        }
    }

    // 保证并发访问时，若HashMap内部结构发生变化，快速响应失败
    modCount++;

    // 4. 不存在重复的 key，新增一个 entry 并添加到链表中
    addEntry(hash, key, value, i);
    return null;
}

通过上述方法可知，确定一个元素的存储位置需要以下步骤：

  1. 通过元素的 key 获取对应的 hash 值，其中使用到了 key 的 hashcode 值。
  2. 通过 hash 值和数组 length 信息计算得到存储的下标索引位置。
  3. 知道了对应的下标索引位置后就可以取出对应的元素了，如果该位置的元素有多个，那么需要遍历获取。

初始化数组

1
2
3
4
5
6
7
8
9
10
11
private void inflateTable(int toSize) {
    // 1 保证数组大小一定是 2 的 n 次方，采用向上取整的策略。如 new HashMap(20)，那么处理成初始数组大小是 32
    int capacity = roundUpToPowerOf2(toSize);
   
    // 2 计算扩容阈值：capacity * loadFactor
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    
    // 3 创建数组
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity); //ignore
}

保证数组大小一定是 2^n 是为了实现一个尽量均匀分布的 Hash 函数。HashMap 采用类似如下的公式计算元素对应的数组位置：

1
2
3
// HashCode 并不是 key 的直接 hashcode 值，而是对其处理后的值
// length 是 HashMap 的长度
index = HashCode(key) & (lenght -1)

可以看到，HashMap 的作者采用了位运算的方式代替取模运算，只要数组大小是 2^n 就可以保证 length - 1 的值的二进制位全是 1，这种情况下，index 的结果等同于 HashCode 后几位的值。只要输入的 HashCode 本身分布均匀，Hash算法的结果就是均匀的。

添加节点到链表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 1 如果当前 HashMap 大小已经达到了阈值，并且新键值对要插入的数组位置已经有元素了，那么要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        
        // 1.1 扩容，后面会介绍一下
        resize(2 * table.length);
        // 1.2 扩容以后，重新计算 hash 值
        hash = (null != key) ? hash(key) : 0;
        // 1.3 重新计算扩容后的新的下标
        bucketIndex = indexFor(hash, table.length);
    }

    // 2 如果需要扩容，是先扩容再插入元素
    createEntry(hash, key, value, bucketIndex);
}

// 将新的键值对放到链表的表头，然后 size++
void createEntry(int hash, K key, V value, int bucketIndex) {
    // 获取待插入位置元素
    Entry<K,V> e = table[bucketIndex];

    // 这里执行链接操作，使得新插入的元素指向原有元素。这保证了新插入的元素总是在链表的头  
    // e 赋值给 Entry 中的 next
    table[bucketIndex] = new Entry<>(hash, key, value, e);

    // 元素个数+1
    size++;
}

在添加元素的过程中需要先判断是否需要扩容，扩容的标准是当前 HashMap 元素大小达到扩展阈值且要插入的位置已经有元素了。需要扩容的话先进行扩容，然后再将这个新的键值对插入到扩容后的数组的相应位置处的链表的表头。

注意，新的 Entry 节点插入链表时使用的是 头插法，作者认为后插入的 Entry 被查找的可能性更大。

Get方法原理

相比较 put 过程，get 过程是非常简单的，主要过程如下：

  1. 根据 key 计算 hash 值
  2. 计算相应的数组下标： index = hash & (length - 1)
  3. 遍历该数组位置处的链表，直到找到相同的 key 或为 null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public V get(Object key) {
    // key 为 null 的话，会被放到 table[0]，所以只要遍历下 table[0] 处的链表就可以了
    if (key == null)
        return getForNullKey();
    
    // 走查找流程
    Entry<K,V> entry = getEntry(key);

    // 返回对应的值
    return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    // 1 通过 hash 函数计算 key 的 hash 值
    int hash = (key == null) ? 0 : hash(key);

    // 2 确定数组下标，然后从头开始遍历链表，直到找到为止
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }

    // 3 在对应的数组位置没有找到
    return null;
}

扩容

HashMap 的容量是有限的，当经过多次元素插入会使得 HashMap 达到一定饱和度时，key 映射位置发生冲突的几率会逐渐提高，这时 HashMap 需要进行扩容。在 put 的过程，如果当前 HashMap 元素个数 size 已经达到了阈值且要插入的数组位置上已经有元素了，那么就会触发扩容，扩容后数组大小是原来的 2 倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
void resize(int newCapacity) {
    // 1 保存旧数组 
    Entry[] oldTable = table;

    // 2 保存旧容量
    int oldCapacity = oldTable.length;

    // 3 如果旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，退出
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 4 扩容，创建一个新的空数组，长度是原数组的 2 倍
    Entry[] newTable = new Entry[newCapacity];
    
    // 5 将原来数组中的键值对迁移到新的更大的数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));

    // 6 扩容完毕后，用新的数组指向 table
    table = newTable;

    // 7 计算新的扩容阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

/*
 * 作用：将旧数组上的数据（键值对）转移到新 table 中，从而完成扩容。
 */
 void transfer(Entry[] newTable, boolean rehash) {  
        // 容量
        int newCapacity = newTable.length;

        // 两层循环
        // 外层 for 循环 用于遍历数组
        // 内层 while 循环 用于遍历数组中对应位置的链表
        for (Entry<K,V> e : table) { 
            while(null != e) { 

                Entry<K,V> next = e.next;  
                //如果是重新 Hash，则需要重新计算hash值  
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }  

                // 计算元素 e 在新数组中的位置
                int i = indexFor(e.hash, newCapacity);

                // 头插入，newTable[i]的值总是最新插入的值
                e.next = newTable[i];
                newTable[i] = e; 

                // 继续下一个元素  
                e = next;
            }  
        }  
    }

以上扩容代码相对还是比较直观的，整个扩容分为两个步骤：扩容和rehash。

我们知道，在多线程环境中 HashMap 是不安全的，其中一个很大的问题就是数组中某个位置的链表可能成环，这个问题就是发生在 rehash 过程。下面我们对该现象详细分析。

链表成环

假设一个 HashMap 已经到了扩容的临界点，此时刚好有两个线程 A 和 B 在同一时刻对 HashMap 进行 put 操作，那么两个线程各自进行扩容：

接着两个线程都来到 transfer 方法中，其中线程 B 遍历到 Entry3 对象，刚执行完以下代码时就被挂起了。此时线程 B 的状态数据，e = Entry3，next = Entry2。

1
Entry<K,V> next = e.next;

而在线程 B 被挂起期间，线程 A 成功完成了 rehash 过程，结果如下（图中的 e 和 next 分别代表线程 B 持有的两个 Entry 引用）。

第一轮

当线程 A 完成 rehash 后线程 B 恢复，继续执行属于它的 rehash 过程。接着执行以下代码，确认 e 对应的元素应该位于新数组哪个索引位置，毫无疑问地 i = 3，因为刚才线程 A 对 Entry3 的映射结果就是 3 。

1
2
// 计算元素 e 在新数组中的位置
int i = indexFor(e.hash, newCapacity);

接续执行后续的代码，如下：

1
2
3
4
5
6
// 头插入，newTable[i]的值总是最新插入的值
e.next = newTable[i];
newTable[i] = e; 

//继续下一个元素  
e = next;

对应的情况如下图所示：

至此，第一轮执行完毕，此时线程 B 将 Entry3 rehash 到了自己的新数组中，且它的 e 和 next 指针同时指向 Entry2 。注意，线程 B 操作的 Entry 节点还是原来的节点，虽然原来的 Entry 节点被线程 A 进行了 rehash ，但是引用指向没有变。

第二轮

接着执行新的一轮，此时又执行到以下代码：

1
Entry<K,V> next = e.next;

此时，e = Entry2，next = Entry3 ，整体情况如下图所示：

接着继续执行以下三行代码，采用头插法把 Entry2 插入到线程 B 的数组的头节点：

1
2
3
4
5
6
 // 头插入，newTable[i]的值总是最新插入的值
 e.next = newTable[i];
 newTable[i] = e; 

 //继续下一个元素  
e = next;

整体情况如下图所示：

至此，第二轮执行完毕，此时线程 B 将 Entry2 rehash 到了自己的新数组中，且它的 e 和 next 指针同时指向 Entry3 。

第三轮

接着执行新的一轮，此时又执行到以下代码：

1
Entry<K,V> next = e.next;

此时，e = Entry3,next = null，接着继续执行以下代码，做头插法：

1
2
// 头插入，newTable[i]的值总是最新插入的值
e.next = newTable[i];

此时，链表出现了环形。相关数据关系如下：

1
2
3
4
newTable[i] = Entry2
e = Entry3
Entry2.next = Entry3
Entry3.next = Entry2

整体情况如下图所示：

最后，执行以下代码将新元素设为头，也就是将 Entry3 设置为头。

1
newTable[i] = e;

至此，第三轮执行完毕，此时线程 B 将 Entry3 和 Entry2 互相使用 next 指针链接起来形成了一个环。由于 next = null ，因此在下一轮开始判断的时候不满足条件，结束数组当前位置数据的 rehash 。

此时，坑已经埋好了，就等调用 get 查找一个不存在的 key ，而这个 key 的 hash 结果映射到桶的位置恰好等于 3 时，由于位置 3 带有环形链表，因此程序会进入死循环。

值得说明的是，在一定程度上链表头插法会颠倒原来一个位置上链表的顺序。在并发的时候原来的顺序被线程 A 颠倒了，而被挂起的线程 B 恢复后拿到挂起前的节点和顺序继续完成 rehash，这个过程会将线程 A rehash 后的链表顺序重新排列，最终形成了环。JDK 1.8 之后就不再采用头插法了，而是直接插入链表尾部，因此不会形成环形链表形成死循环，但是在多线程的情况下仍然是不安全的，在put数据时如果出现两个线程同时操作，可能会发生数据覆盖，引发线程不安全。

JDK 8 HashMap

JDK 1.8 的 HashMap 结构大体上如上图所示，具体细节并没有展示，比如红黑树中的链接指针没有全部显示。JDK 1.7 的 HashMap 采用 数组+链表 的方式在大部分情况下都能有不错的性能，但在极端的情况下可能会退化成一个链表，造成 HashMap 性能急剧下降。因此在 JDK 1.8 中采用了 数组+链表+红黑树的方式来组织数据，新增红黑树是为了解决哈希碰撞，避免过长链表效率低的问题。

关键属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;

    /**
     * 默认容量大小 16，大小必须是 2^N
     * 也称为数组长度或桶的个数。
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * 最大容量，当两个构造函数中任何一个带参数的函数隐式指定较大的值时使用。一定是2 <= 1<<30的幂。
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认负载因子 在构造函数中未指定时使用的负载因子
     * 为什么是 0.75 ，是根据 泊松统计定义的
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 桶的树化阈值： 使用红黑树时的一个条件：元素个数的阈值。
     * 在存储数据时，当链表长度 >= 8 && 数组容量 >= 64，则将链表转换成红黑树。
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 桶的链表还原阈值：红黑树转链表阈值。
     * 当在扩容时，在重新计算存储位置后，当原有的红黑树内数量 <= 6时，则将 红黑树转换成链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 最小树形化容量阈值：使用红黑树时最小的数组容量。当 HashMap 中的容量 >= 该值时，才可能树化即将链表转成红黑树。
     * 这样是为了减少形成很满的桶，因为桶的数量很少时，容易造成桶满
     */
    static final int MIN_TREEIFY_CAPACITY = 64;


    /* ---------------- Fields -------------- */

    /**
     * 存储数据的 Node 数组，长度是 2 的幂。
     */
    transient Node<K, V>[] table;

    /**
     * table 容纳的元素个数
     */
    transient int size;

    /**
     * HashMap 被改变的次数
     */
    transient int modCount;


    // 扩容的阈值（当前 HashMap 所能容纳键值对数量的最大值，超过该值则需要扩容），一般等于 capacity * loadFactory
    int threshold;

    // 负载因子，默认为 0.75
    final float loadFactor;
}

TREEIFY_THRESHOLD 和 UNTREEIFY_THRESHOLD 两个参数是控制链表和红黑树相互转换的阈值，它们中间有个差值 7 可以有效防止链表和树频繁转换。其它属性和 JDK 1.7 版本中的类似。值得说明的是桶数组 table 被申明为 transient ，也就是不会被默认的序列化机制序列化。但 HashMap 通过实现 readObject/writeObject 两个方法自定义了序列化的内容，也就是将键值对序列化，后续可以根据键值对数据重建 HashMap。

这里不直接将 table 进行序列化是为了避免以下问题：

  1. table 多数情况下是无法被存满的，序列化未使用的部分，浪费空间
  2. 同一个键值对在不同 JVM 下所处的桶位置可能是不同的，这种情况下反序列化 table 可能会发生错误。

结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
   * HashMap 中元素项，用于链表的情况。
   *
   * @param <K>
   * @param <V>
   */
  static class Node<K, V> implements Map.Entry<K, V> {
      // key 对应的 hash 值
      final int hash;
      // key
      final K key;
      // value
      V value;
      // 下一个元素的指针
      Node<K, V> next;
  }

  /**
   * HashMap 中元素项，用于红黑树的情况。间接继承了 Node 
   */
  static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
      // 父节点
      TreeNode<K, V> parent;  // red-black tree links
      // 左子节点
      TreeNode<K, V> left;
      // 右子节点
      TreeNode<K, V> right;
      // 链表进行树化时，会先构造成 TreeNode 的双向链表，这个是节点的前驱指针，Node 中的 next 作为后继指针
      TreeNode<K, V> prev;    // needed to unlink next upon deletion
      // 节点的颜色
      boolean red;
  }

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
    * 指定容量大小和负载因子的构造函数，是最基础的构造函数
    * @param initialCapacity
    * @param loadFactor
    */
   public HashMap(int initialCapacity, float loadFactor) {
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: " +
                   initialCapacity);
       // HashMap的最大容量只能是MAXIMUM_CAPACITY
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: " +
                   loadFactor);

       // 设置负载因子
       this.loadFactor = loadFactor;

       // 取大于 cap 且最近的2的整数次幂的数作为扩容的阈值
       this.threshold = tableSizeFor(initialCapacity);
   }

   // 指定容量大小
   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }

   // 使用默认属性
   public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
   }


   // 使用给定的数据源初始化 HashMap
   public HashMap(Map<? extends K, ? extends V> m) {
       this.loadFactor = DEFAULT_LOAD_FACTOR;
       putMapEntries(m, false);
   }

注意：在集合初始化时，推荐指定集合初始值大小，在一定程度上可以减少扩容带来的开销。

确定桶位置

1
tab[(n -1) & hash]

计算方式和 JDK 1.7 HashMap 是一致的。HashMap 的数组长度 length 总是 2^n ，因此 (n - 1) & hash 等价于对 length 取余，由于取余运算效率没有位运算高，这里做了一个优化。此外，length - 1 正好相当于一个低位掩码，& 操作的结果就是 hash 值的高位全部归零，只保留对应的低位值，即定位数组桶的位置取决于 hash 值的低几位。

hash方法

1
2
3
4
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

上述方法计算 hash 值没有直接使用 key 的 hashCode 方法生成的 hash 值，而是通过位运算重新计算出一个 hash 值。在 Java 中 hashCode 方法产生的 hash 是 int 类型，也就是 32 位。由于确定数组的桶位置是通过 (n - 1) & hash 计算得到的，这就要求计算 hash 值的算法要具有随机性。因此，在计算 key 的 hash 值时用其自身 hashCode 与其低 16 位做 ^ 操作，即让 hashCode 的高 16 位异或低 16 位，这让高位也参与到 hash 值的计算中来「n-1 确定了只会与 hash 的低位运算」，进而降低了哈希冲突的风险又不会带来太大的性能问题。此外，重新计算 hash 的另一个好处是可以增加 hash 的复杂度。当我们覆写 hashCode 方法时，可能会写出分布性不佳的 hashCode 方法，进而导致 hash 的冲突率比较高。通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性。计算过程如下：

Get方法原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
   * 根据 key 获取对应 value
   *
   * @param key
   * @return
   */
  public V get(Object key) {
      Node<K, V> e;
      // 根据 key 的 hashCode 计算得到 hash 值，然后利用 pos = （n-1）& hash 计算其在数组中的位置
      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;

      // 1 如果 key 对应的数组位置有元素
      if ((tab = table) != null && (n = tab.length) > 0 &&
              (first = tab[(n - 1) & hash]) != null) {

          // 1.1 先在头节点中找
          if (first.hash == hash && // always check first node
                  ((k = first.key) == key || (key != null && key.equals(k))))
              return first;

          // 1.2 头节点不是目标元素
          if ((e = first.next) != null) {

              // 1.2.1 如果是红黑树，则去红黑树中找
              if (first instanceof TreeNode)
                  return ((TreeNode<K, V>) first).getTreeNode(hash, key);

              // 1.2.2 如果不是红黑树，则说明是链表，那么就从链中找
              do {
                  if (e.hash == hash &&
                          ((k = e.key) == key || (key != null && key.equals(k))))
                      return e;
              } while ((e = e.next) != null);
          }
      }
      return null;
  }

Get方法逻辑还是比较简单的。先定位键所在的桶的位置，然后再对链表或红黑树进行查找。

Put方法原理

Put方法先定位要插入的键值对属于哪个桶，定位到桶后，再判断桶是否为空。如果为空，则将键值对存入即可。如果不为空，则需将键值对插入到链表最后一个位置或红黑树中，或者更新键值对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
   * 添加键值对
   *
   * @param key
   * @param value
   * @return
   */
  public V put(K key, V value) {
      // 通过 hash(key) 计算 key 的 hash 值
      return putVal(hash(key), key, value, false, true);
  }

  /**
   * 尾插法
   *
   * @param hash         key 的 hash
   * @param key          the key
   * @param value        the value to put
   * @param onlyIfAbsent 如果为 true ，那么只有在不存在该 key 时才会进行 put 操作，默认是 false 即覆盖
   * @param evict        if false, the table is in creation mode.
   * @return previous value, or null if none
   */
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
      Node<K, V>[] tab;
      Node<K, V> p;
      int n, i;

      // 初始化数组 table，table 被延迟到插入新数据时再进行初始化
      if ((tab = table) == null || (n = tab.length) == 0)
          n = (tab = resize()).length;

      // key 映射的数组桶位置为空，则创建一个 Node 填充到对应位置即可
      if ((p = tab[i = (n - 1) & hash]) == null)
          tab[i] = newNode(hash, key, value, null);

          // key 映射的数组桶位置有数据
      else {
          Node<K, V> e;
          K k;

 
          // 判断是否 key 冲突
          // 在该位置的第一个数据的 key 和要插入的 key 相同
          if (p.hash == hash &&
                  ((k = p.key) == key || (key != null && key.equals(k))))
              // 保存到 e 中用于后续修改 value 值
              e = p;

              // 判断当前桶是否是树结构，如果是则在红黑树中插入节点
              // a. 往红黑树中插入节点  b. 调整红黑树
          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);

                      // 如果链表长度大于或等于树化阈值，则进行树化操作，也就是将链表转换为红黑树
                      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 因为第一个元素没有加入到binCount中，所以这里-1
                          treeifyBin(tab, hash);
                      break;
                  }

                  // 如果在链表中找到了相同的 key
                  if (e.hash == hash &&
                          ((k = e.key) == key || (key != null && key.equals(k))))
                      // 此时 break，那么 e 为链表中与要插入的新值的 key 相同的 node
                      break;

                  // 用于遍历下一个
                  p = e;
              }
          }

          // 判断要插入的键值对是否存在 HashMap 中
          // e != null 说明存在旧值的 key 与要插入的 key 相同
          if (e != null) { // existing mapping for key
              V oldValue = e.value;

              // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
              // key 相同进行值覆盖
              if (!onlyIfAbsent || oldValue == null)
                  e.value = value;
              afterNodeAccess(e);

              // 返回旧值
              return oldValue;
          }
      }

      // 增加修改次数
      ++modCount;

      // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
      if (++size > threshold)
          resize();

      afterNodeInsertion(evict);
      return null;
  }

下面对 Put逻辑进行小结：

  1. 当桶数组 table 为空时，通过扩容的方式（扩容方法中）初始化 table；
  2. 查找要插入的键值对是否已经存在，存在的话根据条件判断是否用新值替换旧值
  3. 如果不存在，则将键值对插入红黑树或链表中，其中插入到链表的过程还会根据链表的长度决定是否将链表转为红黑树。具体转换会在下文进行介绍。
  4. 判断键值对数量是否大于阈值，大于的话则进行扩容操作。即新增后判扩容。

注意：下面我们回答前文说的数据覆盖的线程安全问题。

HashMap 在添加元素时，也就是上述函数中，如果没有 hash 碰撞即key 映射的数组桶位置为空，这时就会直接插入元素。如果这个过程出现线程并发执行，并且刚好两个数据的 hash 值一样，那么就会出现并发问题。如，线程 A 在创建节点插入桶之前挂起了，此刻线程 B 正常执行，完成了节点的创建并插入到了桶中，然后线程 A 获取 CPU 时间片，此时线程 A 不会再判断是否 hash 冲突，会直接把线程 B 插入的数据给覆盖。涉及的代码如下：

1
2
3
// key 映射的数组桶位置为空，则创建一个 Node 填充到对应位置即可
 if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

扩容机制

在 HashMap 中，桶数组的长度均是 2^n ，当键值对数量超过扩容阈值时，需要进行扩容。HashMap 按当前桶数组长度的 2 倍进行扩容，扩容阈值也更新为原来的 2 倍。扩容之后，需要重新计算键值对的位置，并把它们移动到合适的位置上去。和 JDK 1.7 不同的是，JDK 1.7 是先判断是否需要扩容后插入新值，JDK 1.8 是先插入值再判断是否需要扩容，并且前者是头插法后者是尾插法。此外，前者是完成扩容、迁移数据后再替换旧数组，后者是扩容后替换旧数组，然后进行数据迁移，注意这对并发读写的影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**
   * 初始化数组或数组扩容
   *
   * @return the table
   */
  final Node<K, V>[] resize() {
      Node<K, V>[] oldTab = table;

      // table 旧的容量，最开始 table 为空
      int oldCap = (oldTab == null) ? 0 : oldTab.length;

      // 扩容阈值
      int oldThr = threshold;
      int newCap, newThr = 0;

      // oldCap > 0 ，说明是对数组扩容
      if (oldCap > 0) {
          // 超过最大容量，则使用 Integer.MAX_VALUE 的值，不再进行扩容
          if (oldCap >= MAXIMUM_CAPACITY) {
              threshold = Integer.MAX_VALUE;
              // 返回旧的数组
              return oldTab;

              // 将 数组扩大一倍
          } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
              // 将 扩容阈值 也增大一倍
              newThr = oldThr << 1; // double threshold

          // 对应使用 new HashMap(int initialCapacity) 初始化后，第一次插入元素走到这里，新数组容量设置为 旧扩容阈值
          // 此时，旧扩容阈值等于传入容量向上最近的2的n次方；
          // todo 注意，在构造方法中并没有初始化数组，这里才使用到传入的初始化容量值
      } else if (oldThr > 0) // initial capacity was placed in threshold
          newCap = oldThr;

          // 对应使用 new HashMap() 初始化后，第一次 put 的时候初始容量使用默认值
      else {               // zero initial threshold signifies using defaults
          newCap = DEFAULT_INITIAL_CAPACITY;
          // 计算扩容阈值，为 12
          newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
      }

      // newThr 为 0 时，按阈值计算公式进行计算
      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;

              // 取出下标 j 的元素
              if ((e = oldTab[j]) != null) {
                  // 清空旧桶，便于 GC 回收
                  oldTab[j] = null;
                  // 如果当前数组位置上只有一个 Node 元素，简单迁移即可
                  if (e.next == null)
                      // 通过 hash 值计算出在新数组中所属的位置「无需重新计算 hash 值」
                      newTab[e.hash & (newCap - 1)] = e;

                      // 如果第一个元素是树节点，需要对红黑树进行拆分，也就是将这颗红黑树打散成两颗然后插入到新桶中去
                  else if (e instanceof TreeNode)
                      ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);

                      // 链表处理
                  else { // preserve order

                      // 将当前链表拆分成两个链表，放到新的数组中，并且保留原来的先后顺序

                      // 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;

                          // 根据e的 hash 值和旧的容量做位与运算是否为 0 来拆分当前链表进行分组，注意之前是 e.hash & (oldCap - 1)
                          // 即 (e.hash & oldCap) == 0 的元素放在低位链表中
                          if ((e.hash & oldCap) == 0) {
                              if (loTail == null)
                                  loHead = e;
                              else
                                  loTail.next = e;
                              loTail = e;

                          // (e.hash & oldCap) != 0 的元素放在高位链表中
                          } else {
                              if (hiTail == null)
                                  hiHead = e;
                              else
                                  hiTail.next = e;
                              hiTail = e;
                          }
                      } while ((e = next) != null);

                     
                      /* 1 遍历完链表完成分化成两个链表：
                       *    - 低位链表在新桶中的位置与旧桶中的一样
                       *    - 高位链表在新桶中的位置正好是原来的位置加上旧容量
                       * 2 将分组后的链表映射到新桶中
                       */

                      // 第一条链表
                      if (loTail != null) {
                          loTail.next = null;
                          newTab[j] = loHead;
                      }

                      // 第二条链表的新的位置是 j + oldCap
                      if (hiTail != null) {
                          hiTail.next = null;
                          newTab[j + oldCap] = hiHead;
                      }
                  }
              }
          }
      }
      return newTab;
  }

下面对上述代码流程进行总结：

  1. 计算新桶数组的容量 newCap 和新扩容阈值 newThr；
  2. 根据计算出的 newCap 创建新的桶数组，桶数组 table 也是在这里进行初始化的；
  3. 将遍历的桶数组的键值对节点重新映射到新的桶数组中。如果节点是 TreeNode 类型，则需要拆分红黑树进行分组然后映射；如果是普通节点，也就是链表，则同样需要分组然后映射。注意，以上分组的依据是根据节点的 hash 值和旧的容量做位与运算是否为 0 来限定的。

在 JDK 1.8 中，重新映射节点需要考虑节点类型。对于树形节点，需要先拆分分组然后映射；对于链表类型节点，也需要先拆分分组，然后映射。需要注意的是，分组后，组内节点相对位置保持不变。相对与 JDK 1.7 采用每个节点重新 hash 且头插入 ，JDK 1.8 采用尾插法且以分组的方式进行重新映射，避免了链表成环的问题。

树化、链化与拆分

JDK 1.8 对 HashMap 实现进行了改进。最大的改进莫过于引入红黑树处理频繁的碰撞，同时也增加了代码实现的复杂度。本小结将对 HashMap 中 链表树化、红黑树链化以及红黑树拆分 进行说明。

链表树化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
final void treeifyBin(Node<K, V>[] tab, int hash) {
        int n, index;
        Node<K, V> e;
        // 数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
        // 尽可能避免树化，除非桶中元素碰撞严重
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();

            // 取出数组对应位置的头节点
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            // hd 为头节点(head)，tl 为尾节点（tail）
            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);

            // 将树形链表转换成红黑树
            // hd 是 index 对应桶的首节点
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

    // For treeifyBin
    TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

将链表转为红黑树需要满足以下两个条件：

  1. 链表长度大于等于 TREEIFY_THRESHOLD 8
  2. 桶数组容量大于等于 MIN_TREEIFY_CAPACITY 64

上述方法主要的过程是，先将链表转成由 TreeNode 类型节点组成的双向链表，并在最后调用 treeify 将该链表转为红黑树。TreeNode 继承自 Node ，所以 TreeNode 仍然包含 next 引用，原链表的节点顺序最终通过 next 引用被保存下来。

下面我们重点来介绍链表转红黑树的过程。

TreeNode 链表转红黑树

将链表转为红黑树需要两个过程，第一个是通过 treeifyBin 方法将普通节点链表转成树形节点链表，也就是 TreeNode 链表；另一个则是 treeify 方法再将第一步得到的树形链表结构转成真正的红黑树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
    * 将树形链表转换成红黑树
    */
   final void treeify(HashMap.Node<K, V>[] tab) {

       // 定义红黑树的根节点
       HashMap.TreeNode<K, V> root = null;

       // 1 遍历树形链表节点，依次加入到红黑树中。
       // x 指向当前节点，next 指向下一个节点
       for (HashMap.TreeNode<K, V> x = this, next; x != null; x = next) {
           // 记录 x 的下一个节点
           next = (HashMap.TreeNode<K, V>) x.next;
           // 左右节点先确保干净
           x.left = x.right = null;

           // 2 如果根节点为空，说明还没有开始构建红黑树，这里开始构建。即将当前节点作为根节点，颜色设为黑色
           if (root == null) {
               x.parent = null;
               x.red = false;
               root = x;

               // 3 红黑树已经存在，则往该树中添加节点
           } else {

               // 记录当前遍历到的树形节点的 key 和 hash
               K k = x.key;
               int h = x.hash;
               Class<?> kc = null;

               // 3.1 从根节点遍历，为节点 x 找到空位置并插入
               for (HashMap.TreeNode<K, V> p = root; ; ) {
                   // dir 表示方向（左边/右边），ph 表示 hash 值
                   int dir, ph;
                   K pk = p.key;

                   /* 比较大小，定位插入左边/右边*/
                   // 3.1.1 hash 判断
                   if ((ph = p.hash) > h)
                       dir = -1;
                   else if (ph < h)
                       dir = 1;

                       // 3.1.2 根据比较器判断大小
                   else if ((kc == null &&
                           // Comparable 接口判断
                           (kc = comparableClassFor(k)) == null) ||
                           (dir = compareComparables(kc, k, pk)) == 0)

                       // 3.1.3 通过 k 类名比较
                       dir = tieBreakOrder(k, pk);

                   // 保存当前遍历的树节点
                   HashMap.TreeNode<K, V> xp = p;

                   // 3.2.1 根据 dir 确定放入左边还是右边
                   // 如果根据 dir 确定了位置后，还要判断 p 是不是叶子节点（末节点），如果不是则继续往下找适合节点x插入的位置，也就是 x 节点的父节点
                   if ((p = (dir <= 0) ? p.left : p.right) == null) {
                       // x 节点找到了父节点
                       x.parent = xp;

                       // 将 x 节点挂到它的父节点 xp 下
                       if (dir <= 0)
                           xp.left = x;
                       else
                           xp.right = x;

                       // 3.2.2 x 节点插入后，可能会导致红黑树不符合规则，因此需要尝试进行调整
                       root = balanceInsertion(root, x);
                       break;
                   }
               }
           }
       }

       // 确保根节点作为第一个节点
       moveRootToFront(tab, root);
   }

上面的方法做的只有一个工作，遍历 TreeNode 双向链表，将该链表中每个节点构建到红黑树中。下面对流程进行分步说明：

  1. 遍历第一个节点时，此时红黑树不存在，以第一个节点作为红黑树根节点。
  2. 有了红黑树后，此后遍历链表的每个节点时，都要根据规则到红黑树中从根节点开始寻找要插入当前节点的位置，也就是找到一个父节点，将当前节点作为其左节点或右节点。
  3. 插入节点后，可能会导致红黑树特性被破坏，因此每次插入节点后要尝试重新调整红黑树。

上述方法完成了 TreeNode 链表中每个节点构建红黑树的过程，一个节点构建到红黑树后并没有结束，还要保证红黑树不能因为新增一个节点就被破坏，而保证的手段就是红黑树调整。

红黑树调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
static <K, V> HashMap.TreeNode<K, V> balanceInsertion(HashMap.TreeNode<K, V> root,
                                                         HashMap.TreeNode<K, V> x) {

       // 默认插入红色
       x.red = true;

       // xp -> 父节点
       // xpp -> 祖父节点
       // xppl 是祖父节点的左节点（左叔叔节点）
       // xppr 是祖父节点的右节点（右叔叔节点）
       for (HashMap.TreeNode<K, V> xp, xpp, xppl, xppr; ; ) {

           // 1 x 节点的父节点不存在，说明当前节点是根节点，只需变色为黑色即可
           if ((xp = x.parent) == null) {
               x.red = false;
               return x;

               // 2 x 节点的父节点是黑色，可以在下面直接添加红色节点，不需要调整；x 节点的祖父节点为空，说明 x 的父节点是根节点，可以在下面直接添加红色节点，也不许要调整
           } else if (!xp.red || (xpp = xp.parent) == null)
               return root;

           // 3 x 的父节点 xp 是红色且 x 祖父节点 xxp 不为空。这样就遇到了两个红色节点相连的情况。这种情况分两种可能

           // 3.1 如果父节点 xp 是祖父节点的左节点
           if (xp == (xppl = xpp.left)) {

               // 3.1.1 如果祖父节点的右节点（右叔叔节点）不为空，同时是红色。则：
               // a. 将父节点和右叔叔节点变色 -> 黑色
               // b. 将祖父节点变色 -> 红色
               // c. 将祖父节点作为当前节点 x ，进行下一轮的调整（xxp 节点变成红色后可能与xpp的父节点发生冲突，也就是两个连续的红色节点）
               if ((xppr = xpp.right) != null && xppr.red) {
                   xppr.red = false;
                   xp.red = false;
                   xpp.red = true;
                   x = xpp;

                   // 3.1.2 如果祖父节点的右节点（右叔叔节点）为空或是黑色。那么就可能对应以下两种情况：
               } else {

                   // 3.1.2.1 xpp->xp(xxp的左节点)->x(xp的右节点) => LR 双红
                   if (x == xp.right) {
                       // 将 xp 节点左旋，调整成 LL 双红的情况
                       root = rotateLeft(root, x = xp);
                       // 重置 xp，xxp
                       // 左旋后得到的本来是： xpp->x(xxp的左节点)->xp(x的左节点) => LL 双红
                       // 但是由于 x = xp 了，因此恰巧从变量的角度看是这个样子：xpp->xp(xxp 的左节点)->x(xp的左节点) => LL 双红
                       xpp = (xp = x.parent) == null ? null : xp.parent;
                   }

                   // 3.1.2.2 xpp->xp(xxp 的左节点)->x(xp的左节点) => LL 双红
                   if (xp != null) {
                       // 父节点 xp 变色 -> 黑色
                       xp.red = false;

                       // 存在祖父节点
                       if (xpp != null) {
                           // 祖父节点 xpp 变色 -> 红色
                           xpp.red = true;

                           // 右旋祖父节点
                           // 特别说明：上一步将祖父节点 xpp 变成红色，为啥这里直接旋转祖父节点 xpp 就可以结束了？因为 xp 变成了黑色，旋转后的结果是 xpp 挂到 xp 的右边成为 xp 的孩子节点，
                           // xp 成为最开始 xpp 的父节点的孩子节点（如果 xpp 是根节点，那么此时 xp 就是新的根节点），因此这里不用考虑 xpp 变色后破坏红黑树特点。简单来说，对于 xpp 的父节点
                           // 而言只是将 xpp 这个孩子节点换成了 xp ，但是节点颜色相比之前是没有变的。
                           // todo 后续继续以 x 节点向上调整，一般执行到分支 2 就结束了
                           root = rotateRight(root, xpp);
                       }
                   }
               }


               // 3.2 父节点 xp 是祖父节点的右节点。和上面的情况相反但操作类似，一个是左节点，另一个是右节点
           } else {

               // 3.2.1 如果 x 节点的祖父节点的左节点（左叔叔节点）不为空，同时是红色。则：
               // a. 将父节点和左叔叔节点变色 -> 黑色
               // b. 将祖父节点变色 -> 红色
               // c. 将祖父节点作为当前节点 x ，进行下一轮的调整（xxp 节点变成红色后可能与xpp的父节点发生冲突，也就是两个连续的红色节点）
               if (xppl != null && xppl.red) {
                   xppl.red = false;
                   xp.red = false;
                   xpp.red = true;
                   x = xpp;


                   // 3.2.2 如果祖父节点的左节点（左叔叔节点）为空或是黑色。那么就可能对应以下两种情况：
               } else {

                   // 3.2.2.1 xpp->xp(xxp的右节点)->x(xp的左节点) => RL 双红
                   if (x == xp.left) {
                       // 将父节点 xp 右旋转，得到 RR 双红
                       root = rotateRight(root, x = xp);
                       // 原因同 3.1.2.2
                       xpp = (xp = x.parent) == null ? null : xp.parent;
                   }

                   // 3.2.2.2 xpp->xp(xxp的右节点)->x(xp的右节点) => RR 双红
                   if (xp != null) {

                       // 父节点变色 -> 黑色
                       xp.red = false;

                       // 存在祖父节点
                       if (xpp != null) {

                           // 祖父节点变色 -> 红色
                           xpp.red = true;

                           // 左旋祖父节点
                           // 特别说明：原因同上
                           root = rotateLeft(root, xpp);
                       }
                   }
               }
           }
       }
   }
左旋
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
     * 左旋：
     * 1 将节点 p 旋转为其右节点的左节点，即将节点 p 挂到其右节点的左边
     * 2 其右节点的左节点成为节点p 的右节点
     *
     * @param root
     * @param p
     * @param <K>
     * @param <V>
     * @return
     */
    static <K, V> HashMap.TreeNode<K, V> rotateLeft(HashMap.TreeNode<K, V> root,
                                                    HashMap.TreeNode<K, V> p) {

        // r -> 节点 p 的右节点
        // rl -> 节点 p 的右节点的左节点
        // pp -> 节点 p 的父节点，最后是 p 的右节点的父节点
        HashMap.TreeNode<K, V> r, pp, rl;

        // p 不为空且右节点不为空
        if (p != null && (r = p.right) != null) {

            // 1 将 p 的右节点的左节点挂到 p 的右节点，这有两个信息
            // a. 断开 p 与其右节点 r 的连接
            // b. 因为 p 要挂到其右节点 r 的左边，因此要把节点 r 原来的左节点挂到 p 的右边
            if ((rl = p.right = r.left) != null)
                // r 节点的左节点的父节点重置为 p
                rl.parent = p;

            // 2 将 p 的父节点设置为 p 的右节点的父节点
            if ((pp = r.parent = p.parent) == null)
                // 如果 p 为 root 节点，那么直接将其右节点设置为 root
                (root = r).red = false;

                // 3 确定 r 节点应该挂在 p 的父节点的左边还是右边。这个根据 p 的位置决定
            else if (pp.left == p)
                pp.left = r;
            else
                pp.right = r;

            // 4 将 p 设置为其右节点的左边
            r.left = p;
            // 5 将 p 的右节点指为其父节点
            p.parent = r;
        }

        // 返回根节点
        return root;
    }
右旋
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
     * 右旋：
     * 1 将节点 p 旋转为其左节点的右节点，即将节点 p 挂到其左节点的右边
     * 2 其左节点的右节点成为节点 p 的左节点
     *
     * @param root
     * @param p
     * @param <K>
     * @param <V>
     * @return
     */
    static <K, V> HashMap.TreeNode<K, V> rotateRight(HashMap.TreeNode<K, V> root,
                                                     HashMap.TreeNode<K, V> p) {
        // l -> 节点 P 的左节点
        // pp -> 节点 p 的父节点
        // lr -> 节点 p 的左节点的右孩子
        HashMap.TreeNode<K, V> l, pp, lr;

        // 节点 p 和 其左节点不为空
        if (p != null && (l = p.left) != null) {

            // 1 将 p 的左节点的右孩子挂到 p 的左边
            if ((lr = p.left = l.right) != null)
                // 将 p 指定为 lr 的父节点
                lr.parent = p;

            // 2 将 p 的父节点指定为其右节点的父节点
            if ((pp = l.parent = p.parent) == null)
                (root = l).red = false;

                // 2.1 确定 p 的右节点应该挂在 p的父节点左边还是右边
            else if (pp.right == p)
                pp.right = l;
            else
                pp.left = l;


            // 3 调整 p 的关系：
            // a.将 p 设置为其左节点的右孩子
            // b.将 p 的父节点指定为其左节点
            l.right = p;
            p.parent = l;
        }

        // 返回根节点
        return root;
    }

红黑树调整的过程完全是红黑树节点插入的过程，由于涉及的情况比较多，下面我们对上述过程分情况分析。再强调一遍，调整过程是红黑树的操作过程，并非 HashMap 自己搞的一套调整逻辑。

情况一

红黑树为空树，插入的新节点 X 作为红黑树的根节点，这种情况下将节点 X 的颜色由红色变成黑色即可。

情况二

插入的新节点 X 的父节点是黑色，这种情况下不需要调整。

情况三

插入的新节点 X 的父节点是红色（节点 P 为红色，其父节点必然为黑色），叔叔节点 U 也是红色。由于 P 和 U 都是红色，不满足每个红色节点必须有两个黑色的子节点，也就是不能同时存在两个连续的红节点。这种情况下需要调整，先将 P 和 U 变为黑色，再将 PP 变为红色。但需要注意的是 PP 变为红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整，也就将 PP 看作新插入节点继续尝试调整。

情况四

插入节点 X 的父节点为红色，叔叔节点不存在或为黑色（下面的所有情况以黑色为例进行说明）。这里需要根据插入节点 X 的父节点是祖父节点的左子树还是右子树进行讨论，不同的情况处理的逻辑不同。主要不同在于旋转的方向上不同。

父节点为祖父节点左子树

根据插入节点 X 是父节点的左子树还是右子树又可分为两类。

  • 插入节点是父节点的右子树
    插入节点 X 的父节点 P 为红色，属于 LR 形。叔叔节点 U 为黑色。节点 X 是 P 的右子树，且节点 P 是 PP 的左子树。此时先对节点 P 进行左旋，调整节点 X 与 P 的位置，变为 LL 形。接下来按照 LL 形进行处理即可，也就是下面的 插入节点是父节点的左子树 情况。

  • 插入节点是父节点的左子树
    插入节点 X 的父节点 P 为红色，属于 LL 形。叔叔节点 U 为黑色。节点 X 是 P 的左子树，且节点 P 是 PP 的左子树。此时先将 P 变成黑色，PP 变成红色；然后对 PP 进行右旋，调整 P 和 PP 的位置。

父节点为祖父节点右子树

根据插入节点 X 是父节点的左子树还是右子树又可分为两类。

  • 插入节点是父节点的左子树
    插入节点 X 的父节点 P 为红色，属于 RL 形。叔叔节点 U 为黑色。节点 X 是 P 的左子树，且节点 P 是 PP 的右子树。此时先对节点 P 进行右旋，调整节点 X 与 P 的位置，变为 RR 形。接下来按照 RR 形进行处理即可，也就是下面的 插入节点是父节点的右子树 情况。

  • 插入节点是父节点的右子树
    插入节点 X 的父节点 P 为红色，属于 RR 形。叔叔节点 U 为黑色。节点 X 是 P 的右子树，且节点 P 是 PP 的右子树。此时先将 P 变成黑色，PP 变成红色；然后对 PP 进行左旋，调整 P 和 PP 的位置。

以上四种情况覆盖了黑树调整的所有可能情况，对应了代码注释的 4 个分支。

红黑树拆分

在扩容的过程，普通节点需要重新映射，红黑树节点同样也需要。在将普通链表转成红黑树时，HashMap 通过两个额外的引用 next 和 prev 保留了原链表的节点顺序。这样再对红黑树进行重新映射时，完全可以按照映射链表的方式进行，这样就避免了将红黑树转成链后再映射的过程，在一定程度上提高了效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
final void split(HashMap<K, V> map, HashMap.Node<K, V>[] tab, int index, int bit) {
        HashMap.TreeNode<K, V> b = this;

        // 重新链接到 lo 和 hi 列表，保持顺序
        HashMap.TreeNode<K, V> loHead = null, loTail = null;
        HashMap.TreeNode<K, V> hiHead = null, hiTail = null;
        int lc = 0, hc = 0;

        /**
         * 红黑树节点仍然保留了 next 引用，因此仍可以按链表方式遍历红黑树。下面的循环是对红黑树节点进行分组，与普通链表操作类似
         */
        for (HashMap.TreeNode<K, V> e = b, next; e != null; e = next) {
            next = (HashMap.TreeNode<K, V>) e.next;
            e.next = null;
            if ((e.hash & bit) == 0) {
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
                ++lc;
            } else {
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }

        /* 两个 TreeNode 链表分组完毕 */


        // 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
        if (loHead != null) {
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);

            else {
                tab[index] = loHead;
                // hiHead == null 时，表明扩容后，所有节点仍在原位置，树结构不变，无需重新树化
                // 否则，将 TreeNode 链表重新树化
                if (hiHead != null) // (else is already treeified)
                    loHead.treeify(tab);
            }
        }

        // 同上面逻辑
        if (hiHead != null) {
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else {
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }

从上述代码中可以看到，重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。如果链表长度小于等于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。

红黑树链化

红黑树中仍然保留了原链表节点顺序，有了这个基础再将红黑树转成链表就简单多了，仅需要将 TreeNode 链表转成 Node 类型的链表即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

   /**
    * 红黑树中仍然保留了原链表节点顺序。有个这个特点，再将红黑树转成链表就简单多了，仅需将 TreeNode 链表转成 Node 类型的链表即可。
    */
   final HashMap.Node<K, V> untreeify(HashMap<K, V> map) {
       // 用于组织链表的头、尾指针
       HashMap.Node<K, V> hd = null, tl = null;
       // 遍历 TreeNode 链表，并用 Node 替换
       for (HashMap.Node<K, V> q = this; q != null; q = q.next) {
           /**
            * 替换节点类型
            *    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
            *            return new Node<>(p.hash, p.key, p.value, next);
            *       }
            */
           HashMap.Node<K, V> p = map.replacementNode(q, null);
           if (tl == null)
               hd = p;
           else
               tl.next = p;
           tl = p;
       }
       return hd;
   }

 Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
   return new Node<>(p.hash, p.key, p.value, next);
}

思考

Q：为什么不直接使用红黑树解决 hash 冲突，而选择先使用链表，再转红黑树？

当桶中的元素数量小于 8 的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度。但是红黑树在节点新增或删除时需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

Q：为什么要转成红黑树？二叉搜索树不行吗？

可以。但是二叉查找树在特殊情况下会退化成链表，遍历查找会非常慢。

Q：红黑树退化为链表的阈值为 6 ，链表转为红黑树的阈值为 8 ，为什么这样设计？

根据泊松分布的计算方式，链表中元素个数为 8 时的概率已经非常小了，所以将链表转为红黑树的阈值设置为 8。

红黑树退化为链表的阈值为 6 ，中间有个差值 7 ，这是为了防止链表和树之间的频繁转换。

Q：默认加载因子为什么是 0.75，不是 0.6 或者 0.8 ？

默认负载因子 0.75 是在时间和空间成本上的一个折衷。较高的值会降低空间开销（数组尽可能满），但提高查找成本。一般不需要修改，除非在时间和空间上有特别的要求：

  • 如果内存空间很多而又对时间效率要求很高，可以降低负载因子的值；
  • 如果内存空间紧张而对时间效率要求不高，可以增加负载因子的值，这个值可以大于1；

参考

什么是HashMap

gentryhuang xw

万丈高楼平地起