1 /** 2 * Hashtable继承于Dictionary类，且实现了Map接口 3 * 4 */ 5 public class Hashtable<K,V> 6 extends Dictionary<K,V> 7 implements Map<K,V>, Cloneable, java.io.Serializable { 8 9 /** 10 * 定义内部存储数据的Entry数组。 11 */ 12 private transient Entry[] table; 13 14 /** 15 * 定义table中的实际entry数。 16 */ 17 private transient int count; 18 19 /** 20 * 定义一个界限值，如果count超过这个界限值，则rehash。 21 * threshold = (int)(capacity * loadFactor) 22 */ 23 private int threshold; 24 25 /** 26 * 定义负载系数。 27 */ 28 private float loadFactor; 29 30 /** 31 * 定义modCount表示此Hashtable结构上变化的次数，结构上的变化是指 32 * 改变Hashtable的内部entry数量或者执行了rehash操作。 33 */ 34 private transient int modCount = 0; 35 36 /** 序列化ID */ 37 private static final long serialVersionUID = 1421746759512286392L; 38 39 /** 40 * 根据指定的initialCapacity和loadFactor来创建一个新的空的hashtable。 41 */ 42 public Hashtable(int initialCapacity, float loadFactor) { 43 // 如果initialCapacity小于0，则抛出IllegalArgumentException异常。 44 if (initialCapacity < 0) 45 throw new IllegalArgumentException("Illegal Capacity: "+ 46 initialCapacity); 47 // 如果loadFactor小于0或者loadFactor是NaN（Not a Number），抛出IllegalArgumentException异常。 48 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 49 throw new IllegalArgumentException("Illegal Load: "+loadFactor); 50 // 如果传入的initialFacor是0，则将其赋值为1. 51 if (initialCapacity==0) 52 initialCapacity = 1; 53 this.loadFactor = loadFactor 54 // 创建长度为initialCapacity的Entry数组。 55 table = new Entry[initialCapacity]; 56 // 将initialCapacity * loadFactor的值赋给threshold。 57 threshold = (int)(initialCapacity * loadFactor); 58 } 59 60 /** 61 * 根据给定的initialCapacity创建一个新的空的hashtable， 62 * loadFactor没有传入，所以取默认值0.75。 63 */ 64 public Hashtable(int initialCapacity) { 65 this(initialCapacity, 0.75f); 66 } 67 68 /** 69 * Hashtable的不带参的构造函数，创建一个新的空的hashtable， 70 * initialCapacity的默认值是11，threshold的默认值是0.75. 71 */ 72 public Hashtable() { 73 this(11, 0.75f); 74 } 75 76 /** 77 * 根据传入的t来创建一个与t包含相同内容的hashtable， 78 * threshold取默认值0.75. 79 */ 80 public Hashtable(Map<? extends K, ? extends V> t) { 81 // initialCapacity取2*t.size()和11中的较大值。 82 this(Math.max(2*t.size(), 11), 0.75f); 83 // 把t的数组都加到新创建的hashtable中。 84 putAll(t); 85 } 86 87 /** 88 * 返回hashtable中的key的数量。 89 * 加锁。 90 */ 91 public synchronized int size() { 92 return count; 93 } 94 95 /** 96 * 判断hashtable中是否有key。 97 * 加锁。 98 */ 99 public synchronized boolean isEmpty() { 100 return count == 0; 101 } 102 103 /** 104 * 返回所有key组成的枚举对象。 105 * 加锁。 106 */ 107 public synchronized Enumeration<K> keys() { 108 return this.<K>getEnumeration(KEYS); 109 } 110 111 /** 112 * 返回所有value组成的枚举对象。 113 * 可以通过枚举的方法来依次遍历value值。 114 * 加锁。 115 */ 116 public synchronized Enumeration<V> elements() { 117 return this.<V>getEnumeration(VALUES); 118 } 119 120 /** 121 * 判断传入的value是否存在于hashtable中。 122 * 加锁。 123 */ 124 public synchronized boolean contains(Object value) { 125 // 如果value为null，则抛出NullPointerException异常。 126 if (value == null) { 127 throw new NullPointerException(); 128 } 129 130 Entry tab[] = table; 131 // 遍历table，通过equals方法来判断value是否相等。 132 for (int i = tab.length ; i-- > 0 ;) { 133 for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) { 134 if (e.value.equals(value)) { 135 // 如果相等，则返回true。 136 return true; 137 } 138 } 139 } 140 // 否则返回false。 141 return false; 142 } 143 144 /** 145 * 和contains(Object value)相同。 146 * 未加锁。 147 */ 148 public boolean containsValue(Object value) { 149 return contains(value); 150 } 151 152 /** 153 * 判断hashtable中是否包含有指定的key。 154 * 加锁。 155 */ 156 public synchronized boolean containsKey(Object key) { 157 Entry tab[] = table; 158 // 取得key的hashCode。 159 int hash = key.hashCode(); 160 // 取得key在table数组中对应的下标。 161 // hash & x7FFFFFFF可以防止hash是负数的情况。 162 // 正数与0x7FFFFFFF进行&操作后不变，负数则变为正数。 163 int index = (hash & 0x7FFFFFFF) % tab.length; 164 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 165 // 此处判断key是否相等有两个条件，分别是hashCode相等且equals也返回true。 166 if ((e.hash == hash) && e.key.equals(key)) { 167 return true; 168 } 169 } 170 // 否则返回false。 171 return false; 172 } 173 174 /** 175 * 通过给定的key取value。 176 * 加锁。 177 */ 178 public synchronized V get(Object key) { 179 Entry tab[] = table; 180 // 取得key的hashCode。 181 int hash = key.hashCode(); 182 // 取得key在table数组中对应的下标。 183 int index = (hash & 0x7FFFFFFF) % tab.length; 184 // 遍历此下标上的链表，判断是否存在相同key的值。 185 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 186 if ((e.hash == hash) && e.key.equals(key)) { 187 return e.value; 188 } 189 } 190 return null; 191 } 192 193 /** 194 * 对table数组进行扩容。此方法在key的数量超过界限值时会自动被调用。 195 */ 196 protected void rehash() { 197 // 获取扩容前的数组长度。 198 int oldCapacity = table.length; 199 Entry[] oldMap = table; 200 201 // 定义新的容量，为旧容量的2倍加上1. 202 int newCapacity = oldCapacity * 2 + 1; 203 // 创建长度为newCapacity的新Entry数组。 204 Entry[] newMap = new Entry[newCapacity]; 205 206 modCount++; 207 // 重新计算新的界限值。 208 threshold = (int)(newCapacity * loadFactor); 209 table = newMap; 210 211 // 从旧数组的最后一位开始向前遍历。 212 for (int i = oldCapacity ; i-- > 0 ;) { 213 // 遍历此下标上的链表并加入到新数组中。 214 for (Entry<K,V> old = oldMap[i] ; old != null ; ) { 215 Entry<K,V> e = old; 216 old = old.next; 217 218 int index = (e.hash & 0x7FFFFFFF) % newCapacity; 219 // 新的Entry插在数组下标上链表的第一位。 220 e.next = newMap[index]; 221 newMap[index] = e; 222 } 223 } 224 } 225 226 /** 227 * 向hashtable中添加元素。 228 * 加锁。 229 */ 230 public synchronized V put(K key, V value) { 231 // Make sure the value is not null 232 // 如果value为null，则抛出NullPointerException异常。 233 if (value == null) { 234 throw new NullPointerException(); 235 } 236 237 // Makes sure the key is not already in the hashtable. 238 // 判断hashtable中是否已存在key。 239 Entry tab[] = table; 240 // 此处看出key也不可以是null，否则也会抛出NullPointerException异常。 241 int hash = key.hashCode(); 242 // 获取key对应在数组中的下标。 243 int index = (hash & 0x7FFFFFFF) % tab.length; 244 // 遍历此下标上的链表，判断是否已存在key，如果存在则覆盖value值，并返回旧值。 245 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 246 if ((e.hash == hash) && e.key.equals(key)) { 247 V old = e.value; 248 e.value = value; 249 return old; 250 } 251 } 252 253 // 如果不存在，则要添加新的Entry，hashtable的结构发生改变，modCount自增。 254 modCount++; 255 // 如果count大于或者等于界限值，则执行refresh()方法来扩容。 256 if (count >= threshold) { 257 // Rehash the table if the threshold is exceeded 258 rehash(); 259 260 tab = table; 261 // 扩容完成后，再取得此key对应在新数组中的下标。 262 index = (hash & 0x7FFFFFFF) % tab.length; 263 } 264 265 // Creates the new entry. 266 // 创建新的Entry，并把它添加到链表的第一位。 267 Entry<K,V> e = tab[index]; 268 tab[index] = new Entry<K,V>(hash, key, value, e); 269 count++; 270 // 创建成功则返回null。 271 return null; 272 } 273 274 /** 275 * 从hashtable中删除给定的key对应的Entry。 276 * 加锁。 277 */ 278 public synchronized V remove(Object key) { 279 Entry tab[] = table; 280 int hash = key.hashCode(); 281 // 获取key在数组中对应的下标。 282 int index = (hash & 0x7FFFFFFF) % tab.length; 283 // 遍历下标上的链表。 284 for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) { 285 // 判断key是否相等。 286 if ((e.hash == hash) && e.key.equals(key)) { 287 // 如果相等，则执行删除操作，结构发生改变，modCount自增。 288 modCount++; 289 // 如果被删除的不是该链表的第一位，则将前面Entry的next属性指向后面Entry，跳过此 290 // 将被删除的Entry。 291 if (prev != null) { 292 prev.next = e.next; 293 } else { 294 // 如果被删除的是链表的第一位，则将后一位Entry赋值给此下标上的值。 295 tab[index] = e.next; 296 } 297 count--; 298 V oldValue = e.value; 299 // 将value设为null，等待垃圾回收。 300 e.value = null; 301 // 返回被删除的Entry（value已为null）。 302 return oldValue; 303 } 304 } 305 // 如果hashtable中不存在此key，则直接返回null。 306 return null; 307 } 308 309 /** 310 * 将给定的Map类型的t里所有的Entry添加到当前hashtable中，如果key有重复则会被覆盖。 311 * 加锁。 312 */ 313 public synchronized void putAll(Map<? extends K, ? extends V> t) { 314 for (Map.Entry<? extends K, ? extends V> e : t.entrySet()) 315 put(e.getKey(), e.getValue()); 316 } 317 318 /** 319 * 清空此hashtable中的数组。 320 */ 321 public synchronized void clear() { 322 Entry tab[] = table; 323 // 结构发生改变，modCount自增。 324 modCount++; 325 for (int index = tab.length; --index >= 0; ) 326 tab[index] = null; 327 count = 0; 328 } 329 330 /** 331 * 浅层复制一份hashtable。 332 * 加锁。 333 */ 334 public synchronized Object clone() { 335 try { 336 Hashtable<K,V> t = (Hashtable<K,V>) super.clone(); 337 t.table = new Entry[table.length]; 338 // 因为Entry实现了自己的clone方法，所以需要调用。 339 for (int i = table.length ; i-- > 0 ; ) { 340 t.table[i] = (table[i] != null) 341 ? (Entry<K,V>) table[i].clone() : null; 342 } 343 t.keySet = null; 344 t.entrySet = null; 345 t.values = null; 346 t.modCount = 0; 347 return t; 348 } catch (CloneNotSupportedException e) { 349 // this shouldn't happen, since we are Cloneable 350 throw new InternalError(); 351 } 352 } 353 354 /** 355 * 实现自己的toString方法。 356 * 加锁。 357 */ 358 public synchronized String toString() { 359 int max = size() - 1; 360 if (max == -1) 361 return "{}"; 362 363 StringBuilder sb = new StringBuilder(); 364 Iterator<Map.Entry<K,V>> it = entrySet().iterator(); 365 366 sb.append('{'); 367 for (int i = 0; ; i++) { 368 Map.Entry<K,V> e = it.next(); 369 K key = e.getKey(); 370 V value = e.getValue(); 371 // 这里做了"key == this"的判断，应该是为了防止死循环。 372 sb.append(key == this ? "(this Map)" : key.toString()); 373 sb.append('='); 374 sb.append(value == this ? "(this Map)" : value.toString()); 375 376 if (i == max) 377 return sb.append('}').toString(); 378 sb.append(", "); 379 } 380 } 381 382 /** 383 * 根据传入的type值，返回对应的枚举对象。 384 * 如果count为0，则直接返回枚举类的空实现。 385 */ 386 private <T> Enumeration<T> getEnumeration(int type) { 387 if (count == 0) { 388 return (Enumeration<T>)emptyEnumerator; 389 } else { 390 return new Enumerator<T>(type, false); 391 } 392 } 393 /** 394 * 根据传入的type值，返回对应的迭代器对象。 395 * 如果count为0，则直接返回迭代器的空实现。 396 */ 397 private <T> Iterator<T> getIterator(int type) { 398 if (count == 0) { 399 return (Iterator<T>) emptyIterator; 400 } else { 401 return new Enumerator<T>(type, true); 402 } 403 } 404 405 // Views 406 407 /** 408 * Each of these fields are initialized to contain an instance of the 409 * appropriate view the first time this view is requested. The views are 410 * stateless, so there's no reason to create more than one of each. 411 */ 412 private transient volatile Set<K> keySet = null; 413 private transient volatile Set<Map.Entry<K,V>> entrySet = null; 414 private transient volatile Collection<V> values = null; 415 416 /** 417 * 返回由hashtable中所有key组成的线程安全的Set。 418 * 对于hashtable的任何修改将会反映到此Set中，反之亦然。 419 */ 420 public Set<K> keySet() { 421 if (keySet == null) 422 keySet = Collections.synchronizedSet(new KeySet(), this); 423 return keySet; 424 } 425 426 /** 427 * 定义KeySet类。 428 */ 429 private class KeySet extends AbstractSet<K> { 430 public Iterator<K> iterator() { 431 return getIterator(KEYS); 432 } 433 public int size() { 434 return count; 435 } 436 public boolean contains(Object o) { 437 return containsKey(o); 438 } 439 public boolean remove(Object o) { 440 return Hashtable.this.remove(o) != null; 441 } 442 public void clear() { 443 Hashtable.this.clear(); 444 } 445 } 446 447 /** 448 * 返回线程安全的entrySet。 449 * 450 * @since 1.2 451 */ 452 public Set<Map.Entry<K,V>> entrySet() { 453 if (entrySet==null) 454 entrySet = Collections.synchronizedSet(new EntrySet(), this); 455 return entrySet; 456 } 457 458 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 459 public Iterator<Map.Entry<K,V>> iterator() { 460 return getIterator(ENTRIES); 461 } 462 463 public boolean add(Map.Entry<K,V> o) { 464 return super.add(o); 465 } 466 467 public boolean contains(Object o) { 468 if (!(o instanceof Map.Entry)) 469 return false; 470 Map.Entry entry = (Map.Entry)o; 471 Object key = entry.getKey(); 472 Entry[] tab = table; 473 int hash = key.hashCode(); 474 int index = (hash & 0x7FFFFFFF) % tab.length; 475 476 for (Entry e = tab[index]; e != null; e = e.next) 477 if (e.hash==hash && e.equals(entry)) 478 return true; 479 return false; 480 } 481 482 public boolean remove(Object o) { 483 if (!(o instanceof Map.Entry)) 484 return false; 485 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 486 K key = entry.getKey(); 487 Entry[] tab = table; 488 int hash = key.hashCode(); 489 int index = (hash & 0x7FFFFFFF) % tab.length; 490 491 for (Entry<K,V> e = tab[index], prev = null; e != null; 492 prev = e, e = e.next) { 493 if (e.hash==hash && e.equals(entry)) { 494 modCount++; 495 if (prev != null) 496 prev.next = e.next; 497 else 498 tab[index] = e.next; 499 500 count--; 501 e.value = null; 502 return true; 503 } 504 } 505 return false; 506 } 507 508 public int size() { 509 return count; 510 } 511 512 public void clear() { 513 Hashtable.this.clear(); 514 } 515 } 516 517 518 // Comparison and hashing 519 520 /** 521 * equals方法。 522 * 加锁。 523 */ 524 public synchronized boolean equals(Object o) { 525 // 如果o和this指向的是同一对象，则返回true。 526 if (o == this) 527 return true; 528 // 如果o不是Map类型，则返回false。 529 if (!(o instanceof Map)) 530 return false; 531 Map<K,V> t = (Map<K,V>) o; 532 // 如果o和this的size大小不一样，则返回false。 533 if (t.size() != size()) 534 return false; 535 536 // key和value的equals方法都为true的情况下才返回true。 537 try { 538 Iterator<Map.Entry<K,V>> i = entrySet().iterator(); 539 while (i.hasNext()) { 540 Map.Entry<K,V> e = i.next(); 541 K key = e.getKey(); 542 V value = e.getValue(); 543 if (value == null) { 544 if (!(t.get(key)==null && t.containsKey(key))) 545 return false; 546 } else { 547 if (!value.equals(t.get(key))) 548 return false; 549 } 550 } 551 } catch (ClassCastException unused) { 552 return false; 553 } catch (NullPointerException unused) { 554 return false; 555 } 556 557 return true; 558 } 559 560 /** 561 * 取得hashCode值。 562 * 加锁。 563 */ 564 public synchronized int hashCode() { 565 /* 566 * 在此处，为了防止hashtable中key是自身而导致死循环的现象出现， 567 * 用loadFactor作为guard来进行判断，可以避免死循环的发生。 568 */ 569 int h = 0; 570 if (count == 0 || loadFactor < 0) 571 return h; // Returns zero 572 573 loadFactor = -loadFactor; // Mark hashCode computation in progress 574 Entry[] tab = table; 575 for (int i = 0; i < tab.length; i++) 576 for (Entry e = tab[i]; e != null; e = e.next) 577 h += e.key.hashCode() ^ e.value.hashCode(); 578 loadFactor = -loadFactor; // Mark hashCode computation complete 579 580 return h; 581 } 582 583 /** 584 * Hashtable内部数据结构Entry类。 585 */ 586 private static class Entry<K,V> implements Map.Entry<K,V> { 587 int hash; 588 K key; 589 V value; 590 Entry<K,V> next; 591 592 protected Entry(int hash, K key, V value, Entry<K,V> next) { 593 this.hash = hash; 594 this.key = key; 595 this.value = value; 596 this.next = next; 597 } 598 /** 599 * 自己实现clone方法，创建一个新的Entry，从数组上的那个Entry开始， 600 * 这条链表上的所有Entry都会被clone。 601 */ 602 protected Object clone() { 603 return new Entry<K,V>(hash, key, value, 604 (next==null ? null : (Entry<K,V>) next.clone())); 605 } 606 607 // Map.Entry Ops 608 609 public K getKey() { 610 return key; 611 } 612 613 public V getValue() { 614 return value; 615 } 616 /** 617 * value依然不能为null。 618 */ 619 public V setValue(V value) { 620 if (value == null) 621 throw new NullPointerException(); 622 623 V oldValue = this.value; 624 this.value = value; 625 return oldValue; 626 } 627 628 public boolean equals(Object o) { 629 if (!(o instanceof Map.Entry)) 630 return false; 631 Map.Entry e = (Map.Entry)o; 632 // 在非null的情况下，只有key和value的equals方法都返回true的情况下才返回true。 633 return (key==null ? e.getKey()==null : key.equals(e.getKey())) && 634 (value==null ? e.getValue()==null : value.equals(e.getValue())); 635 } 636 637 // 取得hashCode，通过对key和value的hashCode进行异或操作取得。 638 public int hashCode() { 639 return hash ^ (value==null ? 0 : value.hashCode()); 640 } 641 642 public String toString() { 643 return key.toString()+"="+value.toString(); 644 } 645 } 646 647 // Types of Enumerations/Iterations 648 private static final int KEYS = 0; 649 private static final int VALUES = 1; 650 private static final int ENTRIES = 2; 651 652 /** 653 * 遍历hashtable用的类，此类实现了Enumeration和Iterator接口， 654 * 既可以返回迭代器对象也可以返回枚举对象，由传入的参数iterator决定。 655 */ 656 private class Enumerator<T> implements Enumeration<T>, Iterator<T> { 657 Entry[] table = Hashtable.this.table; 658 int index = table.length; 659 Entry<K,V> entry = null; 660 Entry<K,V> lastReturned = null; 661 int type; 662 663 /** 664 * iterator为true的时候，表明返回迭代器对象而不是枚举对象。 665 */ 666 boolean iterator; 667 668 /** 669 * The modCount value that the iterator believes that the backing 670 * Hashtable should have. If this expectation is violated, the iterator 671 * has detected concurrent modification. 672 */ 673 protected int expectedModCount = modCount; 674 675 Enumerator(int type, boolean iterator) { 676 this.type = type; 677 this.iterator = iterator; 678 } 679 680 public boolean hasMoreElements() { 681 Entry<K,V> e = entry; 682 int i = index; 683 Entry[] t = table; 684 /* Use locals for faster loop iteration */ 685 while (e == null && i > 0) { 686 e = t[--i]; 687 } 688 entry = e; 689 index = i; 690 return e != null; 691 } 692 693 public T nextElement() { 694 Entry<K,V> et = entry; 695 int i = index; 696 Entry[] t = table; 697 /* Use locals for faster loop iteration */ 698 while (et == null && i > 0) { 699 et = t[--i]; 700 } 701 entry = et; 702 index = i; 703 if (et != null) { 704 Entry<K,V> e = lastReturned = entry; 705 entry = e.next; 706 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e); 707 } 708 throw new NoSuchElementException("Hashtable Enumerator"); 709 } 710 711 // Iterator methods 712 public boolean hasNext() { 713 return hasMoreElements(); 714 } 715 716 public T next() { 717 if (modCount != expectedModCount) 718 throw new ConcurrentModificationException(); 719 return nextElement(); 720 } 721 722 public void remove() { 723 if (!iterator) 724 throw new UnsupportedOperationException(); 725 if (lastReturned == null) 726 throw new IllegalStateException("Hashtable Enumerator"); 727 if (modCount != expectedModCount) 728 throw new ConcurrentModificationException(); 729 730 synchronized(Hashtable.this) { 731 Entry[] tab = Hashtable.this.table; 732 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; 733 734 for (Entry<K,V> e = tab[index], prev = null; e != null; 735 prev = e, e = e.next) { 736 if (e == lastReturned) { 737 modCount++; 738 expectedModCount++; 739 if (prev == null) 740 tab[index] = e.next; 741 else 742 prev.next = e.next; 743 count--; 744 lastReturned = null; 745 return; 746 } 747 } 748 throw new ConcurrentModificationException(); 749 } 750 } 751 } 752 753 754 private static Enumeration emptyEnumerator = new EmptyEnumerator(); 755 private static Iterator emptyIterator = new EmptyIterator(); 756 757 /** 758 * Hashtable的枚举对象的空实现。 759 */ 760 private static class EmptyEnumerator implements Enumeration<Object> { 761 762 EmptyEnumerator() { 763 } 764 765 public boolean hasMoreElements() { 766 return false; 767 } 768 769 public Object nextElement() { 770 throw new NoSuchElementException("Hashtable Enumerator"); 771 } 772 } 773 774 775 /** 776 * Hashtable的迭代器的空对象的实现。 777 */ 778 private static class EmptyIterator implements Iterator<Object> { 779 780 EmptyIterator() { 781 } 782 783 public boolean hasNext() { 784 return false; 785 } 786 787 public Object next() { 788 throw new NoSuchElementException("Hashtable Iterator"); 789 } 790 791 public void remove() { 792 throw new IllegalStateException("Hashtable Iterator"); 793 } 794 795 } 796 797 }
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/19418.html