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