HaspMap的原理

实现简单的Map


前几天有想法弄懂HashMap的实现的原理,我自己也YY了一个想法去实现一个简单的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
public class KeyValuePair<K,V> {

public K Key;
public V Value;

public K getKey() {
return Key;
}

public void setKey(K key) {
Key = key;
}

public V getValue() {
return Value;
}

public void setValue(V value) {
Value = value;
}
}

```
然后使用List作为Container对数据进行存储,主体的内部实现原理如下:

```Java
public class MyMap<K, V> {
private List<KeyValuePair<K, V>> map;

public MyMap() {
map = new ArrayList<KeyValuePair<K, V>>();
}

public V put(K k, V v) {
KeyValuePair<K, V> keyValuePair = new KeyValuePair<K, V>();
keyValuePair.setKey(k);
keyValuePair.setValue(v);
map.add(keyValuePair);
return v;
}

public V get(K k) {
for (KeyValuePair pair : map) {
if (pair.getKey().equals(k)) {
return (V) pair.getValue();
}
}
return null;
}
}

虽然也能实现类似的效果,但我们可以看到这个的map的时间复杂度是O(n),当集合数量很大时,则效率可以的非常的糟糕,下面做一个对比的测试:

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
@Test
public void MapTest(){

long start=System.currentTimeMillis();
MyMap<String,String> map =new MyMap();
for (int i=0;i<10000;i++){
map.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
map.get("Key"+i);
}
long end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));

start=System.currentTimeMillis();
Map<String,String> hashMap =new HashMap<>();
for (int i=0;i<10000;i++){
hashMap.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
hashMap.get("Key"+i);
}
end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));
}
```

运行结果如下:

```cte
耗时:1815
耗时:14
```

整整慢了100多倍!

### HashMap的实现原理
----------------------------

对于上面的代码,我们应该知道性能最慢的是查找对应的key值,对于ArrayList来说,可能插入也是很大的性能消耗。在JDK中使用一个数组来存储key,索引是根据Key的Hash值来确定,而每一个key对应数据单元是一个链表。用图表示效果如下:

![HaspMap的原理](/img/assets/22/01.png)

下面我们JDK的原理进行分析:

#### 存值

1. 首先定义一个数组,其类型是一个Key-Value类型

2. 根据key的Hash值来确定当前的索引

3. 根据索引值来判断当前是否有值,如果当前有值则把当前的值插入当前数据之前

#### 取值

1.根据key的Hash值来确定当前的索引,根据索引来找到链表的首节点

2.遍历链表,找到指定的Key对应的节点,取出当前值



具体的实现代码如下(可以利用上面的代码):

```Java
public class KeyValuePair<K,V> {

public K Key;
public V Value;
public KeyValuePair next;

public KeyValuePair getNext() {
return next;
}

public void setNext(KeyValuePair next) {
this.next = next;
}
public KeyValuePair(){

}
public KeyValuePair(K k, V v){
this.Key=k;
this.Value=v;
}
public K getKey() {
return Key;
}

public void setKey(K key) {
Key = key;
}

public V getValue() {
return Value;
}

public void setValue(V value) {
Value = value;
}
}

```

HashMap的实现:
```Java
public class MyHashMap<K, V> {

private int defalutLength = 16;
private int size;
private KeyValuePair<K, V>[] arr;
public MyHashMap() {
arr = new KeyValuePair[defalutLength];
size = 0;
}

public V put(K k, V v) {
int index = findIndex(k);
//todo:find out of index
if (arr[index] == null) {
arr[index] = new KeyValuePair(k, v);
} else {
KeyValuePair tempPair = arr[index];
arr[index] = new KeyValuePair(k, v);
arr[index].setNext(tempPair);
}
size++;
return v;
}

private int findIndex(K key) {
int index=key.hashCode() % defalutLength;
return index>0?index:(-1)*index;
}

public V get(K k) {
int index = findIndex(k);
if (arr[index] == null) {
return null;
}
KeyValuePair<K, V> current = arr[index];
while (current.next != null) {
if (current.getKey().equals(k)) {
return current.getValue();
}
current = current.next;
}
return null;
}
public int size(){
return this.size;
}

}

```

同样我们修改测试的代码:
```Java
@Test
public void MapTest(){

long start=System.currentTimeMillis();
MyMap<String,String> map =new MyMap();
for (int i=0;i<10000;i++){
map.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
map.get("Key"+i);
}
long end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));

start=System.currentTimeMillis();
Map<String,String> hashMap =new HashMap<>();
for (int i=0;i<10000;i++){
hashMap.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
hashMap.get("Key"+i);
}
end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));



start=System.currentTimeMillis();
MyHashMap<String,String> myhashMap =new MyHashMap<>();
for (int i=0;i<10000;i++){
myhashMap.put("Key"+i,"value"+i);
}
for (int i=0;i<10000;i++){
myhashMap.get("Key"+i);
}
end=System.currentTimeMillis();
System.out.println("耗时:"+(end-start));

}
```

运行结果:

```cte
耗时:2337
耗时:26
耗时:337
```

我们看到我们使用的链表在插入数据的时候进行整理,极大的提高了Map的效率,但离Jdk的性能还有很大的差距。


### 优化散列算法
---------------------
对于Map的查找的性能的瓶颈主要在最后的链表的查找,我们可以把Key的数据进行扩大,让Key分布的更加平均,这样就能减少最后链表迭代次数,实现思路:

1. 添加一个报警百分比,当key的使用率长度大于当前的比例,我们对key的数组进行扩容

2. 扩容后对原来的Key进行重新散列

修改后代码如下:

```Java
public class MyHashMap<K, V> {

private int defalutLength = 16;
private final double defaultAlfa = 0.75;
private int size;
private int arrLength;
private KeyValuePair<K, V>[] arr;

public MyHashMap() {
arr = new KeyValuePair[defalutLength];
size = 0;
arrLength=0;
}

public V put(K k, V v) {
int index = findIndex(k);
//todo:find out of index
if(arrLength>defalutLength*defaultAlfa){
extentArr();
}
if (arr[index] == null) {
arr[index] = new KeyValuePair(k, v);
arrLength++;
} else {
KeyValuePair tempPair = arr[index];
arr[index] = new KeyValuePair(k, v);
arr[index].setNext(tempPair);
}
size++;
return v;
}

private int findIndex(K key) {

int index=key.hashCode() % defalutLength;
return index>0?index:(-1)*index;
}
private void extentArr(){
defalutLength=defalutLength*2;
KeyValuePair<K, V>[] newArr=new KeyValuePair[defalutLength];
for (int i=0;i<defalutLength/2;i++){
if(arr[i]!=null){
int index= findIndex(arr[i].getKey());
newArr[index]=arr[i];
}
}
arr=newArr;
}
public V get(K k) {
int index = findIndex(k);
if (arr[index] == null) {
return null;
}

KeyValuePair<K, V> current = arr[index];
while (current.next != null) {
if (current.getKey().equals(k)) {
return current.getValue();
}
current = current.next;
}
return null;
}
public int size(){
return this.size;
}

}

```

最终测试性能结果如下:
```cte
耗时:2263
耗时:23
耗时:33

性能已经很接近了,至于为什么有差异,可能jdk有其它更多的优化(比如当链表长度大于8时,使用红黑树),但本文就讨论到这里。

作者

付威

发布于

2017-11-20

更新于

2020-08-10

许可协议

评论