Hashtable 原理相关

问：谈谈你对 Hashtable 原理的理解？

答：Hashtable 与 HashMap 类似，也是一个存储键值对的散列表，Hashtable 继承自 Dictionary 类，实现了 Map、Cloneable、Serializable 接口，Hashtable 是通过拉链法实现哈希表的，其构造方法主要有四个，如下：

        //默认构造方法，容量为 11，加载因子为 0.75 
    public Hashtable()
        //通过指定初始容量与默认加载因子 (0.75) 构造一个新的空哈希表
    public Hashtable( int initialCapacity )
        // 构造一个给定 Map 的新哈希表
    public Hashtable(Map < ? extends K , ? extends V > t )
        // 通过指定初始容量和指定加载因子构造一个新的空哈希表 
    public Hashtable( int initialCapacity, float loadFactor )

Hashtable 的并发安全 put 原理是先判断 value 是否为空，为空则抛出异常，然后计算 key 的 hash 值（key.hashCode()），如果 key 为空则抛出异常，否则根据 hash 值获得 key 在 table 数组中的位置 index，接着如果 table[index] 元素不为空，则进行迭代，如果遇到相同的 key，则直接替换，并返回旧 value，否则，我们可以将其插入到 table[index] 位置（发生哈希碰撞时变为链表头，否则该数组位置单个元素）；整体看来和 HashMap 十分相似，算是精简版的 HashMap put 原理，具体源码分析如下：

//put方法是通过synchronized保证单操作并发安全的
    public synchronized V put(K key, V value) {
        
// Hashtable的value不允许为空!!! 
        if (value == null) {
            throw new NullPointerException();
        }
        // Makes sure the key is not already in the hashtable.
        HashtableEntry tab[] = table;
        //hash方法的实质是key.hashCode()，所以Hashtable的key也不允许为空!!! 
        int hash = hash(key);
        // 依据key的hash值计算出index值来确定其在table[]中的位置 
        int index = (hash & 0x7FFFFFFF) % tab.length;
        // 迭代index索引位置的链表，如果该位置处的链表存在相同的key，
        // 则替换value，返回旧的value
        for (HashtableEntry<K, V> e = tab[index]; e != null; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }
        modCount++;
        if (count >= threshold) {
            //如果超过阀值，就进行rehash操作 
            rehash();
            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        //插入后返回的为null
        HashtableEntry<K, V> e = tab[index];
        //创建新的 Entry 节点，并将新的 Entry 插入 Hashtable 的 index 位置，
        // 并设置 e 为新的 Entry 的下一个元素 
        tab[index] = new HashtableEntry<>(hash, key, value, e);
        count++;
        return null;
    }

    private static int hash(Object k) {
        return k.hashCode();
    }

Hashtable 的并发安全 get 方法原理是先通过 hash()方法求得 key 的哈希值，然后根据 hash 值得到 index 索引，然后迭代链表，返回匹配的 key 对应的 value，如果找不到则返回 null，源码如下：

        public synchronized V get (Object key ){
            HashtableEntry tab[] = table;
            int hash = hash(key);
            int index = (hash & 0x7FFFFFFF) % tab.length;
            for (HashtableEntry<K, V> e = tab[index]; e != null; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    return e.value;
                }
            }
            return null;
        }

问：说说为什么 Hashtable 的 key、value 都不允许为 null，而类似实现的 HashMap 就可以？

答：因为 Hashtable 比 HashMap 先出来，且 Hashtable 继承自 Dictionary 类，Dictionary 抽象层的 put 方法定义是不允许 key、value 为空的，也就是说设计者当初就没考虑 null 情况，而后来 HashMap 却考量了这种情况；此外由于 Hashtable 在 put 实现时没有对 key 进行判断，获取 key 的哈希值是直接通过 key.hashCode() 方法获取的，所以 key 如果为空就崩溃了，而 value 是直接防御性实现的，而对于 HashMap 来说对于 key、value 为空都进行了单独处理。

最后编辑于：2018.05.25 15:17:45