关于 HashMap

Context

关于 HashMap, 有一件事儿一直很困惑,,在『Redis 核心历险』中是这样被提到的:

Redis 的字典相当于 Java 语言中的 HashMap,它是无序字典,内部存储了很多键值对。实现结构上与 Java 的 HashMap 也是一样的,都是”数组 + 链表”二维结构。第一维的 hash 的数组位置碰撞时,就会将碰撞的元素使用链表串接起来

嗯,第一句没啥问题,,然而”数组 + 链表”什么鬼?还有 hash 碰撞。。作者并没有详细解释这儿,应该默认是每个 Java 开发者都知道的知识点了。然而我却在这儿卡壳了,心慌慌。。趁着周末赶紧补补课。事实证明,这波补课是很有效果的,在这本书后边的内容中,hash 还将会一直出现。

Hash

Wiki 中的定义为:

散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到

用我自己的话来说就是,,为数据创建指纹摘要,通过该摘要就可以找到原始数据。我觉得更多的场景是为相对大的数据创建摘要。假如有个 hash(),可以为任意数据生成一个32位的摘要。那么我们在互联网下载文件的时候,有的网站会在下来链接处给出该文件的 hash 值,等用户下载完成之后,通过 hash() 对该文件提取摘要,将两个 hash 值,进行对比。如果结果一样,说明文件在下载过程中没有被篡改。

那倘若我们对数字 1 进行 hash(),那应该也会得到一个长度为 32 位的摘要,但这时候还能叫『摘要』么?我感觉是不太合适的。

HashMap

OK,back to the point..关于 Hash 我们需要知道👇

所有散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果,具有这种性质的散列函数称为单向散列函数。但另一方面,散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同,这种情况称为“散列碰撞(collision)”。

按我之前不成熟的想法,,HashMap 中为什么要放链表?直接放数据对象不就够了么。。原因就是当我们通过 get(key) 方法从 HashMap 中获取对象的时候,理论上这个 key 对应的 hash 值和某个 whateverKey 对应的 hash 值是一样的(即,散列碰撞),,因为『如果两个散列值相同,两个输入值很可能是相同的,但也可能不同(即,key 和 whateverKey)』。此时我们可以通过 key 和 whateverKey 都可以获取到对应的数据对象。如此,为了解决散列碰撞带来的问题,我们需要在 HashMap 中将两个‘key’都指向同一个数据对象,而在 HashMap 中的链表就是用来维护这些‘key’的。下面,我们试着读读 HashMap 源码。

HashMap 的 DOC 注释

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
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267

/**
* Hash table based implementation of the <tt>Map</tt> interface. This
* implementation provides all of the optional map operations, and permits
* <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
* class is roughly equivalent to <tt>Hashtable</tt>, except that it is
* unsynchronized and permits nulls.) This class makes no guarantees as to
* the order of the map; in particular, it does not guarantee that the order
* will remain constant over time.
* 👆散列表也基于对 Map 接口的实现。HashMap 也是对是 Map 接口的实现,提供了所有对 Map 的可选操作(的方法),并且允许 null 值和 null 键。HashMap 大致相当与 HashTable 相同,除了 HashMap 是非同步的,且接受 null。该类不保证数据对象在内部的顺序,同时也不保证内部的顺序是一成不变的。
*
* <p>This implementation provides constant-time performance for the basic
* operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
* disperses the elements properly among the buckets. Iteration over
* collection views requires time proportional to the "capacity" of the
* <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
* of key-value mappings). Thus, it's very important not to set the initial
* capacity too high (or the load factor too low) if iteration performance
* is important.
* 👆HashMap 中 get 和 put 这两项基本操作提供复杂度为常数级别的性能表现,假定 hash 方法把元素均匀的分配到桶中。对整个集合视图进行迭代所需的时间与 HashMap 实例(桶的数量)乘以它的容量(键值对的数量)之积。所以,如果迭代性能很重要的话,不要在初始化 HashMap 的时候设置过高的容量,及太小的负载系数(负载因子)
* * <p>As a general rule, the default load factor (.75) offers a good tradeoff
* between time and space costs. Higher values decrease the space overhead
* but increase the lookup cost (reflected in most of the operations of the
* <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
* expected number of entries in the map and its load factor should be taken
* into account when setting its initial capacity, so as to minimize the
* number of rehash operations. If the initial capacity is greater
* than the maximum number of entries divided by the load factor, no
* rehash operations will ever occur.
* 👆一般,默认的负载系数(0.75)在时间和空间成本之间提供了很好的平衡。更高的值会减少了空间开销,但同时会增加查找成本(反映在 Hashmap 的大多数操作中,包括 get 和 put)。在设置初始容量时,应考虑到 Map 中预期的条目数量及其负载系数,以尽量减少 rehash 的次数。如果初始容量大于最大条目数除以负载系数的值,则不会发生 rehash 操作。
* <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
* creating it with a sufficiently large capacity will allow the mappings to
* be stored more efficiently than letting it perform automatic rehashing as
* needed to grow the table.
* 👆如果要在一个 HashMap 实例中存储多个键值对,那么创建实例时指定足够大的容量将比让它根据需要 rehash 以扩充容量的效率更高。
* <strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a hash map concurrently, and at least one of
* the threads modifies the map structurally, it <i>must</i> be
* synchronized externally. (A structural modification is any operation
* that adds or deletes one or more mappings; merely changing the value
* associated with a key that an instance already contains is not a
* structural modification.) This is typically accomplished by
* synchronizing on some object that naturally encapsulates the map.
* 👆需要注意的是,HashMap 是非线程安全的。如果多线程同时请求访问 HashMap,并且有至少一条线程改变了 HashMap 实例的结构,那么必须在 HashMap 外层对它添加 synchronized 修饰。(结构修改是指任何添加或删除一个或多个键值对的操作;仅更改实例已包含的键关联的值不是结构修改。)(这一句不太懂诶。。。)
* If no such object exists, the map should be "wrapped" using the
* {@link Collections#synchronizedMap Collections.synchronizedMap}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the map:<pre>
* Map m = Collections.synchronizedMap(new HashMap(...));</pre>
* 👆如果这样的对象不存在,则该 HashMap 应该被Collections.synchronizedMap()方法包裹起来。最好在对象初创建的时候就这样做,以免发生不可预知的对 HashMap 的访问。
* <p>The iterators returned by all of this class's "collection view methods"
* are <i>fail-fast</i>: if the map is structurally modified at any time after
* the iterator is created, in any way except through the iterator's own
* <tt>remove</tt> method, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the
* future.
* 👆HashMap 的迭代器返回的这个类的所有集合视图方法都是‘快速失效’的: 所有在迭代器创建之后对 HashMap 进行结构性修改,除了迭代器自己的 remove()方法外,会抛出 ConcurrentModificationException。在面对并发对 HashMap 的修改时,迭代器会快速彻底的失效,而不会选择在之后冒不确定的、未知的风险。
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
* 👆需要注意的是,迭代器的快速失效并不能被保证(一定发生),,通常来讲,在非同步并发修改 HashMap 的情况下,无法(对快速失效)做出硬性保证。迭代器快速失效后会尽最大努力抛出 ConcurrentModificationException 异常。因此,不能依靠是否抛出该异常来确定写的程序是否是正确的:迭代器的快速失效行为只能被用来查明bug。
*/
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

/**
* The default initial capacity - MUST be a power of two.
* HashMap 的默认初始容量--必须是 2 的 N 次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 (Also Known As, 即初始值为 16)

/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
* 最大容量,在带参构造函数中隐式判断指定的容量是否超出最大容量时使用。
* 必须是 2 的 N 次方,且不大于 2^30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* The load factor used when none specified in constructor.
* 构造器未指定负载系数时,使用该默认值
* (当 HashMap 的 size 大于 HashMap 的 capacity * loadFactor 时,HashMap 扩容,即 capacity *= 2,并 rehash())
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* An empty table instance to share when the table is not inflated.
* 在表还没有扩容之前,共享该空数组实例
*/
static final Entry<?,?>[] EMPTY_TABLE = {};

/**
* The table, resized as necessary. Length MUST Always be a power of two.
* 整个表的容量,如果有必要的话(键值对条数/负载系数 >= table.length)会进行扩容。容量大小必须是 2 的幂次方
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/**
* The number of key-value mappings contained in this map.
* map 中键值对的条数
*/
transient int size;

/**
* The next size value at which to resize (capacity * load factor).
* @serial
* 下一次扩容后的大小(容量*负载系数)
*/
int threshold;

/**
* The load factor for the hash table.
* table 的负载系数
* @serial
*/
final float loadFactor;

/**
* 无参构造方法,使用默认初始容量(16),默认负载系数(.75)
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 带参构造方法,指定初始容量为initialCapacity
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 带参构造方法,指定初始容量和负载系数
* 最终所有构造函数都指向该构造函数
*/
public HashMap(int initialCapacity, float loadFactor) {
// 如果指定的初始容量 <0,则抛出不合法参数异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 如果指定的容量大于最大容量,则使用最大容量为初始容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 如果指定的负载系数不大于零或不是浮点数,则抛出不合法参数异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}

/**
* 组建一个与指定 map 相同的 HashMap,使用默认负载系数,初始容量足以盛下该 Map。
*/
public HashMap(Map<? extends K, ? extends V> m) {
// 如果初始容量大于允许的最大容量,则使用最大容量;否则初始容量为指定 Map 的大小除以负载系数后加一
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
// HashMap扩容到指定容量
inflateTable(threshold);

putAllForCreate(m);
}

/**
* Inflates the table.
* 表扩容
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 找到大于 toSize 的最小的2的幂次方的值(因为容量只能为2的幂次方)
int capacity = roundUpToPowerOf2(toSize);
// 下次扩容时创建表的初始大小
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
// 寻找大于某个非负数的的最小的2的幂次方的值(eg. roundUpToPowerOf2(5)=8)
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
// 断言 number 为非负数
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
// 当 number 不小于允许的最大容量时,直接返回最大值;
// 当 number = 1 时,直接返回 1。
// 否则返回 Integer.highestOneBit((number - 1) << 1):
// (number - 1) << 1) = (number - 1)*2
// Integer.highestOneBit(i): 取 i 这个数的二进制形式最左边的最高一位且高位后面全部补零,最后返回int型的结果。

// 假设 number 值为 5;那么十进制 5 减去 1 之后得 4,4 的二进制带符号左移一位,得十进制 8;8 的二进制为:1000;经过 Integer.highestOneBit 处理后值还是 8。
// 假设 number 值为 6,那么十进制 6 减去 1 之后得 5,5 的二进制带符号左移一位,得十进制 10;10 的二进制为 1010;取最高位 1,其余 3 位补零,得 1000,即十进制 8。
}

// 再看看 HashMap 的静态内部类 Entry<K,V>
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
// 只有 next,没有 prev,即单向链
Entry<K,V> next;
int hash;

/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}

// key 的 getter 方法..略
// value 的 getter 方法..略
// value 的 setter 方法
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

// Entry 的 key 和 value 与 o 的 key 和 value 都相等,则return true,否则return false
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}

public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}

public final String toString() {
return getKey() + "=" + getValue();
}

/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}

/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
put() 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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
public V put(K key, V value) {
// 如果这是空表,则首先为表进行扩容,threshold 初始值为 DEFAULT_INITIAL_CAPACITY,即 16
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 为 null
if (key == null)
// 该方法进行的操作与下面对非 null key值的操作逻辑基本一致,只不过是在 for 循环中的 判断条件改为了 e.key == null
return putForNullKey(value);
int hash = hash(key);
// 通过 Hash 值找到在数组中的索引值
int i = indexFor(hash, table.length);
// 遍历索引指向的单向链表,查看 key 在当前 Map 中是否存在
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果 当前 Entry 对象 e 的 hash 值与 key 的 hash 值相等,且 e.key 与 key 相等,则覆盖原有 e.value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果要插入的 key 在 map 中不存在,,
// 结构修改次数 ++
modCount++;
// 在 HashMap 的 Entry 数组中添加新的 Entry 对象
addEntry(hash, key, value, i);
return null;
}

/**
* Returns index for hash code h.
* 找到 hash 值在 table 中的索引值
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
//Integer.bitCount(length) 用于计算十进制 length 值的二进制值中 '1' 的个数;Integer.bitCount(length) == 1,即断言 length 值(HashMap 中Entry<?,?>[]的length,即 HashMap capacity)为 2 的幂次方。

// 刚开始是没有看明白这行代码的,求助搜索引擎之后,才有些眉目。
// 首先,这是按位与操作,,因为 length 值为 2 的幂次方,所以 length - 1后,其二进制的值除高位外全为1(eg. 假设length 值为 8(二进制表现为 1000), 减 1 得 7;7 的二进制为 0111)
return h & (length-1);
}

/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket. It is the responsibility of this
* method to resize the table if appropriate.
* 通过指定的 key、value、hash code 向指定的 bucket 添加一个新的 entry 对象。在适当的时候扩容 table 也是该方法的主要责任。
* Subclass overrides this to alter the behavior of put method.
* 子类重写该方法可以修改 put() 方法的行为。
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果当前 HashMap 的 size 大于等于扩容临界值,且当前 Entry 不为 null 的时候
// 当 table 的 capacity 等于 Integer.MAX_VALUE时,int 类型的 size 最多与 threshold(此时 threshold = Integer.MAX_VALUE)相等,而且 null != table[bucketIndex] 肯定为 true。所以,当 table 达到最大容量后,再调用 put() 会一直覆盖原有的值。
if ((size >= threshold) && (null != table[bucketIndex])) {
// 2 倍扩容
resize(2 * table.length);
// key 为 null,则 hash 值为 0;否则 通过 hash() 方法计算 hash 值
hash = (null != key) ? hash(key) : 0;
// 计算扩容之后 entry 将要被放在的 bucket 索引
bucketIndex = indexFor(hash, table.length);
}
// 实际添加 entry 对象的方法
createEntry(hash, key, value, bucketIndex);
}

/**
* Rehashes the contents of this map into a new array with a
* larger capacity. This method is called automatically when the
* number of keys in this map reaches its threshold.
* Rehash 当前 map 对象到一个新的更大的数组中去;该方法在 map.size() 达到临界值时自动调用
* If current capacity is MAXIMUM_CAPACITY, this method does not
* resize the map, but sets threshold to Integer.MAX_VALUE.
* This has the effect of preventing future calls.
* 如果当前容量达到允许的最大容量时,该方法不会再进行扩容操作,而是直接将临界值设置为 Integer.MAX_VALUE。
* @param newCapacity the new capacity, MUST be a power of two;
* must be greater than current capacity unless current
* capacity is MAXIMUM_CAPACITY (in which case value
* is irrelevant).
*/
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// MAXIMUM_CAPACITY = 2^30,即 oldCapacity 最大值为 2^30
if (oldCapacity == MAXIMUM_CAPACITY) {
// Integer.MAX_VALUE = 2^31 - 1,之后不可能再进行扩容操作了
threshold = Integer.MAX_VALUE;
return;
}

Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
* 本方法与 addEntry() 类似,只不过是用于'伪构造方法时'(克隆、反序列化),而且该方法不用担心扩容的问题~
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
// 在未发生散列碰撞时,e 为 null;否则 e 为 entry 实例
Entry<K,V> e = table[bucketIndex];
// 构建新的Entry对象,并其属性 next 指向 e,,即在发生散列碰撞的情况下,每次添加 entry 实例时,都是 insert(添加到单向链开始位置),而非 append。
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
/**
* Transfers all entries from current table to newTable.
* 将现在的 table 转移到新的 table中
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历原 Entry 数组中所有对象
for (Entry<K,V> e : table) {
// 遍历每个槽位的 entry 单向链
while(null != e) {
// ① 👉 记录下 e.next 先
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 计算 e.hash 在新 entry 数组中 bucket 索引
int i = indexFor(e.hash, newCapacity);
// ② 👉 将原槽位的 entry 单向链添加到当前 e 的 next 属性中。
e.next = newTable[i];
// ③ 👉 将 新数组的指定索引的值 指向 拼接过的新的 entry 单向链。
newTable[i] = e;
// ④ 👉 将之前记录下来的 e.next 值重新赋给 e,开始下一轮循环(类似 for 循环中的 i++)。
e = next;
}
}
}
// 👆 transfer() 方法中 将while 循环转成 for 循环,①、④ 处可能会更好理解一点; ②、③ 位置不太好理解,我也是反复咀嚼了好多遍才大概明白一点。
// eg. 我们假设在索引为 i 的槽位处有个 entry 对象 e0,它链接的 entry 对象结构大概为:e0 -> e1 -> e2 -> e3;现在有个 entry 对象 e,e 的 hash 值在新数组中计算得到的索引值同样为 i(即,散列碰撞);此时需将 e 添加到 e0 的单向链中,③、④ 操作执行过后,该槽位的单向链结构变为:e -> e0 -> e1 -> e2 -> e3。

@加张图片会不会更容易理解些~

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

return null == entry ? null : entry.getValue();
}

/**
* Offloaded version of get() to look up null keys. Null keys map
* to index 0. This null case is split out into separate methods
* for the sake of performance in the two most commonly used
* operations (get and put), but incorporated with conditionals in
* others.
* key 值为 null 的指向 map 中 Entry 数组 index 为 0 的 entry 对象。为了更高的性能表现,在 get 和 put 请求中,key 为 null 的情况被分支出单独的方法来处理,但在其他方法中并没有这样去做。
*/
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}

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

int hash = (key == null) ? 0 : hash(key);
// 遍历指定 index 位置的的单项链
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
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
public V remove(Object key) {
// 直接看关键方法
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
// ①看到这儿时候我是有些懵哔的..
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;

while (e != null) {
Entry<K,V> next = e.next;
Object k;
// ③ 关键在这儿
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
// ②直到看到了这儿,我意识到我刚才懵逼早了...
// 由 ① 很容易得出结论啊,妥妥相等
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}

prev = e;
e = next;
}
return e;
}
// 👆在上面的代码中,如果只看①②,会蒙圈的,,关键在③的分支判断。
// 在发生散列碰撞(由不同的 key,生成了相同的 hash 值)情况下,e.hash == hash 是成立的,但 (k = e.key) == key 或 key.equals(k)就不成立了。
// eg. 如果要删除的单向链节点在链的开头,则直接走 (prev == e) 分支,将 table[i] 指向 其 next 属性的节点;如果要删除的单向链节点位于第二,则在直接将第一个节点的 next 属性指向第 3 个节点即可。
entrySet() 方法
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
/**
* Returns a {@link Set} view of the mappings contained in this map.
* The set is backed by the map, so changes to the map are
* reflected in the set, and vice-versa. If the map is modified
* while an iteration over the set is in progress (except through
* the iterator's own <tt>remove</tt> operation, or through the
* <tt>setValue</tt> operation on a map entry returned by the
* iterator) the results of the iteration are undefined. The set
* supports element removal, which removes the corresponding
* mapping from the map, via the <tt>Iterator.remove</tt>,
* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
* <tt>clear</tt> operations. It does not support the
* <tt>add</tt> or <tt>addAll</tt> operations.
* 返回当前 map 键值对映射的 set 快照(??)。该集合由 map 支持,所以对 map 的修改会反映到 set中,反之亦然。
* 如果 map 在 set 迭代的过程中被修改(除了迭代器本身的remove()和迭代器返回的 map entry的 setValue()操作)话,其结果是未知(??)的。
* set 支持移除元素, Set.remove(),removeAll(), retainAll() 和 clear() 会直接影响到相关的 map。set 不知道 add()和 addAll() 操作。
* @return a set view of the mappings contained in this map
*/
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
(实测,在 for(Map.Entry<String,String> m:map.entrySet()) 循环中,通过 map.put() 方法放入新的值,会抛出 ConcurrentModificationException:👇
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextEntry(HashMap.java:922)
at java.util.HashMap$EntryIterator.next(HashMap.java:962)
at java.util.HashMap$EntryIterator.next(HashMap.java:960)
at Test.main(Test.java:12)
如果放入 map 中已存在的 key,不会抛出 ConcurrentModificationException。)

private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}

到这里之后是有点儿懵的,,因为 entrySet0() 方法中第一行代码,entrySet在 HashMap 中是这样声明的:👇

1
private transient Set<Map.Entry<K,V>> entrySet = null;

之后在其他地方没有明确对其进行赋值的代码,然鹅我们在 Test 类进行 for(Map.Entry<String,String> m: map.entrySet()) 循环时,entrySet明明是有值的。那么 map.entrySet() 到底是在什么时候进行赋值的呢?!这个问题困扰了我很久,在 HashMap 显式继承的 AbstractMap 类和实现的 Map<K,V> 接口中,也没有找到答案。出门遛了一圈,突然想到了 Test 类被编译之后的 class 文件!!然后用 JD-JUI 反编译之后,终于有些发现了:👇

1
2
// class 文件反编译之后的 forEach 循环
for (Iterator i$ = map.entrySet().iterator(); i$.hasNext(); localEntry = (Map.Entry)i$.next())

👆我们可以看到,虽说用的是 forEach 循环,但在编译之后还是通过 Iterator 迭代器进行遍历的。首先初始条件 Iterator i$ = map.entrySet().iterator(),我们可以看到 map.entrySet() 返回的是一个 Set<Map.Entry<K,V>>,所以其 iterator()Set 接口实现类的 iterator() 方法。我们继续看 entrySet0() 方法的第二行代码,在 entrySet 为空的情况下,会初始化一个新的 Set<Map.Entry<K,V>> 对象,即 new EntrySet(),我们看看 EntrySet 类:👇

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
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
// EntrySet 类集成了 AbstractSet 类,而 AbstractSet 类又实现了 Set<E> 接口,那么 EntrySet 类中的 iterator() 方法就是我们要找的。我们继续顺着往下看 newEntryIterator :👇
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
// 形式渐渐明朗,,再看 nextEntry()
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry

HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}

public final boolean hasNext() {
return next != null;
}

final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();

if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}

public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
// 至此,所有问题解决~ 在 Iterator i$ = map.entrySet().iterator() 中,i$ 为 HashIterator,i$.hasNext() 调用的是 HashIterator.hasNext(),(Map.Entry)i$.next() 调用的是 EntryIterator.next(),而 EntryIterator.next() 最终还是调用了 HashIterator.nextEntry()。

<<<<<<<<<<<< 2019-04-02.update

上个月末的时候,花了一个晚上更新了下简历,但并没有到处去投,只是对外可见。陆陆续续开始有公司接触,其中还接到一个电话面试,,是某外包公司的。突如其来的电话面试,有点仓促,但好在前端时间也一直在看书恶补。其中有个很基础的问题,,『简单说下 Java 集合框架各容器类之间的关系』。多亏了学习 『Redis 核心历险』时,对 LinkedList 多看了一眼,也经受住了超越妹妹的考验。当中面试官特地提到 MapCollection 有没有关系? 可以确定是肯定有关系,但有什么关系呢?没有答上来。。那时还没有整理 HashMap 这篇文章,只有 LinkedList。其实在整理这篇文章时也没找到两者之间的关系,因为 interface Map<K,V>interface Collection<E>并没有直接的继承关系。。这时候需要感谢的是『码出高效 Java 开发手册』了,平时把这本书放在了床头,睡前会翻一翻从此再无失眠,并没有从第一张开始读,而是直接挑了最薄弱的数据结构与集合这一章。

OK,下面来说说 MapCollection 的关系!在书中是这样描述的: 👇

在数据元素的存储、查找、修改和遍历中,Java 中的 Map 类集合都与 Collection 类集合存在很大的不同。它是与 Collection 类平级的一个接口,在集合框架图上,它有一条微弱的依赖线月 Collection 类产生联系,那是因为部分方法返回 Collection 视图,比如 values() 方法返回的所有 values 的列表

我们先看 Map 接口的 values() 方法:👇

1
2
// Map 接口类
Collection<V> values();

非常明显,,说到values()方法,肯定会想到 keySet()entrySet() ,毕竟这三个方法在 HashMap 迭代的时候可是肩并肩的~👇

1
2
3
// Map 接口类
Set<K> keySet();
Set<Map.Entry<K, V>> entrySet();

我们再看看,这三个方法在 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
// values 方法
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
// Values 类,AbstractCollection 类实现类了 Collection 接口
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
// keySet 方法
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
// KeySet 类,abstract class AbstractSet<E> 继承了 AbstractCollection<E> 实现了 Set<E>,而抽象类 AbstractCollection 和 Set 接口 都继承了 Collection 接口。
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
// 至于 entrySet() 方法,我们在分析 HashMap 的 forEach 循环时已经挖过源码了。EntrySet 类与 KeySet 类一样,都继承了 AbstractSet 抽象类。

  1. 米一–Hash表的前世今生
  2. 追逐盛夏流年–HashMap中的indexFor方法分析
  3. March@dhyin.top–hashmap的实现原理 数组 entry
  4. 哈希拉链法
  5. 贝壳风铃–Java遍历HashMap并修改(remove)