HaspMap的原理
实现简单的Map
前几天有想法弄懂HashMap的实现的原理，我自己也YY了一个想法去实现一个简单的Map， 代码如下：
1 | public class KeyValuePair<K,V> { |
虽然也能实现类似的效果，但我们可以看到这个的map的时间复杂度是O(n)，当集合数量很大时，则效率可以的非常的糟糕，下面做一个对比的测试：
1 |
|
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
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
192public 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
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时，使用红黑树），但本文就讨论到这里。