Hashtable源码解析（JDK1.8）

   1 package java.util;
   2 
   3 import java.io.*;
   4 import java.util.concurrent.ThreadLocalRandom;
   5 import java.util.function.BiConsumer;
   6 import java.util.function.Function;
   7 import java.util.function.BiFunction;
   8 
   9 import sun.misc.SharedSecrets;
  10 
  11 /**
  12  * Hashtable存储的内容是键值对(key-value)映射，其底层实现是一个Entry数组+链表；
  13  * Hashtable和HashMap一样也是散列表，存储元素也是键值对；
  14  * HashMap允许key和value都为null，而Hashtable都不能为null，Hashtable中的映射不是有序的；
  15  * Hashtable和HashMap扩容的方法不一样，Hashtable中数组默认大小11，扩容方式是 old*2+1。
  16  * HashMap中数组的默认大小是16，而且一定是2的指数，增加为原来的2倍。
  17  * Hashtable继承于Dictionary类（Dictionary类声明了操作键值对的接口方法），实现Map接口（定义键值对接口）；
  18  * Hashtable大部分类用synchronized修饰，证明Hashtable是线程安全的。
  19  */
  20 public class Hashtable<K, V>
  21         extends Dictionary<K, V>
  22         implements Map<K, V>, Cloneable, java.io.Serializable {
  23 
  24     /**
  25      * 键值对/Entry数组，每个Entry本质上是一个单向链表的表头
  26      */
  27     private transient Entry<?, ?>[] table;
  28 
  29     /**
  30      * 当前表中的Entry数量，如果超过了阈值，就会扩容，即调用rehash方法
  31      */
  32     private transient int count;
  33 
  34     /**
  35      * rehash阈值
  36      *
  37      * @serial
  38      */
  39     private int threshold;
  40 
  41     /**
  42      * 负载因子
  43      *
  44      * @serial
  45      */
  46     private float loadFactor;
  47 
  48     /**
  49      * 用来实现"fail-fast"机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行
  50      * 迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出
  51      * ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你（你已经出错了）。
  52      */
  53     private transient int modCount = 0;
  54 
  55     /**
  56      * 版本序列号
  57      */
  58     private static final long serialVersionUID = 1421746759512286392L;
  59 
  60     /**
  61      * 指定容量大小和加载因子的构造函数
  62      *
  63      * @param initialCapacity 容量大小
  64      * @param loadFactor      负载因子
  65      * @throws IllegalArgumentException if the initial capacity is less
  66      *                                  than zero, or if the load factor is nonpositive.
  67      */
  68     public Hashtable(int initialCapacity, float loadFactor) {
  69         if (initialCapacity < 0)
  70             throw new IllegalArgumentException("Illegal Capacity: " +
  71                     initialCapacity);
  72         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  73             throw new IllegalArgumentException("Illegal Load: " + loadFactor);
  74 
  75         if (initialCapacity == 0)
  76             initialCapacity = 1;
  77         this.loadFactor = loadFactor;
  78         table = new Entry<?, ?>[initialCapacity];
  79         threshold = (int) Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  80     }
  81 
  82     /**
  83      * 指定容量大小的构造函数
  84      *
  85      * @param initialCapacity 容量大小
  86      * @throws IllegalArgumentException if the initial capacity is less
  87      *                                  than zero.
  88      */
  89     public Hashtable(int initialCapacity) {
  90         this(initialCapacity, 0.75f);
  91     }
  92 
  93     /**
  94      * 默认构造函数
  95      */
  96     public Hashtable() {
  97         // 默认构造函数，指定的容量大小是11；加载因子是0.75
  98         this(11, 0.75f);
  99     }
 100 
 101     /**
 102      * 包含子Map的构造函数
 103      *
 104      * @param t the map whose mappings are to be placed in this map.
 105      * @throws NullPointerException if the specified map is null.
 106      * @since 1.2
 107      */
 108     public Hashtable(Map<? extends K, ? extends V> t) {
 109         this(Math.max(2 * t.size(), 11), 0.75f);
 110         putAll(t);
 111     }
 112 
 113     /**
 114      * 返回容量大小
 115      *
 116      * @return the number of keys in this hashtable.
 117      */
 118     public synchronized int size() {
 119         return count;
 120     }
 121 
 122     /**
 123      * 判空
 124      *
 125      * @return <code>true</code> if this hashtable maps no keys to values;
 126      * <code>false</code> otherwise.
 127      */
 128     public synchronized boolean isEmpty() {
 129         return count == 0;
 130     }
 131 
 132     /**
 133      * 返回所有key的枚举对象
 134      *
 135      * @return an enumeration of the keys in this hashtable.
 136      * @see Enumeration
 137      * @see #elements()
 138      * @see #keySet()
 139      * @see Map
 140      */
 141     public synchronized Enumeration<K> keys() {
 142         return this.<K>getEnumeration(KEYS);
 143     }
 144 
 145     /**
 146      * 返回所有value的枚举对象
 147      *
 148      * @return an enumeration of the values in this hashtable.
 149      * @see java.util.Enumeration
 150      * @see #keys()
 151      * @see #values()
 152      * @see Map
 153      */
 154     public synchronized Enumeration<V> elements() {
 155         return this.<V>getEnumeration(VALUES);
 156     }
 157 
 158     /**
 159      * 判断是否含有该value的键值对，在Hashtable中hashCode相同的Entry用链表组织，hashCode不同的存储在Entry数组table中；
 160      *
 161      * @param value a value to search for
 162      * @return <code>true</code> if and only if some key maps to the
 163      * <code>value</code> argument in this hashtable as
 164      * determined by the <tt>equals</tt> method;
 165      * <code>false</code> otherwise.
 166      * @throws NullPointerException if the value is <code>null</code>
 167      */
 168     public synchronized boolean contains(Object value) {
 169         if (value == null) {
 170             throw new NullPointerException();
 171         }
 172 
 173         Entry<?, ?> tab[] = table;
 174         // 查找：遍历所有Entry链表
 175         for (int i = tab.length; i-- > 0; ) {
 176             for (Entry<?, ?> e = tab[i]; e != null; e = e.next) {
 177                 if (e.value.equals(value)) {
 178                     return true;
 179                 }
 180             }
 181         }
 182         return false;
 183     }
 184 
 185     /**
 186      * 判断是否包含value值对象
 187      *
 188      * @param value value whose presence in this hashtable is to be tested
 189      * @return <tt>true</tt> if this map maps one or more keys to the
 190      * specified value
 191      * @throws NullPointerException if the value is <code>null</code>
 192      * @since 1.2
 193      */
 194     public boolean containsValue(Object value) {
 195         return contains(value);
 196     }
 197 
 198     /**
 199      * 判断是否包含key键值对象
 200      *
 201      * @param key possible key
 202      * @return <code>true</code> if and only if the specified object
 203      * is a key in this hashtable, as determined by the
 204      * <tt>equals</tt> method; <code>false</code> otherwise.
 205      * @throws NullPointerException if the key is <code>null</code>
 206      * @see #contains(Object)
 207      */
 208     public synchronized boolean containsKey(Object key) {
 209         Entry<?, ?> tab[] = table;
 210         int hash = key.hashCode();
 211         /**
 212          * 计算index, % tab.length防止数组越界
 213          * index表示key对应entry所在链表表头
 214          */
 215         int index = (hash & 0x7FFFFFFF) % tab.length;
 216         for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {
 217             if ((e.hash == hash) && e.key.equals(key)) {
 218                 return true;
 219             }
 220         }
 221         return false;
 222     }
 223 
 224     /**
 225      * 根据指定key查找对应value，查找原理与containsKey相同，查找成功返回value，否则返回null
 226      *
 227      * @param key the key whose associated value is to be returned
 228      * @return the value to which the specified key is mapped, or
 229      * {@code null} if this map contains no mapping for the key
 230      * @throws NullPointerException if the specified key is null
 231      * @see #put(Object, Object)
 232      */
 233     @SuppressWarnings("unchecked")
 234     public synchronized V get(Object key) {
 235         Entry<?, ?> tab[] = table;
 236         int hash = key.hashCode();
 237         int index = (hash & 0x7FFFFFFF) % tab.length;
 238         for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {
 239             if ((e.hash == hash) && e.key.equals(key)) {
 240                 return (V) e.value;
 241             }
 242         }
 243         return null;
 244     }
 245 
 246     /**
 247      * 规定的最大数组容量
 248      */
 249     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 250 
 251     /**
 252      * 当Hashtable中键值对总数超过阈值（容量*装载因子）后，内部自动调用rehash()增加容量，重新计算每个键值对的hashCode
 253      * int newCapacity = (oldCapacity << 1) + 1计算新容量 = 2 * 旧容量 + 1；并且根据新容量更新阈值
 254      */
 255     @SuppressWarnings("unchecked")
 256     protected void rehash() {
 257         int oldCapacity = table.length;
 258         Entry<?, ?>[] oldMap = table;
 259 
 260         /**
 261          * 新的大小为  原大小 * 2 + 1
 262          * 虽然不保证capacity是一个质数，但至少保证它是一个奇数
 263          */
 264         int newCapacity = (oldCapacity << 1) + 1;
 265         if (newCapacity - MAX_ARRAY_SIZE > 0) {
 266             if (oldCapacity == MAX_ARRAY_SIZE)
 267                 // Keep running with MAX_ARRAY_SIZE buckets
 268                 return;
 269             newCapacity = MAX_ARRAY_SIZE;
 270         }
 271         Entry<?, ?>[] newMap = new Entry<?, ?>[newCapacity];
 272 
 273         modCount++;
 274         threshold = (int) Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
 275         table = newMap;
 276         // 拷贝每个Entry链表
 277         for (int i = oldCapacity; i-- > 0; ) {
 278             for (Entry<K, V> old = (Entry<K, V>) oldMap[i]; old != null; ) {
 279                 Entry<K, V> e = old;
 280                 old = old.next;
 281                 // 重新计算每个Entry链表的表头索引（rehash）
 282                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
 283                 // 开辟链表节点
 284                 e.next = (Entry<K, V>) newMap[index];
 285                 // 拷贝
 286                 newMap[index] = e;
 287             }
 288         }
 289     }
 290 
 291     /**
 292      * 当键值对个数超过阈值，先进行rehash然后添加entry，否则直接添加entry
 293      */
 294     private void addEntry(int hash, K key, V value, int index) {
 295         modCount++;
 296 
 297         Entry<?, ?> tab[] = table;
 298         // 当前元素大于等于阈值，就扩容并且再计算hash值
 299         if (count >= threshold) {
 300             rehash();
 301 
 302             tab = table;
 303             hash = key.hashCode();
 304             index = (hash & 0x7FFFFFFF) % tab.length;
 305         }
 306 
 307         // Creates the new entry.
 308         @SuppressWarnings("unchecked")
 309         Entry<K, V> e = (Entry<K, V>) tab[index];
 310         // 和HashMap不同，Hashtable选择把新插入的元素放到链表最前边，而且没有使用红黑树
 311         tab[index] = new Entry<>(hash, key, value, e);
 312         count++;
 313     }
 314 
 315     /**
 316      * 设置键值对，key和value都不可为null，设置顺序:
 317      * 如果Hashtable含有key，设置(key, oldValue) -> (key, newValue)；
 318      * 如果Hashtable不含有key, 调用addEntry(...)添加新的键值对；
 319      *
 320      * @param key   the hashtable key
 321      * @param value the value
 322      * @return the previous value of the specified key in this hashtable,
 323      * or <code>null</code> if it did not have one
 324      * @throws NullPointerException if the key or value is
 325      *                              <code>null</code>
 326      * @see Object#equals(Object)
 327      * @see #get(Object)
 328      */
 329     public synchronized V put(K key, V value) {
 330         // value为空抛出空指针异常
 331         if (value == null) {
 332             throw new NullPointerException();
 333         }
 334 
 335         // Makes sure the key is not already in the hashtable.
 336         Entry<?, ?> tab[] = table;
 337         /**
 338          * key的hashCode是调用Object的hashCode()方法，
 339          * 是native的方法，如果为null，就会抛出空指针异常
 340          */
 341         int hash = key.hashCode();
 342         /**
 343          * 因为hash可能为负数，所以就先和0x7FFFFFFF相与
 344          * 在HashMap中，是用 (table.length - 1) & hash 计算要放置的位置
 345          */
 346         int index = (hash & 0x7FFFFFFF) % tab.length;
 347         @SuppressWarnings("unchecked")
 348         Entry<K, V> entry = (Entry<K, V>) tab[index];
 349         for (; entry != null; entry = entry.next) {
 350             if ((entry.hash == hash) && entry.key.equals(key)) {
 351                 V old = entry.value;
 352                 entry.value = value;
 353                 return old;
 354             }
 355         }
 356         // 如果key对应的值不存在，就调用addEntry方法加入
 357         addEntry(hash, key, value, index);
 358         return null;
 359     }
 360 
 361     /**
 362      * remove操作，计算key所在链表表头table[index]，然后进行单向链表的节点删除操作
 363      *
 364      * @param key the key that needs to be removed
 365      * @return the value to which the key had been mapped in this hashtable,
 366      * or <code>null</code> if the key did not have a mapping
 367      * @throws NullPointerException if the key is <code>null</code>
 368      */
 369     public synchronized V remove(Object key) {
 370         Entry<?, ?> tab[] = table;
 371         int hash = key.hashCode();
 372         int index = (hash & 0x7FFFFFFF) % tab.length;
 373         @SuppressWarnings("unchecked")
 374         Entry<K, V> e = (Entry<K, V>) tab[index];
 375         for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
 376             if ((e.hash == hash) && e.key.equals(key)) {
 377                 modCount++;
 378                 if (prev != null) {
 379                     prev.next = e.next;
 380                 } else {
 381                     tab[index] = e.next;
 382                 }
 383                 count--;
 384                 V oldValue = e.value;
 385                 e.value = null;
 386                 return oldValue;
 387             }
 388         }
 389         return null;
 390     }
 391 
 392     /**
 393      * 把所有的 映射从指定的map复制到hashTable中
 394      * 如果给定的map中的key值已经存在于hashTable中，则将会覆盖hashTable中key所对应的value（hashTable中key值不允许重复）
 395      *
 396      * @param t mappings to be stored in this map
 397      * @throws NullPointerException if the specified map is null
 398      * @since 1.2
 399      */
 400     public synchronized void putAll(Map<? extends K, ? extends V> t) {
 401         //foreach 循环map数据put到hashTable中
 402         for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
 403             put(e.getKey(), e.getValue());
 404     }
 405 
 406     /**
 407      * 清空Hashtable
 408      * 将Hashtable的table数组的值全部设为null
 409      */
 410     public synchronized void clear() {
 411         Entry<?, ?> tab[] = table;
 412         modCount++;
 413         for (int index = tab.length; --index >= 0; )
 414             tab[index] = null;
 415         count = 0;
 416     }
 417 
 418     /**
 419      * 对Hashtable的浅拷贝操作，浅拷贝所有bucket（单向链表组织形式）的表头
 420      *
 421      * @return a clone of the hashtable
 422      */
 423     public synchronized Object clone() {
 424         try {
 425             Hashtable<?, ?> t = (Hashtable<?, ?>) super.clone();
 426             t.table = new Entry<?, ?>[table.length];
 427             for (int i = table.length; i-- > 0; ) {
 428                 t.table[i] = (table[i] != null)
 429                         ? (Entry<?, ?>) table[i].clone() : null;
 430             }
 431             t.keySet = null;
 432             t.entrySet = null;
 433             t.values = null;
 434             t.modCount = 0;
 435             return t;
 436         } catch (CloneNotSupportedException e) {
 437             // this shouldn't happen, since we are Cloneable
 438             throw new InternalError(e);
 439         }
 440     }
 441 
 442     /**
 443      * 返回Hashtable对象的String表达方式，一系列以括号和逗号，空格分隔的Entry，如{key1=value1, key2=value2}
 444      *
 445      * @return a string representation of this hashtable
 446      */
 447     public synchronized String toString() {
 448         int max = size() - 1;
 449         if (max == -1)
 450             return "{}";
 451 
 452         StringBuilder sb = new StringBuilder();
 453         Iterator<Map.Entry<K, V>> it = entrySet().iterator();
 454 
 455         sb.append('{');
 456         for (int i = 0; ; i++) {
 457             Map.Entry<K, V> e = it.next();
 458             K key = e.getKey();
 459             V value = e.getValue();
 460             sb.append(key == this ? "(this Map)" : key.toString());
 461             sb.append('=');
 462             sb.append(value == this ? "(this Map)" : value.toString());
 463 
 464             if (i == max)
 465                 return sb.append('}').toString();
 466             sb.append(", ");
 467         }
 468     }
 469 
 470 
 471     private <T> Enumeration<T> getEnumeration(int type) {
 472         if (count == 0) {
 473             return Collections.emptyEnumeration();
 474         } else {
 475             return new Enumerator<>(type, false);
 476         }
 477     }
 478 
 479     /**
 480      * 获得迭代器
 481      */
 482     private <T> Iterator<T> getIterator(int type) {
 483         if (count == 0) {
 484             return Collections.emptyIterator();
 485         } else {
 486             return new Enumerator<>(type, true);
 487         }
 488     }
 489 
 490     // 视图
 491 
 492     /**
 493      * 以下每个字段初始化后会包含一个首次请求后的指定视图，视图是无状态的，所以不必创建多个
 494      */
 495     private transient volatile Set<K> keySet;
 496     private transient volatile Set<Map.Entry<K, V>> entrySet;
 497     private transient volatile Collection<V> values;
 498 
 499     /**
 500      * 返回一个被synchronizedSet封装后的KeySet对象
 501      * synchronizedSet封装的目的是对KeySet的所有方法都添加synchronized，实现多线程同步
 502      */
 503     public Set<K> keySet() {
 504         if (keySet == null)
 505             keySet = Collections.synchronizedSet(new KeySet(), this);
 506         return keySet;
 507     }
 508 
 509     /**
 510      * Hashtable的Key的Set集合
 511      * KeySet继承于AbstractSet，所以，KeySet中的元素没有重复的
 512      */
 513     private class KeySet extends AbstractSet<K> {
 514         public Iterator<K> iterator() {
 515             return getIterator(KEYS);
 516         }
 517 
 518         public int size() {
 519             return count;
 520         }
 521 
 522         public boolean contains(Object o) {
 523             return containsKey(o);
 524         }
 525 
 526         public boolean remove(Object o) {
 527             return Hashtable.this.remove(o) != null;
 528         }
 529 
 530         public void clear() {
 531             Hashtable.this.clear();
 532         }
 533     }
 534 
 535     /**
 536      * 返回一个被synchronizedSet封装后的EntrySet对象
 537      * synchronizedSet封装的目的是对EntrySet的所有方法都添加synchronized，实现多线程同步
 538      */
 539     public Set<Map.Entry<K, V>> entrySet() {
 540         if (entrySet == null)
 541             entrySet = Collections.synchronizedSet(new EntrySet(), this);
 542         return entrySet;
 543     }
 544 
 545     /**
 546      * Hashtable的Entry的Set集合
 547      * EntrySet继承于AbstractSet，所以，EntrySet中的元素没有重复的
 548      */
 549     private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
 550         public Iterator<Map.Entry<K, V>> iterator() {
 551             return getIterator(ENTRIES);
 552         }
 553 
 554         public boolean add(Map.Entry<K, V> o) {
 555             return super.add(o);
 556         }
 557 
 558         /**
 559          * 查找EntrySet中是否包含Object(0)
 560          * 首先，在table中找到o对应的Entry(Entry是一个单向链表)
 561          * 然后，查找Entry链表中是否存在Object
 562          */
 563         public boolean contains(Object o) {
 564             if (!(o instanceof Map.Entry))
 565                 return false;
 566             Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
 567             Object key = entry.getKey();
 568             Entry<?, ?>[] tab = table;
 569             int hash = key.hashCode();
 570             int index = (hash & 0x7FFFFFFF) % tab.length;
 571 
 572             for (Entry<?, ?> e = tab[index]; e != null; e = e.next)
 573                 if (e.hash == hash && e.equals(entry))
 574                     return true;
 575             return false;
 576         }
 577 
 578         /**
 579          * 删除元素Object(0)
 580          * 首先，在table中找到o对应的Entry(Entry是一个单向链表)
 581          * 然后，删除链表中的元素Object
 582          */
 583         public boolean remove(Object o) {
 584             if (!(o instanceof Map.Entry))
 585                 return false;
 586             Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
 587             Object key = entry.getKey();
 588             Entry<?, ?>[] tab = table;
 589             int hash = key.hashCode();
 590             int index = (hash & 0x7FFFFFFF) % tab.length;
 591 
 592             @SuppressWarnings("unchecked")
 593             Entry<K, V> e = (Entry<K, V>) tab[index];
 594             for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
 595                 if (e.hash == hash && e.equals(entry)) {
 596                     modCount++;
 597                     if (prev != null)
 598                         prev.next = e.next;
 599                     else
 600                         tab[index] = e.next;
 601 
 602                     count--;
 603                     e.value = null;
 604                     return true;
 605                 }
 606             }
 607             return false;
 608         }
 609 
 610         public int size() {
 611             return count;
 612         }
 613 
 614         public void clear() {
 615             Hashtable.this.clear();
 616         }
 617     }
 618 
 619     /**
 620      * 返回一个被synchronizedCollection封装后的ValueCollection对象
 621      * synchronizedCollection封装的目的是对ValueCollection的所有方法都添加synchronized，实现多线程同步
 622      */
 623     public Collection<V> values() {
 624         if (values == null)
 625             values = Collections.synchronizedCollection(new ValueCollection(),
 626                     this);
 627         return values;
 628     }
 629 
 630     /**
 631      * Hashtable的value的Collection集合。
 632      * ValueCollection继承于AbstractCollection，所以，ValueCollection中的元素可以重复的。
 633      */
 634     private class ValueCollection extends AbstractCollection<V> {
 635         public Iterator<V> iterator() {
 636             return getIterator(VALUES);
 637         }
 638 
 639         public int size() {
 640             return count;
 641         }
 642 
 643         public boolean contains(Object o) {
 644             return containsValue(o);
 645         }
 646 
 647         public void clear() {
 648             Hashtable.this.clear();
 649         }
 650     }
 651 
 652     // Comparison and hashing
 653 
 654     /**
 655      * 重新equals()函数
 656      * 若两个Hashtable的所有key-value键值对都相等，则判断它们两个相等
 657      *
 658      * @param o object to be compared for equality with this hashtable
 659      * @return true if the specified Object is equal to this Map
 660      * @see Map#equals(Object)
 661      * @since 1.2
 662      */
 663     public synchronized boolean equals(Object o) {
 664         if (o == this)
 665             return true;
 666 
 667         if (!(o instanceof Map))
 668             return false;
 669         Map<?, ?> t = (Map<?, ?>) o;
 670         if (t.size() != size())
 671             return false;
 672 
 673         try {
 674             /**
 675              * 通过迭代器依次取出当前Hashtable的key-value键值对
 676              * 并判断该键值对，存在于Hashtable(o)中。
 677              * 若不存在，则立即返回false；否则，遍历完“当前Hashtable”并返回true。
 678              */
 679             Iterator<Map.Entry<K, V>> i = entrySet().iterator();
 680             while (i.hasNext()) {
 681                 Map.Entry<K, V> e = i.next();
 682                 K key = e.getKey();
 683                 V value = e.getValue();
 684                 if (value == null) {
 685                     if (!(t.get(key) == null && t.containsKey(key)))
 686                         return false;
 687                 } else {
 688                     if (!value.equals(t.get(key)))
 689                         return false;
 690                 }
 691             }
 692         } catch (ClassCastException unused) {
 693             return false;
 694         } catch (NullPointerException unused) {
 695             return false;
 696         }
 697 
 698         return true;
 699     }
 700 
 701     /**
 702      * 计算Hashtable的哈希值
 703      *
 704      * @see Map#hashCode()
 705      * @since 1.2
 706      */
 707     public synchronized int hashCode() {
 708         int h = 0;
 709         //若 Hashtable的实际大小为0 或者 加载因子<0，则返回0
 710         if (count == 0 || loadFactor < 0)
 711             return h;  // Returns zero
 712 
 713         loadFactor = -loadFactor;  // Mark hashCode computation in progress
 714         Entry<?, ?>[] tab = table;
 715         //返回Hashtable中的每个Entry的key和value的异或值的总和
 716         for (Entry<?, ?> entry : tab) {
 717             while (entry != null) {
 718                 h += entry.hashCode();
 719                 entry = entry.next;
 720             }
 721         }
 722 
 723         loadFactor = -loadFactor;  // Mark hashCode computation complete
 724 
 725         return h;
 726     }
 727 
 728     @Override
 729     public synchronized V getOrDefault(Object key, V defaultValue) {
 730         V result = get(key);
 731         return (null == result) ? defaultValue : result;
 732     }
 733 
 734     @SuppressWarnings("unchecked")
 735     @Override
 736     public synchronized void forEach(BiConsumer<? super K, ? super V> action) {
 737         Objects.requireNonNull(action);     // explicit check required in case
 738         // table is empty.
 739         final int expectedModCount = modCount;
 740 
 741         Entry<?, ?>[] tab = table;
 742         for (Entry<?, ?> entry : tab) {
 743             while (entry != null) {
 744                 action.accept((K) entry.key, (V) entry.value);
 745                 entry = entry.next;
 746 
 747                 if (expectedModCount != modCount) {
 748                     throw new ConcurrentModificationException();
 749                 }
 750             }
 751         }
 752     }
 753 
 754     @SuppressWarnings("unchecked")
 755     @Override
 756     public synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
 757         Objects.requireNonNull(function);     // explicit check required in case
 758         // table is empty.
 759         final int expectedModCount = modCount;
 760 
 761         Entry<K, V>[] tab = (Entry<K, V>[]) table;
 762         for (Entry<K, V> entry : tab) {
 763             while (entry != null) {
 764                 entry.value = Objects.requireNonNull(
 765                         function.apply(entry.key, entry.value));
 766                 entry = entry.next;
 767 
 768                 if (expectedModCount != modCount) {
 769                     throw new ConcurrentModificationException();
 770                 }
 771             }
 772         }
 773     }
 774 
 775     @Override
 776     public synchronized V putIfAbsent(K key, V value) {
 777         Objects.requireNonNull(value);
 778 
 779         // Makes sure the key is not already in the hashtable.
 780         Entry<?, ?> tab[] = table;
 781         int hash = key.hashCode();
 782         int index = (hash & 0x7FFFFFFF) % tab.length;
 783         @SuppressWarnings("unchecked")
 784         Entry<K, V> entry = (Entry<K, V>) tab[index];
 785         for (; entry != null; entry = entry.next) {
 786             if ((entry.hash == hash) && entry.key.equals(key)) {
 787                 V old = entry.value;
 788                 if (old == null) {
 789                     entry.value = value;
 790                 }
 791                 return old;
 792             }
 793         }
 794 
 795         addEntry(hash, key, value, index);
 796         return null;
 797     }
 798 
 799     @Override
 800     public synchronized boolean remove(Object key, Object value) {
 801         Objects.requireNonNull(value);
 802 
 803         Entry<?, ?> tab[] = table;
 804         int hash = key.hashCode();
 805         int index = (hash & 0x7FFFFFFF) % tab.length;
 806         @SuppressWarnings("unchecked")
 807         Entry<K, V> e = (Entry<K, V>) tab[index];
 808         for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
 809             if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
 810                 modCount++;
 811                 if (prev != null) {
 812                     prev.next = e.next;
 813                 } else {
 814                     tab[index] = e.next;
 815                 }
 816                 count--;
 817                 e.value = null;
 818                 return true;
 819             }
 820         }
 821         return false;
 822     }
 823 
 824     @Override
 825     public synchronized boolean replace(K key, V oldValue, V newValue) {
 826         Objects.requireNonNull(oldValue);
 827         Objects.requireNonNull(newValue);
 828         Entry<?, ?> tab[] = table;
 829         int hash = key.hashCode();
 830         int index = (hash & 0x7FFFFFFF) % tab.length;
 831         @SuppressWarnings("unchecked")
 832         Entry<K, V> e = (Entry<K, V>) tab[index];
 833         for (; e != null; e = e.next) {
 834             if ((e.hash == hash) && e.key.equals(key)) {
 835                 if (e.value.equals(oldValue)) {
 836                     e.value = newValue;
 837                     return true;
 838                 } else {
 839                     return false;
 840                 }
 841             }
 842         }
 843         return false;
 844     }
 845 
 846     /**
 847      * 替换
 848      *
 849      * @param key
 850      * @param value
 851      * @return
 852      */
 853     @Override
 854     public synchronized V replace(K key, V value) {
 855         Objects.requireNonNull(value);
 856         Entry<?, ?> tab[] = table;
 857         int hash = key.hashCode();
 858         int index = (hash & 0x7FFFFFFF) % tab.length;
 859         @SuppressWarnings("unchecked")
 860         Entry<K, V> e = (Entry<K, V>) tab[index];
 861         for (; e != null; e = e.next) {
 862             if ((e.hash == hash) && e.key.equals(key)) {
 863                 V oldValue = e.value;
 864                 e.value = value;
 865                 return oldValue;
 866             }
 867         }
 868         return null;
 869     }
 870 
 871     @Override
 872     public synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
 873         Objects.requireNonNull(mappingFunction);
 874 
 875         Entry<?, ?> tab[] = table;
 876         int hash = key.hashCode();
 877         int index = (hash & 0x7FFFFFFF) % tab.length;
 878         @SuppressWarnings("unchecked")
 879         Entry<K, V> e = (Entry<K, V>) tab[index];
 880         for (; e != null; e = e.next) {
 881             if (e.hash == hash && e.key.equals(key)) {
 882                 // Hashtable not accept null value
 883                 return e.value;
 884             }
 885         }
 886 
 887         V newValue = mappingFunction.apply(key);
 888         if (newValue != null) {
 889             addEntry(hash, key, newValue, index);
 890         }
 891 
 892         return newValue;
 893     }
 894 
 895     @Override
 896     public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 897         Objects.requireNonNull(remappingFunction);
 898 
 899         Entry<?, ?> tab[] = table;
 900         int hash = key.hashCode();
 901         int index = (hash & 0x7FFFFFFF) % tab.length;
 902         @SuppressWarnings("unchecked")
 903         Entry<K, V> e = (Entry<K, V>) tab[index];
 904         for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
 905             if (e.hash == hash && e.key.equals(key)) {
 906                 V newValue = remappingFunction.apply(key, e.value);
 907                 if (newValue == null) {
 908                     modCount++;
 909                     if (prev != null) {
 910                         prev.next = e.next;
 911                     } else {
 912                         tab[index] = e.next;
 913                     }
 914                     count--;
 915                 } else {
 916                     e.value = newValue;
 917                 }
 918                 return newValue;
 919             }
 920         }
 921         return null;
 922     }
 923 
 924     @Override
 925     public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 926         Objects.requireNonNull(remappingFunction);
 927 
 928         Entry<?, ?> tab[] = table;
 929         int hash = key.hashCode();
 930         int index = (hash & 0x7FFFFFFF) % tab.length;
 931         @SuppressWarnings("unchecked")
 932         Entry<K, V> e = (Entry<K, V>) tab[index];
 933         for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
 934             if (e.hash == hash && Objects.equals(e.key, key)) {
 935                 V newValue = remappingFunction.apply(key, e.value);
 936                 if (newValue == null) {
 937                     modCount++;
 938                     if (prev != null) {
 939                         prev.next = e.next;
 940                     } else {
 941                         tab[index] = e.next;
 942                     }
 943                     count--;
 944                 } else {
 945                     e.value = newValue;
 946                 }
 947                 return newValue;
 948             }
 949         }
 950 
 951         V newValue = remappingFunction.apply(key, null);
 952         if (newValue != null) {
 953             addEntry(hash, key, newValue, index);
 954         }
 955 
 956         return newValue;
 957     }
 958 
 959     @Override
 960     public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
 961         Objects.requireNonNull(remappingFunction);
 962 
 963         Entry<?, ?> tab[] = table;
 964         int hash = key.hashCode();
 965         int index = (hash & 0x7FFFFFFF) % tab.length;
 966         @SuppressWarnings("unchecked")
 967         Entry<K, V> e = (Entry<K, V>) tab[index];
 968         for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
 969             if (e.hash == hash && e.key.equals(key)) {
 970                 V newValue = remappingFunction.apply(e.value, value);
 971                 if (newValue == null) {
 972                     modCount++;
 973                     if (prev != null) {
 974                         prev.next = e.next;
 975                     } else {
 976                         tab[index] = e.next;
 977                     }
 978                     count--;
 979                 } else {
 980                     e.value = newValue;
 981                 }
 982                 return newValue;
 983             }
 984         }
 985 
 986         if (value != null) {
 987             addEntry(hash, key, value, index);
 988         }
 989 
 990         return value;
 991     }
 992 
 993     /**
 994      * 将Hashtable的总的容量，实际容量，所有的Entry都写入到输出流中
 995      */
 996     private void writeObject(java.io.ObjectOutputStream s)
 997             throws IOException {
 998         Entry<Object, Object> entryStack = null;
 999 
1000         synchronized (this) {
1001             // Write out the threshold and loadFactor
1002             s.defaultWriteObject();
1003 
1004             // Write out the length and count of elements
1005             s.writeInt(table.length);
1006             s.writeInt(count);
1007 
1008             // Stack copies of the entries in the table
1009             for (int index = 0; index < table.length; index++) {
1010                 Entry<?, ?> entry = table[index];
1011 
1012                 while (entry != null) {
1013                     entryStack =
1014                             new Entry<>(0, entry.key, entry.value, entryStack);
1015                     entry = entry.next;
1016                 }
1017             }
1018         }
1019 
1020         // Write out the key/value objects from the stacked entries
1021         while (entryStack != null) {
1022             s.writeObject(entryStack.key);
1023             s.writeObject(entryStack.value);
1024             entryStack = entryStack.next;
1025         }
1026     }
1027 
1028     /**
1029      * 将Hashtable的总的容量，实际容量，所有的Entry依次读出
1030      */
1031     private void readObject(java.io.ObjectInputStream s)
1032             throws IOException, ClassNotFoundException {
1033         // Read in the threshold and loadFactor
1034         s.defaultReadObject();
1035 
1036         // Validate loadFactor (ignore threshold - it will be re-computed)
1037         if (loadFactor <= 0 || Float.isNaN(loadFactor))
1038             throw new StreamCorruptedException("Illegal Load: " + loadFactor);
1039 
1040         // Read the original length of the array and number of elements
1041         int origlength = s.readInt();
1042         int elements = s.readInt();
1043 
1044         // Validate # of elements
1045         if (elements < 0)
1046             throw new StreamCorruptedException("Illegal # of Elements: " + elements);
1047 
1048         // Clamp original length to be more than elements / loadFactor
1049         // (this is the invariant enforced with auto-growth)
1050         origlength = Math.max(origlength, (int) (elements / loadFactor) + 1);
1051 
1052         // Compute new length with a bit of room 5% + 3 to grow but
1053         // no larger than the clamped original length.  Make the length
1054         // odd if it's large enough, this helps distribute the entries.
1055         // Guard against the length ending up zero, that's not valid.
1056         int length = (int) ((elements + elements / 20) / loadFactor) + 3;
1057         if (length > elements && (length & 1) == 0)
1058             length--;
1059         length = Math.min(length, origlength);
1060 
1061         // Check Map.Entry[].class since it's the nearest public type to
1062         // what we're actually creating.
1063         SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, length);
1064         table = new Entry<?, ?>[length];
1065         threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
1066         count = 0;
1067 
1068         // Read the number of elements and then all the key/value objects
1069         for (; elements > 0; elements--) {
1070             @SuppressWarnings("unchecked")
1071             K key = (K) s.readObject();
1072             @SuppressWarnings("unchecked")
1073             V value = (V) s.readObject();
1074             // sync is eliminated for performance
1075             reconstitutionPut(table, key, value);
1076         }
1077     }
1078 
1079     /**
1080      * readObject使用的put方法（重建put），因为put方法支持重写，并且子类尚未初始化的时候不能调用put方法，所以就提供了reconstitutionPut
1081      * 它和常规put方法有几点不同，不检测rehash,因为初始元素数目已知。modCount不会自增，因为我们是在创建一个新的实例。
1082      */
1083     private void reconstitutionPut(Entry<?, ?>[] tab, K key, V value)
1084             throws StreamCorruptedException {
1085         if (value == null) {
1086             throw new java.io.StreamCorruptedException();
1087         }
1088         // 确保Key不在Hashtable中
1089         // 反序列化过程中不应该 会发生的情况
1090         int hash = key.hashCode();
1091         int index = (hash & 0x7FFFFFFF) % tab.length;
1092         for (Entry<?, ?> e = tab[index]; e != null; e = e.next) {
1093             //反序列化过程中如果出现Key值重复，抛出异常StreamCorruptedException
1094             if ((e.hash == hash) && e.key.equals(key)) {
1095                 throw new java.io.StreamCorruptedException();
1096             }
1097         }
1098         // 创建新的Entry.
1099         @SuppressWarnings("unchecked")
1100         Entry<K, V> e = (Entry<K, V>) tab[index];
1101         tab[index] = new Entry<>(hash, key, value, e);
1102         count++;
1103     }
1104 
1105     /**
1106      * Hashtable的Entry节点，它本质上是一个单向链表。
1107      * 因此，我们能推断出Hashtable是由拉链法实现的散列表
1108      */
1109     private static class Entry<K, V> implements Map.Entry<K, V> {
1110         final int hash;
1111         final K key;
1112         V value;
1113         Entry<K, V> next;
1114 
1115         protected Entry(int hash, K key, V value, Entry<K, V> next) {
1116             this.hash = hash;
1117             this.key = key;
1118             this.value = value;
1119             this.next = next;
1120         }
1121 
1122         @SuppressWarnings("unchecked")
1123         protected Object clone() {
1124             return new Entry<>(hash, key, value,
1125                     (next == null ? null : (Entry<K, V>) next.clone()));
1126         }
1127 
1128         // Map.Entry Ops
1129 
1130         public K getKey() {
1131             return key;
1132         }
1133 
1134         public V getValue() {
1135             return value;
1136         }
1137 
1138         // 进行判断value是否为空，即不允许value为空，其实key也不能为空
1139         public V setValue(V value) {
1140             if (value == null)
1141                 throw new NullPointerException();
1142 
1143             V oldValue = this.value;
1144             this.value = value;
1145             return oldValue;
1146         }
1147 
1148         // 覆盖equals()方法，判断两个Entry是否相等。
1149         // 若两个Entry的key和value都相等，则认为它们相等。
1150         public boolean equals(Object o) {
1151             if (!(o instanceof Map.Entry))
1152                 return false;
1153             Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
1154 
1155             return (key == null ? e.getKey() == null : key.equals(e.getKey())) &&
1156                     (value == null ? e.getValue() == null : value.equals(e.getValue()));
1157         }
1158 
1159         public int hashCode() {
1160             // 直接用hash进行异或，与HashMap不同
1161             return hash ^ Objects.hashCode(value);
1162         }
1163 
1164         public String toString() {
1165             return key.toString() + "=" + value.toString();
1166         }
1167     }
1168 
1169     // Types of Enumerations/Iterations
1170     private static final int KEYS = 0;
1171     private static final int VALUES = 1;
1172     private static final int ENTRIES = 2;
1173 
1174     /**
1175      * Enumerator的作用是提供了通过elements()遍历Hashtable的接口和通过entrySet()遍历Hashtable的接口。
1176      * 因为，它同时实现了 Enumerator接口和Iterator接口。
1177      */
1178     private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1179         // 指向Hashtable的table
1180         Entry<?, ?>[] table = Hashtable.this.table;
1181         // Hashtable的总的大小
1182         int index = table.length;
1183         Entry<?, ?> entry;
1184         Entry<?, ?> lastReturned;
1185         int type;
1186 
1187         /**
1188          * Enumerator是 迭代器(Iterator) 还是 枚举类(Enumeration)的标志
1189          * iterator为true，表示它是迭代器；否则，是枚举类。
1190          */
1191         boolean iterator;
1192 
1193         /**
1194          * 在将Enumerator当作迭代器使用时会用到，用来实现fail-fast机制。
1195          */
1196         protected int expectedModCount = modCount;
1197 
1198         Enumerator(int type, boolean iterator) {
1199             this.type = type;
1200             this.iterator = iterator;
1201         }
1202 
1203         /**
1204          * 从遍历table的数组的末尾向前查找，直到找到不为null的Entry。
1205          */
1206         public boolean hasMoreElements() {
1207             Entry<?, ?> e = entry;
1208             int i = index;
1209             Entry<?, ?>[] t = table;
1210             /* Use locals for faster loop iteration */
1211             while (e == null && i > 0) {
1212                 e = t[--i];
1213             }
1214             entry = e;
1215             index = i;
1216             return e != null;
1217         }
1218 
1219         /**
1220          * 获取下一个元素
1221          * 注意：从hasMoreElements() 和nextElement() 可以看出Hashtable的elements()遍历方式
1222          * 首先，从后向前的遍历table数组。table数组的每个节点都是一个单向链表(Entry)。
1223          * 然后，依次向后遍历单向链表Entry。
1224          */
1225         @SuppressWarnings("unchecked")
1226         public T nextElement() {
1227             Entry<?, ?> et = entry;
1228             int i = index;
1229             Entry<?, ?>[] t = table;
1230             /* Use locals for faster loop iteration */
1231             while (et == null && i > 0) {
1232                 et = t[--i];
1233             }
1234             entry = et;
1235             index = i;
1236             if (et != null) {
1237                 Entry<?, ?> e = lastReturned = entry;
1238                 entry = e.next;
1239                 return type == KEYS ? (T) e.key : (type == VALUES ? (T) e.value : (T) e);
1240             }
1241             throw new NoSuchElementException("Hashtable Enumerator");
1242         }
1243 
1244         // 迭代器Iterator的判断是否存在下一个元素
1245         // 实际上，它是调用的hasMoreElements()
1246         public boolean hasNext() {
1247             return hasMoreElements();
1248         }
1249 
1250         // 迭代器获取下一个元素
1251         // 实际上，它是调用的nextElement()
1252         public T next() {
1253             if (modCount != expectedModCount)
1254                 throw new ConcurrentModificationException();
1255             return nextElement();
1256         }
1257 
1258         // 迭代器的remove()接口。
1259         // 首先，它在table数组中找出要删除元素所在的Entry，
1260         // 然后，删除单向链表Entry中的元素。
1261         public void remove() {
1262             if (!iterator)
1263                 throw new UnsupportedOperationException();
1264             if (lastReturned == null)
1265                 throw new IllegalStateException("Hashtable Enumerator");
1266             if (modCount != expectedModCount)
1267                 throw new ConcurrentModificationException();
1268 
1269             synchronized (Hashtable.this) {
1270                 Entry<?, ?>[] tab = Hashtable.this.table;
1271                 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1272 
1273                 //获取该槽位第一个元素
1274                 @SuppressWarnings("unchecked")
1275                 Entry<K, V> e = (Entry<K, V>) tab[index];
1276                 //从单链表的一端向后遍历
1277                 for (Entry<K, V> prev = null; e != null; prev = e, e = e.next) {
1278                     //当前元素即为上一个返回元素
1279                     if (e == lastReturned) {
1280                         modCount++;
1281                         expectedModCount++;
1282                         //删除上一个元素
1283                         if (prev == null)
1284                             tab[index] = e.next;
1285                         else
1286                             prev.next = e.next;
1287                         count--;
1288                         lastReturned = null;
1289                         return;
1290                     }
1291                 }
1292                 throw new ConcurrentModificationException();
1293             }
1294         }
1295     }
1296 }