Hashtable源码解析-阿里云开发者社区

开发者社区> 西北野狼> 正文

Hashtable源码解析

简介: Hashtable同样是基于哈希表实现的,同样每个元素是一个key-value对,其内部也是通过单链表解决冲突问题,容量不足(超过了阀值)时,同样会自动增长。 Hashtable也是JDK1.0引入的类,是线程安全的,能用于多线程环境中。
+关注继续查看

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

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();
            }
        }
    }
}

1、二者的存储结构和解决冲突的方法都是相同的。

2、HashTable在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。

3、Hashtable中key和value都不允许为null,而HashMap中key和value都允许为null(key只能有一个为null,而value则可以有多个为null)。但是如果在Hashtable中有类似put(null,null)的操作,编译同样可以通过,因为key和value都是Object类型,但运行时会抛出NullPointerException异常,这是JDK的规范规定的。

4、Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。

5、Hashtable计算hash值,直接用key的hashCode(),而HashMap重新计算了key的hash值,Hashtable在求hash值对应的位置索引时,用取模运算,而HashMap在求位置索引时,则用与运算,且这里一般先用hash&0x7FFFFFFF后,再对length取模,&0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数,而&0x7FFFFFFF后,只有符号外改变,而后面的位都不变。

6、Hashtable是线程安全的,HashMap不是

推荐阅读:http://www.importnew.com/24822.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
(周期计划-8)常用集合的源码分析:HashMap
写在前面 感兴趣的看官,可以看看我的其他文章:1、从公司代码看Notification2、Java反射实践:从反射中理解class3、从公司项目配置看Gradle 上一篇博客,我们分析了ArrayList的源码实现,ArrayList吊起来观察一番之后,那么下一个被吊起来的肯定就是HashMap了。
811 0
Java 集合源码解析 - ConcurrentHashMap(JDK7)(下)
Java 集合源码解析 - ConcurrentHashMap(JDK7)(下)
8 0
fastjson解析json字符串,key缺少双引号导致下游服务无法解析
背景说明 在使用fastjson 1.2.60版本将对象转化为json字符串时,为处理Map值为null的情况,采用了WRITE_MAP_NULL_FEATURES属性,但该属性解析出来的key中缺少双引号,在key包含特殊字符时,如“-”和“:",下游服务在进行反序列化时出现无法解析的错误,从而出现问题。
3036 0
VB源码之友2006正式发布了,欢迎大家下载使用
工具栏功能: 1、【添加模块说明】(图标①):在每个VB模块的起始行添加该模块的说明信息。 2、【添加函数说明】(图标②):在指定的函数(或过程)的起始行添加该函数(或过程)的说明信息。
665 0
Java集合源码学习(四)HashMap分析
ArrayList、LinkedList和HashMap的源码是一起看的,横向对比吧,感觉对这三种数据结构的理解加深了很多。 数据结构中有数组和链表来实现对数据的存储,这两者有不同的应用场景, 数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,插入和删除容易; 哈希表的实现结合了这两点,哈希表的实现方式有多种,在HashMap中使用的是链地址法,也就是拉链法。
1501 0
一起谈.NET技术,VS2010 C++下编译调试MongoDB源码
  考虑到mongodb使用了boost库源码,参考mongodb官方文档后,下载编译boost版本是1.42(时间为2010-2-2)或更新版本:  boost版本1.42:  http://sourceforge.net/projects/boost/files/boost/1.42.0/boost_1_42_0.zip/download         下载boost源码之后,我把boost解压在D盘。
978 0
HashMap源码分析(基于JDK1.6)
在Java集合类中最常用的除了ArrayList外,就是HashMap了。本文尽自己所能,尽量详细的解释HashMap的源码。一山还有一山高,有不足之处请之处,定感谢指定并及时修正。     在看HashMap源码之前先复习一下数据结构。
497 0
HashSet及LinkedHashSet源码分析(基于JDK1.6)
Java容器类的用途是“保存对象”,分为两类:Map——存储“键值对”组成的对象;Collection——存储独立元素。Collection又可以分为List和Set两大块。List保持元素的顺序,而Set不能有重复的元素。
718 0
+关注
西北野狼
擅长Android ,J2EE开发 博客园地址:http://www.cnblogs.com/androidsuperman/p/7834762.html github地址: https://github.com/soyoungboy
463
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载