Java集合(五) Map

Java集合(五) Map

第一节 映射

映射,即Map,存放键值对的数据结构,也叫字典,键唯一,值不唯一。

散列映射(HashMap)对键进行散列,树映射(TreeMap)用键的整体顺序对元素排序,并将其组织为搜索树。映射的处理都是基于键,关联的值一般不做处理。

和Set一样,树映射因为实现有序而比散列映射要慢一些。


第二节 Map

2.1 Map接口

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
public interface Map<K, V> {
// Query Operations
int size();//元素数目
boolean isEmpty();//集合是否为空
boolean containsKey(Object key);//集合是否包含给定key
boolean containsValue(Object value);//集合是否包含给定value
V get(Object key);//给定key获取对应的value,没有返回null

// Modification Operations
V put(K key, V value);//存放Key-value,若映射中已有此key,则覆盖原value,返回旧VALUE,若之前不存在此key则返回null
V remove(Object key);//从映射中删除给定KV

// Bulk Operations
void putAll(Map<? extends K, ? extends V> m);//将map所含键值对加入此映射
void clear();//清空映射所有键值对

// Views 映射视图
Set<K> keySet();//键集
Collection<V> values();//值数组
Set<Map.Entry<K, V>> entrySet();//entry集
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();

public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}

public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}

public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}

public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}

// Comparison and hashing
boolean equals(Object o);
int hashCode();

// Defaultable methods
default V getOrDefault(Object key, V defaultValue) {//给定key获取对应的value,没有返回给定defaultValue
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
default void forEach(BiConsumer<? super K, ? super V> action) {//迭代处理映射中的键值对
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch (IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}

default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {//在所有映射项上应用函数,替换值为处理的非空结果,若结果为null,删除对应键
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch (IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}

// ise thrown from function is not a cme.
v = function.apply(k, v);

try {
entry.setValue(v);
} catch (IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}

default V putIfAbsent(K key, V value) {//只有当key已存在时才替换value
V v = get(key);
if (v == null) {
v = put(key, value);
}

return v;
}

default boolean remove(Object key, Object value) {//移除键值对
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}

default boolean replace(K key, V oldValue, V newValue) {//当和给定参数等值的键值对存在时,替换新的value
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}

default V replace(K key, V value) {//当键存在并映射到某个值时,替换为新的映射项,替换成功返回原值,替换失败返回NULL
//等价于 if (map.containsKey(key)) { return map.put(key, value); } else return null;
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {//相比注释的写法,这种写法强行多出一个局部变量,我还以为这样写有什么深意,转为字节码看了一下,性能上会差一丢丢局部变量的存读,没有明白这样写的好处是什么,只能猜测是历史原因或编程习惯,如果有知道可以联系告知我,万分感谢。
curValue = put(key, value);
}
return curValue;
}


default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {//若key不与非空v关联,将函数应用到key,将key和结果关联,返回结果,若结果为null,则删除此key,返回null
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}

return v;
}

default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {//若key与非空v关联,将函数应用到key和v,将key和结果关联,返回结果,若结果为null,则删除此key,返回null
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}

default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {//将函数应用到key和get(key),将key和结果关联,返回结果,若结果为null,则删除此key,返回null
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);

V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}

default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {//若key与非空v关联,则将函数应用到value和v上,将结果和key关联,若结果为null,则删除此key。若没有关联的v,则关联key和value
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if (newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
}

2.2 映射视图

在集合框架中映射并不能算作是集合,其它数据结构框架认为映射是一个键值对集合。但映射可以获取其视图view,就是实现了Collection接口的对象。

1
2
3
4
// Views
Set<K> keySet(); //键集视图,非HashSet或TreeSet,可以删除但不能新增元素
Collection<V> values(); //值集合视图,可以删除但不能新增元素
Set<Map.Entry<K, V>> entrySet(); //键值对集视图,可以删除但不能新增元素

这三个视图就是映射中的集合部分。


第三节 SortedMap

有序映射接口,和SortedXX系列一样,相较xx具有有序性。映射比较的是Key,前面有提到不会对value进行处理。

1
2
3
4
5
6
7
8
9
10
11
public interface SortedMap<K,V> extends Map<K,V> {
Comparator<? super K> comparator();
SortedMap<K,V> subMap(K fromKey, K toKey);
SortedMap<K,V> headMap(K toKey);
SortedMap<K,V> tailMap(K fromKey);
K firstKey();//最小元素
K lastKey();//最大元素
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
}

第四节 NavigableMap

和NavigableXX系列一样,继承SortedMap并声明了便于搜索和遍历的迭代器等。

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 interface NavigableMap<K,V> extends SortedMap<K,V> {
Map.Entry<K,V> lowerEntry(K key);
K lowerKey(K key);

Map.Entry<K,V> floorEntry(K key);
K floorKey(K key);

Map.Entry<K,V> ceilingEntry(K key);
K ceilingKey(K key);

Map.Entry<K,V> higherEntry(K key);
K higherKey(K key);

Map.Entry<K,V> firstEntry();
Map.Entry<K,V> lastEntry();

Map.Entry<K,V> pollFirstEntry();
Map.Entry<K,V> pollLastEntry();

NavigableMap<K,V> descendingMap();

NavigableSet<K> navigableKeySet();
NavigableSet<K> descendingKeySet();

NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);

NavigableMap<K,V> headMap(K toKey, boolean inclusive);
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

SortedMap<K,V> subMap(K fromKey, K toKey);
SortedMap<K,V> headMap(K toKey);
SortedMap<K,V> tailMap(K fromKey);
}


第五节 HashMap

5.1 结构

散列映射HashMap,通过一个Node数组来存储元素,Node是一个单向链表结构,实现了 Map.Entry<K,V> 接口。所以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
38
39
40
41
42
43
44
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {

transient Node<K,V>[] table;//哈希表
transient Set<Map.Entry<K,V>> entrySet;//条目集
transient int size;
transient int modCount;//操作数
int threshold;//再散列阈值 = 容量 * 装填因子
final float loadFactor;//装填因子,决定再再散列

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//当前链表对应哈希码
final K key;//键
V value;//值
Node<K,V> next;//下个节点
......
}

//散列函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
...
}

...

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
}

5.2 简单使用

示例通过Lambda表达式迭代处理键值对,以及合理的进行更新。

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
Map<String,Person> personMap = new HashMap<>();
personMap.put("001",new Person("Mary",17));
personMap.put("002",new Person("Lee",20));
personMap.put("003",new Person("Ada",17));

//通过Lambda表达式迭代打印,replaceAll全部替换为Mary
personMap.forEach((k,v) -> System.out.println("key[" + k + "] value[" + v + "]"));
personMap.replaceAll((k,vo) -> new Person("Mary",18));
personMap.forEach((k,v) -> System.out.println("key[" + k + "] value[" + v + "]"));

//实现姓名计数器
Map<String,Integer> nameMap = new HashMap<>();
nameMap.put("Michael",0);
nameMap.put("Lay",0);
nameMap.put("Amanda",0);
nameMap.forEach((k,v) -> System.out.println("key[" + k + "] value[" + v + "]"));

//put更新
//System.out.println("put更新");
//nameMap.put("Michael",nameMap.get("Michael")+1);
//nameMap.put("Jack",nameMap.get("Jack")+1);//当key不存在时get返回null,所以抛出异常java.lang.NullPointerException
//nameMap.forEach((k,v) -> System.out.println("key[" + k + "] value[" + v + "]"));

//put+getOrDefault更新
System.out.println("put+getOrDefault更新");
nameMap.put("Michael",nameMap.getOrDefault("Michael",0)+1);
nameMap.put("Jack",nameMap.getOrDefault("Jack",0)+1);
nameMap.forEach((k,v) -> System.out.println("key[" + k + "] value[" + v + "]"));

//putIfAbsent+put更新,putIfAbsent已有键值不会覆盖
System.out.println("putIfAbsent+put更新");
nameMap.putIfAbsent("Michael",0);
nameMap.put("Michael",nameMap.get("Michael")+1);
nameMap.putIfAbsent("Jack",0);
nameMap.put("Jack",nameMap.get("Jack")+1);
nameMap.forEach((k,v) -> System.out.println("key[" + k + "] value[" + v + "]"));

//merge更新,可以把更新行为参数化传递
System.out.println("merge更新");
nameMap.merge("Michael",1,Integer::sum);
nameMap.merge("Jack",1,Integer::sum);
nameMap.forEach((k,v) -> System.out.println("key[" + k + "] value[" + v + "]"));

执行结果如下:

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
key[001] value[name: Mary age: 17]
key[002] value[name: Lee age: 20]
key[003] value[name: Ada age: 17]
key[001] value[name: Mary age: 18]
key[002] value[name: Mary age: 18]
key[003] value[name: Mary age: 18]

key[Lay] value[0]
key[Michael] value[0]
key[Amanda] value[0]

put+getOrDefault更新
key[Lay] value[0]
key[Michael] value[1]
key[Jack] value[1]
key[Amanda] value[0]

putIfAbsent+put更新
key[Lay] value[0]
key[Michael] value[2]
key[Jack] value[2]
key[Amanda] value[0]

merge更新
key[Lay] value[0]
key[Michael] value[3]
key[Jack] value[3]
key[Amanda] value[0]

5.3 怎么get

  1. 首先计算键对应的哈希码。
  2. 然后通过哈希码直接根据数组索引找到对应桶(链表),并判断首节点是否命中。
  3. 未命中则遍历链表查询键。

所以我们可以算一下get方法的时间复杂度,已知数组的随机访问时间复杂度是O(1),这是硬件保证的,然后理想状况下,也就是散列均匀的情况下,首节点就应该是所找元素,而链表的存在是为了解决哈希冲突,如果不考虑哈希冲突时最终复杂度仍是O(1)。

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
public V get(Object key) {
Node<K,V> e;
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;
// 排查Node数组为空或表长为0,数组上链表首节点为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 检查首节点哈希值,然后检查首节点键是否相等,是则命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 移到下个节点
if ((e = first.next) != null) {
//判断是否已裂变为红黑树,是就调用树API获取节点
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//否则循环遍历链表,查找对应Node节点
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

5.4 怎么计算哈希码

调用key的 hashcode() 得到原始的哈希码,然后把32位的整型h右移了16位,再和h做一次异或运算,这样操作的结果是高区16位保持不变,低区16位混合了原高区和低区16位

为什么要这样做?在取数组索引时会进行此运算:(n - 1) & hash ,因为n不够大(无法达到2^16),高区16位基本会被屏蔽,所以失去了高区特征的哈希码发生碰撞的几率会变大。通过将原高位特征与低位合并从而使散列更均匀。

1
2
3
4
5
6
7
static final int hash(Object key) {
int h;
//>>>表示无符号右移,也叫逻辑右移,即若该数为正,则高位补0,而若该数为负数,则右移后高位同样补0
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

first = tab[(n - 1) & hash]

5.5 怎么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
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

static final int TREEIFY_THRESHOLD = 8;//红黑树优化的阈值

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//哈希表未初始化,则先初始化,并返回哈希表长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根据哈希码得到对应索引的桶,若桶还为空,则直接以value创建Node链
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//对应桶已有链表
else {
Node<K,V> e; K k;
//检查首节点哈希码,并判断首节点是否命中键(==或equals),命中则获取首节点引用
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//首节点未命中则判断是否已裂变为红黑树,若是则用树API获取节点
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);
// -1 for 1st 若已执行到阈值,替换指定下标处所有链接节点,把链表升级为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//取得节点非空,判断当前节点是否即要找的映射,若是则跳出循环,已获取节点引用
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;//移动链表指针
}
}
//e不为空则表示命中,替换value,并返回oldValue
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//操作数更新
++modCount;
//若此时元素数超过阈值,则扩容resize并rehash再散列
if (++size > threshold)
resize();
//红黑树则还需要再平衡
afterNodeInsertion(evict);
return null;
}

5.6 怎么扩容

当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
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
final Node<K,V>[] resize() {
//首先获取旧表信息
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//当旧容量大于0时
if (oldCap > 0) {
//且旧容量大于等于最大容量时,阈值取最大整型,直接返回哈希表,扩容失败
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//且旧容量未到最大容量,新容量和新阈值都为旧值2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// initial capacity was placed in threshold
// 旧容量小于等于0,且旧阈值大于0,则新容量即为旧阈值
else if (oldThr > 0)
newCap = oldThr;
// zero initial threshold signifies using defaults
// 否则都设置为初始值
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

//若此时新阈值仍为0,则重新计算
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//创建新的Node数组,并更新table指向新数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//转移:遍历旧哈希表并重新散列元素到新哈希表
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//先断开与旧哈希表的链接
oldTab[j] = null;
//如果e是链表尾节点,将e再散列后链接到新哈希表
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果e是红黑树节点,则拆开树节点
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// preserve order 如果桶存在一条链表,则分割为两条链表,一条保持大小
else {
//lo和hi分别对应不需要再散列和需要再散列的节点
//lo表示一条链表,该链表在新数组中的下标不变
Node<K,V> loHead = null, loTail = null;
//hi表示一条链表,该链表在新数组中的下标比原来增加oldCap
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//通过next指针循环遍历链表,并把head和tail分别指向首尾节点
//将原来的整条链表拆分成两个链表,一个是在新数组中位置不变的,另一个是在新数组中的位置是旧数组中的位置增加oldCap
do {
next = e.next;
//原数组中计算key在数组中的位置:hash&(oldCap-1)
//新数组为:hash&(2*oldCap-1)=hash&(oldCap<<1 - 1)
//所以如果hash对应在oldCap中的最高位为0,则hash&(oldCap-1)==hash&(2*oldCap-1),即在新数组中位置不变
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//lo组合,将loHead首节点节点链接到新哈希表
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//hi组合,将hiHead首节点节点链接到新哈希表,需要映射到新的下标
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

5.7 怎么裂变为红黑树

当链表节点长度达到阈值 TREEIFY_THRESHOLD 后(即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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

static final int TREEIFY_THRESHOLD = 8;//红黑树优化的阈值

static final int MIN_TREEIFY_CAPACITY = 64;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
//遍历节点链表,直到找到节点或循环结束
for (int binCount = 0; ; ++binCount) {
//取得的下个节点为空,则表示未找到对应键,直接创建新的映射,获取节点引用
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// -1 for 1st 若已执行到阈值,替换指定下标处所有链接节点,把链表升级为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
...
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//若表为空或表长度未达到最小树容量64,只做扩容操作
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//若hash对应索引的桶不为null,则尝试构建红黑树
else if ((e = tab[index = (n - 1) & hash]) != null) {
//hd是头结点,tl则用来串联每个新节点
TreeNode<K,V> hd = null, tl = null;
//循环遍历链表,重新构建一组TreeNode组成的双向链表
do {
//创建一个空红黑树节点
TreeNode<K,V> p = replacementTreeNode(e, null);
//若tl指针为空,当前是首个节点,将新节点赋予hd指针,表示头节点
if (tl == null)
hd = p;
//否则是中间或尾节点,串联前后节点
//将p前驱节点指针指向tl(上个节点),tl下个节点指向新树节点
else {
p.prev = tl;
tl.next = p;
}
//更新tl指向当前节点
tl = p;
} while ((e = e.next) != null);
//循环后还未形成红黑树
//若头节点非空,更新数组对应索引指向新头节点,并调用TreeNode.treeify组建红黑树
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);
}

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<K,V> prev; // needed to unlink next upon deletion
boolean red;
...

/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//遍历新的“双向链表”,一个个的重新插入红黑树,并平衡
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {//循环刚开始初始化
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//内层循环,尝试将当前节点x插入合适位置,并平衡红黑树
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
//p的哈希码大于x的哈希码
if ((ph = p.hash) > h)
dir = -1;
//p的哈希码小于x的哈希码
else if (ph < h)
dir = 1;
//p的哈希码等于x的哈希码,且x的键类和p的键类不可比较时,则通过System.identityHashCode获取二者的比较大小-1或1。
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
//x的键类未实现Comparable接口,或x的键类不等于p的键类
dir = tieBreakOrder(k, pk);

TreeNode<K,V> xp = p;
//根据p和x哈希码大小决定左右子节点,当子节点为空,
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//p哈希码大于x时跳至右子节点,小于时跳至左子节点
//x父节点为p
x.parent = xp;
//p的左/右子节点为x
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//插入后平衡二叉树
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}

static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//每次都默认为红节点
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
}

5.8 旧版本的问题

以上内容基于JDK 1.8版本,相比旧版本的HashMap优化了一些问题:

  1. 优化了高位运算的hash算法,通过移位异或:h^(h>>>16),融合了高位的特征
  2. 有数组+链表的结构优化为数组+链表+红黑树。当拉链过长时链表就会转换为红黑树,优化拉链过长时的查询效率。
  3. 新版本中的扩容通过上述源码可以得知,元素要么保持下标j不变,要么就是j + oldCap,链表的顺序也不会改变,不需要重新计算hash,只需要根据原来hash值新增的bit是1还是0分别放进两个链表lo和hi(非红黑树的情况)里,0的话索引没变,1的话索引变为原索引加原来的数组长度。
    • 旧版本扩容时需要重新计算哈希码,新增元素时是头插法(新元素next指向老元素),第二个线程会覆盖掉第一个线程的值,使第一个线程的值丢失,也可能会因为第一个线程刚读到e和next就挂起,此时e指向a1,next指向a2,第二个线程执行,并使链表变为a2.next = a1,此时第一个线程恢复运行,e和next分别指向a1和a2,再继续执行就又生成了反向的链路,导致了单向循环链表
    • 而新版因为用的尾插法所以新数组链表不会倒置,多线程下不会出现死循环。

第六节 WeakHashMap

若映射中存储的值,其键已经过了最后一次调用,若其是对象则GC会回收,但映射中的键值对并不会被回收。垃圾回收器跟踪活动的对象,只要映射对象是活动的,其中所有的桶也是活动的,它们不能被回收,如果想要回收映射中的无用对象需要有程序负责从长期存活的映射表中删除那些没用的值。

弱散列映射,WeakHashMap,当对键的唯一引用来自于散列条目时,映射会和垃圾回收器协同删除键值对

WeakHashMap怎么实现对无用对象的回收?

  • WeakHashMap通过弱引用(weak references)来保存键,WeakReference对象将引用保存到另外一个对象中,对于WeakHashMap就是散列键。
  • 对于此类对象,GC有一种特殊的方式来处理,普通的对象如果引用已没有调用,GC会回收此对象,若对象由WeakReference引用,GC仍会回收它,但会将引用此对象的弱引用放入队列中,WeakHashMap会周期性的检查此队列,去找出新添加的弱引用,若找到弱引用则表示此键已不再被使用,WeakHashMap就会删除此条目。
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
public class WeakHashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V> {

Entry<K,V>[] table;
private int size;
private int threshold;
private final float loadFactor;
private final ReferenceQueue<Object> queue = new ReferenceQueue<>();//引用队列
int modCount;

private Entry<K,V>[] newTable(int n) {
return (Entry<K,V>[]) new Entry<?,?>[n];
}

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {//相比HashMap的Node,WeakHashMap的Entry继承了弱引用类
V value;
final int hash;
Entry<K,V> next;

/**
* Creates new entry.
*/
Entry(Object key, V value,
ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) {
super(key, queue);
this.value = value;
this.hash = hash;
this.next = next;
}
...
}

...

//会在size和resize等方法中被调用
private void expungeStaleEntries() {//帮助GC消除无用的条目
for (Object x; (x = queue.poll()) != null; ) {
synchronized (queue) {//获取队列的私有锁,同步迭代queue
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) x;//要清理的垃圾对象e
int i = indexFor(e.hash, table.length);//获取hash值对应的坐标index

Entry<K,V> prev = table[i];//根据坐标获取条目prev
Entry<K,V> p = prev;
while (p != null) {//循环遍历坐标对应的entry链表
Entry<K,V> next = p.next;
if (p == e) {//找到链表中的此对象,修正链表
if (prev == e)
table[i] = next;
else
prev.next = next;
// Must not null out e.next;
// stale entries may be in use by a HashIterator
e.value = null; // Help GC 回收强引用的value
size--;
break;
}
prev = p;
p = next;
}
}
}
}
}


public class WeakReference<T> extends Reference<T> {//弱引用接口

public WeakReference(T referent) {
super(referent);
}

public WeakReference(T referent, ReferenceQueue<? super T> q) {
super(referent, q);
}
}

第七节 LinkedHashMap

链接散列映射,采用访问顺序,而不是插入顺序,对映射条目进行迭代。每次调用get或put,受到影响的条目会从当前位置删除,放到条目链表的尾部,注意只是链表的位置而非散列表的桶。

为什么访问顺序会在某些场景下很重要?访问顺序对于实现高速缓存的应用场景下遵守的最近最少使用很重要,如频繁访问的元素放在内存,很少访问的元素放到数据库。

重写removeEldestEntry方法,使其返回true,在put方法返回true时就会移除哈希表中最老的键值

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
public class LinkedHashMap<K,V> extends HashMap<K,V>
implements Map<K,V>{

static class Entry<K,V> extends HashMap.Node<K,V> {//继承Node,但Entry是双向的
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
transient LinkedHashMap.Entry<K,V> head;//首节点
transient LinkedHashMap.Entry<K,V> tail;//尾节点
final boolean accessOrder;//用来标识是否进行迭代排序

public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}

void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)//e为首节点,则将e.after更新为首节点
head = a;
else//e不是首节点,则链接e.before到e.after
b.after = a;
if (a != null)//e不是尾节点,则链接e.after到e.before
a.before = b;
else//e是尾节点,则将e.before更新为尾节点
last = b;
if (last == null)//尾节点还为空,说明此时只有节点e和e.before,更新首节点为e.before
head = p;
else {//尾节点不为空,链接e和尾节点的两个方向
p.before = last;
last.after = p;
}
tail = p;//更新尾节点
++modCount;
}
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {//当返回true时,删除eldest条目,添加一个新条目
return false;//return size() > x; 覆盖此方法实现自动定义大小,当条目数达到时自动删除元素。
}

void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {//首节点就是最老被访问节点
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}

}

第八节 TreeMap

树映射,当需要顺序读取键值对时可以考虑使用。

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
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{

//比较器,用来对树映射进行排序,如果使用键的自然顺序则为空
private final Comparator<? super K> comparator;
//根节点
private transient Entry<K,V> root;
//树的节点数
private transient int size = 0;
//操作数
private transient int modCount = 0;

private static final boolean RED = false;
private static final boolean BLACK = true;
//树节点-红黑树实现
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
//布尔值对应红黑,新节点默认为黑
boolean color = BLACK;

......

public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;

return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}

public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
......
}

//空构造器
public TreeMap() {
comparator = null;
}

//带比较器的构造器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}

//带映射的构造器
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}

//带有序映射的构造器
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}

...
}

8.1 怎么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
46
47
48
49
50
51
52
53
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
//为了提高性能,卸载了基于比较器的版本
//比较器不为空,则换getEntryUsingComparator比较器版本
if (comparator != null)
return getEntryUsingComparator(key);
//键为空,抛出空指针异常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
//循环遍历树
while (p != null) {
//比较键大小
int cmp = k.compareTo(p.key);
//所需键小于当前节点键,向左查询
if (cmp < 0)
p = p.left;
//所需键大于当前节点键,向右查询
else if (cmp > 0)
p = p.right;
//等于直接返回
else
return p;
}
//未找到
return null;
}

//根据比较器查询,过程一致,区别在调用了自定义的比较器
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}

8.2 怎么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
final int compare(Object k1, Object k2) {//给定比较器或键默认比较方法
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}

public V put(K key, V value) {
Entry<K,V> t = root;
//若根节点为空,创建节点,初始化树
if (t == null) {
//类型检查,可能为空
compare(key, key); // type (and possibly null) check

root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths 拆分比较器和可比较路径
Comparator<? super K> cpr = comparator;
//若比较器不为空,循环遍历查找键
if (cpr != null) {
//循环遍历树,查找所给键对应节点,若找到则直接赋值,找不到最后为null
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}//未指定比较器,则用键默认的比较方法,循环遍历查找键
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
//未找到键,parent是遍历到最后的节点
//新建节点
Entry<K,V> e = new Entry<>(key, value, parent);
//根据新节点和最后节点的大小决定放在左边还是右边
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//插入后维持红黑树的平衡
fixAfterInsertion(e);
//更新节点数目和操作数
size++;
modCount++;
return null;
}

8.3 怎么remove

若删除的节点是唯一节点,则清空根节点。

若删除的节点没有子节点,则断开和父节点的双向链接。

若删除的节点有子节点,则先找到右边大于此节点的最小值,若无则找到

将找到的节点直接切出并替换在要删除的节点位置

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
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;

V oldValue = p.value;
deleteEntry(p);
return oldValue;
}

/**
* Delete node p, and then rebalance the tree.
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;

// If strictly internal, copy successor's element to p and then make p
// point to successor.
//若p左右节点都不为空,则找到p的右子树大于p的最小节点,并把p替换为此节点
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children

// Start fixup at replacement node, if it exists.
//replacement优先取左节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);

//replacement不为空
if (replacement != null) {
// Link replacement to parent
//更新replacement的父节点为p的父节点
replacement.parent = p.parent;
//若p的父节点为空,则更新根节点为replacement
if (p.parent == null)
root = replacement;
//把p替换为replacement
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;

// Null out links so they are OK to use by fixAfterDeletion.
//清空链接,以便可以通过fixAfterDeletion使用它们。
p.left = p.right = p.parent = null;

// Fix replacement
//若p为黑节点,则调用fixAfterDeletion
if (p.color == BLACK)
fixAfterDeletion(replacement);
}
//replacement为空,且p父节点为空,则p是唯一节点,更新root返回
else if (p.parent == null) { // return if we are the only node.
root = null;
}
//有父节点,但没有子节点,
else { // No children. Use self as phantom replacement and unlink.
//若p为黑节点,则调用fixAfterDeletion
if (p.color == BLACK)
fixAfterDeletion(p);

if (p.parent != null) {
//清除和父节点的链接
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}

/**
* Returns the successor of the specified Entry, or null if no such.
* 若t有右节点,则找到右子树大于t的最小节点,
* 若t没有右节点,则向左上方向,找到能找到的最后的节点的父节点,最右的子节点找到null
*/
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
//t右节点不为空,则顺着t的右节点的左方向迭代返回最后一个左节点,即大于t的最小节点
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
}
//否则,顺着t的左上方向能找到的最后的值的父节点并返回,即小于t的最小节点
else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}

8.3 红黑树维持平衡

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;

//当节点不为空,且不为根节点,且父节点为红节点则循环
while (x != null && x != root && x.parent.color == RED) {
//当x的父节点等于x的父父节点的左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
//获取x的父父节点的右节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//若y为红节点
if (colorOf(y) == RED) {
//更新父节点为黑节点,y为黑节点,x的父父节点为红节点
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
//并更新x为父节点的父节点
x = parentOf(parentOf(x));
}
//若y为黑节点
else {
//且x等于父节点的右节点,则更新x为其原父节点
//将(x)节点转移到比它大的右节点的左下方,作为原左下方节点的父节点,原左下方节点则变更为节点的右下节点
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
//更新x的父节点为黑节点
setColor(parentOf(x), BLACK);
//更新x的父节点的父节点为红节点
setColor(parentOf(parentOf(x)), RED);
//将(x的父父节点)节点转移到比它小的做节点的右下方,作为原右下方节点的父节点,原右下方节点则变更为节点的左下节点
rotateRight(parentOf(parentOf(x)));
}
}
//若x的父节点不等于父父节点的左节点
else {
//y为x的父节点的父节点的左节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//若y为红节点
if (colorOf(y) == RED) {
//更新x的父节点为黑节点,更新y为黑节点,更新x的父父节点为红节点
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
//更新x为原x的父父节点
x = parentOf(parentOf(x));
}
//若y为黑节点
else {
//且x等于x父节点的左节点
if (x == leftOf(parentOf(x))) {
//则把x更新为x的父节点
x = parentOf(x);
//将(x)节点转移到比它小的做节点的右下方,作为原右下方节点的父节点,原右下方节点则变更为节点的左下节点
rotateRight(x);
}
//将x的父节点更新为黑节点,x的父父节点更新为红节点
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
//将(x的父父节点)节点转移到比它大的右节点的左下方,作为原左下方节点的父节点,原左下方节点则变更为节点的右下节点
rotateLeft(parentOf(parentOf(x)));
}
}
}
//循环结束,更新根节点为黑节点
root.color = BLACK;
}

//将节点转移到比它大的右节点的左下方,作为原左下方节点的父节点,原左下方节点则变更为节点的右下节点
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
//r为p的右节点
Entry<K,V> r = p.right;
//p的右节点更新为r的左节点
p.right = r.left;
//若r的左节点不为空,则把r左节点的父节点更新为p
if (r.left != null)
r.left.parent = p;
//更新r的父节点为p的父节点
r.parent = p.parent;
//若p的父节点为空,p为原根节点,则更新根节点为r
if (p.parent == null)
root = r;
//根据p是左或右边节点,替换为r
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
//r的左节点更新为p,p的父节点更新为r
r.left = p;
p.parent = r;
}
}

//将节点转移到比它小的做节点的右下方,作为原右下方节点的父节点,原右下方节点则变更为节点的左下节点
private void rotateRight(Entry<K,V> p) {
if (p != null) {
//l为p的左节点
Entry<K,V> l = p.left;
//更新p的左节点为l的右节点
p.left = l.right;
//若l的右节点不为空,则把p更新为其父节点
if (l.right != null) l.right.parent = p;
//更新l的父节点为p的父节点
l.parent = p.parent;
//若p为根节点,则更新为l
if (p.parent == null)
root = l;
//根据p是左或右边节点,替换为l
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
//更新l的右节点为p,p的父节点更新为l
l.right = p;
p.parent = l;
}
}

private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));

if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}

if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
Entry<K,V> sib = leftOf(parentOf(x));

if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}

if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}

setColor(x, BLACK);
}


第九节 EnumMap

枚举映射即一个键类型为枚举类型的映射,其由一个值数组来实现。

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
public class EnumMap<K extends Enum<K>, V> extends AbstractMap<K, V>
implements java.io.Serializable, Cloneable{

private final Class<K> keyType;//键对应枚举类型
private transient K[] keyUniverse;//键集合
private transient Object[] vals;//值集合
private transient int size = 0;//条目数目
private static final Object NULL = new Object() {
public int hashCode() {
return 0;
}

public String toString() {
return "java.util.EnumMap.NULL";
}
};

public EnumMap(Class<K> keyType) {
this.keyType = keyType;
keyUniverse = getKeyUniverse(keyType);
vals = new Object[keyUniverse.length];
}

...
}

第十节 IdentityHashMap

表示散列映射,键的散列值并不是用hashcode函数来计算的,而是System.identityHashCode()。且比较两个对象时,IdentityHashMap通过==比较而不是equals。

扩展:equals和hashCode异同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class IdentityHashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, java.io.Serializable, Cloneable{

transient Object[] table; // non-private to simplify nested class access
int size;
transient int modCount;
static final Object NULL_KEY = new Object();

private static int hash(Object x, int length) {//Object.hashCode方法根据对象的内存地址来计算散列码
int h = System.identityHashCode(x);
// Multiply by -127, and left-shift to use least bit as part of hash
return ((h << 1) - (h << 8)) & (length - 1);
}


static final int hash(Object key) {//HashMap的hash函数
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

...
}

第十一节 Hashtable

Hashtable和HashMap类作用一致,实现相同的接口,类似Vector,Hashtable的方法也都通过synchronized锁同步。

Hashtable对部分方法加了synchronized,来保证线程安全。根据源码可知Hashtable的键值都不允许为空

对同步没有要求就使用HashMap,单线程环境下效率很高,若需要并发特性则使用ConcurrentHashMap,而不要使用Hashtable,虽然其保证了一定的线程安全,但效率并不高。

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
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {

private transient Entry<?,?>[] table;
private transient int count;
private int threshold;
private float loadFactor;
private transient int modCount = 0;

public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}

// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}

addEntry(hash, key, value, index);
return null;
}
}

11.1 属性映射

Properties,其特性:键值都是字符串,表可以保存在文件中也可以从文件加载,使用一个默认辅助表

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
public class Properties extends Hashtable<Object,Object> {
protected Properties defaults;
private transient ConcurrentHashMap<Object, Object> map;
public Properties() {
this(null, 8);
}

public Properties(int initialCapacity) {
this(null, initialCapacity);
}

private Properties(Properties defaults, int initialCapacity) {
// use package-private constructor to
// initialize unused fields with dummy values
super((Void) null);
map = new ConcurrentHashMap<>(initialCapacity);
this.defaults = defaults;
}

...

public String getProperty(String key) {//获得键对应值,若映射不存在,则获取默认表中键对应值
Object oval = map.get(key);
String sval = (oval instanceof String) ? (String)oval : null;
return ((sval == null) && (defaults != null)) ? defaults.getProperty(key) : sval;
}
public String getProperty(String key, String defaultValue) {//获得键对应值,若没找到则返回默认字符串
String val = getProperty(key);
return (val == null) ? defaultValue : val;
}

public synchronized void load(Reader reader) throws IOException {//从Reader加载属性映射
Objects.requireNonNull(reader, "reader parameter is null");
load0(new LineReader(reader));
}
public synchronized void load(InputStream inStream) throws IOException {//从流inStream加载属性映射
Objects.requireNonNull(inStream, "inStream parameter is null");
load0(new LineReader(inStream));
}

public void store(OutputStream out, String comments) throws IOException {//将属性映射存入流out
store0(new BufferedWriter(new OutputStreamWriter(out, "8859_1")),
comments,
true);
}
}

第十二节 ConcurrentHashMap

参考ConcurrentHashMap的实现原理与使用


参考博客和文章书籍等:

《Java核心技术 卷Ⅰ》

HashMap与ConcurrentHashMap旧版源码笔记

JAVA HashMap 不同版本的解析

因博客主等未标明不可引用,若部分内容涉及侵权请及时告知,我会尽快修改和删除相关内容