HashTable解析

注：本文基于Android的HashTable
一些概念性的东西，比如哈希表、冲突等，请先阅读HashMap解析（建议先看这边文章）
秉承我一贯的风格，带着问题去一步一步解析HashTable的实现原理：
1、HashTable的数据结构是什么？
2、HashTable默认容量是多少？
3、HashTable最大容量是多少？
4、HashTable默认扩容阈值是多少？加载因子默认值是多少？
5、HashTable每次扩容大小是多少？
6、HashTable hash函数是怎么实现的？
7、HashTable get的原理是什么？
8、HashTable put的原理是什么？
9、HashTable 是否是线程安全？
10、HashTable与HashMap的区别是什么？
下面我根据源码一一解答上面的问题：

问题1：HashTable的数据结构是什么？

起始它跟HashMap一样使用的是一位数组+链表的数据结构，不同的是HashMap的节点使用的是Node内部类，而HashTable使用的是HashTableEntry内部类。看如下源码：

/**
* The hash table data.
*/
private transient HashtableEntry<?,?>[] table;

private static class HashtableEntry<K,V> implements Map.Entry<K,V> {
    // END Android-changed: Renamed Entry -> HashtableEntry.
    final int hash;
    final K key;
    V value;
    HashtableEntry<K,V> next;
   //...省略
}

问题2：HashTable默认容量是多少？

跟HashMap不一样的是，HashTable并没有定义一个默认容量的常量，我们可以理解为HashTable的默认容量为11，HashTable的初始容量大小根据不同的构造函数定义的，我们来看下其构造函数：

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;
}
public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
}
public Hashtable() {
        this(11, 0.75f);
}
public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
}

通过上面代码，默认大小确实是11，只是它的初始容量可能不一样：

• 如果initialCapacity 未0，则初始容量为1
• 如果new HasTable不指定容量大小，默认是11，初始容量也是11
• 如果new时，传入的Map容量比较默认大小11大，那么初始容量大小为传入Map大小的2倍；否则默认默认的11

问题3：HashTable最大容量是多少？

Hashtable最大容量是Integer.MAX_VALUE - 8，为什么是Integer.MAX_VALUE - 8而不是Integer.MAX_VALUE，因为部分虚拟机占用了前8位，如果超出了Integer.MAX_VALUE - 8虚拟机会抛出OutOfMemoryError
我们来看下源码中的定义：

/**
 * 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;

源码明确的定义了最大容量的值，且注释说明了为什么是Integer.MAX_VALUE - 8。
HashMap中即使页指定了最大容量的值为2^30，但是却允许在扩容操作时扩容到Integer.MAX_VALUE ，那么HashTable会不会跟HashMap一样处理呢？我们来看HashTable扩容操作的源码：

protected void rehash() {
        //当前散列表的容量
        int oldCapacity = table.length;
        //当前散列表
        HashtableEntry<?,?>[] 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
                /**如果扩容的容量比限定的容量大，并且原容容量等于MAX_ARRAY_SIZE，则返回不做扩容处理
               */
                return;
            /** 如果扩容的容量比限定的容量大，并且原容容量不等于MAX_ARRAY_SIZE，则修正扩融入为限定的最大值
            */
            newCapacity = MAX_ARRAY_SIZE;
        }
        //创建一个新的HashtableEntry一维数组，其容量为扩容之后的大小newCapacity
        HashtableEntry<?,?>[] newMap = new HashtableEntry<?,?>[newCapacity];
        //HashTable修改此时加1
        modCount++;
        //设置扩容阈值为newCapacity * loadFactor, MAX_ARRAY_SIZE + 1中的最小值
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        
        table = newMap;
        //使用新的扩容大小从新计算数组的下标值，并设定新的数组对应的值
        for (int i = oldCapacity ; i-- > 0 ;) {
            for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
                HashtableEntry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (HashtableEntry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }

上述代码证明了HashTable与HashMap最大容量大小在扩容操作时是不一样的，即HashTable的最大大小为Integer.MAX_VALUE - 8

问题4：HashTable默认扩容阈值是多少？加载因子默认值是多少？

根据解答上述几个问题，知道，HashTable默认扩容阈值为容量加载因子，而加载因子默认值为0.75，故默认扩容阈值=容量0.75

问题5：HashTable每次扩容大小是多少？

根据问题3中的源码，我们可以得出HashTable每次扩容大小是：
1、默认扩容的容量=原容量*2 + 1
2、如果扩容的容量比MAX_ARRAY_SIZE大，则设置为MAX_ARRAY_SIZE

问题6：HashTable hash函数是怎么实现的？

这个问题在问题7中一并回调

问题7：HashTable get的原理是什么？

我们先看get的源码：

public synchronized V get(Object key) {
        // 当前散列表
        HashtableEntry<?,?> tab[] = table;
        // hash值，取的是key的hashcode()
        int hash = key.hashCode();
        // 通过(hash & 0x7FFFFFFF) % tab.length计算出当前key所对应的散列地址即下标
        int index = (hash & 0x7FFFFFFF) % tab.length;
        //根据下标取出链表，遍历链表找到匹配的值
        for (HashtableEntry<?,?> e = tab[index] ; e != null ; e = e.next) {
            //匹配的条件是hash相等，且节点key相等
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

通过源码，我们来总结下get的原理：
1、首先取key的hashcode()作为散列函数的值hash
2、通过对hash进行(hash & 0x7FFFFFFF) % tab.length求余操作，得到散列地址，即散列表的下标
3、根据求出的下标取出链表
4、遍历链表，判断链表中的节点是否匹配，匹配则返回节点的值

根据get源码我们回答下HashTable的hash函数实现是key.hashCode();
注意观察的同学会看到get操作中并没有对key进行空处理，那么如果key为null的话，会抛出NullPointerException异常

问题8：HashTable put的原理是什么？

先上源码：

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        // value为空时直接抛出NullPointerException
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        HashtableEntry<?,?> tab[] = table;
        // 取key的hashCode作为hash值
        int hash = key.hashCode();
        // 对hash进行(hash & 0x7FFFFFFF) % tab.length得到散列地址即下标
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        //根据下标取得对应的记录即链表
        HashtableEntry<K,V> entry = (HashtableEntry<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;
    }

private void addEntry(int hash, K key, V value, int index) {
        //修改次数加1
        modCount++;
        //散列表
        HashtableEntry<?,?> tab[] = table;

        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            //如果容量大于等于阈值，则进行扩容处理
            rehash();
            //因为扩容之后，散列表更改了，需要重新取散列表
            tab = table;
            //扩容之后，需要重新计算散列地址
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        
        // Creates the new entry.
        //新增节点，作为链表的表头
        @SuppressWarnings("unchecked")
        HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index];
        //将链表加入散列表中
        tab[index] = new HashtableEntry<>(hash, key, value, e);
        //大小加1
        count++;
    }

根据源码总结put原理如下：
1、先对要插入的值进行判空处理
2、先判断散列表中是否已经存在要插入的键值对：
2.1、对hash计算出散列地址即下标
2.2、根据下标取得链表
2.3、遍历链表，查找要插入的键值对
2.4、如果已经存在对应的节点，则直接更新值，并返回旧值
3、如果散列表中不存在要插入的键值对，则：
3.1、先判断是否需要进行扩容处理，如果需要则先进行扩容处理，再重新计算散列地址
3.2、接着创建新的节点作为链表的表头，再将链表加入散列表中
兄die，你细心观察了吗？key一样是不允许为null的哦，不然会抛出NullPointerException

问题9：HashTable 是否是线程安全？

如果你够细心，会发现上面的get、put源码中，方法都使用了synchronized修饰的，我们再来看下删除和清除操作：

public synchronized void putAll(Map<? extends K, ? extends V> t) {
}
public synchronized boolean remove(Object key, Object value) {
}
public synchronized void clear() {
}

public synchronized Object clone() {
}

其他读写操作的函数就不一一列举了，这些读写操作的函数都使用了同步内置锁synchronized修饰，也就是HashTable是线程安全类

问题10：HashTable与HashMap的区别是什么？

区别还是很大的，我们主要说它主主要的区别：
1、HashTable是线程安全类，而HashMap不是线程安全类，因为HashTable中的读写相关的操作均使用了同步内置锁进行修饰，而HashMap的读写操作并没有任何加锁、同步机制
2、HashTable是不允许key和value为null的，如果HashTable的key或value为null会抛出NullPointerException，而HashMap是允许key和value都为null的，所有相比而言HashMap更为健壮，不需要额外的处理null
3、HashTable默认的容量是11，而HashMap默认容量是16；HashTable阈值计算规则和HashMap的一样都是等于容量*加载因子；HashTable和HashMap的加载因子默认值都是0.75；HashTable最大容量是Integer.MAX_VALUE-8，而HashMap最大容量是Integer.MAX_VALUE
4、HashTable和HashMap都使用的是数组+单链表数据结构，不同的是HashTable使用的HashTableEntry作为节点，而HashMap使用Node作为节点
5、HashMap比HashTable性能更好，因为HashTable使用了同步内置锁，而HashMap没有；但是HashMap不是线程安全