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
| package java.util; import java.io.*; public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 默认的初始容量(容量为HashMap中槽的数目)是16,且实际容量必须是2的整数次幂。 static final int DEFAULT_INITIAL_CAPACITY = 16; // 最大容量(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换) static final int MAXIMUM_CAPACITY = 1 << 30; // 默认加载因子为0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 存储数据的Entry数组,长度是2的幂。 // HashMap采用链表法解决冲突,每一个Entry本质上是一个单向链表 transient Entry[] table; // HashMap的底层数组中已用槽的数量 transient int size; // HashMap的阈值,用于判断是否需要调整HashMap的容量(threshold = 容量*加载因子) int threshold; // 加载因子实际大小 final float loadFactor; // HashMap被改变的次数 transient volatile int modCount; // 指定“容量大小”和“加载因子”的构造函数 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // HashMap的最大容量只能是MAXIMUM_CAPACITY if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //加载因此不能小于0 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 找出“大于initialCapacity”的最小的2的幂 int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; // 设置“加载因子” this.loadFactor = loadFactor; // 设置“HashMap阈值”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。 threshold = (int)(capacity * loadFactor); // 创建Entry数组,用来保存数据 table = new Entry[capacity]; init(); } // 指定“容量大小”的构造函数 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 默认构造函数。 public HashMap() { // 设置“加载因子”为默认加载因子0.75 this.loadFactor = DEFAULT_LOAD_FACTOR; // 设置“HashMap阈值”,当HashMap中存储数据的数量达到threshold时,就需要将HashMap的容量加倍。 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); // 创建Entry数组,用来保存数据 table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } // 包含“子Map”的构造函数 public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); // 将m中的全部元素逐个添加到HashMap中 putAllForCreate(m); } //求hash值的方法,重新计算hash值 static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } // 返回h在数组中的索引值,这里用&代替取模,旨在提升效率 // h & (length-1)保证返回值的小于length static int indexFor(int h, int length) { return h & (length-1); } public int size() { return size; } public boolean isEmpty() { return size == 0; } // 获取key对应的value public V get(Object key) { if (key == null) return getForNullKey(); // 获取key的hash值 int hash = hash(key.hashCode()); // 在“该hash值对应的链表”上查找“键值等于key”的元素 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //判断key是否相同 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } //没找到则返回null return null; } // 获取“key为null”的元素的值 // HashMap将“key为null”的元素存储在table[0]位置,但不一定是该链表的第一个位置! private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } // HashMap是否包含key public boolean containsKey(Object key) { return getEntry(key) != null; } // 返回“键为key”的键值对 final Entry<K,V> getEntry(Object key) { // 获取哈希值 // HashMap将“key为null”的元素存储在table[0]位置,“key不为null”的则调用hash()计算哈希值 int hash = (key == null) ? 0 : hash(key.hashCode()); // 在“该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; } // 将“key-value”添加到HashMap中 public V put(K key, V value) { // 若“key为null”,则将该键值对添加到table[0]中。 if (key == null) return putForNullKey(value); // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。 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取代旧的value。然后退出! if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 若“该key”对应的键值对不存在,则将“key-value”添加到table中 modCount++; //将key-value添加到table[i]处 addEntry(hash, key, value, i); return null; } // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置 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; } } // 如果没有存在key为null的键值对,则直接题阿见到table[0]处! modCount++; addEntry(0, null, value, 0); return null; } // 创建HashMap对应的“添加方法”, // 它和put()不同。putForCreate()是内部方法,它被构造函数等调用,用来创建HashMap // 而put()是对外提供的往HashMap中添加元素的方法。 private void putForCreate(K key, V value) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); // 若该HashMap表中存在“键值等于key”的元素,则替换该元素的value值 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; } } // 若该HashMap表中不存在“键值等于key”的元素,则将该key-value添加到HashMap中 createEntry(hash, key, value, i); } // 将“m”中的全部元素都添加到HashMap中。 // 该方法被内部的构造HashMap的方法所调用。 private void putAllForCreate(Map<? extends K, ? extends V> m) { // 利用迭代器将元素逐个添加到HashMap中 for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry<? extends K, ? extends V> e = i.next(); putForCreate(e.getKey(), e.getValue()); } } // 重新调整HashMap的大小,newCapacity是调整后的容量 void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果就容量已经达到了最大值,则不能再扩容,直接返回 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 新建一个HashMap,将“旧HashMap”的全部元素添加到“新HashMap”中, // 然后,将“新HashMap”赋值给“旧HashMap”。 Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } // 将HashMap中的全部元素都添加到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; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } // 将"m"的全部元素都添加到HashMap中 public void putAll(Map<? extends K, ? extends V> m) { // 有效性判断 int numKeysToBeAdded = m.size(); if (numKeysToBeAdded == 0) return; // 计算容量是否足够, // 若“当前阀值容量 < 需要的容量”,则将容量x2。 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); } // 通过迭代器,将“m”中的元素逐个添加到HashMap中。 for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) { Map.Entry<? extends K, ? extends V> e = i.next(); 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) { // 获取哈希值。若key为null,则哈希值为0;否则调用hash()进行计算 int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; // 删除链表中“键为key”的元素 // 本质是“删除单向链表中的节点” 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; } // 删除“键值对” final Entry<K,V> removeMapping(Object o) { if (!(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.hashCode()); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; // 删除链表中的“键值对e” // 本质是“删除单向链表中的节点” 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; } // 清空HashMap,将所有的元素设为null public void clear() { modCount++; Entry[] tab = table; for (int i = 0; i < tab.length; i++) tab[i] = null; size = 0; } // 是否包含“值为value”的元素 public boolean containsValue(Object value) { // 若“value为null”,则调用containsNullValue()查找 if (value == null) return containsNullValue(); // 若“value不为null”,则查找HashMap中是否有值为value的节点。 Entry[] tab = 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; } // 是否包含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; } // 克隆一个HashMap,并返回Object对象 public Object clone() { HashMap<K,V> result = null; try { result = (HashMap<K,V>)super.clone(); } catch (CloneNotSupportedException e) { // assert false; } result.table = new Entry[table.length]; result.entrySet = null; result.modCount = 0; result.size = 0; result.init(); // 调用putAllForCreate()将全部元素添加到HashMap中 result.putAllForCreate(this); return result; } // Entry是单向链表。 // 它是 “HashMap链式存储法”对应的链表。 // 它实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数 static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; // 指向下一个节点 Entry<K,V> next; final int hash; // 构造函数。 // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 判断两个Entry是否相等 // 若两个Entry的“key”和“value”都相等,则返回true。 // 否则,返回false 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; } // 实现hashCode() public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } // 当向HashMap中添加元素时,绘调用recordAccess()。 // 这里不做任何处理 void recordAccess(HashMap<K,V> m) { } // 当从HashMap中删除元素时,绘调用recordRemoval()。 // 这里不做任何处理 void recordRemoval(HashMap<K,V> m) { } } // 新增Entry。将“key-value”插入指定位置,bucketIndex是位置索引。 void addEntry(int hash, K key, V value, int bucketIndex) { // 保存“bucketIndex”位置的值到“e”中 Entry<K,V> e = table[bucketIndex]; // 设置“bucketIndex”位置的元素为“新Entry”, // 设置“e”为“新Entry的下一个节点” table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 若HashMap的实际大小 不小于 “阈值”,则调整HashMap的大小 if (size++ >= threshold) resize(2 * table.length); } // 创建Entry。将“key-value”插入指定位置。 void createEntry(int hash, K key, V value, int bucketIndex) { // 保存“bucketIndex”位置的值到“e”中 Entry<K,V> e = table[bucketIndex]; // 设置“bucketIndex”位置的元素为“新Entry”, // 设置“e”为“新Entry的下一个节点” table[bucketIndex] = new Entry<K,V>(hash, key, value, e); size++; } // HashIterator是HashMap迭代器的抽象出来的父类,实现了公共了函数。 // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。 private abstract class HashIterator<E> implements Iterator<E> { // 下一个元素 Entry<K,V> next; // expectedModCount用于实现fast-fail机制。 int expectedModCount; // 当前索引 int index; // 当前元素 Entry<K,V> current; HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; // 将next指向table中第一个不为null的元素。 // 这里利用了index的初始值为0,从0开始依次向后遍历,直到找到不为null的元素就退出循环。 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(); // 注意!!! // 一个Entry就是一个单向链表 // 若该Entry的下一个节点不为空,就将next指向下一个节点; // 否则,将next指向下一个链表(也是下一个Entry)的不为null的节点。 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; } } // value的迭代器 private final class ValueIterator extends HashIterator<V> { public V next() { return nextEntry().value; } } // key的迭代器 private final class KeyIterator extends HashIterator<K> { public K next() { return nextEntry().getKey(); } } // Entry的迭代器 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } } // 返回一个“key迭代器” Iterator<K> newKeyIterator() { return new KeyIterator(); } // 返回一个“value迭代器” Iterator<V> newValueIterator() { return new ValueIterator(); } // 返回一个“entry迭代器” Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } // HashMap的Entry对应的集合 private transient Set<Map.Entry<K,V>> entrySet = null; // 返回“key的集合”,实际上返回一个“KeySet对象” public Set<K> keySet() { Set<K> ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } // Key对应的集合 // KeySet继承于AbstractSet,说明该集合中没有重复的Key。 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集合”,实际上返回的是一个Values对象 public Collection<V> values() { Collection<V> vs = values; return (vs != null ? vs : (values = new Values())); } // “value集合” // Values继承于AbstractCollection,不同于“KeySet继承于AbstractSet”, // Values中的元素能够重复。因为不同的key可以指向相同的value。 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(); } } // 返回“HashMap的Entry集合” public Set<Map.Entry<K,V>> entrySet() { return entrySet0(); } // 返回“HashMap的Entry集合”,它实际是返回一个EntrySet对象 private Set<Map.Entry<K,V>> entrySet0() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } // EntrySet对应的集合 // EntrySet继承于AbstractSet,说明该集合中没有重复的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(); } } // java.io.Serializable的写入函数 // 将HashMap的“总的容量,实际容量,所有的Entry”都写入到输出流中 private void writeObject(java.io.ObjectOutputStream s) throws IOException { Iterator<Map.Entry<K,V>> i = (size > 0) ? entrySet0().iterator() : null; // Write out the threshold, loadfactor, and any hidden stuff s.defaultWriteObject(); // Write out number of buckets s.writeInt(table.length); // Write out size (number of Mappings) s.writeInt(size); // Write out keys and values (alternating) if (i != null) { while (i.hasNext()) { Map.Entry<K,V> e = i.next(); s.writeObject(e.getKey()); s.writeObject(e.getValue()); } } } private static final long serialVersionUID = 362498820763181265L; // java.io.Serializable的读取函数:根据写入方式读出 // 将HashMap的“总的容量,实际容量,所有的Entry”依次读出 private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { // Read in the threshold, loadfactor, and any hidden stuff s.defaultReadObject(); // Read in number of buckets and allocate the bucket array; int numBuckets = s.readInt(); table = new Entry[numBuckets]; init(); // Give subclass a chance to do its thing. // Read in size (number of Mappings) int size = s.readInt(); // Read the keys and values, and put the mappings in the HashMap for (int i=0; i<size; i++) { K key = (K) s.readObject(); V value = (V) s.readObject(); putForCreate(key, value); } } // 返回“HashMap总的容量” int capacity() { return table.length; } // 返回“HashMap的加载因子” float loadFactor() { return loadFactor; } }
|