HashMap是常用的Java集合之一，是基於哈希表的Map介面的實現。與HashTable主要區別為不支持同步和允許null作為key和value。HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導致數據的不一致。 ...
1 package java.util; 2 3 import sun.misc.SharedSecrets; 4 5 import java.io.IOException; 6 import java.io.InvalidObjectException; 7 import java.io.Serializable; 8 import java.lang.reflect.ParameterizedType; 9 import java.lang.reflect.Type; 10 import java.util.function.BiConsumer; 11 import java.util.function.BiFunction; 12 import java.util.function.Consumer; 13 import java.util.function.Function; 14 15 /** 16 * HashMap是常用的Java集合之一，是基於哈希表的Map介面的實現。與HashTable主要區別為不支持同步和允許null作為key和value。 17 * HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導致數據的不一致。 18 * 如果需要滿足線程安全，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap。 19 * 在JDK1.6中，HashMap採用數組+鏈表實現，即使用鏈表處理衝突，同一hash值的鏈表都存儲在一個鏈表裡。 20 * 但是當位於一個數組中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。 21 * 而JDK1.8中，HashMap採用數組+鏈表+紅黑樹實現，當鏈表長度超過閾值8時，將鏈表轉換為紅黑樹，這樣大大減少了查找時間。 22 * 原本Map.Entry介面的實現類Entry改名為了Node。轉化為紅黑樹時改用另一種實現TreeNode。 23 */ 24 public class HashMap<K, V> extends AbstractMap<K, V> 25 implements Map<K, V>, Cloneable, Serializable { 26 27 private static final long serialVersionUID = 362498820763181265L; 28 29 30 /** 31 * 預設的初始容量（容量為HashMap中槽的數目）是16，且實際容量必須是2的整數次冪。 32 */ 33 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 34 35 /** 36 * 最大容量（必須是2的冪且小於2的30次方，傳入容量過大將被這個值替換） 37 */ 38 static final int MAXIMUM_CAPACITY = 1 << 30; 39 40 /** 41 * 預設裝填因數0.75，如果當前鍵值對個數 >= HashMap最大容量*裝填因數，進行rehash操作 42 */ 43 static final float DEFAULT_LOAD_FACTOR = 0.75f; 44 45 /** 46 * JDK1.8 新加，Entry鏈表最大長度，當桶中節點數目大於該長度時，將鏈表轉成紅黑樹存儲； 47 */ 48 static final int TREEIFY_THRESHOLD = 8; 49 50 /** 51 * JDK1.8 新加，當桶中節點數小於該長度，將紅黑樹轉為鏈表存儲； 52 */ 53 static final int UNTREEIFY_THRESHOLD = 6; 54 55 /** 56 * 桶可能被轉化為樹形結構的最小容量。當哈希表的大小超過這個閾值，才會把鏈式結構轉化成樹型結構，否則僅採取擴容來嘗試減少衝突。 57 * 應該至少4*TREEIFY_THRESHOLD來避免擴容和樹形結構化之間的衝突。 58 */ 59 static final int MIN_TREEIFY_CAPACITY = 64; 60 61 /** 62 * JDK1.6用Entry描述鍵值對，JDK1.8中用Node代替Entry 63 */ 64 static class Node<K, V> implements Map.Entry<K, V> { 65 // hash存儲key的hashCode 66 final int hash; 67 // final:一個鍵值對的key不可改變 68 final K key; 69 V value; 70 //指向下個節點的引用 71 Node<K, V> next; 72 73 //構造函數 74 Node(int hash, K key, V value, Node<K, V> next) { 75 this.hash = hash; 76 this.key = key; 77 this.value = value; 78 this.next = next; 79 } 80 81 public final K getKey() { 82 return key; 83 } 84 85 public final V getValue() { 86 return value; 87 } 88 89 public final String toString() { 90 return key + "=" + value; 91 } 92 93 public final int hashCode() { 94 return Objects.hashCode(key) ^ Objects.hashCode(value); 95 } 96 97 public final V setValue(V newValue) { 98 V oldValue = value; 99 value = newValue; 100 return oldValue; 101 } 102 103 public final boolean equals(Object o) { 104 if (o == this) 105 return true; 106 if (o instanceof Map.Entry) { 107 Map.Entry<?, ?> e = (Map.Entry<?, ?>) o; 108 if (Objects.equals(key, e.getKey()) && 109 Objects.equals(value, e.getValue())) 110 return true; 111 } 112 return false; 113 } 114 } 115 116 /* ---------------- Static utilities -------------- */ 117 118 /** 119 * HashMap中鍵值對的存儲形式為鏈表節點，hashCode相同的節點（位於同一個桶）用鏈表組織 120 * hash方法分為三步: 121 * 1.取key的hashCode 122 * 2.key的hashCode高16位異或低16位 123 * 3.將第一步和第二步得到的結果進行取模運算。 124 */ 125 static final int hash(Object key) { 126 int h; 127 //計算key的hashCode, h = Objects.hashCode(key) 128 //h >>> 16表示對h無符號右移16位，高位補0，然後h與h >>> 16按位異或 129 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 130 } 131 132 /** 133 * 如果參數x實現了Comparable介面，返回參數x的類名，否則返回null 134 */ 135 static Class<?> comparableClassFor(Object x) { 136 if (x instanceof Comparable) { 137 Class<?> c; 138 Type[] ts, as; 139 Type t; 140 ParameterizedType p; 141 if ((c = x.getClass()) == String.class) // bypass checks 142 return c; 143 if ((ts = c.getGenericInterfaces()) != null) { 144 for (int i = 0; i < ts.length; ++i) { 145 if (((t = ts[i]) instanceof ParameterizedType) && 146 ((p = (ParameterizedType) t).getRawType() == 147 Comparable.class) && 148 (as = p.getActualTypeArguments()) != null && 149 as.length == 1 && as[0] == c) // type arg is c 150 return c; 151 } 152 } 153 } 154 return null; 155 } 156 157 /** 158 * 如果x的類型為kc，則返回k.compareTo(x)，否則返回0 159 */ 160 @SuppressWarnings({"rawtypes", "unchecked"}) // for cast to Comparable 161 static int compareComparables(Class<?> kc, Object k, Object x) { 162 return (x == null || x.getClass() != kc ? 0 : 163 ((Comparable) k).compareTo(x)); 164 } 165 166 /** 167 * 結果為>=cap的最小2的自然數冪 168 */ 169 static final int tableSizeFor(int cap) { 170 //先移位再或運算，最終保證返回值是2的整數冪 171 int n = cap - 1; 172 n |= n >>> 1; 173 n |= n >>> 2; 174 n |= n >>> 4; 175 n |= n >>> 8; 176 n |= n >>> 16; 177 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 178 } 179 180 /* ---------------- Fields -------------- */ 181 182 /** 183 * 哈希桶數組，分配的時候，table的長度總是2的冪 184 */ 185 transient Node<K, V>[] table; 186 187 /** 188 * HashMap將數據轉換成set的另一種存儲形式，這個變數主要用於迭代功能 189 */ 190 transient Set<Map.Entry<K, V>> entrySet; 191 192 /** 193 * 實際存儲的數量，則HashMap的size()方法，實際返回的就是這個值，isEmpty()也是判斷該值是否為0 194 */ 195 transient int size; 196 197 /** 198 * hashmap結構被改變的次數，fail-fast機制 199 */ 200 transient int modCount; 201 202 /** 203 * HashMap的擴容閾值，在HashMap中存儲的Node鍵值對超過這個數量時，自動擴容容量為原來的二倍 204 * 205 * @serial 206 */ 207 int threshold; 208 209 /** 210 * HashMap的負載入因數，可計算出當前table長度下的擴容閾值：threshold = loadFactor * table.length 211 * 212 * @serial 213 */ 214 final float loadFactor; 215 216 /* ---------------- Public operations -------------- */ 217 218 /** 219 * 使用指定的初始化容量initial capacity 和載入因數load factor構造一個空HashMap 220 * 221 * @param initialCapacity 初始化容量 222 * @param loadFactor 載入因數 223 * @throws IllegalArgumentException 如果指定的初始化容量為負數或者載入因數為非正數 224 */ 225 public HashMap(int initialCapacity, float loadFactor) { 226 if (initialCapacity < 0) 227 throw new IllegalArgumentException("Illegal initial capacity: " + 228 initialCapacity); 229 if (initialCapacity > MAXIMUM_CAPACITY) 230 initialCapacity = MAXIMUM_CAPACITY; 231 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 232 throw new IllegalArgumentException("Illegal load factor: " + 233 loadFactor); 234 this.loadFactor = loadFactor; 235 this.threshold = tableSizeFor(initialCapacity); 236 } 237 238 /** 239 * 使用指定的初始化容量initial capacity和預設載入因數DEFAULT_LOAD_FACTOR（0.75）構造一個空HashMap 240 * 241 * @param initialCapacity 初始化容量 242 * @throws IllegalArgumentException 如果指定的初始化容量為負數 243 */ 244 public HashMap(int initialCapacity) { 245 this(initialCapacity, DEFAULT_LOAD_FACTOR); 246 } 247 248 /** 249 * 使用指定的初始化容量（16）和預設載入因數DEFAULT_LOAD_FACTOR（0.75）構造一個空HashMap 250 */ 251 public HashMap() { 252 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 253 } 254 255 /** 256 * 使用指定Map m構造新的HashMap。使用指定的初始化容量（16）和預設載入因數DEFAULT_LOAD_FACTOR（0.75） 257 * 258 * @param m 指定的map 259 * @throws NullPointerException 如果指定的map是null 260 */ 261 public HashMap(Map<? extends K, ? extends V> m) { 262 this.loadFactor = DEFAULT_LOAD_FACTOR; 263 putMapEntries(m, false); 264 } 265 266 /** 267 * Map.putAll and Map constructor的實現需要的方法 268 * 將m的鍵值對插入本map中 269 * 270 * @param m 指定的map 271 * @param evict 初始化map時使用false，否則使用true 272 */ 273 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 274 int s = m.size(); 275 //如果參數map不為空 276 if (s > 0) { 277 // 判斷table是否已經初始化 278 if (table == null) { // pre-size 279 // 未初始化，s為m的實際元素個數 280 float ft = ((float) s / loadFactor) + 1.0F; 281 int t = ((ft < (float) MAXIMUM_CAPACITY) ? 282 (int) ft : MAXIMUM_CAPACITY); 283 // 計算得到的t大於閾值，則初始化閾值 284 if (t > threshold) 285 //根據容量初始化臨界值 286 threshold = tableSizeFor(t); 287 // 已初始化，並且m元素個數大於閾值，進行擴容處理 288 } else if (s > threshold) 289 //擴容處理 290 resize(); 291 // 將m中的所有元素添加至HashMap中 292 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 293 K key = e.getKey(); 294 V value = e.getValue(); 295 putVal(hash(key), key, value, false, evict); 296 } 297 } 298 } 299 300 /** 301 * 返回map中鍵值對映射的個數 302 * 303 * @return map中鍵值對映射的個數 304 */ 305 public int size() { 306 return size; 307 } 308 309 /** 310 * 如果map中沒有鍵值對映射，返回true 311 * 312 * @return 如果map中沒有鍵值對映射，返回true 313 */ 314 public boolean isEmpty() { 315 return size == 0; 316 } 317 318 /** 319 * 返回指定的key映射的value，如果value為null，則返回null 320 * get可以分為三個步驟： 321 * 1.通過hash(Object key)方法計算key的哈希值hash。 322 * 2.通過getNode( int hash, Object key)方法獲取node。 323 * 3.如果node為null，返回null，否則返回node.value。 324 * 325 * @see #put(Object, Object) 326 */ 327 public V get(Object key) { 328 Node<K, V> e; 329 //根據key及其hash值查詢node節點，如果存在，則返回該節點的value值 330 return (e = getNode(hash(key), key)) == null ? null : e.value; 331 } 332 333 /** 334 * 根據key的哈希值和key獲取對應的節點 335 * getNode可分為以下幾個步驟： 336 * 1.如果哈希表為空，或key對應的桶為空，返回null 337 * 2.如果桶中的第一個節點就和指定參數hash和key匹配上了，返回這個節點。 338 * 3.如果桶中的第一個節點沒有匹配上，而且有後續節點 339 * 3.1如果當前的桶採用紅黑樹，則調用紅黑樹的get方法去獲取節點 340 * 3.2如果當前的桶不採用紅黑樹，即桶中節點結構為鏈式結構，遍歷鏈表，直到key匹配 341 * 4.找到節點返回null，否則返回null。 342 * 343 * @param hash 指定參數key的哈希值 344 * @param key 指定參數key 345 * @return 返回node，如果沒有則返回null 346 */ 347 final Node<K, V> getNode(int hash, Object key) { 348 Node<K, V>[] tab; 349 Node<K, V> first, e; 350 int n; 351 K k; 352 //如果哈希表不為空，而且key對應的桶上不為空 353 if ((tab = table) != null && (n = tab.length) > 0 && 354 (first = tab[(n - 1) & hash]) != null) { 355 //如果桶中的第一個節點就和指定參數hash和key匹配上了 356 if (first.hash == hash && // always check first node 357 ((k = first.key) == key || (key != null && key.equals(k)))) 358 //返回桶中的第一個節點 359 return first; 360 //如果桶中的第一個節點沒有匹配上，而且有後續節點 361 if ((e = first.next) != null) { 362 //如果當前的桶採用紅黑樹，則調用紅黑樹的get方法去獲取節點 363 if (first instanceof TreeNode) 364 return ((TreeNode<K, V>) first).getTreeNode(hash, key); 365 //如果當前的桶不採用紅黑樹，即桶中節點結構為鏈式結構 366 do { 367 //遍歷鏈表，直到key匹配 368 if (e.hash == hash && 369 ((k = e.key) == key || (key != null && key.equals(k)))) 370 return e; 371 } while ((e = e.next) != null); 372 } 373 } 374 //如果哈希表為空，或者沒有找到節點，返回null 375 return null; 376 } 377 378 /** 379 * 如果map中含有key為指定參數key的鍵值對，返回true 380 * 381 * @param key 指定參數key 382 * @return 如果map中含有key為指定參數key的鍵值對，返回true 383 * key. 384 */ 385 public boolean containsKey(Object key) { 386 return getNode(hash(key), key) != null; 387 } 388 389 /** 390 * 將指定參數key和指定參數value插入map中，如果key已經存在，那就替換key對應的value 391 * put(K key, V value)可以分為三個步驟： 392 * 1.通過hash(Object key)方法計算key的哈希值。 393 * 2.通過putVal(hash(key), key, value, false, true)方法實現功能。 394 * 3.返回putVal方法返回的結果。 395 * 396 * @param key 指定key 397 * @param value 指定value 398 * @return 如果value被替換，則返回舊的value，否則返回null。當然，可能key對應的value就是null 399 */ 400 public V put(K key, V value) { 401 // 倒數第二個參數false：表示允許舊值替換 402 // 最後一個參數true：表示HashMap不處於創建模式 403 return putVal(hash(key), key, value, false, true); 404 } 405 406 /** 407 * Map.put和其他相關方法的實現需要的方法 408 * putVal方法可以分為下麵的幾個步驟: 409 * 1.如果哈希表為空，調用resize()創建一個哈希表。 410 * 2.如果指定參數hash在表中沒有對應的桶，即為沒有碰撞，直接將鍵值對插入到哈希表中即可。 411 * 3.如果有碰撞，遍歷桶，找到key映射的節點 412 * 3.1桶中的第一個節點就匹配了，將桶中的第一個節點記錄起來。 413 * 3.2如果桶中的第一個節點沒有匹配，且桶中結構為紅黑樹，則調用紅黑樹對應的方法插入鍵值對。 414 * 3.3如果不是紅黑樹，那麼就肯定是鏈表。遍歷鏈表，如果找到了key映射的節點，就記錄這個節點，退出迴圈。如果沒有找到，在鏈表尾部插入節點。插入後，如果鏈的長度大於TREEIFY_THRESHOLD這個臨界值，則使用treeifyBin方法把鏈表轉為紅黑樹。 415 * 4.如果找到了key映射的節點，且節點不為null 416 * 4.1記錄節點的vlaue。 417 * 4.2如果參數onlyIfAbsent為false，或者oldValue為null，替換value，否則不替換。 418 * 4.3返回記錄下來的節點的value。 419 * 5.如果沒有找到key映射的節點（2、3步中講了，這種情況會插入到hashMap中），插入節點後size會加1，這時要檢查size是否大於臨界值threshold，如果大於會使用resize方法進行擴容。 420 * 421 * @param hash 指定參數key的哈希值 422 * @param key 指定參數key 423 * @param value 指定參數value 424 * @param onlyIfAbsent 如果為true，即使指定參數key在map中已經存在，也不會替換value 425 * @param evict 如果為false，數組table在創建模式中 426 * @return 如果value被替換，則返回舊的value，否則返回null。當然，可能key對應的value就是null。 427 */ 428 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 429 boolean evict) { 430 Node<K, V>[] tab; 431 Node<K, V> p; 432 int n, i; 433 //如果哈希表為空，調用resize()創建一個哈希表，並用變數n記錄哈希表長度 434 if ((tab = table) == null || (n = tab.length) == 0) 435 n = (tab = resize()).length; 436 /** 437 * 如果指定參數hash在表中沒有對應的桶，即為沒有碰撞 438 * Hash函數，(n - 1) & hash 計算key將被放置的槽位 439 * (n - 1) & hash 本質上是hash % n，位運算更快 440 */ 441 if ((p = tab[i = (n - 1) & hash]) == null) 442 //直接將鍵值對插入到map中即可 443 tab[i] = newNode(hash, key, value, null); 444 else {// 桶中已經存在元素 445 Node<K, V> e; 446 K k; 447 // 比較桶中第一個元素(數組中的結點)的hash值相等，key相等 448 if (p.hash == hash && 449 ((k = p.key) == key || (key != null && key.equals(k)))) 450 // 將第一個元素賦值給e，用e來記錄 451 e = p; 452 // 當前桶中無該鍵值對，且桶是紅黑樹結構，按照紅黑樹結構插入 453 else if (p instanceof TreeNode) 454 e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); 455 // 當前桶中無該鍵值對，且桶是鏈表結構，按照鏈表結構插入到尾部 456 else { 457 for (int binCount = 0; ; ++binCount) { 458 // 遍歷到鏈表尾部 459 if ((e = p.next) == null) { 460 p.next = newNode(hash, key, value, null); 461 // 檢查鏈表長度是否達到閾值，達到將該槽位節點組織形式轉為紅黑樹 462 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 463 treeifyBin(tab, hash); 464 break; 465 } 466 // 鏈表節點的<key, value>與
