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接口

  • MapCollection 并列存在。用于保存具有映射关系的数据:Key-Value
  • Map 中的 keyvalue 可以是任何引用类型的数据,会封装到 HashMap$Node 对象中
  • Map 中的 key 不允许重复,原因和 HashSet 一样,Map 中的 value 可以重复
  • Mapkey 可以为 null , value 也可以为 null,注意 keynull, 只能有一个valuenull ,可以多个.
  • 常用 String 类作为 Mapkey
  • keyvalue 之间存在单向一对一关系,即通过指定的 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 值存入: putMapEntriesboolean 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 已经大于当前 mapthreshold,即当前 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(...),根据 keyvalue 并返回,找不到则返回 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(…)

  • matchValuetrue: key & value 都相同才能删除;false: key 相同就可删除
  • movablefalse: 删除过程中不移动其他节点
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并发死链问题

  • 首先说明:JDK7HashMap 插入操作是 头插法

关注到 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);
}
  • 传入集合类,判断是不是 SortedSetPriorityQueue ,是他们的实例,则会按照之前的顺序构造新的优先队列,否则按照默认排序器构造堆
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 < 64newCap = oldCap x 2 + 2
  • oldCap >= 64newCap = oldCap x 2
  • oldCap > Integer.MAX_VALUE - 8newCap = 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源码解析


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