淺析 HashMap
筆記對原始碼解讀的理解以及面試經常問到的問題。
HashMap的資料結構
資料結構中有陣列和連結串列來實現對資料的儲存，但這兩者基本上是兩個極端。
陣列
陣列儲存區間是連續的，佔用記憶體嚴重，故空間複雜的很大。但陣列的二分查詢時間複雜度小，為O(1)；陣列的特點是：定址容易，插入和刪除困難；
連結串列
連結串列儲存區間離散，佔用記憶體比較寬鬆，故空間複雜度很小，但時間複雜度很大，達O(N)。連結串列的特點是：定址困難，插入和刪除容易。
雜湊表
那麼能不能綜合兩者的特性，做出一種定址容易，插入刪除也容易的資料結構？答案是肯定的。雜湊表（(Hash table）既滿足了資料的查詢方便，同時不佔用太多的內容空間，使用也十分方便。
雜湊表有多種不同的實現方法，接下來解釋的是最常用的一種方法—— 拉鍊法，可以理解為“連結串列的陣列” ，如圖：
從上圖可以理解為 Hashmap 中存放數據的Entry透過%運算得到最後放入陣列的格子中，比如hash為16%16得0則直接放到[0]中，不過這樣的計算效率太低，後面會接著說原始碼上針對這部分做了哪些改進，接著是每個Entry中都帶著next節點指向下個Entry形成單向連結串列。
原始碼分析
|
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 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 |
package java.util; import java.io.*; public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { /** * 默认初始容量，默认为2的4次方 = 16，2的n次方是为了加快hash计算速度，；；减少hash冲突，，，h & (length-1)，，1111111 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * 最大容量，默认为2的30次方， */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认负载因子，默认为0.75 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** *当数组表还没扩容的时候，一个共享的空表对象 */ static final Entry<?,?>[] EMPTY_TABLE = {}; /** * 数组表，大小可以改变，且大小必须为2的幂 */ transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; /** * 当前Map中key-value映射的个数 */ transient int size; /** * 下次扩容阈值，当size > capacity * load factor时，开始扩容 */ int threshold; /** * 负载因子 */ final float loadFactor; /** * Hash表结构性修改次数，用于实现迭代器快速失败行为 */ transient int modCount; /** * 容量阈值，默认大小为Integer.MAX_VALUE */ static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; /** * 静态内部类Holder，存放一些只能在虚拟机启动后才能初始化的值 */ private static class Holder { /** * 容量阈值，初始化hashSeed的时候会用到该值 */ static final int ALTERNATIVE_HASHING_THRESHOLD; static { //获取系统变量jdk.map.althashing.threshold String altThreshold = java.security.AccessController.doPrivileged( new sun.security.action.GetPropertyAction( "jdk.map.althashing.threshold")); int threshold; try { threshold = (null != altThreshold) ? Integer.parseInt(altThreshold) : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; // jdk.map.althashing.threshold系统变量默认为-1，如果为-1，则将阈值设为Integer.MAX_VALUE if (threshold == -1) { threshold = Integer.MAX_VALUE; } //阈值需要为正数 if (threshold < 0) { throw new IllegalArgumentException("value must be positive integer."); } } catch(IllegalArgumentException failed) { throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed); } ALTERNATIVE_HASHING_THRESHOLD = threshold; } } /** * 计算hash值的时候需要用到 */ transient int hashSeed = 0; /** * 生成一个空的HashMap,并指定其容量大小和负载因子 * */ public HashMap(int initialCapacity, float loadFactor) { //保证初始容量大于等于0 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //保证初始容量不大于最大容量MAXIMUM_CAPACITY if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //loadFactor小于0或为无效数字 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); //负载因子 this.loadFactor = loadFactor; //下次扩容大小 threshold = initialCapacity; init(); } /** * 生成一个空的HashMap,并指定其容量大小，负载因子使用默认的0.75 * */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 生成一个空的HashMap,容量大小使用默认值16，负载因子使用默认值0.75 */ public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * 根据指定的map生成一个新的HashMap,负载因子使用默认值，初始容量大小为Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY) */ public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); } //返回>=number的最小2的n次方值，如number=5，则返回8 private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; } /** * 对table扩容 */ private void inflateTable(int toSize) { // Find a power of 2 >= toSize //找一个值（2的n次方，且>=toSize） int capacity = roundUpToPowerOf2(toSize); //下次扩容阈值 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); } // internal utilities void init() { } /** * 初始化hashSeed */ final boolean initHashSeedAsNeeded(int capacity) { boolean currentAltHashing = hashSeed != 0; boolean useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); boolean switching = currentAltHashing ^ useAltHashing; if (switching) { hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0; } return switching; } /** * 生成hash值 */ final int hash(Object k) { int h = hashSeed; //如果key是字符串，调用un.misc.Hashing.stringHash32生成hash值 //Oracle表示能生成更好的hash分布，不过这在jdk8中已删除 if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } //一次散列，调用k的hashCode方法，与hashSeed做异或操作 h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). //二次散列， h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * 返回hash值的索引，采用除模取余法，h & (length-1)操作 等价于 hash % length操作， 但&操作性能更优 */ static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); } /** * 返回key-value映射个数 */ public int size() { return size; } /** * 判断map是否为空 */ public boolean isEmpty() { return size == 0; } /** * 返回指定key对应的value */ public V get(Object key) { //key为null情况 if (key == null) return getForNullKey(); //根据key查找节点 Entry<K,V> entry = getEntry(key); //返回key对应的值 return null == entry ? null : entry.getValue(); } /** * 查找key为null的value，注意如果key为null，则其hash值为0，默认是放在table[0]里的 */ private V getForNullKey() { if (size == 0) { return null; } //在table[0]的链表上查找key为null的键值对，因为null默认是存在table[0]的桶里 for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } /** *判断是否包含指定的key */ public boolean containsKey(Object key) { return getEntry(key) != null; } /** * 根据key查找键值对，找不到返回null */ final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } //如果key为null，hash值为0，否则调用hash方法，对key生成hash值 int hash = (key == null) ? 0 : hash(key); //调用indexFor方法生成hash值的索引，遍历该索引下的链表，查找key“相等”的键值对 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } /** * 向map存入一个键值对，如果key已存在，则覆盖 */ public V put(K key, V value) { //数组为空，对数组扩容 if (table == EMPTY_TABLE) { inflateTable(threshold); } //对key为null的键值对调用putForNullKey处理 if (key == null) return putForNullKey(value); //生成hash值 int hash = hash(key); //生成hash值索引 int i = indexFor(hash, table.length); //查找是否有key“相等”的键值对，有的话覆盖 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } //操作次数加一，用于迭代器快速失败行为 modCount++; //在指定hash值索引处的链表上增加该键值对 addEntry(hash, key, value, i); return null; } /** * 存放key为null的键值对，存放在索引为0的链表上，已存在的话，替换 */ private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { //已存在key为null，则替换 if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } //操作次数加一，用于迭代器快速失败行为 modCount++; //在指定hash值索引处的链表上增加该键值对 addEntry(0, null, value, 0); return null; } /** * 添加键值对 */ private void putForCreate(K key, V value) { //生成hash值 int hash = null == key ? 0 : hash(key); //生成hash值索引， int i = indexFor(hash, table.length); /** * key“相等”，则替换 */ for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value; return; } } //在指定索引处的链表上创建该键值对 createEntry(hash, key, value, i); } //将制定map的键值对添加到map中 private void putAllForCreate(Map<? extends K, ? extends V> m) { for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) putForCreate(e.getKey(), e.getValue()); } /** * 对数组扩容 */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //创建一个指定大小的数组 Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); //table索引替换成新数组 table = newTable; //重新计算阈值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } /** * 拷贝旧的键值对到新的哈希表中 */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //遍历旧的数组 for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } //根据新的数组长度，重新计算索引， int i = indexFor(e.hash, newCapacity); //插入到链表表头 e.next = newTable[i]; //将e放到索引为i处 newTable[i] = e; //将e设置成下个节点 e = next; } } } /** * 将制定map的键值对put到本map，key“相等”的直接覆盖 */ public void putAll(Map<? extends K, ? extends V> m) { int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; //空map，扩容 if (table == EMPTY_TABLE) { inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold)); } /* * 判断是否需要扩容 */ if (numKeysToBeAdded > threshold) { int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); if (targetCapacity > MAXIMUM_CAPACITY) targetCapacity = MAXIMUM_CAPACITY; int newCapacity = table.length; while (newCapacity < targetCapacity) newCapacity <<= 1; if (newCapacity > table.length) resize(newCapacity); } //依次遍历键值对，并put for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) put(e.getKey(), e.getValue()); } /** * 移除指定key的键值对 */ public V remove(Object key) { Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value); } /** * 移除指定key的键值对 */ final Entry<K,V> removeEntryForKey(Object key) { if (size == 0) { return null; } //计算hash值及索引 int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; //头节点为table[i]的单链表上执行删除节点操作 while (e != null) { Entry<K,V> next = e.next; Object k; //找到要删除的节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } /** * 删除指定键值对对象(Entry对象) */ final Entry<K,V> removeMapping(Object o) { if (size == 0 || !(o instanceof Map.Entry)) return null; Map.Entry<K,V> entry = (Map.Entry<K,V>) o; Object key = entry.getKey(); int hash = (key == null) ? 0 : hash(key); //得到数组索引 int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; //开始遍历该单链表 while (e != null) { Entry<K,V> next = e.next; //找到节点 if (e.hash == hash && e.equals(entry)) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } /** * 清空map，将table数组所有元素设为null */ public void clear() { modCount++; Arrays.fill(table, null); size = 0; } /** * 判断是否含有指定value的键值对 */ public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry[] tab = table; //遍历table数组 for (int i = 0; i < tab.length ; i++) //遍历每条单链表 for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; } /** * 判断是否含有value为null的键值对 */ private boolean containsNullValue() { Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (e.value == null) return true; return false; } /** * 浅拷贝，键值对不复制 */ public Object clone() { HashMap<K,V> result = null; try { result = (HashMap<K,V>)super.clone(); } catch (CloneNotSupportedException e) { // assert false; } if (result.table != EMPTY_TABLE) { result.inflateTable(Math.min( (int) Math.min( size * Math.min(1 / loadFactor, 4.0f), // we have limits... HashMap.MAXIMUM_CAPACITY), table.length)); } result.entrySet = null; result.modCount = 0; result.size = 0; result.init(); result.putAllForCreate(this); return result; } //内部类，节点对象，每个节点包含下个节点的引用 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; /** * 创建节点 */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } //获取节点的key public final K getKey() { return key; } //获取节点的value public final V getValue() { return value; } //设置新value，并返回旧的value public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } //判断key和value是否相同,两个都“相等”，返回true public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that's already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { } } /** * 添加新节点，如有必要，执行扩容操作 */ void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } /** * 插入单链表表头 */ void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; } //hashmap迭代器 private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // 下个键值对索引 int expectedModCount; // 用于判断快速失败行为 int index; // current slot Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } } //ValueIterator迭代器 private final class ValueIterator extends HashIterator<V> { public V next() { return nextEntry().value; } } //KeyIterator迭代器 private final class KeyIterator extends HashIterator<K> { public K next() { return nextEntry().getKey(); } } ////KeyIterator迭代器 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } } // 返回迭代器方法 Iterator<K> newKeyIterator() { return new KeyIterator(); } Iterator<V> newValueIterator() { return new ValueIterator(); } Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } // Views private transient Set<Map.Entry<K,V>> entrySet = null; /** * 返回一个set集合，包含key */ public Set<K> keySet() { Set<K> ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } private final class KeySet extends AbstractSet<K> { public Iterator<K> iterator() { return newKeyIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { return HashMap.this.removeEntryForKey(o) != null; } public void clear() { HashMap.this.clear(); } } /** * 返回一个value集合，包含value */ public Collection<V> values() { Collection<V> vs = values; return (vs != null ? vs : (values = new Values())); } private final class Values extends AbstractCollection<V> { public Iterator<V> iterator() { return newValueIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsValue(o); } public void clear() { HashMap.this.clear(); } } /** * 返回一个键值对集合 */ public Set<Map.Entry<K,V>> entrySet() { return entrySet0(); } private Set<Map.Entry<K,V>> entrySet0() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { return newEntryIterator(); } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<K,V> e = (Map.Entry<K,V>) o; Entry<K,V> candidate = getEntry(e.getKey()); return candidate != null && candidate.equals(e); } public boolean remove(Object o) { return removeMapping(o) != null; } public int size() { return size; } public void clear() { HashMap.this.clear(); } } /** * map序列化,可实现深拷贝 */ private void writeObject(java.io.ObjectOutputStream s) throws IOException { // Write out the threshold, loadfactor, and any hidden stuff s.defaultWriteObject(); // Write out number of buckets if (table==EMPTY_TABLE) { s.writeInt(roundUpToPowerOf2(threshold)); } else { s.writeInt(table.length); } // Write out size (number of Mappings) s.writeInt(size); // Write out keys and values (alternating) if (size > 0) { for(Map.Entry<K,V> e : entrySet0()) { s.writeObject(e.getKey()); s.writeObject(e.getValue()); } } } private static final long serialVersionUID = 362498820763181265L; /** * 反序列化，读取字节码转为对象 */ private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold (ignored), loadfactor, and any hidden stuff s.defaultReadObject(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) { throw new InvalidObjectException("Illegal load factor: " + loadFactor); } // set other fields that need values table = (Entry<K,V>[]) EMPTY_TABLE; // Read in number of buckets s.readInt(); // ignored. // Read number of mappings int mappings = s.readInt(); if (mappings < 0) throw new InvalidObjectException("Illegal mappings count: " + mappings); // capacity chosen by number of mappings and desired load (if >= 0.25) int capacity = (int) Math.min( mappings * Math.min(1 / loadFactor, 4.0f), // we have limits... HashMap.MAXIMUM_CAPACITY); // allocate the bucket array; if (mappings > 0) { inflateTable(capacity); } else { threshold = capacity; } init(); // Give subclass a chance to do its thing. // Read the keys and values, and put the mappings in the HashMap for (int i = 0; i < mappings; i++) { K key = (K) s.readObject(); V value = (V) s.readObject(); putForCreate(key, value); } } // These methods are used when serializing HashSets int capacity() { return table.length; } float loadFactor() { return loadFactor; } } } |
上述轉自: HashMap源码分析
探討 Hashmap 存取
既然是線性陣列，為什麼能隨機存取？這裡HashMap用了一個小演算法，大致是這樣實現：
|
1 2 3 4 5 6 7 8 9 |
// 存储时: int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值 int index = hash % Entry[].length; Entry[index] = value; // 取值时: int hash = key.hashCode(); int index = hash % Entry[].length; return Entry[index]; |
put
疑問：如果兩個key通過hash%Entry[].length得到的index相同，會不會有覆蓋的危險？
這裡HashMap裡面用到鏈式資料結構的一個概念。上面我們提到過Entry類裡面有一個next屬性，作用是指向下一個Entry。打個比方， 第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:Entry[0] = A。一會後又進來一個鍵值對B，通過計算其index也等於0，現在怎麼辦？HashMap會這樣做:B.next = A,Entry[0] = B,如果又進來C，index也等於0,那麼C.next = B,Entry[0] = C；這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性連結在一起。所以疑問不用擔心。也就是說陣列中儲存的是最後插入的元素。到這裡為止，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 |
public V put(K key, V value) { if (key == null) return putForNullKey(value); //null总是放在数组的第一个链表中 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); //遍历链表 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果key在链表中已存在，则替换为新value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next //如果size超过threshold，则扩充table大小。再散列 if (size++ >= threshold) resize(2 * table.length); } |
當然HashMap裡面也包含一些優化方面的實現，這裡也說一下。比如：Entry[]的長度一定後，隨著map裡面資料的越來越長，這樣同一個index的鏈就會很長，會不會影響效能？HashMap裡面設定一個因子，隨著map的size越來越大，Entry[]會以一定的規則加長長度。
get
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); //先定位到数组元素，再遍历该元素处的链表 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } |
null key的存取
null key總是存放在Entry[]陣列的第一個元素。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } |
確定陣列index：hashcode % table.length取模
HashMap存取時，都需要計算當前key應該對應Entry[]陣列哪個元素，即計算陣列下標；演算法如下：
|
1 2 3 4 5 6 |
/** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); } |
按位取並，作用上相當於取模mod或者取餘%。
這意味著陣列下標相同，並不表示hashCode相同。
table初始大小
|
1 2 3 4 5 6 7 8 9 10 11 |
public HashMap(int initialCapacity, float loadFactor) { ..... // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); } |
注意 table初始大小并不是构造函数中的initialCapacity！！而是 >= initialCapacity的2的n次幂！！！！
解決hash衝突的辦法
- 開放定址法（線性探測再雜湊，二次探測再雜湊，偽隨機探測再雜湊）
- 再雜湊法
- 鏈地址法
- 建立一個公共溢位區
Java中hashmap的解決辦法就是採用的鏈地址法。
再散列rehash过程
當雜湊表的容量超過預設容量時，必須調整table的大小。當容量已經達到最大可能值時，那麼該方法就將容量調整到Integer.MAX_VALUE返回，這時，需要建立一張新表，將原表的對映到新表中。
|
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 |
/** * Rehashes the contents of this map into a new array with a * larger capacity. This method is called automatically when the * number of keys in this map reaches its threshold. * * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * * @param newCapacity the new capacity, MUST be a power of two; * must be greater than current capacity unless current * capacity is MAXIMUM_CAPACITY (in which case value * is irrelevant). */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } /** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; //重新计算index int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } |
常見問題
如果兩個鍵的hashcode相同，你如何獲取值物件？
當我們呼叫get()方法，HashMap會使用鍵物件的hashcode找到bucket位置，然後獲取值物件。找到bucket位置之後，會呼叫keys.equals()方法去找到連結串列中正確的節點，最終找到要找的值物件。
如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦？
hashMap預設的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會建立原來HashMap大小的兩倍的bucket陣列，來重新調整map的大小，並將原來的物件放入新的bucket陣列中。這個過程叫作rehashing，因為它呼叫hash方法找到新的bucket位置。
當重新調整HashMap大小的時候，確實存在條件競爭，因為如果兩個執行緒都發現HashMap需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，儲存在連結串列中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap並不會將元素放在連結串列的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了，那麼就死迴圈了。
為什麼String, Interger這樣的wrapper類適合作為鍵？
String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那麼就不能從HashMap中找到你想要的物件。不可變性還有其他的優點如執行緒安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那麼請這麼做吧。因為獲取物件的時候要用到equals()和hashCode()方法，那麼鍵物件正確的重寫這兩個方法是非常重要的。如果兩個不相等的物件返回不同的hashcode的話，那麼碰撞的機率就會小些，這樣就能提高HashMap的效能。
我們可以使用自定義的物件作為鍵嗎？
你可能使用任何物件作為鍵，只要它遵守了equals()和hashCode()方法的定義規則，並且當物件插入到Map中之後將不會再改變了。如果這個自定義物件時不可變的，那麼它已經滿足了作為鍵的條件，因為當它建立之後就已經不能改變了。
我們可以使用CocurrentHashMap來代替Hashtable嗎？
Hashtable是synchronized的，但是ConcurrentHashMap同步效能更好，因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的執行緒安全性。
為什麼需要使用Hashcode？
Java中的集合（Collection）有兩類，一類是List，再有一類是Set。前者集合內的元素是有序的，元素可以重複；後者元素無序，但元素不可重複。那麼這裡就有一個比較嚴重的問題了：要想保證元素不重複，可兩個元素是否重複應該依據什麼來判斷呢？這就是 Object.equals方法了。但是，如果每增加一個元素就檢查一次，那麼當元素很多時，後新增到集合中的元素比較的次數就非常多了。也就是說，如果集合中現在已經有1000個元素，那麼第1001個元素加入集合時，它就要呼叫1000次equals方法。這顯然會大大降低效率。
於是，Java採用了雜湊表的原理。雜湊演算法也稱為雜湊演算法，是將資料依特定演算法直接指定到一個地址上。可以這樣簡單理解，hashCode方法實際上返回的就是物件儲存位置的映像。
這樣一來，當集合要新增新的元素時，先呼叫這個元素的hashCode方法，就能定位到它應該放置的儲存位置。如果這個位置上沒有元素，它就可以直接儲存在這個位置上，不用再進行任何比較了；如果這個位置上已經有元素了，就呼叫它的equals方法與新元素進行比較，相同的話就不存了，不相同就表示發生衝突了，散列表對於衝突有具體的解決辦法，但最終還會將新元素儲存在適當的位置。這樣一來，實際呼叫equals方法的次數就大大降低了，幾乎只需要一兩次。
擅長使用 C# 和 Java 開發項目，全棧開發工程師，前端主要使用 Vue 其次 Angular ，目前正在學習分布式架構，運維研發兼具，平時愛好鑽研技術並應用於實務當中，常駐於上海。
相逢就是有緣，留下足跡吧！