Hashtable源码分析。

﹏ヽ暗。殇╰゛Y 2022-02-28 19:22 291阅读 0赞

/**
     * 此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 null 对象都可以用作键或值。
     * 
     * 为了成功地在哈希表中存储和获取对象，用作键的对象必须实现 hashCode 方法和 equals 方法。
     * 
     * Hashtable 的实例有两个参数影响其性能：初始容量 和加载因子。容量 是哈希表中桶 的数量，初始容量 就是哈希表创建时的容量。注意，哈希表的状态为
     * open：在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。加载因子
     * 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash
     * 方法的具体细节则依赖于该实现。
     * 
     * 通常，默认加载因子(.75)在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 Hashtable
     * 操作中，包括 get 和 put 操作，都反映了这一点）。
     * 
     * 初始容量主要控制空间消耗与执行 rehash 操作所需要的时间损耗之间的平衡。如果初始容量大于 Hashtable 所包含的最大条目数除以加载因子，则永远
     * 不会发生 rehash 操作。但是，将初始容量设置太高可能会浪费空间。
     * 
     * 如果很多条目要存储在一个 Hashtable 中，那么与根据需要执行自动 rehashing
     * 操作来增大表的容量的做法相比，使用足够大的初始容量创建哈希表或许可以更有效地插入条目。
     * 
     *
     */
    public class Hashtable<K, V> extends Dictionary<K,V>
    	implements Map<K,V>, Cloneable, java.io.Serializable{
    	/*
    	 * 继承Dictionary类，实现了Map接口。
    	 * Map是“key-value键值对”接口，
    	 * Dictionary是声明了操作“键值对”函数接口的抽象类。
    	 */
    	
    	/**
    	 * 存储键值对对象的桶数组
    	 */
    	private transient Entry<?,?>[] table;
    	/**
    	 * 哈希表中条目的总数。
    	 */
    	private transient int count;
    	/**
    	 * 当表的大小超过此阈值时，将重新哈希表。
    	 * threshold的值=容量*加载因子。
    	 */
        private int threshold;
        /**
         * 哈希表的加载因子。
         */
        private float loadFactor;
        /**
         * hashtable被改变的次数，用来实现fail-fast机制
         */
        private transient int modCount = 0;
        /**
         * 使用JDK 1.0.2中的serialVersionUID实现互操作性
         */
        private static final long serialVersionUID = 1421746759512286392L;
        
        /**
         * 用指定初始容量和指定加载因子构造一个新的空哈希表。
         * @param initialCapacity	哈希表的初始容量。
         * @param loadFactor	哈希表的加载因子。
         */
        public Hashtable(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0) // 初始容量小于零
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 加载因子为非正数
                throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    
            if (initialCapacity==0)
                initialCapacity = 1; // 初始容量最小值为1
            this.loadFactor = loadFactor;
            table = new Entry<?,?>[initialCapacity]; // 创建桶数组
            threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        }
        
        /**
         * 用指定初始容量和默认的加载因子 (0.75) 构造一个新的空哈希表。 
         * @param initialCapacity	 哈希表的初始容量
         */
        public Hashtable(int initialCapacity) {
            this(initialCapacity, 0.75f);
        }
        
        /**
         * 用默认的初始容量 (11) 和加载因子 (0.75) 构造一个新的空哈希表。
         */
        public Hashtable() {
            this(11, 0.75f);
        }
        
        /**
         * 构造一个与给定的 Map 具有相同映射关系的新哈希表。
         * 该哈希表是用足以容纳给定 Map 中映射关系的初始容量和默认的加载因子（0.75）创建的。
         * @param t	其映射关系将存放在此映射中的映射。
         */
        public Hashtable(Map<? extends K, ? extends V> t) {
            this(Math.max(2*t.size(), 11), 0.75f);
            putAll(t);	// 将t的所有映射关系复制到此哈希表中
        }
        
        /**
         * 返回此哈希表中的键的数量。
         * 覆写Dictionary<K,V> 中的 size
         */
        public synchronized int size() {
            return count;
        }
        
        /**
         * 测试此哈希表是否没有键映射到值。
         * 覆写Dictionary<K,V> 中的 isEmpty
         */
        public synchronized boolean isEmpty() {
            return count == 0;
        }
        
        /**
         * 返回此哈希表中的键的枚举。
         * 覆写Dictionary<K,V> 中的 keys
         */
        public synchronized Enumeration<K> keys() {
            return this.<K>getEnumeration(KEYS);
        }
        
        /**
         * 返回此哈希表中的值的枚举。对返回的对象使用 Enumeration 方法，以便按顺序获取这些元素。
         * 覆写Dictionary<K,V> 中的 elements
         */
        public synchronized Enumeration<V> elements() {
            return this.<V>getEnumeration(VALUES);
        }
        
        /**
         * 测试此映射表中是否存在与指定值关联的键。
         * 此操作比 containsKey 方法的开销更大。
         * 注意，此方法在功能上等同于 containsValue 方法，
         * containValue 是 collection 框架中 Map 接口的一部分。 
         * @param value	要搜索的值
         * @return	当且仅当此哈希表中某个键映射到 value 参数（由 equals 方法确定）时，返回 true；否则返回 false。 
         */
        public synchronized boolean contains(Object value) {
            if (value == null) { // 如果该值为 null
                throw new NullPointerException();
            }
    
            Entry<?,?> tab[] = table;
            for (int i = tab.length ; i-- > 0 ;) {
                for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
                    if (e.value.equals(value)) {
                        return true;
                    }
                }
            }
            return false;
        }
        
        /**
         * 如果此 Hashtable 将一个或多个键映射到此值，则返回 true。
         * 注意，此方法在功能上等同于contains（它先于 Map 接口）。
         * 覆写 Map<K,V> 中的 containsValue
         */
        public boolean containsValue(Object value) {
            return contains(value);
        }
        
        /**
         * 测试指定对象是否为此哈希表中的键。
         * 覆写 Map<K,V> 中的 containsKey
         */
        public synchronized boolean containsKey(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;// 再根据hash值找到索引
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    return true;
                }
            }
            return false;
        }
        
        /**
         * 返回指定键所映射到的值，如果此映射不包含此键的映射，则返回 null. 
         * 更确切地讲，如果此映射包含满足 (key.equals(k)) 的从键 k 到值 v 的映射，
         * 则此方法返回 v；否则，返回 null。（最多只能有一个这样的映射。） 
         * 覆写 Dictionary<K,V> 中的 get
         */
        @SuppressWarnings("unchecked")
        public synchronized V get(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();	
            int index = (hash & 0x7FFFFFFF) % tab.length;	// 再根据hash值找到索引
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {	// 遍历entry链
                if ((e.hash == hash) && e.key.equals(key)) {	// 若找到该键
                    return (V)e.value;	// 返回对应的值
                }
            }
            return null;	// 否则返回null
        }
        
        /**
         * 要分配的数组的最大大小。
         * 一些vm在数组中保留一些头信息。
         * 试图分配更大的数组可能会导致OutOfMemoryError:请求的数组大小超过VM限制
         */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        
        /**
         * 增加此哈希表的容量并在内部对其进行重组，以便更有效地容纳和访问其元素。
         * 当哈希表中的键的数量超出哈希表的容量和加载因子时，自动调用此方法。
         */
        @SuppressWarnings("unchecked")
        protected void rehash() {
            int oldCapacity = table.length;	// 记录旧容量
            Entry<?,?>[] oldMap = table;	// 记录旧的桶数组
    
            // overflow-conscious code
            int newCapacity = (oldCapacity << 1) + 1;	// 新容量为老容量的2倍加1
            if (newCapacity - MAX_ARRAY_SIZE > 0) {	
                if (oldCapacity == MAX_ARRAY_SIZE)	// 容量不得超过约定的最大值
                    // 继续使用MAX_ARRAY_SIZE桶运行
                    return;
                newCapacity = MAX_ARRAY_SIZE;
            }
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];	// 创建新的数组
    
            modCount++;
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            table = newMap;
    
            for (int i = oldCapacity ; i-- > 0 ;) {	// 转移键值对到新数组
                for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                    Entry<K,V> e = old;
                    old = old.next;
    
                    int index = (e.hash & 0x7FFFFFFF) % newCapacity; // 根据hash值找到索引
                    e.next = (Entry<K,V>)newMap[index];
                    newMap[index] = e;
                }
            }
        }
        
        /**
         * 加节点
         * @param hash	hash值
         * @param key	hash表的键
         * @param value	值
         * @param index	hash表中的存储位置
         */
        private void addEntry(int hash, K key, V value, int index) {
            modCount++;
    
            Entry<?,?> tab[] = table;
            if (count >= threshold) {
                // 如果超过阈值，则重新哈希表
                rehash();	// 重新构建桶数组，并对数组中所有键值对重哈希，耗时！
    
                tab = table;
                hash = key.hashCode();
                index = (hash & 0x7FFFFFFF) % tab.length;	// 这里是取模运算
            }
    
            // 创建新条目。
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            // 将新结点插到链表首部
            tab[index] = new Entry<>(hash, key, value, e); // 生成一个新结点
            count++;
        }
        
        /**
         * 将指定 key 映射到此哈希表中的指定 value。键和值都不可以为 null。 
         * 通过使用与原来的键相同的键调用 get 方法，可以获取相应的值。
         * 覆写 Dictionary<K,V> 中的 put
         */
        public synchronized V put(K key, V value) {
            // 确保值不为空
            if (value == null) {
                throw new NullPointerException();
            }
    
            // 确保键不在散列表中。
            Entry<?,?> tab[] = table;	
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;	// 通过hash值找到其存储位置
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for(; entry != null ; entry = entry.next) {	// 遍历链表
                if ((entry.hash == hash) && entry.key.equals(key)) {	// 若键相同，则新值覆盖旧值
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
    
            addEntry(hash, key, value, index);
            return null;
        }
    
        /**
         * 从哈希表中移除该键及其相应的值。如果该键不在哈希表中，则此方法不执行任何操作。
         * 覆写 Dictionary<K,V> 中的 remove
         */
        public synchronized V remove(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;	// 计算索引
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {	// 遍历entry链
                if ((e.hash == hash) && e.key.equals(key)) {	// 找到指定键
                    modCount++;
                    if (prev != null) {	// 修改相关指针
                        prev.next = e.next;
                    } else {
                        tab[index] = e.next;
                    }
                    count--;
                    V oldValue = e.value;
                    e.value = null;
                    return oldValue;
                }
            }
            return null;
        }
        
        /**
         * 将指定映射的所有映射关系复制到此哈希表中，这些映射关系将替换此哈希表拥有的、针对当前指定映射中所有键的所有映射关系。
         * 覆写 Map<K,V> 中的 putAll
         */
        public synchronized void putAll(Map<? extends K, ? extends V> t) {
            for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
                put(e.getKey(), e.getValue()); // 将e.getKey() 映射到此哈希表中的e.getValue()。
        }
        
        /**
         * 将此哈希表清空，使其不包含任何键。
         * 覆写 Map<K,V> 中的 clear
         */
        public synchronized void clear() {
            Entry<?,?> tab[] = table;
            modCount++;
            for (int index = tab.length; --index >= 0; )
                tab[index] = null;	// 直接置空
            count = 0;
        }
        
        /**
         * 创建此哈希表的浅表副本。复制哈希表自身的所有结构，但不复制它的键和值。这是一个开销相对较大的操作。 
         * 覆写 类 Object 中的 clone
         */
        public synchronized Object clone() {
            try {
                Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
                t.table = new Entry<?,?>[table.length];
                for (int i = table.length ; i-- > 0 ; ) {
                    t.table[i] = (table[i] != null)
                        ? (Entry<?,?>) table[i].clone() : null;
                }
                t.keySet = null;
                t.entrySet = null;
                t.values = null;
                t.modCount = 0;
                return t;
            } catch (CloneNotSupportedException e) {
                // 这不应该发生，因为我们是Cloneable
                throw new InternalError(e);
            }
        }
        
        /**
         * 返回此 Hashtable 对象的字符串表示形式，其形式为 ASCII 字符 ", " （逗号加空格）分隔开的、括在括号中的一组条目。
         * 每个条目都按以下方式呈现：键，一个等号 = 和相关元素，其中 toString 方法用于将键和元素转换为字符串。 
         */
        public synchronized String toString() {
            int max = size() - 1;
            if (max == -1)
                return "{}";
    
            StringBuilder sb = new StringBuilder();
            Iterator<Map.Entry<K,V>> it = entrySet().iterator();
    
            sb.append('{');
            for (int i = 0; ; i++) { // 遍历拼接字符串
                Map.Entry<K,V> e = it.next();
                K key = e.getKey();
                V value = e.getValue();
                sb.append(key   == this ? "(this Map)" : key.toString());
                sb.append('=');
                sb.append(value == this ? "(this Map)" : value.toString());
    
                if (i == max)
                    return sb.append('}').toString();
                sb.append(", ");
            }
        }
        
        /**
         * 返回此哈希表中的相关类型的枚举。
         * @param type	KEYS or VALUES
         * @return	
         */
        private <T> Enumeration<T> getEnumeration(int type) {
            if (count == 0) { // 如果为0，返回没有元素的枚举。
                return Collections.emptyEnumeration();
            } else {
                return new Enumerator<>(type, false);
            }
        }
        
        /**
         * 返回此哈希表中的相关类型的迭代器。
         * @param type	KEYS or VALUES
         * @return
         */
        private <T> Iterator<T> getIterator(int type) {
            if (count == 0) { // 如果为0，返回一个没有元素的迭代器。
                return Collections.emptyIterator();
            } else {
                return new Enumerator<>(type, true);
            }
        }
        
        // 视图
        
        /**
         * 在第一次请求该视图时，这些字段都初始化为包含适当视图的实例。
         * 视图是无状态的，因此没有理由创建多个视图。
         */
        private transient volatile Set<K> keySet;
        private transient volatile Set<Map.Entry<K,V>> entrySet;
        private transient volatile Collection<V> values;
        
        /**
         * 返回此映射中包含的键的 Set 视图。此 set 受映射支持，因此对映射的更改可在 set 中反映出来，反之亦然。
         * 如果在此 set 上的迭代器处于进行中时修改此映射（除非通过迭代器自身的 remove 操作），
         * 则迭代器的结果是不确定的。通过 Iterator.remove、Set.remove、removeAll、 
         * retainAll、和 clear 操作，此 set 支持元素移除，可从映射中移除相应的映射关系。
         * 它不支持 add 或 addAll 操作。 
         * 覆写 Map<K,V> 中的 keySet
         */
        public Set<K> keySet() {
            if (keySet == null)	// 通过Collections包装，返回的是线程安全的键集
                keySet = Collections.synchronizedSet(new KeySet(), this);
            return keySet;
        }
        
        private class KeySet extends AbstractSet<K> {
            public Iterator<K> iterator() {
                return getIterator(KEYS);
            }
            public int size() {
                return count;
            }
            public boolean contains(Object o) {
                return containsKey(o);
            }
            public boolean remove(Object o) {
                return Hashtable.this.remove(o) != null;
            }
            public void clear() {
                Hashtable.this.clear();
            }
        }
        
        /**
         * 返回此映射中包含的键的 Set 视图。此 set 受映射支持，因此对映射的更改可在 set 中反映出来，反之亦然。
         * 如果在此 set 上的迭代器处于进行中时修改此映射（除非通过迭代器自身的 remove 操作，
         * 或通过由迭代器返回的映射条目上的 setValue 操作），则迭代器的结果是不确定的。
         * 通过 Iterator.remove、Set.remove、removeAll、 retainAll、 和 clear 操作，
         * 此set 支持元素移除，可从映射中移除相应的映射关系。它不支持 add 或 addAll 操作。
         * 覆写  Map<K,V> 中的 entrySet
         */
        public Set<Map.Entry<K,V>> entrySet() {
            if (entrySet==null)	// 通过Collections的包装，返回的是线程安全的键值集
                entrySet = Collections.synchronizedSet(new EntrySet(), this);
            return entrySet;
        }
        
        private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
            public Iterator<Map.Entry<K,V>> iterator() {
                return getIterator(ENTRIES);
            }
    
            public boolean add(Map.Entry<K,V> o) {
                return super.add(o);
            }
    
            public boolean contains(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
                Object key = entry.getKey();
                Entry<?,?>[] tab = table;
                int hash = key.hashCode();
                int index = (hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
    
                for (Entry<?,?> e = tab[index]; e != null; e = e.next) // 遍历查找是否存在
                    if (e.hash==hash && e.equals(entry))
                        return true;
                return false;
            }
    
            public boolean remove(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
                Object key = entry.getKey();
                Entry<?,?>[] tab = table;
                int hash = key.hashCode();
                int index = (hash & 0x7FFFFFFF) % tab.length; // 通过hash值找到其存储位置
    
                @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>)tab[index];
                for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {// 遍历entry链
                    if (e.hash==hash && e.equals(entry)) { // 找到指定链
                        modCount++;
                        if (prev != null) // 修改相关指针
                            prev.next = e.next;
                        else
                            tab[index] = e.next;
    
                        count--;
                        e.value = null;
                        return true;
                    }
                }
                return false;
            }
    
            public int size() {
                return count;
            }
    
            public void clear() {
                Hashtable.this.clear();
            }
        }
        
        /**
         * 返回此映射中包含的键的 Collection 视图。此 collection 受映射支持，
         * 因此对映射的更改可在 collection 中反映出来，反之亦然。
         * 如果在此 collection 上的迭代器处于进行中时修改此映射（除非通过迭代器自身的 remove 操作），
         * 则迭代器的结果是不确定的。通过 Iterator.remove、Collection.remove、removeAll、 
         * retainAll、 和 clear 操作，此set 支持元素移除，可从映射中移除相应的映射关系。
         * 它不支持 add 或 addAll 操作。
         * 覆写 Map<K,V> 中的 values
         */
        public Collection<V> values() {
            if (values==null)// 通过Collections的包装，返回的是线程安全的值集
                values = Collections.synchronizedCollection(new ValueCollection(), this);
            return values;
        }
    
        private class ValueCollection extends AbstractCollection<V> {
            public Iterator<V> iterator() {
                return getIterator(VALUES);
            }
            public int size() {
                return count;
            }
            public boolean contains(Object o) {
                return containsValue(o);
            }
            public void clear() {
                Hashtable.this.clear();
            }
        }
        
        // 比较和散列
        
        /**
         * 按照 Map 接口的定义，比较指定 Object 与此 Map 是否相等。
         * 覆写 Map<K,V> 中的 equals
         */
        public synchronized boolean equals(Object o) {
            if (o == this)
                return true;
    
            if (!(o instanceof Map))
                return false;
            Map<?,?> t = (Map<?,?>) o;
            if (t.size() != size())
                return false;
    
            try {
                Iterator<Map.Entry<K,V>> i = entrySet().iterator();
                while (i.hasNext()) { // 遍历链
                    Map.Entry<K,V> e = i.next();
                    K key = e.getKey();
                    V value = e.getValue();
                    if (value == null) { 
                        if (!(t.get(key)==null && t.containsKey(key)))
                            return false;
                    } else { // 判断value值
                        if (!value.equals(t.get(key)))
                            return false;
                    }
                }
            } catch (ClassCastException unused)   {
                return false;
            } catch (NullPointerException unused) {
                return false;
            }
    
            return true;
        }
        
        /**
         * 按照 Map 接口的定义，返回此 Map 的哈希码值。 
         * 覆写 Map<K,V> 中的 hashCode
         */
        public synchronized int hashCode() {
            /*
             * 此代码检测由计算自引用哈希表的哈希代码引起的递归，并防止否则会导致堆栈溢出。
             * 这允许带有自引用哈希表的某些1.1时代的applet工作。
             * 这段代码滥用loadFactor字段作为一个hashCode in progress标志执行双重任务，以避免降低空间性能。
             * 负负载因子表示哈希码计算正在进行中。
             */
            int h = 0;
            if (count == 0 || loadFactor < 0)
                return h;  // 返回0
    
            loadFactor = -loadFactor;  // 标记正在进行的hashCode计算
            Entry<?,?>[] tab = table;
            for (Entry<?,?> entry : tab) {
                while (entry != null) {
                    h += entry.hashCode();
                    entry = entry.next;
                }
            }
    
            loadFactor = -loadFactor;  // 标记hashCode计算完成
    
            return h;
        }
        
        /**
         * 返回指定键映射到的值，如果此映射不包含键的映射，则返回defaultValue。
         * 覆写  Map<K,V> getOrDefault
         */
        @Override
        public synchronized V getOrDefault(Object key, V defaultValue) {
            V result = get(key);
            return (null == result) ? defaultValue : result;
        }
        
        /**
         * 对此映射中的每个条目执行给定的操作，直到所有条目都被处理或操作引发异常。
         * 覆写  Map<K,V> forEach
         */
        @SuppressWarnings("unchecked")
        @Override
        public synchronized void forEach(BiConsumer<? super K, ? super V> action) {
            Objects.requireNonNull(action);     // 如果case表为空，则需要显式检查。
            final int expectedModCount = modCount;
    
            Entry<?, ?>[] tab = table;
            for (Entry<?, ?> entry : tab) { // 遍历entry链
                while (entry != null) {
                    action.accept((K)entry.key, (V)entry.value); // 对给定的参数执行此操作。
                    entry = entry.next;
    
                    if (expectedModCount != modCount) {
                        throw new ConcurrentModificationException();
                    }
                }
            }
        }
        
        /**
         * 将每个条目的值替换为对该条目调用给定函数的结果，直到所有条目都被处理或函数抛出异常。
         * 函数抛出的异常将传递给调用者。
         * 覆写  Map<K,V> replaceAll
         */
        @SuppressWarnings("unchecked")
        @Override
        public synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
            Objects.requireNonNull(function);     //如果case表为空，则需要显式检查。
            final int expectedModCount = modCount;
    
            Entry<K, V>[] tab = (Entry<K, V>[])table;
            for (Entry<K, V> entry : tab) { // 遍历链
                while (entry != null) {
                    entry.value = Objects.requireNonNull(
                        function.apply(entry.key, entry.value)); // 检查指定的对象（将此函数应用于给定的参数。）引用是否为null。
                    entry = entry.next;
    
                    if (expectedModCount != modCount) {
                        throw new ConcurrentModificationException();
                    }
                }
            }
        }
        
        /**
         * 如果指定的键尚未与值关联(或映射到null)，则将其与给定值关联并返回null，否则将返回当前值。
         * 覆写  Map<K,V> putIfAbsent
         */
        @Override
        public synchronized V putIfAbsent(K key, V value) {
            Objects.requireNonNull(value);
    
            // 确保键不在散列表中。
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length; // 通过hash值找到其存储位置
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for (; entry != null; entry = entry.next) {
                if ((entry.hash == hash) && entry.key.equals(key)) { // 若键相同，则新值覆盖旧值
                    V old = entry.value;
                    if (old == null) {
                        entry.value = value;
                    }
                    return old;
                }
            }
    
            addEntry(hash, key, value, index); // 加节点
            return null;
        }
        
        /**
         * 仅当当前映射到指定值时，才删除指定键的项。
         * 覆写  Map<K,V> remove
         */
        @Override
        public synchronized boolean remove(Object key, Object value) {
            Objects.requireNonNull(value);
    
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
                    modCount++;
                    if (prev != null) {// 修改相关指针
                        prev.next = e.next;
                    } else {
                        tab[index] = e.next;
                    }
                    count--;
                    e.value = null;
                    return true;
                }
            }
            return false;
        }
        
        /**
         * 仅当当前映射到指定值时，才替换指定键的项。
         * 覆写  Map<K,V> replace
         */
        @Override
        public synchronized boolean replace(K key, V oldValue, V newValue) {
            Objects.requireNonNull(oldValue);
            Objects.requireNonNull(newValue);
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for (; e != null; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    if (e.value.equals(oldValue)) {
                        e.value = newValue;
                        return true;
                    } else {
                        return false;
                    }
                }
            }
            return false;
        }
        
        /**
         * 如果指定的键尚未与值关联(或映射到null)，则尝试使用给定的映射函数计算其值，并将其输入到此映射中，除非null。
         * 覆写  Map<K,V> computeIfAbsent
         */
        @Override
        public synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
            Objects.requireNonNull(mappingFunction);
    
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for (; e != null; e = e.next) {
                if (e.hash == hash && e.key.equals(key)) {
                    // 哈希表不接受空值
                    return e.value;
                }
            }
    
            V newValue = mappingFunction.apply(key); // 将此函数应用于给定的参数。
            if (newValue != null) {
                addEntry(hash, key, newValue, index); // 加节点
            }
    
            return newValue;
        }
    
        /**
         * 指定键的值存在且非空，尝试计算给定键及其当前映射值的新映射。
         * 覆写  Map<K,V> computeIfPresent
         */
        @Override
        public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
            Objects.requireNonNull(remappingFunction);
    
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                if (e.hash == hash && e.key.equals(key)) {
                    V newValue = remappingFunction.apply(key, e.value);// 将此函数应用于给定的参数。
                    if (newValue == null) {
                        modCount++;
                        if (prev != null) {// 修改相关指针
                            prev.next = e.next;
                        } else {
                            tab[index] = e.next;
                        }
                        count--;
                    } else {
                        e.value = newValue;
                    }
                    return newValue;
                }
            }
            return null;
        }
    
        /**
         * 尝试为指定的键及其当前映射值计算映射(如果没有当前映射，则为null)。
         * 覆写  Map<K,V> compute
         */
        @Override
        public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
            Objects.requireNonNull(remappingFunction);
    
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                if (e.hash == hash && Objects.equals(e.key, key)) {
                    V newValue = remappingFunction.apply(key, e.value);// 将此函数应用于给定的参数。
                    if (newValue == null) {
                        modCount++;
                        if (prev != null) {// 修改相关指针
                            prev.next = e.next;
                        } else {
                            tab[index] = e.next;
                        }
                        count--;
                    } else {
                        e.value = newValue;
                    }
                    return newValue;
                }
            }
    
            V newValue = remappingFunction.apply(key, null);// 将此函数应用于给定的参数。
            if (newValue != null) {
                addEntry(hash, key, newValue, index); // 加节点
            }
    
            return newValue;
        }
    
        /**
         * 如果指定的键尚未与值关联或与null关联，则将其与给定的非null值关联。
         * 否则，将关联值替换为给定映射函数的结果，如果结果为null，则删除关联值。
         * 此方法可用于组合键的多个映射值。
         * 覆写  Map<K,V> merge
         */
        @Override
        public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
            Objects.requireNonNull(remappingFunction);
    
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                if (e.hash == hash && e.key.equals(key)) {
                    V newValue = remappingFunction.apply(e.value, value);// 将此函数应用于给定的参数。
                    if (newValue == null) {
                        modCount++;
                        if (prev != null) { // 修改指针
                            prev.next = e.next;
                        } else {
                            tab[index] = e.next;
                        }
                        count--;
                    } else {
                        e.value = newValue;
                    }
                    return newValue;
                }
            }
    
            if (value != null) {
                addEntry(hash, key, value, index); // 加节点
            }
    
            return value;
        }
    
        /**
         * 将哈希表的状态保存到流中(即,序列化)。
         */
        private void writeObject(java.io.ObjectOutputStream s)
                throws IOException {
            Entry<Object, Object> entryStack = null;
    
            synchronized (this) {
                // 写出阈值和负载因子
                s.defaultWriteObject();
    
                //写出元素的长度和个数
                s.writeInt(table.length);
                s.writeInt(count);
    
                // 表中条目的堆栈副本
                for (int index = 0; index < table.length; index++) {
                    Entry<?,?> entry = table[index];
    
                    while (entry != null) {
                        entryStack =
                            new Entry<>(0, entry.key, entry.value, entryStack);
                        entry = entry.next;
                    }
                }
            }
    
            //从堆积的条目中写出key/value对象
            while (entryStack != null) {
                s.writeObject(entryStack.key);
                s.writeObject(entryStack.value);
                entryStack = entryStack.next;
            }
        }
    
        /**
         * 从流中重新构造散列表(即,反序列化)。
         */
        private void readObject(java.io.ObjectInputStream s)
             throws IOException, ClassNotFoundException
        {
            // 读取阈值和加载因子
            s.defaultReadObject();
    
            // 验证loadFactor(忽略阈值——它将被重新计算)
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new StreamCorruptedException("Illegal Load: " + loadFactor);
    
            // 读取数组的原始长度和元素的数量
            int origlength = s.readInt();
            int elements = s.readInt();
    
            // 验证#元素
            if (elements < 0)
                throw new StreamCorruptedException("Illegal # of Elements: " + elements);
    
            // 钳位原始长度要大于元素/加载因子(这是自动增长强制的不变值)
            origlength = Math.max(origlength, (int)(elements / loadFactor) + 1);
    
            // 新长度增加5% + 3，但不大于原来的长度。使长度为奇数，如果足够大，这有助于分配条目。防止长度为零，这是无效的。
            int length = (int)((elements + elements / 20) / loadFactor) + 3;
            if (length > elements && (length & 1) == 0)
                length--;
            length = Math.min(length, origlength);
    
            if (length < 0) { // overflow
                length = origlength;
            }
    
            // 检查Map.Entry[].class，因为它是我们实际创建的最近的公共类型。
            SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, length);
            table = new Entry<?,?>[length];
            threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
            count = 0;
    
            // 读取元素的数量，然后读取所有键/值对象
            for (; elements > 0; elements--) {
                @SuppressWarnings("unchecked")
                    K key = (K)s.readObject();
                @SuppressWarnings("unchecked")
                    V value = (V)s.readObject();
                // 为了提高性能，取消了同步
                reconstitutionPut(table, key, value);
            }
        }
    
        /**
         * readObject使用的put方法。这是因为put是可覆盖的，并且不应该在readObject中调用，因为子类还没有初始化。
         *
         * 这与常规put方法有几个方面的不同。不需要检查重哈希，因为表中初始元素的数量是已知的。
         * modCount没有增加，也没有同步，因为我们正在创建一个新实例。此外，不需要返回值。
         */
        private void reconstitutionPut(Entry<?,?>[] tab, K key, V value)
            throws StreamCorruptedException
        {
            if (value == null) {
                throw new java.io.StreamCorruptedException();
            }
            // 确保键不在散列表中。这在反序列化版本中不应该发生。
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    throw new java.io.StreamCorruptedException();
                }
            }
            // 创建新条目。
            @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>)tab[index];
            tab[index] = new Entry<>(hash, key, value, e);
            count++;
        }
    
        /**
         * 哈希表桶冲突列表项
         */
        private static class Entry<K,V> implements Map.Entry<K,V> {
            final int hash;	// 哈希值
            final K key;	// 键
            V value;	// 值
            Entry<K,V> next;	// 指向下一个
    
            protected Entry(int hash, K key, V value, Entry<K,V> next) {
                this.hash = hash;
                this.key =  key;
                this.value = value;
                this.next = next;
            }
    
            /**
             * 直接通过new的方式克隆
             */
            @SuppressWarnings("unchecked")
            protected Object clone() {
                return new Entry<>(hash, key, value,
                                      (next==null ? null : (Entry<K,V>) next.clone()));
            }
    
            // Map.Entry Ops
    
            public K getKey() {
                return key;
            }
    
            public V getValue() {
                return value;
            }
    
            /**
             * 可设置值
             */
            public V setValue(V value) {
                if (value == null)
                    throw new NullPointerException();
    
                V oldValue = this.value;
                this.value = value;
                return oldValue;
            }
    
            public boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    
                return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
                   (value==null ? e.getValue()==null : value.equals(e.getValue()));
            }
    
            public int hashCode() {
                return hash ^ Objects.hashCode(value);
            }
    
            public String toString() {
                return key.toString()+"="+value.toString();
            }
        }
    
        // 类型的枚举/迭代
        private static final int KEYS = 0;
        private static final int VALUES = 1;
        private static final int ENTRIES = 2;
    
        /**
         * 一个散列表枚举器类。该类同时实现枚举和迭代器接口，但是可以在禁用迭代器方法的情况下创建单个实例。
         * 这是必要的，以避免通过传递枚举无意中增加授予用户的功能。
         */
        private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
            Entry<?,?>[] table = Hashtable.this.table;
            int index = table.length;
            Entry<?,?> entry;
            Entry<?,?> lastReturned;
            int type;
    
            /**
             * 指示此枚举数是用作迭代器还是枚举。(true -> Iterator).
             */
            boolean iterator;
    
            /**
             * 迭代器认为支持散列表应该具有的modCount值。如果违背了这个期望，迭代器将检测到并发修改。
             */
            protected int expectedModCount = modCount;
    
            Enumerator(int type, boolean iterator) {
                this.type = type;
                this.iterator = iterator;
            }
    
            public boolean hasMoreElements() {
                Entry<?,?> e = entry;
                int i = index;
                Entry<?,?>[] t = table;
                /* 使用局部变量加快循环迭代 */
                while (e == null && i > 0) {
                    e = t[--i];
                }
                entry = e;
                index = i;
                return e != null;
            }
    
            @SuppressWarnings("unchecked")
            public T nextElement() {
                Entry<?,?> et = entry;
                int i = index;
                Entry<?,?>[] t = table;
                /* 使用局部变量加快循环迭代 */
                while (et == null && i > 0) {
                    et = t[--i];
                }
                entry = et;
                index = i;
                if (et != null) {
                    Entry<?,?> e = lastReturned = entry;
                    entry = e.next;
                    return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
                }
                throw new NoSuchElementException("Hashtable Enumerator");
            }
    
            // Iterator methods
            public boolean hasNext() {
                return hasMoreElements();
            }
    
            public T next() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                return nextElement();
            }
    
            public void remove() {
                if (!iterator)
                    throw new UnsupportedOperationException();
                if (lastReturned == null)
                    throw new IllegalStateException("Hashtable Enumerator");
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
    
                synchronized(Hashtable.this) {
                    Entry<?,?>[] tab = Hashtable.this.table;
                    int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;// 通过hash值找到其存储位置
    
                    @SuppressWarnings("unchecked")
                    Entry<K,V> e = (Entry<K,V>)tab[index];
                    for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
                        if (e == lastReturned) {
                            modCount++;
                            expectedModCount++;
                            if (prev == null)
                                tab[index] = e.next;
                            else// 修改相关指针
                                prev.next = e.next;
                            count--;
                            lastReturned = null;
                            return;
                        }
                    }
                    throw new ConcurrentModificationException();
                }
            }
        }
    }