实现简单的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 @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的实现: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
性能已经很接近了,至于为什么有差异,可能jdk有其它更多的优化(比如当链表长度大于8时,使用红黑树),但本文就讨论到这里。