手写HashMap 数组+链表+自动扩容+相关问题

  1 package dataStructure.myHashmap;
  2 import java.util.Objects;
  3 
  4 /**
  5  *
  6  * @param <K>
  7  * @param <V>
  8  */
  9 
 10 public class Myhashmap<K, V> implements MyMap<K, V> {
 11     private static final long serialVersionUID = 362498820763181265L;
 12 
 13     //默认的bin初始化长度 -- 必须是2的幂
 14     private static final int DEFAULT_INITIAL_CAPACITY  = 1 << 4;
 15 
 16     //数组的最长长度 1 << 30
 17     private static final int MAXIMUM_CAPACITY = 1 << 30;
 18 
 19     //默认的装载因子
 20     private static final float DEFAULT_LOAD_FACTOR = 0.75f;
 21 
 22 
 23 
 24     //树化的阙值，达到这个值就进行树化
 25     private static final int TREEIFY_THRESHOLD = 8;
 26 
 27     //从红黑树变回链表的阙值
 28     private static final int UNTREEIFY_THRESHOLD = 6;
 29 /*---------------Fields----------------------------- */
 30     //map中的元素个数
 31     private transient int size;
 32     //bin
 33     Node<K, V>[] table;
 34 
 35     //map的操作数
 36     transient int modCount = 0;
 37 
 38     //loadFactor
 39     float loadFactor;
 40 
 41     //threshold
 42     int threshold;
 43 
 44 
 45 //----------------------------------------constructor------------------------------------------------
 46     public Myhashmap(){
 47         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
 48     }
 49     public Myhashmap(int capacity, float loadFactor){
 50         if(capacity < 0){
 51             throw new IllegalArgumentException("Illegal Initial Capacity" + capacity);
 52         }
 53         if(capacity > MAXIMUM_CAPACITY){
 54             capacity = MAXIMUM_CAPACITY;
 55         }
 56         if(loadFactor <= 0 || Float.isNaN(loadFactor)){
 57             throw new IllegalArgumentException("Illegal LoadFactory" + loadFactor);
 58         }
 59         this.size = 0;
 60         this.modCount = 0;
 61         this.loadFactor = loadFactor;
 62         //初始化阙值的时候找到大于自己设置的值的最小二次幂
 63         this.threshold = (int) (capacity * loadFactor);
 64     }
 65 
 66 
 67 //-------------------------------------Node----------------------------------------------------
 68     static class Node<K, V> implements MyMap.Entry<K, V>{
 69         final int hash;
 70         final K key;
 71         V value;
 72         Node<K, V> next;
 73         public Node(int hash, K key, V value, Node<K, V> next){
 74             this.hash = hash;
 75             this.key = key;
 76             this.value = value;
 77             this.next = next;
 78         }
 79 
 80         @Override
 81         public V getValue() {
 82             return this.value;
 83         }
 84 
 85         @Override
 86         public K getKey() {
 87             return this.key;
 88         }
 89 
 90 
 91     public final String toString(){
 92             return this.key + "=" + this.value;
 93         }
 94         //
 95         public final int hashCode(){
 96             return Objects.hashCode(key) ^ Objects.hashCode(value);
 97         }
 98         public V setValue(V newValue){
 99             V oldValue = value;
100             value = newValue;
101             return oldValue;
102         }
103     }
104     //-------------------------------------OutsideMethod-------------------------------------
105 
106     @Override
107     public V put(K k, V v) {
108         return putVal(hash(k), k, v);
109     }
110 
111     @Override
112     public V get(K k) {
113         return getNode(hash(k),k).value;
114     }
115 
116     public Node<K, V> remove(K k, V v){
117         return removeNode(hash(k), k, v);
118     }
119 
120     public int size(){
121         return size;
122     }
123 
124     public Boolean isEmpty(){
125         return size == 0;
126     }
127 
128     public boolean contaisKey(K k){
129         return getNode(hash(k), k) != null;
130     }
131 
132     //------------------------method----------------------
133 
134     final Node<K, V> getNode(int hash, Object key){
135         Node<K, V>[] tab = table;
136         int n;
137         Node<K, V> p;
138         if(tab == null || (n = tab.length) == 0){
139             return null;
140         }
141         if((p = tab[indexFor(hash, n)]) == null){
142             return null;
143         }else if(p.hash == hash && (p.key == key || (key != null && key.equals(p.key)))){
144            return p;
145         } else{
146             Node<K, V> e;
147             if((e = p.next) != null){
148                 do{
149                     if(e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))){
150                         return e;
151                     }
152                 }while((e = e.next) != null);
153             }
154 
155         }
156         return null;
157     }
158 
159 
160 
161     static final int hash(Object key){
162         int h;
163         return key == null ? 0 : (h = Objects.hashCode(key)) ^ (h >>> 16);
164     }
165 
166     public V putVal(int hash, K key, V value){
167         if(key == null || value == null){
168             throw new NullPointerException("key or value is null");
169         }
170         int i = 0;
171         Node<K, V>[] tab = table;
172         Node<K, V> p;
173         int n;
174         if(tab == null || (n = tab.length) == 0) {
175            n = (tab = resize()).length;
176         }
177         if((p = tab[i = (hash & (n - 1))]) == null){
178             tab[i] = new Node<>(hash, key, value, null);
179         }else{
180             Node<K, V> e; K k;
181             //判断当前p节点是不是你要插入的节点
182             if(p.hash == hash && ((k = p.key) == key || (k.equals(key) && key != null))){
183                 e = p;
184             }else{
185                 while(true){
186                     if((e = p.next) == null){
187                         p.next = new Node<>(hash, key, value, null);
188                         break;
189                     }
190                     if(e.hash == hash && (e.key == key || (key.equals(e.key) && key != null))){
191                         break;
192                     }
193                     //向下传递
194                     p = e;
195                 }
196             }
197             if(e != null){
198                 V oldVal = e.value;
199                 e.value = value;
200                 return oldVal;
201             }
202         }
203         this.table = tab;
204         ++modCount;
205         if (++size > threshold) {
206             resize();
207         }
208         return null;
209     }
210 
211     /**
212      * 扩容方法
213      * @return
214      */
215 
216     final Node<K, V>[] resize(){
217         Node<K, V>[] oldTab = table;
218         int oldCap = (oldTab == null) ? 0 : oldTab.length;
219         int oldThr = threshold;
220         int newCap, newThr = 0;
221         if(oldCap > 0){
222             if(oldCap > MAXIMUM_CAPACITY){
223                 newThr =Integer.MAX_VALUE;
224                 return oldTab;
225             } else if((newCap = oldCap >> 1) < MAXIMUM_CAPACITY && oldCap > DEFAULT_INITIAL_CAPACITY){
226                 newCap = oldCap >> 1;
227             }
228         }
229         else if(oldThr == 0){
230             newCap = DEFAULT_INITIAL_CAPACITY;
231             newThr = (int) (loadFactor * DEFAULT_INITIAL_CAPACITY);
232         }else{
233             newCap = oldThr;
234         }
235         threshold = newThr;
236         Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
237         newTab = transfer(oldTab, newTab);
238         this.table = newTab;
239         return newTab;
240     }
241     final Node<K, V>[] transfer(Node<K, V>[] oldTab, Node<K, V>[] newTab){
242         int oldCap = oldTab.length;
243         int newCap = newTab.length;
244         for (int i = 0; i < oldTab.length; i++) {
245             Node<K, V> e = oldTab[i];
246             if(e != null){
247                 oldTab[i] = null;
248                 //当前桶中只有一个节点
249                 if(e.next == null){
250                     newTab[e.hash & (newCap - 1)] = e;
251                 }else{
252                     //拆分链表
253                     //低位链表
254                     Node<K, V> loHead = null, loTail = null;
255                     //高位链表
256                     Node<K, V> hiHead = null, hiTail = null;
257                     while(e != null){
258                         //链表中保持原数组位置不会改变的节点
259                         if(indexFor(e.hash, newCap) == 0){
260                             if(loTail == null){
261                                 loHead = e;
262                             }else{
263                                 loTail.next = e;
264                             }
265                             loTail = e;
266                         }else{
267                             if(hiTail == null){
268                                 hiHead = e;
269                             }else{
270                                 hiTail.next = e;
271                             }
272                             hiTail = e;
273                         }
274                         if(e.next == null){
275                             break;
276                         }
277                         e = e.next;
278                     }
279                     if(loTail != null){
280                         loTail.next = null;
281                         newTab[i] = loHead;
282                     }
283                     if(hiTail != null){
284                         hiTail.next = null;
285                         newTab[i + oldCap] = hiHead;
286                     }
287                 }
288             }
289         }
290         return newTab;
291     }
292     final int indexFor(int h, int length){
293         return h & (length - 1);
294     }
295 
296     final Node<K, V> removeNode(int hash, K k, V v){
297         if(k == null || v == null){
298             throw new ArithmeticException("this key or value is null!");
299         }
300         Node<K, V>[] tab = table;
301         int n = 0;
302         int index;
303         Node<K, V> p;
304         if(tab == null || (n = tab.length) == 0){
305             return null;
306         }if((p = tab[index = indexFor(hash, n)]) == null){
307             return null;
308         }else{
309             Node<K, V> e;
310             Node<K, V> node = null;
311             K key = p.key;
312             if(p.hash == hash && (k == key) || (key.equals(k) && k != null)){
313                 node = p;
314             }else if((e = p.next) != null){
315                 do{
316                     if(e.hash == hash && (k == e.key || (k != null && k.equals(e.key)))){
317                         node = e;
318                         break;
319                     }
320                     //双指针一起移动，p是前驱节点
321                     p = e;
322                 }while((e = e.next) != null);
323             }
324             if(node != null && node.value == v){
325                 if(node == p){
326                     tab[index] = node.next;
327                 }else{
328                     p.next = node.next;
329                 }
330                 ++ modCount;
331                 --size;
332                 return node;
333             }
334         }
335         return null;
336     }
337 
338 }