java集合框架之HashTable

starlin 253 2018-05-07

HashTable介绍

先来看看HashMap和HashTable有哪些区别

  1. 关于null,HashMap运行key和value都可以为null,而HashTable不允许key或者value为null的键值对
    当HashMap遇到null为key时,回调用putForNullKey方法来进行处理,当HashTable遇到null时,直接抛出异常
  2. 关于线程安全,Hashmap不是线程安全的,HashTable则是线程安全的,它的需要操作都是由synchronized修饰
  3. Hashtable与HashMap实现的接口一致,但Hashtable继承Dictionary,而HashMap继承自AbstractMap,即父类不同
  4. 默认初始容量不同,扩容大小不同。HashMap的hash数组file:///Users/starlin/Documents/Hexo/source/_posts/java集合框架/的默认大小是16,而且一定是2 的指数,增加方式old2;Hashtable中hash数组默认大小是11,增加的方式是old2+1

![hashtable锁机制](https://raw.githubusercontent.com/smartlin/pic/main/_posts/java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6/java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6%E4%B9%8Bhashtable.md/hashtable%E9%94%81%E6%9C%BA%E5%88%B6.png =888x)

HashTable源码

HashTable定义

HashTable继承Dictionary类,实现Map接口。其中Dictionary类是任何可将键映射到相应值的类的抽象父类。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中,每个键至多与一个值相关联。

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {
HashTable中的属性
    /**
     * The hash table data.
     */
    //为一个Entry[]数组类型,Entry代表了“拉链”的节点,每一个Entry代表了一个键值对,
    //哈希表的"key-value键值对"都是存储在Entry数组中的 
    private transient Entry<?,?>[] table;

    /**
     * The total number of entries in the hash table.
     */
    //HashTable的大小,注意这个大小并不是HashTable的容器大小,而是他所包含Entry键值对的数量。 
    private transient int count;

    /**
     * The table is rehashed when its size exceeds this threshold.  (The
     * value of this field is (int)(capacity * loadFactor).)
     */
    //Hashtable的阈值,用于判断是否需要调整Hashtable的容量。threshold的值="容量*加载因子"。
    private int threshold;
    
    /**
     * The load factor for the hashtable.
     */
    //加载因子
    private float loadFactor;
    
    /**
     * The number of times this Hashtable has been structurally modified
     * Structural modifications are those that change the number of entries in
     * the Hashtable or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the Hashtable fail-fast.  (See ConcurrentModificationException).
     */
    //用来实现“fail-fast”机制的(也就是快速失败)。
    //所谓快速失败就是在并发集合中,其进行迭代操作时,
    //若有其他线程对其进行结构性的修改,这时迭代器会立马感知到,并且立即抛出
    //ConcurrentModificationException异常,而不是等到迭代完成之后才告诉你已经出错了
    private transient int modCount = 0;
HashTable中的构造函数
    /**
     * Constructs a new, empty hashtable with the specified initial capacity
     * and default load factor (0.75).
     *
     * @param     initialCapacity   the initial capacity of the hashtable.
     * @exception IllegalArgumentException if the initial capacity is less
     *              than zero.
     */
    //用指定初始容量和默认的加载因子 (0.75) 构造一个新的空哈希表。 
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).
     */
    //默认构造函数,容量为11,加载因子为0.75。 
    public Hashtable() {
        this(11, 0.75f);
    }

    /**
     * Constructs a new, empty hashtable with the specified initial
     * capacity and the specified load factor.
     *
     * @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) {
        //验证初始容量
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //验证加载因子                                       
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);

        if (initialCapacity==0)
            initialCapacity = 1;
        this.loadFactor = loadFactor;
        //初始化table,获得大小为initialCapacity的table数组
        table = new Entry<?,?>[initialCapacity];
        //计算阀值
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    /**
     * Constructs a new hashtable with the same mappings as the given
     * Map.  The hashtable is created with an initial capacity sufficient to
     * hold the mappings in the given Map and a default load factor (0.75).
     *
     * @param t the map whose mappings are to be placed in this map.
     * @throws NullPointerException if the specified map is null.
     * @since   1.2
     */
    // 构造一个与给定的 Map 具有相同映射关系的新哈希表。 
    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }
HashTable中的主要方法
put方法
    /**
     * Maps the specified <code>key</code> to the specified
     * <code>value</code> in this hashtable. Neither the key nor the
     * value can be <code>null</code>. <p>
     *
     * The value can be retrieved by calling the <code>get</code> method
     * with a key that is equal to the original key.
     *
     * @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)
     */
    //用了 synchronized修饰,线程安全
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        //确保value不为null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        //确保key在table[]是不重复的
        Entry<?,?> tab[] = table;
        //计算key的hash值
        int hash = key.hashCode();
        //(hash & 0x7FFFFFFF)获取数组元素下标,先对hash值取正,然后取余
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

接上面,看下addEntry()方法:

    private void addEntry(int hash, K key, V value, int index) {
        //修改次数
        modCount++;

        Entry<?,?> tab[] = table;
        ////键值对的总数大于其阀值
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            //在rehash里进行扩容处理
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        //插入一个新的节点
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }

我们看下扩容方法rehash(),其源码如下:

    /**
     * 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.
     */
    @SuppressWarnings("unchecked")
    protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // overflow-conscious code
        //新容量等于旧容量*2 + 1
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        //重新计算阀值
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;
        
        //将原来的元素拷贝到新的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;
            }
        }
    }
get方法

和put方法相比,get方法简单的多,其源码如下:

    /**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key.equals(k))},
     * then this method returns {@code v}; otherwise it returns
     * {@code null}.  (There can be at most one such mapping.)
     *
     * @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;
        //
        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)) {
                return (V)e.value;
            }
        }
        return null;
    }

总结

鉴于HashTable的历史遗留问题,现在已经很少用到的,即使我们在对线程安全有要求的场景中,也是通过使用ConcurrentHashMap来解决,而不是使用Hashtable。关于ConcurrentHashMap的使用会在并发章节中会详细介绍


# java集合