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
| 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);
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);
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
|
