Java常用集合源码分析 Ⅱ

本文最后更新于：2021年10月17日 晚上

Java常用集合源码分析 Ⅱ

@Version: JDK 1.8

@IDE: IntellJ IDEA 2021.1

@Date: 2021/8/10

@Author: Hypocrite30

一、集合

Ⅰ、Set接口

  • 无序「添加和取出的顺序不一致」，没有索引
  • 不允许重复元素，所以最多包含一个 null
  • 常用实现类有 HashSet & TreeSet

Ⅱ、Map接口

  • Map 与 Collection 并列存在。用于保存具有映射关系的数据：Key-Value
  • Map 中的 key 和 value 可以是任何引用类型的数据，会封装到 HashMap$Node 对象中
  • Map 中的 key 不允许重复，原因和 HashSet 一样，Map 中的 value 可以重复
  • Map 的 key 可以为 null , value 也可以为 null，注意 key为 null, 只能有一个，value 为 null ，可以多个.
  • 常用 String 类作为 Map 的 key
  • key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value

二、HashMap

Ⅰ、Field

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
// 默认初始化容量，且容量必须是 2 次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量，在两个带参构造中的任何一个隐式指定更高的值时使用。
// 必须是 2 的次幂 <= 1<<30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认缺省负载因子大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 桶的链表还原阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 存储箱可树化的最小表容量
// 当Map table 数组数量「桶数量」超过这个值时，表中的桶才能进行树形化,
// 否则桶内元素太多时会对数组扩容，而不是树形化 
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
// 哈希表，即 Node 数组
transient Node<K,V>[] table;
// Set集合，存 Node 节点，因为 Node implements Entry，多态的形式
transient Set<Map.Entry<K,V>> entrySet;
// 哈希表元素个数
transient int size;
// 哈希表修改次数，不包括 K-V 的替换
transient int modCount;
// 要调整大小的下一个大小值，为「容量 * 负载系数」
int threshold;
// 负载因子，建议用默认的 0.75
final float loadFactor;

Ⅱ、Constructor

无参构造

  • 使用默认的 负载因子，容量还是有其它的初始化设置都是默认的
1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

有参构造

  1. 自定义 table 容量，负载因子是默认的 0.75
1
2
3
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
  1. 自定义 容量 和 负载因子
  • 检验 容量 的合法性，不合法抛异常
  • if 自定义容量超过限制最大值 1 << 30，容量按最大值来取
  • 检验 负载因子 是否「小于0 || 不是一个数」，不合法抛异常
  • 阈值 threshold 「要调整大小的下一个大小值」需要 「计算大于等于给定数的最近2次幂数」，因为阈值必须是 2 次幂的数。
1
2
3
4
5
6
7
8
9
10
11
12
13
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // MAXIMUM_CAPACITY = 1 << 30;
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

📌：按照逻辑 (当size到达threshold时扩容) threshold 应该这样写 「this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;」但 jdk8 之后的构造方法，没有对 table 数组进行初始化，而是推移到 HashMap::put，在 put 中对 threshold 重新计算。

  1. 传入 Map，使用默认 负载因子，容量足够存下入参的 Map
  • 负载因子使用默认 0.75
  • 然后创建table，将入参 map 值存入： putMapEntries，boolean evict = false 说明是表创建模式
1
2
3
4
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

Ⅲ、Method

插入元素 put(K key, V value)

  • 实际的实现函数是 putVal(...)
  • putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
    • 哈希值需要重新计算，使用 hash() 再次计算哈希值，使得哈希值更分散
    • onlyIfAbsent = false：遇到相同的 key，则会替换原先的值，并返回旧值，否则返回 null
    • evict = true：不是创建模式
1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

Map.put 实现方法及相关方法 putVal(…)

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
/**
  * 实现 Map.put 和 相关方法
  * @param hash key的哈希值
  * @param key key
  * @param value value
  * @param onlyIfAbsent true: 不替换已存在元素; false: 替换
  * @param evict false: 表为创建模式
  * @return 以前的值，如果没有，则为 null
  */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    /**
      * tab: 桶数组
      * p: 当前的桶
      * n: 桶数组长度
      * i: 路由地址「下标位置」
      */
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果 table 没初始化或长度为0，则扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果 hash 位置桶没有数据，则直接插入数据
    // (length - 1) & hash == hash % length
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 如果桶有数据，再放入桶中
    else {
        // e: 临时的 Node; k: 临时的 key
        Node<K,V> e; K k;
        // 判断put的元素和已经存在的元素是相同(hash一致，并且equals返回true)
        // 则将已存在的节点暂存
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // put的元素与已存在元素不同
        // 如果桶内类型时树结构，则插入到树中
        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
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果已经存在key，停止遍历，进行下面的替换操作
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 游标向后移动
                p = e;
            }
        }
        // 判断 K-V 有没有插入进哈希表里
        // 上面操作，只要插入进桶里，e != null，否则还是初始的 null 值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent = true: 不替换旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // K-V 超过阈值，扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

HashMap.putVal

Map.putAll 实现方法及Map构造方法 putMapEntries(…)

  • ((float)s / loadFactor) + 1.0F 加 1 的目的：计算得到容量有可能为小数，后面需要对长度进行取整，容量就会算小，所以加一取整，就是向上取整。

  • if (t > threshold)，此 threshold 存放的是 capacity 的值。在 table 未初始化时，带初始化容量的构造器会传入 capacity，并通过 tableSizeFor 计算扩容阈值，让 threshold 暂存这个值。在 HashMap 中没有capacity 这个变量，只是作为 table 数组的大小而隐式存在。

  • else if (s > threshold) 说明入参 map 的 size 已经大于当前 map 的 threshold，即当前 map 肯定装不下两个 map 的并集，所以需要扩容

  • putVal 过程中也可能出现扩容

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
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 入参集合长度
    int s = m.size();
    if (s > 0) {
        // table 没有被初始化
        if (table == null) { // pre-size
            // s/loadFactor 计算入参map长度是否达到扩容阈值
            float ft = ((float)s / loadFactor) + 1.0F;
            // 入参map长度是否超过最大容量，否则取整
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 如果计算出来的容量t > 当前暂存容量，会用t计算出新扩容阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // table 已经初始化，且 m 元素个数大于阈值，扩容处理
        else if (s > threshold)
            resize();
        // 将 m 中所有元素添加到 table 中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

扩容方法 resize()

  • 注释①：public HashMap(int initialCapacity, float loadFactor) 两个参数的构造方法，会使用 tableSizeFor() 获得大于等于初始容量的最近2次幂数，并给 threshold 赋值，导致在 else if (oldThr > 0) 判断时成立，有参构造都会直接或间接使用到 tableSizeFor，所以都会走这段程序
  • 注释②：if (newThr == 0) 的情况，有两种。
    • 一、在上面 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) 的判断，如果不满足 oldCap >= DEFAULT_INITIAL_CAPACITY(16)，即传入的初始化容量小于 16，则没法完成 newThr 的赋值，则 newThr == 0
    • 二、else if (oldThr > 0) 中，也没有对 newThr 进行赋值，所以此时也是 newThr == 0
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
final Node<K,V>[] resize() {
    // 旧哈希表
    Node<K,V>[] oldTab = table;
    // 旧table数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 扩容之前的扩容阈值，触发本次扩容
    int oldThr = threshold;
    // newCap: 扩容之后的容量大小
    // newThr: 扩容之后，下次扩容的触发条件
    int newCap, newThr = 0;
    
    // 哈希表已经初始化过了，正常扩容
    if (oldCap > 0) {
        // 旧容量超出最大容量，则不扩容，阈值保持为int最大值，返回旧表
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新容量为旧容量扩大一倍，且小于最大容量
        // 还要满足：旧容量 <= 16，才将新扩容阈值扩大一倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 下面都是未初始化情况
    // 注释①
    // 未初始化，oldThr旧扩容阈值已经计算的情况是有参构造中计算的
    // 1. public HashMap(int initialCapacity, float loadFactor)
    // 2. public HashMap(int initialCapacity
    // 3. public HashMap(Map<? extends K, ? extends V> m)
    else if (oldThr > 0) // 初始容量设置为阈值，容量为2的次幂
        newCap = oldThr;
    // 1. oldThr == 0 -> 无参构造创建的table
    // 2. oldCap == 0 -> 因为容量最小为0，不为负数
    else {               // 零初始阈值表示使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY; // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16 * 0.75 = 12
    }
    
    // 注释②
    // newThr == 0时，通过 newCap * loadFactor 计算 newThr，即新的扩容上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 更新 threshold，下次按照本次计算的结果作为扩容上限
    threshold = newThr;
    // 以上做了两件事：计算 newCap & newThr
    // 以下完成扩容操作
    @SuppressWarnings({"rawtypes","unchecked"})
    // 创建新数组，并赋值替换原table，在一开始就将原table 用 oldTab 标记出来
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 扩容前，table不为null
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            // 当前 node 节点
            Node<K,V> e;
            // 说明当前节点有数据，但数据结构并不清楚
            if ((e = oldTab[j]) != null) {
                // help GC
                oldTab[j] = null;
                // next无值，没有发生碰撞，直接存入新桶中
                // 寻址算法：(length - 1) & hash == hash % length，其实length为2次幂数
                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: .... 1 1111
                          * hash: .... 0 1111
                          * oldCap: ...1 0000
                          * if 走低位，else 走高位
                          */
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 新table的位置在高位「原索引+旧容量」
                        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;
                    }
                    // 原索引 + oldCap 放到新桶里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

📌补充：

  1. 当HashMap中的其中一个链表的对象个数如果达到了 8 个，此时如果数组长度没有达到 64，那么HashMap 会先扩容解决，如果已经达到了 64，那么这个链表会变成红黑树，节点类型由 Node 变成TreeNode 类型。当然，如果映射关系被移除后，下次执行resize方法时判断树的节点个数低于 6，也会再把树转换为链表。
  2. HashMap在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n - 1) & hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么就被分配到 “原位置+旧容量“ 这个位置。

例如：16 扩展到32时

16扩展到32

因此元素在重新计算hash之后，因为 n 变为 2 倍，那么 n-1 的标记范围在高位多1bit(红色)，因此新的 index 就会发生这样的变化：

rehash后的index变化

  1. 两种情况会进行扩容：①元素个数超过「数组长度 * 负载因子」②桶链表长度大于 8 且 table 数组长度小于 64，则会进行扩容，而不是变成树结构

获取键值对的值 get(Object key)

  • 核心方法是 getNode(...)，根据 key 找 value 并返回，找不到则返回 null
  • key 传入时需要 hash(int) 计算一次，因为 put(K, V) 时也用到 hash(int)
1
2
3
4
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

Map.get 实现方法及相关方法 getNode(int hash, Object key)

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
final Node<K,V> getNode(int hash, Object key) {
    // tab: 当前 hashmap 的散列表
    // first: 桶中的首节点
    // e: 临时节点
	// n: table 数组长度
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 给 tab, n, first 初始化赋值，并判空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // (key != null && key.equals(k)) 正好头结点就是需要找的节点
        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;
}

删除 remove

  • 实现方法为 removeNode(...)
    • removeNode(int hash, Object key, Object value, boolean matchValue boolean movable)
    • matchValue == false 表示必须是 key & value 都相同才删除
1
2
3
4
5
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
  • key & value 都相同才能删除节点
    • matchValue == true
1
2
3
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

Map.remove 实现方法及相关方法 removeNode(…)

  • matchValue： true: key & value 都相同才能删除；false: key 相同就可删除
  • movable： false: 删除过程中不移动其他节点 
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 Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    // tab: 引用 hashmap 中的散列表
    // p: 当前 node 节点
    // n: table散列表的数组长度
    // index: 寻址结果
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 对变量初始化赋值，判空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        // node: 查找到的结果
        // e: 当前node的下一个节点
        Node<K,V> node = null, e; K k; V v;
        // 当前桶中元素就是待删除元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 桶中遍历其他元素进行删除
        else if ((e = p.next) != null) {
            // 桶为树结构
            if (p instanceof TreeNode)
                // 树中查找
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 桶为链表结构
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // matchValue为false，就不进行后面的value值判断
        // 为true，则找到value也匹配的情况
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 树节点删除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 上面的 if 的情况，桶中的首元素为待删除元素
            else if (node == p)
                tab[index] = node.next;
            // 链表结构删除节点
            else
                p.next = node.next;
            ++modCount;
            --size;
            // 在HashMap中是空方法，为了给其子类LinkedHashMap继承重写
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

获取 get(Object key)

  • 实现方法 getNode(...)，找不到，则返回 null
1
2
3
4
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

Map.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
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) {
        // 如果桶顶元素符合key，则直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶后面有其他元素碰撞
        if ((e = first.next) != null) {
            // 红黑树结构，二分查找，O(logn)
            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;
}

hash 计算

  • 再次计算 key.hashCode()，将 高 16 位 参与进来，使得哈希值更加分散
  • (h = key.hashCode()) ^ (h >>> 16)
  • 右移 16 位， 与原先的哈希值异或
  • 将 高 16 位 与原哈希值异或，即将高 16 位 参与进哈希值的运算中。随着元素的增加，哈希碰撞的几率会更低。
1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

计算大于等于给定数的最近2次幂数

输入7，结果为8；输入10，结果为16；

🌰：以入参为 10 为例

1
2
3
4
5
6
7
8
9
10
11
12
static final int tableSizeFor(int cap) {
    int n = cap - 1; // 9
    n |= n >>> 1; // 0b1001 | 0b0100 = 0b1101
    n |= n >>> 2; // 0b1101 | 0b0011 = 0b1111
    n |= n >>> 4; // 下面都是 0b1111
    n |= n >>> 8;
    n |= n >>> 16;
    // n = 0b1111
    // (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1
    // n + 1 = 15 + 1 = 16
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

📌注：如果一开始 n 不减一，算出来的结果会大一倍

Ⅳ、HashMap 初始化建议

一、初始化问题

由于 HashMap 自动扩容机制，需要重新计算键值对的哈希值，并进行拷贝，开销较大，为了避免自动扩容，尽量在创建哈希表时，有参构造 指定初始容量。

HashMap 的扩容机制 在 resize() 有介绍，两种情况会进行扩容：①元素个数超过「数组长度 * 负载因子」（threshold = loadFactor * capacity）②桶链表长度大于 8 且 table 数组长度小于 64，则会进行扩容，而不是变成树结构

二、建议初始化大小计算

  • 根据《阿里巴巴Java开发手册》编程规约中，对集合处理有以下建议：

HashMap创建指定初始化大小

🌰举例：

如果设置的默认值为 7，经过 tableSizeFor() 计算后，设置为 8。此时 Threshold = 8 * 0.75 = 6，会进行一次扩容，并不是最佳方案。

通过 initialCapacity / 0.75F + 1.0F 计算，得到设置值为 7 / 0.75 + 1 = 10，经过 tableSizeFor() 计算后设置为 16，在容量达到 16 * 0.75 = 12 时进行扩容，符合预期。

Ⅴ、线程安全问题

一、HashMap 线程安全问题

HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖这些问题。其中死循环和数据丢失是在 JDK1.7 中出现的问题，在 JDK1.8 中已经得到解决，然而 1.8 中仍会有数据覆盖的问题，即在并发执行 HashMap::put 操作时会发生数据覆盖的情况。

二、JDK7 HashMap并发死链问题

  • 首先说明：JDK7 中 HashMap 插入操作是 头插法。

关注到 JDK7 的扩容操作，实现的方法是 transfer(...)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]; // ②
            newTable[i] = e; // ③
            e = next; // ④
        }
    }
}

①：Entry<K,V> next = e.next; 获取 e 的下一个节点指针

②：e.next = newTable[i]; 待转移节点指向新桶

③：newTable[i] = e; 待转移节点移动到桶位置

④：e = next; 成功移动后，将 e 指针回到原来链表位置，对下一个节点转移\

以下视频有详细讲解：

https://www.bilibili.com/video/BV1n541177Ea

https://coolshell.cn/articles/9606.html#

三、HashSet

  • 基于 HashCode 实现元素不重复
  • 当存入元素哈希码相同时，调用 equals 确认，若为 true，拒绝后者存入「实现不重复」

Ⅰ、Field

1
2
3
4
// HashSet 底层使用 HashMap 实现
private transient HashMap<E,Object> map;
// 虚拟对象，充当 map 的 value
private static final Object PRESENT = new Object();

Ⅱ、Constructor

无参构造

  • 构造一个新的空集合；备份HashMap实例具有默认的初始容量（16）和负载因子（0.75）
1
2
3
public HashSet() {
    map = new HashMap<>();
}

四、TreeSet

  • 基于排列顺序实现元素不重复
  • 实现 SortedSet 接口，对集合元素自动排序
  • 元素对象的类型必须实现 Comparable 接口，指定排序规则
  • 通过 CompareTo 方法确定是否为重复元素

五、PriorityQueue

  • 看名称知道，该类属于 Queue ，由默认的排序器维护的堆为 **小根堆 **
  • 优先队列 是 Java 实现 堆 的方式
  • 堆 逻辑上是完全二叉树，按照层序遍历的顺序，可以使用数组进行存储，而其余的树大多是用链式数据结构存储。
  • 堆分类：
    • 大根堆：根节点「整棵树或任意子树」，父节点的值最大
    • 小根堆：同上，父节点值最小
  • 堆的操作：
    • 上浮：向堆添加新元素后的堆平衡操作
    • 下沉：取出堆顶并将堆尾换至堆顶后的堆平衡操作

小根堆

根据完全二叉树的性质，节点元素的下标与其父节点、左孩子和右孩子的关系：
$$
leftChild = parent \times 2 + 1
$$

$$
rightChild = parent \times 2 + 2
$$

$$
parent = (child - 1) / 2
$$

时间复杂度

  • peek() & element() -> O(1)
  • add() & offer() & remove() & poll() -> O(logN)
  • 建堆 -> O(n)
  • 堆排序：把根与末尾 n 调换，堆化，再把 n - 1 与根调换，最终为倒序「小根堆」
    • log n + log (n - 1) + … + 1 = O(nlogn)
    • 空间 **O(1)**，只需要交换的临时变量，原来的堆空间「数组」基础上做交换即可

Ⅰ、Field

1
2
3
4
5
6
7
8
9
10
// 默认初始化大小
private static final int DEFAULT_INITIAL_CAPACITY = 11; 
// 优先队列存储数据结构为数组，不能参与序列化
transient Object[] queue;
// 堆中元素数量
private int size = 0;
// 造成堆结构变化的次数「插入、删除、交换」
transient int modCount = 0;
// 构造器、默认为小根堆，可在有参中自定义
private final Comparator<? super E> comparator;

Ⅱ、Constructor

无参构造

  • 使用默认初始化大小「11」创建数组，默认排序器「小根堆」
1
2
3
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

有参构造

  • 指定初始化容量 和 自定义构造器
1
2
3
4
5
6
7
8
9
public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility 
    if (initialCapacity < 1) // 对 1.5 以下版本向下兼容
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}
  • 指定构造器，使用默认初始化容量「11」
1
2
3
public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}
  • 传入集合类，判断是不是 SortedSet 或 PriorityQueue ，是他们的实例，则会按照之前的顺序构造新的优先队列，否则按照默认排序器构造堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public PriorityQueue(Collection<? extends E> c) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}

Ⅲ、Method

插入元素 add(E e) & offer(E e)

1
2
3
public boolean add(E e) {
    return offer(e);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size; // 获取堆数组的容量
    if (i >= queue.length)
        grow(i + 1); // 扩容
    size = i + 1; // 让 size 到下一个位置，准备插入元素
    if (i == 0) // 数组为空，直接插入
        queue[0] = e;
    else
        siftUp(i, e); // 插入到末尾，然后向上浮动调整
    return true;
}
  • add() 直接调 offer()
  • 插入元素之前需要判断数组容量够不够，调用 grow() 扩容
  • 插入元素可能会破坏原堆的性质，所以插入到数组末尾，然后再让末尾元素递归上浮「siftUp」调整

扩容函数 grow()

  • 本质是数组的拷贝 Arrays.copyOf(oldArray, newArray)
  • oldCap < 64：newCap = oldCap x 2 + 2
  • oldCap >= 64：newCap = oldCap x 2
  • oldCap > Integer.MAX_VALUE - 8：newCap = oldCap x 2 + 2
1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}
  • 添加元素传进来的 minCapacity = i + 1，即原数组的容量 + 1，该值含义是 扩容后至少达到指定容量
  • 小于 0，说明溢出，抛异常
  • 如果指定容量比安全数组大小 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 大，最多给到 Integer.MAX_VALUE ，否则只给到 MAX_ARRAY_SIZE 
1
2
3
4
5
6
7
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

末尾元素上浮，调整堆化 siftUp(int k, E x)

  • 先将新元素插入到数组的末尾，即完全二叉树的末尾叶子结点，然后按照排序器规则，与其根节点比较，判断是否交换，循环此过程，直到堆化。

siftUp过程

  • 判断是否自定义排序器规则，有就用自定义的，没有就默认构造成小根堆
1
2
3
4
5
6
private void siftUp(int k, E x) {    
    if (comparator != null)        
        siftUpUsingComparator(k, x);    
    else        
        siftUpComparable(k, x);
}
  • 自定义排序器
    • 先将插入元素强转成 Comparable，让后面的值比较 compareTo 正常进行
    • 完全二叉树索引规则求父节点索引 parent = (child - 1) / 2
    • 满足自定义规则，break，插入到当前位置结束
    • 不满足，父节点移到子节点处，下一次循环会重新计算此次父节点的父节点
1
2
3
4
5
6
7
8
9
10
11
12
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}
  • 默认排序器「小根堆」
    • 待插入元素 x >= 父节点 e，break，就插入到当前位置
    • 父节点比子节点小，所以堆是小根堆
1
2
3
4
5
6
7
8
9
10
11
private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

获取堆顶元素 element() & peek()

  • element() & peek() 都获取堆顶元素，但不删除。前者获取不到抛异常，后者返回 null
  • 返回下标为 0 的元素，大顶堆返回最大值，小顶堆返回最小值
1
2
3
public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

删除元素 remove() & poll()

  • remove() & poll() 都删除堆顶元素，前者失败抛异常，后者失败返回 null
  • 删除元素会改变堆结构，所以删除完后要调整，将末尾元素移到堆顶，然后下沉「siftDown()」
  • size 判空，为空返回 null
  • 获取 size 减一后的容量 s
  • 保存堆顶即为 result 最后返回
  • 保存数组尾元素，然后将尾元素删掉「置为null」
  • 下沉调整堆结构 「siftDown()」
1
2
3
4
5
6
7
8
9
10
11
12
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}

下沉 siftDown(int k, E x)

  • 把末尾元素放到堆顶，然后下沉

siftDown

  • 判断使用自定义排序器「如果构造时指定有的话」还是默认排序器
1
2
3
4
5
6
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
  • 使用自定义排序器
  • 强转 Comparable，便于下面 compareTo() 正常使用
  • half 为数组中间位置，游标 k 的循环范围只有数组一半，另一半不用动，因为下沉需要找到两个孩子较小或较大的一个进行交换即可
  • 获取左孩子索引 (parent / 2) + 1，获取左孩子值 c
  • 获取右孩子索引 leftChild + 1
  • 取出符合排序器条件的孩子「left or right」，值保存为 c
  • 原堆末尾节点 x 与孩子值做判断，满足排序器，break，插入到当前位置「k」即可
  • 否则与孩子进行交换 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}
  • 使用默认排序器
  • 前面同上
  • 默认排序器选择较小的孩子，值保存为 c
  • 后面同上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

🔗Reference

https://tech.meituan.com/2016/06/24/java-hashmap.html

《阿里巴巴Java开发手册 v1.7.0嵩山版》

HashMap死链问题

Collection - PriorityQueue源码解析

JavaSE

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！