Hashtable source code parsing

Hashtable is also implemented based on hash tables, each element is a key-value pair, and its internal conflicts are resolved through a single linked list. When the capacity is insufficient (beyond the threshold), it will automatically grow. Hashtable, also introduced in JDK1.0, is thread-safe and can be used in multithreaded environments. Hashtable also implements Serializable interface, which supports serialization and Cloneable interface, which can be cloned.

package java.util;

import java.io.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.BiConsumer;
import java.util.function.Function;
import java.util.function.BiFunction;
import sun.misc.SharedSecrets;

/**
 *    Hashtable同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
 *
 *  Hashtable也是JDK1.0引入的类，是线程安全的，能用于多线程环境中。
 *
    Hashtable同样实现了Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。
 */
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    /**
     *  保存key-value的数组。
     *  Hashtable同样采用单链表解决冲突，每一个Entry本质上是一个单向链表
     */
    private transient Entry<?,?>[] table;

    /**
     * Hashtable中键值对的数量/个数
     */
    private transient int count;

    /**
     *  阈值，用于判断是否需要调整Hashtable的容量（threshold = 容量*加载因子）
     * @serial
     */
    private int threshold;

    /**
     * 加载因子
     *
     * @serial
     */
    private float loadFactor;

    /**
     * Hashtable被改变的次数，用于fail-fast机制的实现
     */
    private transient int modCount = 0;

    /** 序列版本号     */
    private static final long serialVersionUID = 1421746759512286392L;

    /**
     *  指定“容量大小”和“加载因子”的构造函数
     *  MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
     * @param      initialCapacity   the initial capacity of the hashtable.
     * @param      loadFactor        the load factor of the hashtable.
     * @exception  IllegalArgumentException  if the initial capacity is less
     *             than zero, or if the load factor is nonpositive.
     */
    public Hashtable(int initialCapacity, float loadFactor) {
        //如果指定参数初始化容量小于0，抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //如果指定参数负载因子为非正数，抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
        //初始化hashtable的loadFactor、table、threshold属性
        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        table = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    /**
     *  指定“容量大小”的构造函数
     *  默认加载引资为0.75f
     * @param     initialCapacity   the initial capacity of the hashtable.
     * @exception IllegalArgumentException if the initial capacity is less
     *              than zero.
     */
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     *  默认构造函数。
     */
    public Hashtable() {
      // 默认构造函数，指定的容量大小是11；加载因子是0.75
        this(11, 0.75f);
    }

    /**
     * 包含“子Map”的构造函数
     * @param t the map whose mappings are to be placed in this map.
     * @throws NullPointerException if the specified map is null.
     * @since   1.2
     */
    public Hashtable(Map<? extends K, ? extends V> t) {
        //初始hashMap
        this(Math.max(2*t.size(), 11), 0.75f);
        // 将“子Map”的全部元素都添加到Hashtable中
        putAll(t);
    }

    /**
     * 返回hashtable大小
     */
    public synchronized int size() {
        return count;
    }

    /**
     * 判断hashtable是否是空的
     */
    public synchronized boolean isEmpty() {
        return count == 0;
    }

    /**
     * 返回key的枚举对象
     * @return  an enumeration of the keys in this hashtable.
     * @see     Enumeration
     * @see     #elements()
     * @see     #keySet()
     * @see     Map
     */
    public synchronized Enumeration<K> keys() {
        return this.<K>getEnumeration(KEYS);
    }

    /**
     * 返回value的枚举对象
     * @return  an enumeration of the values in this hashtable.
     * @see     java.util.Enumeration
     * @see     #keys()
     * @see     #values()
     * @see     Map
     */
    public synchronized Enumeration<V> elements() {
        return this.<V>getEnumeration(VALUES);
    }

    /**
     * 判断Hashtable是否包含“值(value)”
     * @param      value   a value to search for
     * @return     <code>true</code> if and only if some key maps to the
     *             <code>value</code> argument in this hashtable as
     *             determined by the <tt>equals</tt> method;
     *             <code>false</code> otherwise.
     * @exception  NullPointerException  if the value is <code>null</code>
     */
    public synchronized boolean contains(Object value) {
        //注意，Hashtable中的value不能是null，
        // 若是null的话，抛出异常!
        if (value == null) {
            throw new NullPointerException();
        }

        // 从后向前遍历table数组中的元素(Entry)
       // 对于每个Entry(单向链表)，逐个遍历，判断节点的值是否等于value
        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;
    }

    /**
     *是否包含有指定参数value
     * @param value value whose presence in this hashtable is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     * @throws NullPointerException  if the value is <code>null</code>
     * @since 1.2
     */
    public boolean containsValue(Object value) {
        return contains(value);
    }

    /**
     *判断hashtable中是否包含key
     *
     * @param   key   possible key
     * @return  <code>true</code> if and only if the specified object
     *          is a key in this hashtable, as determined by the
     *          <tt>equals</tt> method; <code>false</code> otherwise.
     * @throws  NullPointerException  if the key is <code>null</code>
     * @see     #contains(Object)
     */
    public synchronized boolean containsKey(Object key) {
        Entry<?,?> tab[] = table;
        //计算hash值，直接用key的hashCode代替
        int hash = key.hashCode();
         // 计算在数组中的索引值
        int index = (hash & 0x7FFFFFFF) % tab.length;
         // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return true;
            }
        }
        return false;
    }

    /**
     *  返回key对应的value，没有的话返回null
     * @param key the key whose associated value is to be returned
     * @return the value to which the specified key is mapped, or
     *         {@code null} if this map contains no mapping for the key
     * @throws NullPointerException if the specified key is null
     * @see     #put(Object, Object)
     */
    @SuppressWarnings("unchecked")
    public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        //计算hash值，直接用key的hashCode代替
        int hash = key.hashCode();
         // 计算在数组中的索引值
        int index = (hash & 0x7FFFFFFF) % tab.length;
         // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
              //返回该key对应的value的值
                return (V)e.value;
            }
        }
        //找不到返回null
        return null;
    }

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * Increases the capacity of and internally reorganizes this
     * hashtable, in order to accommodate and access its entries more
     * efficiently.  This method is called automatically when the
     * number of keys in the hashtable exceeds this hashtable's capacity
     * and load factor.
     * 调整Hashtable的长度，将长度变成原来的2倍+1
     */
    @SuppressWarnings("unchecked")
    protected void rehash() {
        //记录旧容量
        int oldCapacity = table.length;
        //记录旧桶的数组
        Entry<?,?>[] oldMap = table;

        // overflow-conscious code
        //创建新容量大小的Entry数组
        int newCapacity = (oldCapacity << 1) + 1;
        //不能大于MAX_ARRAY_SIZE
        //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
          //如果原来容量已经是MAX_ARRAY_SIZE大小，就不进行扩容
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
             //如果旧容量不为MAX_ARRAY_SIZE，新容量变为MAX_ARRAY_SIZE
            newCapacity = MAX_ARRAY_SIZE;
        }
        //创建新的数组，容量为新容量
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
        //结构性修改次数+1
        modCount++;
        //计算扩容的临界值
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;
       //将“旧的Hashtable”中的元素复制到“新的Hashtable”中
        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;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }
    /**
     * 根据指参数向table中添加entry
     * put方法会使用此方法
     */
    private void addEntry(int hash, K key, V value, int index) {
       //结构性修改次数+1
        modCount++;
        //记录现在的table
        Entry<?,?> tab[] = table;
        //如果现在的entry数量大于临界值
        if (count >= threshold) {
             // 扩容
            rehash();
            //记录新的table
            tab = table;
            //重新计算key的hash
            hash = key.hashCode();
            //重新计算index
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // 创建一个新的entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        //将entry添加到table中
        tab[index] = new Entry<>(hash, key, value, e);
        //table大小+1
        count++;
    }

    /**
     *将“key-value”添加到Hashtable中
     * @param      key     the hashtable key
     * @param      value   the value
     * @return     the previous value of the specified key in this hashtable,
     *             or <code>null</code> if it did not have one
     * @exception  NullPointerException  if the key or value is
     *               <code>null</code>
     * @see     Object#equals(Object)
     * @see     #get(Object)
     */
    public synchronized V put(K key, V value) {
       // Hashtable中不能插入value为null的元素！！！
        if (value == null) {
            throw new NullPointerException();
        }

        // 若“Hashtable中已存在键为key的键值对”，
       // 则用“新的value”替换“旧的value”
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        //找到key在table中的索引
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //获取key所在索引的entry
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
         //遍历entry，判断key是否已经存在
        for(; entry != null ; entry = entry.next) {
             //如果key已经存在
            if ((entry.hash == hash) && entry.key.equals(key)) {
                //保存旧的value
                V old = entry.value;
                //替换value
                entry.value = value;
                //返回旧的value
                return old;
            }
        }
       //如果key在hashtable不是已经存在，就直接将键值对添加到table中，返回null
        addEntry(hash, key, value, index);
        return null;
    }

    /**
     *删除Hashtable中key对应的元素
     * @param   key   the key that needs to be removed
     * @return  the value to which the key had been mapped in this hashtable,
     *          or <code>null</code> if the key did not have a mapping
     * @throws  NullPointerException  if the key is <code>null</code>
     */
    public synchronized V remove(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //从table[index]链表中找出要删除的节点，并删除该节点。
        //因为是单链表，因此要保留带删节点的前一个节点，才能有效地删除节点
        @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)) {
                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<? extends K, ? extends V> t”的中全部元素逐一添加到Hashtable中
     * @param t mappings to be stored in this map
     * @throws NullPointerException if the specified map is null
     * @since 1.2
     */
    public synchronized void putAll(Map<? extends K, ? extends V> t) {
        // //遍历参数t中所有的键值对，将其复制到hashtable中
        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
            put(e.getKey(), e.getValue());
    }

    /**
     * Clears this hashtable so that it contains no keys.
     * 清空Hashtable
     * 将Hashtable的table数组的值全部设为null
     */
    public synchronized void clear() {
        Entry<?,?> tab[] = table;
        modCount++;
        //遍历hashtable中所有的entry，将其置为null
        for (int index = tab.length; --index >= 0; )
            tab[index] = null;
        //修改hashtable大小为0
        count = 0;
    }

    /**
     * 克隆一个Hashtable，并以Object的形式返回。
     * @return  a clone of the hashtable
     */
    public synchronized Object clone() {
        try {
          //调用父类的clone方法，浅拷贝一个HashTable对象t
            Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
             //给table属性赋值
            t.table = new Entry<?,?>[table.length];
             //遍历原散列数组，单独地拷贝并生成每个桶的链表。
            for (int i = table.length ; i-- > 0 ; ) {
                t.table[i] = (table[i] != null)
                    ? (Entry<?,?>) table[i].clone() : null;
            }
            //给keySet属性赋值
            t.keySet = null;
             //给entrySet属性赋值
            t.entrySet = null;
            //给values 属性赋值
            t.values = null;
            //给modCount 属性赋值
            t.modCount = 0;
            //返回浅拷贝
            return t;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

    /**
     * Returns a string representation of this <tt>Hashtable</tt> object
     * in the form of a set of entries, enclosed in braces and separated
     * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each
     * entry is rendered as the key, an equals sign <tt>=</tt>, and the
     * associated element, where the <tt>toString</tt> method is used to
     * convert the key and element to strings.
     *
     * @return  a string representation of this hashtable
     */
    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(", ");
        }
    }

       /**
        *获取Hashtable的枚举类对象
        *若Hashtable的实际大小为0,则返回“空枚举类”对象；
        *否则，返回正常的Enumerator的对象。
        */
    private <T> Enumeration<T> getEnumeration(int type) {
        if (count == 0) {
            return Collections.emptyEnumeration();
        } else {
            return new Enumerator<>(type, false);
        }
    }

    /**
     * 获取Hashtable的迭代器
     * 若Hashtable的实际大小为0,则返回“空迭代器”对象；
     * 否则，返回正常的Enumerator的对象。(Enumerator实现了迭代器和枚举两个接口)
     *
     */
    private <T> Iterator<T> getIterator(int type) {
        if (count == 0) {
            return Collections.emptyIterator();
        } else {
            return new Enumerator<>(type, true);
        }
    }

    // Views

    // Hashtable的“key的集合”。它是一个Set，没有重复元素
    private transient volatile Set<K> keySet;
    // Hashtable的“key-value的集合”。它是一个Set，没有重复元素
    private transient volatile Set<Map.Entry<K,V>> entrySet;
    // Hashtable的“key-value的集合”。它是一个Collection，可以有重复元素
    private transient volatile Collection<V> values;

    /**
     * 返回一个被synchronizedSet封装后的KeySet对象
     * synchronizedSet封装的目的是对KeySet的所有方法都添加synchronized，实现多线程同步
     * @since 1.2
     */
    public Set<K> keySet() {
        if (keySet == null)
            keySet = Collections.synchronizedSet(new KeySet(), this);
        return keySet;
    }
    /**
     *Hashtable的Key的Set集合
     *KeySet继承于AbstractSet，所以，KeySet中的元素没有重复的。
     * @since 1.2
     */
    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();
        }
    }

    /**
     *返回一个被synchronizedSet封装后的EntrySet对象
     *synchronizedSet封装的目的是对EntrySet的所有方法都添加synchronized，实现多线程同步
     */
    public Set<Map.Entry<K,V>> entrySet() {
        if (entrySet==null)
            entrySet = Collections.synchronizedSet(new EntrySet(), this);
        return entrySet;
    }
    /**
     * Hashtable的Entry的Set集合
     * EntrySet继承于AbstractSet，所以，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);
        }
        /**
        * 查找EntrySet中是否包含Object(0)，找到返回true,否则返回false
        * 首先，在table中找到o对应的Entry链表
        * 然后，查找Entry链表中是否存在Object
        */
        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;

            for (Entry<?,?> e = tab[index]; e != null; e = e.next)
                if (e.hash==hash && e.equals(entry))
                    return true;
            return false;
        }

        /**
        * 删除元素Object(0)
        * 首先，在table中找到o对应的Entry链表
        * 然后，删除链表中的元素Object
        */
        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();
            //index为索引位置
            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) {
                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();
        }
    }

    /**
     * 返回一个被synchronizedCollection封装后的ValueCollection对象
     * synchronizedCollection封装的目的是对ValueCollection的所有方法都添加synchronized，实现多线程同步
     * @since 1.2
     */
    public Collection<V> values() {
        if (values==null)
            values = Collections.synchronizedCollection(new ValueCollection(),
                                                        this);
        return values;
    }
    /**
     * Hashtable的value的Collection集合。
     * ValueCollection继承于AbstractCollection，所以，ValueCollection中的元素可以重复的。
     */
    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();
        }
    }

    // Comparison and hashing

    /**
     * 重写equal方法， 若两个Hashtable的所有key-value键值对都相等，则判断它们两个相等
     * @param  o object to be compared for equality with this hashtable
     * @return true if the specified Object is equal to this Map
     * @see Map#equals(Object)
     * @since 1.2
     */
    public synchronized boolean equals(Object o) {
        //如果参数就是hashtable，返回true
        if (o == this)
            return true;
        //如果参数o不是map，返回false
        if (!(o instanceof Map))
            return false;
        Map<?,?> t = (Map<?,?>) o;
        //如果大小不同，返回false
        if (t.size() != size())
            return false;

        try {
          // 通过迭代器依次取出当前Hashtable的key-value键值对
          // 并判断该键值对，存在于Hashtable中。
          // 若不存在，则立即返回false；否则，遍历完“当前Hashtable”并返回true。
            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 {
                    if (!value.equals(t.get(key)))
                        return false;
                }
            }
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }

        return true;
    }

    /**
     * 计算Entry的hashCode
     * Map interface.
     *
     * @see Map#hashCode()
     * @since 1.2
     */
    public synchronized int hashCode() {
        int h = 0;
        //若 Hashtable的实际大小为0 或者 加载因子<0，则返回0。
        if (count == 0 || loadFactor < 0)
           //返回0
            return h;  // Returns zero
         //将loadFactor变为负数
        loadFactor = -loadFactor;  // Mark hashCode computation in progress
        Entry<?,?>[] tab = table;
        //遍历hashtable中所有的entry
        for (Entry<?,?> entry : tab) {
           //如果entry不为null
            while (entry != null) {
               //hashcode加entry的hashcode
                h += entry.hashCode();
                //准备entry的下个entry
                entry = entry.next;
            }
        }
       //将loadFactor变为正数
        loadFactor = -loadFactor;  // Mark hashCode computation complete
       //返回hashcode
        return h;
    }
   /**
    *返回指定参数key映射的value，如果没有对应映射，返回默认值defaultValue
    */
    @Override
    public synchronized V getOrDefault(Object key, V defaultValue) {
        V result = get(key);
        return (null == result) ? defaultValue : result;
    }

    @SuppressWarnings("unchecked")
    @Override
    public synchronized void forEach(BiConsumer<? super K, ? super V> action) {
        Objects.requireNonNull(action);     // explicit check required in case
                                            // table is empty.
        final int expectedModCount = modCount;

        Entry<?, ?>[] tab = table;
        for (Entry<?, ?> entry : tab) {
            while (entry != null) {
                action.accept((K)entry.key, (V)entry.value);
                entry = entry.next;

                if (expectedModCount != modCount) {
                    throw new ConcurrentModificationException();
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    @Override
    public synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        Objects.requireNonNull(function);     // explicit check required in case
                                              // table is empty.
        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));
                entry = entry.next;

                if (expectedModCount != modCount) {
                    throw new ConcurrentModificationException();
                }
            }
        }
    }
      /**
      *在hashtable中插入参数key和value组成的键值对，如果key已经存在，返回旧value，如果旧value为null，则用参数value替换旧value
      */
    @Override
    public synchronized V putIfAbsent(K key, V value) {
        //判断value是否为null，如果为null，抛出NullPointerException
        Objects.requireNonNull(value);

        // 确认key是不是已经才hashtable中存在
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        //获取key在hashtable中的索引
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //根据key在hashtable中的索引获取对应entry
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        //遍历entry中的所有键值对，如果key已经存在，返回旧value，如果旧value为null，则用参数value替换旧value
        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;
            }
        }
        //如果，key在entry中不存在，添加entry，返回null
        addEntry(hash, key, value, index);
        return null;
    }

    /**
     * 在hashtable中删除key和value都和参数key和参数value匹配的键值对
     *
     * @return 如果删除成功，返回true
     */
    @Override
    public synchronized boolean remove(Object key, Object value) {
        //如果value为null，抛出空指针异常
        Objects.requireNonNull(value);

        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        //计算key在hashtable中的索引
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //根据key在hashtable中的索引获取对应entry
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>)tab[index];
        //遍历entry，如果entry中存在和参数value和参数key都存在的键值对，则删除这个键值对，并返回true
        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;
            }
        }
        //如果entry中不存在和参数value和参数key都存在的键值对，返回false
        return false;
    }

    /**
     * 在hashtable中查找key和value都和参数key和参数oldValue都匹配的键值对，如果找到，将键值对的value替换为参数newValue
     *
     * @return 如果替换成功，返回true
     */
    @Override
    public synchronized boolean replace(K key, V oldValue, V newValue) {
       //如果oldValue或者newValue为null，抛出空指针异常
        Objects.requireNonNull(oldValue);
        Objects.requireNonNull(newValue);
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        //计算key在hashtable中的索引
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>)tab[index];
       //遍历entry，如果key和value都和参数key和参数oldValue都匹配的键值对，如果找到，将键值对的value替换为参数newValue，返回true。如果都不匹配，返回false
        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;
                }
            }
        }
        //如果都不匹配，返回false
        return false;
    }

    /**
     * 在hashtable中查找key和参数key匹配的键值对，如果找到，将键值对的value替换为参数value
     *
     * @return 如果替换成功，返回键值对的旧value
     */
    @Override
    public synchronized V replace(K key, V value) {
       //如果value为null，抛出空指针异常
        Objects.requireNonNull(value);
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        //计算key在hashtable中的索引
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        //根据key在hashtable中的索引获取entry
        Entry<K,V> e = (Entry<K,V>)tab[index];
        //遍历entry，如果存在key和参数key匹配的键值对，将键值对的value替换为参数value，返回true。如果都不匹配，返回null
        for (; e != null; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        return null;
    }

    @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;
        @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)) {
                // Hashtable not accept null value
                return e.value;
            }
        }

        V newValue = mappingFunction.apply(key);
        if (newValue != null) {
            addEntry(hash, key, newValue, index);
        }

        return newValue;
    }

    @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;
        @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;
    }

    @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;
        @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;
    }

    @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;
        @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;
    }

    /**
   * 序列化hashtable到ObjectOutputStream中
   * 将hashtable的总容量table.length、实际容量count、键值对映射写入到ObjectOutputStream中。键值对映射序列化时是无序的。
   */
    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);

            // Stack copies of the entries in the table
            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;
                }
            }
        }

      // 写入hashtable键值对到ObjectOutputStream中
        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();

         // 验证负载因子，忽略临界值，因为它会被重新计算
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new StreamCorruptedException("Illegal Load: " + loadFactor);

         // 读出hashtable总容量和实际大小
        int origlength = s.readInt();
        int elements = s.readInt();

         // 验证实际大小
        if (elements < 0)
            throw new StreamCorruptedException("Illegal # of Elements: " + elements);

        // 重新计算总容量，使其大于(实际大小/负载因子)+1
        origlength = Math.max(origlength, (int)(elements / loadFactor) + 1);

        // Compute new length with a bit of room 5% + 3 to grow but
        // no larger than the clamped original length.  Make the length
        // odd if it's large enough, this helps distribute the entries.
        // Guard against the length ending up zero, that's not valid.
        int length = (int)((elements + elements / 20) / loadFactor) + 3;
        if (length > elements && (length & 1) == 0)
            length--;
        length = Math.min(length, origlength);

        // Check Map.Entry[].class since it's the nearest public type to
        // what we're actually creating.
        SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, length);
        table = new Entry<?,?>[length];
        threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
        count = 0;

        // 读出所有的key-value键值对，并将其添加到table中
        for (; elements > 0; elements--) {
            @SuppressWarnings("unchecked")
                K key = (K)s.readObject();
            @SuppressWarnings("unchecked")
                V value = (V)s.readObject();
            // sync is eliminated for performance
            reconstitutionPut(table, key, value);
        }
    }

    /**
   * 此方法被readObject方法使用。
   * 提供该方法是因为put方法是可重写的，不应该被readObject调用。
   *
   * 该方法和put方法在以下几个方面不同：
   * 从hashtable容量被初始化开始，不扩容。
   * modCount不增长
   * 不同步，因为我们在创建一个新的实例
   * 不需要返回值
   */
    private void reconstitutionPut(Entry<?,?>[] tab, K key, V value)
        throws StreamCorruptedException
    {
        if (value == null) {
            throw new java.io.StreamCorruptedException();
        }
        // Makes sure the key is not already in the hashtable.
        // This should not happen in deserialized version.
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                throw new java.io.StreamCorruptedException();
            }
        }
        // Creates the new entry.
        @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

    /**
     * Hashtable的Entry节点，它本质上是一个单向链表。
     * 也因此，我们才能推断出Hashtable是由拉链法实现的散列表
     */
    private static class Entry<K,V> implements Map.Entry<K,V> {
        // 哈希值
        final int hash;
        final K key;
        V value;
        // 指向的下一个Entry，即链表的下一个节点
        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;
        }

        @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;
        }
         // 设置value。若value是null，则抛出异常
        public V setValue(V value) {
            if (value == null)
                throw new NullPointerException();

            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
        /**
         *覆盖equals()方法，判断两个Entry是否相等。
         */
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            //若两个Entry的key和value不为null且都相等，则认为它们相等。
            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();
        }
    }

    // Types of Enumerations/Iterations
    private static final int KEYS = 0;
    private static final int VALUES = 1;
    private static final int ENTRIES = 2;

    /**
     *Enumerator的作用是提供了“通过elements()遍历Hashtable的接口” 和 “通过entrySet()遍历Hashtable的接口”。
     */
    private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
        // 指向Hashtable的table
        Entry<?,?>[] table = Hashtable.this.table;
         // Hashtable的总的大小
        int index = table.length;
        Entry<?,?> entry;
        Entry<?,?> lastReturned;
        int type;

        /**
         * Enumerator是 “迭代器(Iterator)” 还是 “枚举类(Enumeration)”的标志
         *  iterator为true，表示它是迭代器；否则，是枚举类。
         */
        boolean iterator;

        /**
         * 在将Enumerator当作迭代器使用时会用到，用来实现fail-fast机制。
         */
        protected int expectedModCount = modCount;

        Enumerator(int type, boolean iterator) {
            this.type = type;
            this.iterator = iterator;
        }

        /**
         * 从遍历table的数组的末尾向前查找，直到找到不为null的Entry。
         */
        public boolean hasMoreElements() {
            Entry<?,?> e = entry;
            int i = index;
            Entry<?,?>[] t = table;
            /* Use locals for faster loop iteration */
            while (e == null && i > 0) {
                e = t[--i];
            }
            entry = e;
            index = i;
            return e != null;
        }
        /**
         * 获取下一个元素
         *  注意：从hasMoreElements() 和nextElement() 可以看出“Hashtable的elements()遍历方式”
         *  首先，从后向前的遍历table数组。table数组的每个节点都是一个单向链表(Entry)。
         *
         */
        @SuppressWarnings("unchecked")
        public T nextElement() {
            Entry<?,?> et = entry;
            int i = index;
            Entry<?,?>[] t = table;
            /* Use locals for faster loop iteration */
            //首先，从后向前的遍历table数组。table数组的每个节点都是一个单向链表(Entry)。
            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的判断是否存在下一个元素
         *  实际上，它是调用的hasMoreElements()
         */
        public boolean hasNext() {
            return hasMoreElements();
        }
        /**
         * 迭代器获取下一个元素
         * 实际上，它是调用的nextElement()
         */
        public T next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            return nextElement();
        }

        /**
         * 迭代器的remove()接口。
         * 首先，它在table数组中找出要删除元素所在的Entry，
         *  然后，删除单向链表Entry中的元素。
         */
        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;

                @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();
            }
        }
    }
}Copy the code

1. Both storage structures and conflict resolution methods are the same.

2. The default size of a HashTable without specifying the size is 11, and that of a HashMap is 16. A HashTable does not require the underlying array to be an integer power of 2, whereas a HashMap requires that the underlying array be an integer power of 2.

3. In a Hashtable, neither key nor value is allowed to be null. In a HashMap, both key and value are allowed to be NULL. However, if there is an operation like PUT (NULL, NULL) in a Hashtable, the compilation will also pass because the key and value are both Object types, but NullPointerException is thrown at runtime, as specified in the JDK specification.

4. When Hashtable is expanded, the capacity is multiplied by 1, and when HashMap is expanded, the capacity is doubled.

A HashMap recalculates the hash value of a key. A HashMap recalculates the hash value of a key. A HashMap recalculates the hash value of a key. In general, hash&0x7FFFFFFF is used first and then modulo length. The purpose of & 0x7fffff is to convert the negative hash value into a positive value, because the hash value can be negative, while & 0x7fffff only changes outside the sign, and the bits behind it remain unchanged.

6. Hashtable is thread-safe, HashMap is not

Recommended reading: www.importnew.com/24822.html

search

Commonly used links

• My essay
• My comments
• I participate in
• The latest comments
• My label

My label

• The android 5.0 (16)
• ormlite(3)
• AndroidGradle(2)
• Java review (2)
• Swift Object C Learning (1)
• Swift or Object c(1)

Classification of essays

• 【android Interview 】(12)
• [android] (195).
• Bug 】 【 android – (33)
• 【 android – openGL 】 (1)
• 【androidstudio– learning and using experience 】(2)
• Android –Thread– Thread pool (1)
• 【 Android — Performance Optimization 】(19)
• [App R & D record reading notes] (6)
• 【Effactive Java】(2)
• 【 Eventbus 】 (7)
• 【Gradle learning 】
• [HTML] (6)
• (3) the IOS 】 【
• J2EE (22) 】
• 【J2EE interview Questions 】(2)
• 【Java — JDBC Learning 】(12)
• Learning new Features in Java 1.8
• [Java NIO — IO Advanced] (7)
• (5)
• (2) JavaWeb 】 【
• [Java Multithreading — Advanced advanced] (10)
• 【JDK source code learning 】(4)
• Json exception (2)
• [Kotlin’s Learning and Practice] (1)
• (4)
• 【 MySQL 】 (1)
• 【phoneGap Learning 】(1)
• 【 Python 】(11)
• 【Rxjava learning 】(1)
• (2) the Servlet 】 【
• 【 Shell Scripting 】
• Sqlite (1)
• 【Volley learning and source code analysis 】(7)
• 【Web Front End — JavaScript Learning and Review 】(8)
• 【Web front-end –Html&Css learning review 】(39)
• [Product knowledge learning]
• [Project] (1)
• 【 Design Pattern Review 】(26)
• Understanding the Java Virtual Machine (2)
• 【 Data Structure and Algorithm 】(6)
• Mobile Payment (3)
• Refactoring – Improving the design of existing code
• [Custom controls] (7)

Archives of essays

• March 2018 (1)
• February 2018 (2)
• November 2017 (3)
• October 2017 (8)
• September 2017 (9)
• August 2017 (11)
• July 2017 (4)
• June 2017 (26)
• May 2017 (22)
• April 2017 (40)
• March 2017 (18)
• February 2017 (11)
• January 2017 (9)
• September 2016 (5)
• August 2016 (6)
• July 2016 (2)
• June 2016 (4)
• May 2016 (7)
• April 2016 (8)
• March 2016 (2)
• February 2016 (2)
• January 2016 (2)
• December 2015 (6)
• November 2015 (10)
• October 2015 (10)
• September 2015 (11)
• August 2015 (5)
• July 2015 (13)
• June 2015 (6)
• May 2015 (17)
• April 2015 (10)
• March 2015 (6)
• February 2015 (4)
• January 2015 (19)
• December 2014 (15)
• November 2014 (11)
• October 2014 (1)
• September 2014 (2)
• August 2014 (4)
• July 2014 (2)
• June 2014 (2)
• May 2014 (17)
• April 2014 (11)
• March 2014 (6)
• February 2014 (4)
• January 2014 (17)
• December 2013 (38)
• November 2013 (21)
• October 2013 (2)
• September 2013 (1)
• August 2013 (7)

My github

• My Github address

My personal blog site

• Job Tribes (edited with Markdown)

Points and Rankings

• Integral – 113806.
• No – 2631

The latest comments

• 1. Re:J2EE– often meet
• mark
• –Jason928
• Re:LinkedHashMap source code parsing
• @Daohua thank you, also welcome a lot of advice and suggestions…
• — Northwest Wolf
• Re:LinkedHashMap source code parsing
• Very good
• – paddy fields
• 4. Re: Integrated mail development for project practice
• Good job!
• – in the sky
• 5. Re:Spring — AOP
• @billySIR ProceedingJoinPoint or JoinPoint…
• — Northwest Wolf

Reading leaderboards

• 1. Glide loading round picture (14018)
• 2. Androidstudio — gsonFormat — Super cool data parsing (10026)
• 3. Android App integrates Alipay payment and wechat Payment (6485)
• 4. Custom control of the circular color gradient progress bar –SweepGradient(4561)
• 5. Handling android 6.0 rights management in the project (4506)

Review charts

• 1. Material Design of Android open source code (4)
• 2. Spring — AOP(2)
• 3. How to clean up redundant class files, resource files and redundant images in Android project under the condition of Eclipse (2)
• 4. Android uses Shape to animate the selector button press and bounce (2)
• 5. Review of Java generics and explain the scenarios used in Android (2)

Recommended leaderboard

• 1. Material Design of Android open source code (8)
• Android project Summary (1)
• 3. Android Classic Open Source Code Collection (1)
• 4. Android — Load GIF to prevent OOM (1)
• 5. Android transparent Status bar (1)

Blog garden
Hj blog