实现一个简单的HashMap

概述


  HashMap是基于哈希表的Map接口的实现,以key-value的形式存在,在HashMap中,key-value会被当成一个整体(Entry)来处理,HashMap内部维护了一个链表数组,会根据hash算法来计算key-value在数组中的存储位置.

HashMap的内部结构


  HashMap内部使用了桶(bucket)来存储键值对,桶就是一个存储key-value的链表.而HashMap中维护了一个数组,这个数组的每个元素就是一个桶(bucket),在HashMap中,桶是使用链表实现的.

  • HashMap使用散列函数(hash)将给定键转化为一个数组索引(桶号),不同的key会被转化为不同的索引,实际中有几率会把不同的键转化为同一个索引,这种情况叫做hash碰撞,HashMap使用了拉链法解决hash碰撞.

  • 当发生hash碰撞时,会生成一个新的key-value对象,并将新对象挂在链表头部.

  • 得到数组索引后,就可以遍历这个链表来进行各种操作了.

  在HashMap中有2个重要的参数:capaCity(容量),loadFactor(负载因子).

  • 容量:它表示HashMap中桶的数量.

  • 负载因子:它是HashMap在其容量自动扩容之前可以达到多满的一种尺度,它衡量的是一个散列表的空间使用程度,负载因子越大表示散列表的空间利用率越大,反之越小.对于使用拉链法的散列表来说,查找一个元素的平均时间是O(1+a),因此负载因子越大,对空间的利用越充分,但是查找效率就会越低,如果负载因子很小,那么散列表的空间利用率将会很小,对空间造成严重浪费,但是查找效率则会变快.HashMap中负载因子的默认值为0.75.

  • 阈值:容量自动扩展的阈值,当HashMap中的键值对数量到达阈值时,将会进行自动扩容(当前容量x2),阈值通常的计算方法为 capaCity * loadFactor.

简单实现


construction

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
/**
* 构造一个空的SimpleHashMap,使用默认的capacity和负载因子
*/
public SimpleHashMap(int initialiCapacity, float loadFactor) {
if (initialiCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialiCapacity);
if (initialiCapacity > MAXIMUM_CAPACITY)
initialiCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
//计算出大于initialCapacity的最小的2的n次方值
int capacity = 1;
while (capacity < initialiCapacity) {
capacity <<= 1;
}
this.loadFactor = loadFactor;
//设置HashMap的扩容阈值,当到达这个阈值时会进行自动扩容
threshold = (int) (capacity * loadFactor);
//初始化table数组
table = new Node[capacity];
}

  其中table是一个Node数组,它是由链表实现的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final String toString() {
return key + "=" + value;
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?, ?> e = (Entry<?, ?>) o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue())) {
return true;
}
}
return false;
}
}

put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public V put(K key, V value) {
//如果key为null,调用putForNullKey()向null key存入value
if (key == null)
return putForNullKey(value);
//计算key的hash
int hash = hash(key.hashCode()); ---1
//计算key的hash在table数组中的索引
int i = indexFor(hash, table.length); --2
//遍历table
for (Node<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//如果有相同的key,直接覆盖value,返回oldValue
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++; //修改次数++
//将key,value添加至i处
addEntry(hash, key, value, i); --3
return null;
}

  看以上代码1、2处,这2个函数计算了hash值和bucket索引.

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
/**
* 预处理hash值,避免较差的离散hash序列,导致桶没有充分利用.
*/
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* 返回对应hash值得索引
*/
static int indexFor(int h, int length) {
/**
* 由于length是2的n次幂,所以h & (length-1)相当于h % length。
* 对于length,其2进制表示为1000...0,那么length-1为0111...1。
* 那么对于任何小于length的数h,该式结果都是其本身h。
* 对于h = length,该式结果等于0。
* 对于大于length的数h,则和0111...1位与运算后,
* 比0111...1高或者长度相同的位都变成0,
* 相当于减去j个length,该式结果是h-j*length,
* 所以相当于h % length。
* 其中一个很常用的特例就是h & 1相当于h % 2。
* 这也是为什么length只能是2的n次幂的原因,为了优化。
*/
return h % (length - 1);
}

  代码3的addEntry函数向数组添加了一对key-value.

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 添加一对key-value,如果当前索引上已有桶(发生hash碰撞),则将新元素放入链表头
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//保存对应table的值
Node<K, V> e = table[bucketIndex];
//用新桶链住旧桶
table[bucketIndex] = new Node<K, V>(hash, key, value, e);
//如果HashMap中元素的个数已经超过阈值,则扩容两倍
if (size++ >= threshold)
resize(2 * table.length);
}

get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public V get(Object key) {
//如果key为null,则调用getForNullkey()获得key为null的值
if (key == null)
return getForNullKey();
//根据key的hashCode计算它的hash
int hash = hash(key.hashCode());
//取出table中指定索引处的值
for (Node<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//如果查找相同的key,返回其对应的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
return e.value;
}
}
return null;
}

all

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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
/**
* 一个简单的HashMap,内部使用拉链法解决hash碰撞.
* <p>
* Created by sylvanasp on 2017/1/12.
*/
public class SimpleHashMap<K, V> extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable {
private static final long serialVersionUID = 6623475452522370065L;
/**
* 默认的容量(bucket数量),1 << 4(16).
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* 最大的容量,1 << 30 (2^30)
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的负载因子,0.75.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* KV链表
*/
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final String toString() {
return key + "=" + value;
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?, ?> e = (Entry<?, ?>) o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue())) {
return true;
}
}
return false;
}
}
/**
* 链表数组,数组中的每一个元素代表了一个链表的头部.
*/
transient Node[] table;
/**
* 当前map的key-value映射数,也就是当前size
*/
transient int size;
/**
* 代表这个HashMap修改key-value的次数.
*/
transient int modCount;
/**
* 自动扩展的阈值(capacity * loadfactor)
*/
int threshold;
/**
* 负载因子:
* 它是哈希表在其容量自动增加之前可以达到多满的一种尺度,
* 它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,
* 反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),
* 因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;
* 如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费.
*/
final float loadFactor;
/**
* 构造一个空的SimpleHashMap,使用默认的capacity和负载因子
*/
public SimpleHashMap(int initialiCapacity, float loadFactor) {
if (initialiCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialiCapacity);
if (initialiCapacity > MAXIMUM_CAPACITY)
initialiCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
//计算出大于initialCapacity的最小的2的n次方值
int capacity = 1;
while (capacity < initialiCapacity) {
capacity <<= 1;
}
this.loadFactor = loadFactor;
//设置HashMap的扩容阈值,当到达这个阈值时会进行自动扩容
threshold = (int) (capacity * loadFactor);
//初始化table数组
table = new Node[capacity];
}
public SimpleHashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 预处理hash值,避免较差的离散hash序列,导致桶没有充分利用.
*/
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* 返回对应hash值得索引
*/
static int indexFor(int h, int length) {
/**
* 由于length是2的n次幂,所以h & (length-1)相当于h % length。
* 对于length,其2进制表示为1000...0,那么length-1为0111...1。
* 那么对于任何小于length的数h,该式结果都是其本身h。
* 对于h = length,该式结果等于0。
* 对于大于length的数h,则和0111...1位与运算后,
* 比0111...1高或者长度相同的位都变成0,
* 相当于减去j个length,该式结果是h-j*length,
* 所以相当于h % length。
* 其中一个很常用的特例就是h & 1相当于h % 2。
* 这也是为什么length只能是2的n次幂的原因,为了优化。
*/
return h % (length - 1);
}
/**
* 获得key为null的值
*/
private V getForNullKey() {
//遍历table[0]
for (Node<K, V> e = table[0]; e != null; e = e.next) {
//如果找到key为null,则返回对应的值
if (e.key == null) {
return e.value;
}
}
return null;
}
/**
* 当Key为Null时如何放入值
*/
private V putForNullKey(V value) {
//遍历table[0]
for (Node<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
//取出oldValue,并存入newValue
V oldValue = e.value;
e.value = value;
//返回oldValue
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
/**
* 添加一对key-value,如果当前索引上已有桶(发生hash碰撞),则将新元素放入链表头
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//保存对应table的值
Node<K, V> e = table[bucketIndex];
//用新桶链住旧桶
table[bucketIndex] = new Node<K, V>(hash, key, value, e);
//如果HashMap中元素的个数已经超过阈值,则扩容两倍
if (size++ >= threshold)
resize(2 * table.length);
}
/**
* 扩充容量
*/
void resize(int newCapacity) {
//保存oldTable
Node[] oldTable = table;
//保存旧容量
int oldCapacity = oldTable.length;
//如果旧的容量已经是系统默认最大容量了,那么将阈值设置成整形的最大值
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根据newCapacity创建一个table
Node[] newTable = new Node[newCapacity];
//将table转换为newTable
transfer(newTable);
table = newTable;
//设置阈值
threshold = (int) (newCapacity * loadFactor);
}
// 将所有格子里的桶都放到新的table中
void transfer(Node[] newTable) {
// 得到旧的table
Node[] src = table;
// 得到新的容量
int newCapacity = newTable.length;
// 遍历src里面的所有格子
for (int j = 0; j < src.length; j++) {
// 取到格子里的桶(也就是链表)
Node<K, V> e = src[j];
// 如果e不为空
if (e != null) {
// 将当前格子设成null
src[j] = null;
// 遍历格子的所有桶
do {
// 取出下个桶
Node<K, V> next = e.next;
// 寻找新的索引
int i = indexFor(e.hash, newCapacity);
// 设置e.next为newTable[i]保存的桶(也就是链表连接上)
e.next = newTable[i];
// 将e设成newTable[i]
newTable[i] = e;
// 设置e为下一个桶
e = next;
} while (e != null);
}
}
}
@Override
public V get(Object key) {
//如果key为null,则调用getForNullkey()获得key为null的值
if (key == null)
return getForNullKey();
//根据key的hashCode计算它的hash
int hash = hash(key.hashCode());
//取出table中指定索引处的值
for (Node<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//如果查找相同的key,返回其对应的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
return e.value;
}
}
return null;
}
@Override
public V put(K key, V value) {
//如果key为null,调用putForNullKey()向null key存入value
if (key == null)
return putForNullKey(value);
//计算key的hash
int hash = hash(key.hashCode());
//计算key的hash在table数组中的索引
int i = indexFor(hash, table.length);
//遍历table
for (Node<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//如果有相同的key,直接覆盖value,返回oldValue
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
modCount++; //修改次数++
//将key,value添加至i处
addEntry(hash, key, value, i);
return null;
}
@Override
public Set<Entry<K, V>> entrySet() {
return null;
}
public static void main(String[] args) {
Map<String, String> map = new SimpleHashMap<>();
map.put("hello", "world");
System.out.println(map.get("hello"));
}
}
分享