Java集合框架（二十一）：HashTable 源码分析

秒速五厘米 2021-10-19 06:56 371阅读 0赞

### 文章目录 ###

*   *  1、HashTable 简介
     *   *  1.1、HashTable 定义
         *  1.2、HashTable 属性
         *  1.3、HashTable 构造方法
         *   *  1.3.1、Hashtable()
             *  1.3.2、Hashtable(int initialCapacity)
             *  1.3.3、Hashtable(int initialCapacity, float loadFactor)
             *  1.3.4、Hashtable(Map<? extends K,? extends V> t)
     *  2、HashTable 源码分析
     *   *  2.1、put 方法
         *  2.2、get 方法
         *  2.3、remove 方法
         *  2.4、rehash 方法
     *  3、Hashtable 如何保证线程安全
     *  4、Hashtable 与 HashMap 的区别

## 1、HashTable 简介 ##

和 HashMap 一样，Hashtable 也是一个散列表。从Java 1.2开始，这个类被改进以实现Map接口，使其成为Java Collections Framework的成员。 与新的集合实现不同，Hashtable是同步的。 如果不需要线程安全实现，建议使用HashMap代替Hashtable。 如果需要线程安全的高度并发实现，那么建议使用ConcurrentHashMap代替Hashtable。

该类实现了一个哈希表，它将键映射到值。 任何非null对象都可以用作键或值。要成功存储和检索哈希表中的对象，用作键的对象必须实现hashCode方法和equals方法。

通常，默认负载系数（.75）在时间和空间成本之间提供了良好的折衷。 较高的值会减少空间开销，但会增加查找条目的时间成本（这反映在大多数Hashtable操作中，包括get和put）。

初始容量控制了浪费空间和重新运算操作的需要之间的权衡，这是非常耗时的。 如果初始容量大于Hashtable将包含的最大条目数除以其加载因子，则不会发生重复操作。 但是，将初始容量设置得太高会浪费空间。

如果要将多个元素设置为Hashtable，则创建具有足够容量的初始大小可以更有效地插入元素，而不是根据需要执行自动扩容来扩展表。

### 1.1、HashTable 定义 ###

![在这里插入图片描述][20190818162435118.png]

public class Hashtable<K,V>
        extends Dictionary<K,V>
        implements Map<K,V>, Cloneable, java.io.Serializable

从源码中，我们可以看出，Hashtable 继承于 Dictionary 类，实现了 Map, Cloneable, java.io.Serializable接口。

其中Dictionary类是任何可将键映射到相应值的类（如 Hashtable）的抽象父类，每个键和值都是对象。

> Dictionary 源码注释中有这样一句话，NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class.（ Dictionary 这个类过时了，新的实现类应该实现Map接口。）

### 1.2、HashTable 属性 ###

Hashtable 是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, count, threshold, loadFactor, modCount。

*  table：是一个 Entry\[\] 数组类型，而 Entry（在 HashMap 中有讲解过）实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。
 *  count：是 Hashtable 的大小，它是 Hashtable 保存的键值对的数量。
 *  threshold：是 Hashtable 的阈值，用于判断是否需要调整 Hashtable 的容量。threshold 的值=“容量\*加载因子”。
 *  loadFactor：是加载因子。
 *  modCount：是用来实现 fail-fast 机制的。

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中键值对的数量，这个大小并不是HashTable的容器大小，而是他所包含Entry键值对的数量。
         */
        private transient int count;
    
        /**
         *  阈值，用于判断是否需要调整Hashtable的容量（threshold = 容量*加载因子）
         *
         * @serial
         */
        private int threshold;
    
        /**
         * 加载因子
         *
         * @serial
         */
        private float loadFactor;
    
        /**
         * Hashtable被改变的次数，用于fail-fast机制的实现。
         * 所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知* 到，并且立即抛出ConcurrentModificationException异常，而不是等到迭代完成之后才告诉你
         */
        private transient int modCount = 0;
            
        }

其中table中存储的是Entry节点，Entry节点直接采用内部类的方式实现，实现了Map.Entry类，其数据结构源码如下：

private static class Entry<K,V> implements Map.Entry<K,V> {
        int hash;
        K key;
        V value;
        Entry<K,V> next;// 下一个节点，构成链表
    }

Entry 节点中存储了元素的hash值，key, value，next引用。至此Hashtable的数据结构从源码就能看出来是数组+链表的方式实现的。

### 1.3、HashTable 构造方法 ###

#### 1.3.1、Hashtable() ####

在默认构造方法中，调用了Hashtable(int initialCapacity, float loadFactor)方法，初始Hashtable的容量为11，负载因子为0.75，那么初始阈值就是8。这点和HashMap很不同，HashMap在初始化时，table的大小总是2的幂次方，即使给定一个不是2的幂次方容量的值，也会自动初始化为最接近其2的幂次方的容量。

/**
         * 使用默认初始容量（11）和加载因子（0.75）构造一个新的空哈希表。
         */
        public Hashtable() {
            this(11, 0.75f);
        }

#### 1.3.2、Hashtable(int initialCapacity) ####

使用指定的初始容量和默认加载因子（0.75）构造一个新的空哈希表。

/**
         * 使用指定的初始容量和默认加载因子（0.75）构造一个新的空哈希表。
         *
         * @param     initialCapacity   初始容量
         * @exception IllegalArgumentException if the initial capacity is less
         *              than zero.
         */
        public Hashtable(int initialCapacity) {
            this(initialCapacity, 0.75f);
        }

#### 1.3.3、Hashtable(int initialCapacity, float loadFactor) ####

使用指定的初始容量和指定的加载因子构造一个新的空哈希表。

/**
         * 使用指定的初始容量和指定的加载因子构造一个新的空哈希表。
         *
         * @param      initialCapacity   初始容量
         * @param      loadFactor        加载因子
         * @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 = new Entry<?,?>[initialCapacity];
            threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        }

#### 1.3.4、Hashtable(Map<? extends K,? extends V> t) ####

构造一个新的哈希表，其具有与给定Map相同的映射。 创建哈希表的初始容量足以容纳给定Map中的映射和默认加载因子（0.75）。

/**
         * 构造一个新的哈希表，其具有与给定Map相同的映射。 创建哈希表的初始容量足以容纳给定Map中的映射和默认加载因子（0.75）。
         *
         * @param t 指定的map
         * @throws NullPointerException 如果给定的 map 是 null.
         * @since   1.2
         */
        public Hashtable(Map<? extends K, ? extends V> t) {
            this(Math.max(2*t.size(), 11), 0.75f);
            putAll(t);
        }

## 2、HashTable 源码分析 ##

### 2.1、put 方法 ###

put方法是同步的，即线程安全的，这点和HashMap不一样，还有具体的put操作和HashMap也存在很大的差别，Hashtable插入的时候是插入到链表头部，而HashMap是插入到链表尾部

put 方法的整体逻辑如下：

1.  判断 value 是否为空，为空则抛出异常；
2.  计算 key 的 hash 值，并根据 hash 值获得 key 在 table 数组中的位置 index，如果 table\[index\] 元素不为空，则进行迭代，如果遇到相同的 key，则直接替换，并返回旧 value；
3.  否则，我们可以将其插入到 table\[index\] 位置。

public synchronized V put(K key, V value) {
            // Hashtable 中不能插入value为null的元素
            if (value == null) {
                throw new NullPointerException();
            }
    
            // 若“Hashtable中已存在键为key的键值对”，则用“新的value”替换“旧的value”
            Entry<?,?> tab[] = table;
            //直接取key的hashCode()作为哈希地址，这与HashMap的取hashCode()之后再进行hash()的结果作为哈希地址 不一样
            int hash = key.hashCode();
            //数组下标=(哈希地址 & 0x7FFFFFFF) % Hashtable容量，这与HashMap的数组下标=哈希地址 & (HashMap容量-1)计算数组下标方式不一样，前者是取模运算，后者是位于运算，这也是为什么HashMap的容量要是2的幂次方的原因，效率上后者的效率更高。
            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;
                }
            }
            //如果为新的节点，则调用addEntry()方法添加新的节点
            addEntry(hash, key, value, index);
            //插入成功返回null
            return null;
        }
        
         /**
         * 根据参数向table中添加entry
         */
        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链表的引用 复赋值给e
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            //创建新的Entry链表，将新的节点插入到Entry链表的头部，再指向之前的Entry，即在链表头部插入节点
            tab[index] = new Entry<>(hash, key, value, e);
            //table大小+1
            count++;
        }

通过源码，我们可以看出 HashMap 与 Hashtable 计算索引的方式是不一样的：

*  HashMap 计算索引的方式是h&(length-1),而Hashtable用的是模运算，效率上是低于HashMap的
 *  Hashtable计算索引时将hash值先与上0x7FFFFFFF,这是为了保证hash值始终为正数
 *  特别需要注意的是这个方法加了synchronized关键字，也就意味着这个Hashtable是个线程安全的类，这也是它和HashMap最大的不同点

### 2.2、get 方法 ###

get方法也是同步的，和HashMap不一样,即线程安全，具体的get操作和HashMap也有区别。

public synchronized V get(Object key) {
            Entry<?,?> tab[] = table;
            // 直接获取key的hashCode()作为哈希地址
            int hash = key.hashCode();
            // 通过(哈希地址 & 0x7FFFFFFF)与Hashtable容量做%运算 计算出下标
            int index = (hash & 0x7FFFFFFF) % tab.length;
            //遍历Entry链表，如果链表中存在key、哈希地址一样的节点，则找到 返回该节点的值，否者返回null
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    return (V)e.value;
                }
            }
            return null;
        }

### 2.3、remove 方法 ###

public synchronized V remove(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>)tab[index];
            // 遍历Entry链表，e为当前节点，prev为上一个节点
            for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
               // 找到key及哈希地址相等的节点
                if ((e.hash == hash) && e.key.equals(key)) {
                    modCount++;
                    // 如果上一个节点不为空，将上一个节点的next指向当前节点的next，即将当前节点移除链表
                    if (prev != null) {
                        prev.next = e.next;
                    } else {
                    // 如果上一个节点为空，即当前节点为头结点，将table数组保存的链表头结点地址改成当前节点的下一个节点
                        tab[index] = e.next;
                    }
                    // 键值对数量-1
                    count--;
                    // 获取被删除节点的值，并返回
                    V oldValue = e.value;
                    e.value = null;
                    return oldValue;
                }
            }
            return null;
        }

### 2.4、rehash 方法 ###

Hashtable 的rehash方法是用来扩容哈希表的。Hashtable每次扩容,容量都为原来的2倍加1,而HashMap为原来的2倍。

protected void rehash() {
            // 获取旧的Hashtable的容量
            int oldCapacity = table.length;
            // 获取旧的Hashtable引用
            Entry<?,?>[] oldMap = table;
    
            // 新的Hashtable容量=旧的Hashtable容量 * 2 + 1，HashMap是新的Hashtable容量=旧的Hashtable容量 * 2。
            int newCapacity = (oldCapacity << 1) + 1;
            // 如果新的Hashtable容量大于允许的最大容量值(Integer的最大值 - 8)
            if (newCapacity - MAX_ARRAY_SIZE > 0) {
                // 如果旧的容量等于允许的最大容量值则返回
                if (oldCapacity == MAX_ARRAY_SIZE)
                    // Keep running with MAX_ARRAY_SIZE buckets
                    return;
                // 新的容量等于允许的最大容量值
                newCapacity = MAX_ARRAY_SIZE;
            }
            // 使用新的容量构建一个新的Hashtable 
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
            modCount++;
            // 计算新的阈值
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            table = newMap;
            // 扩容后迁移Hashtable的Entry链表
            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;
                }
            }
        }

## 3、Hashtable 如何保证线程安全 ##

通过Hashtable源码，我们发现对外提供的public方法，几乎全部加上了synchronized关键字。

public synchronized int size(){}
    public synchronized boolean isEmpty() {}
    public synchronized Enumeration<K> keys() {}
    public synchronized Enumeration<V> elements() {}
    public synchronized boolean contains(Object value) {}
    public synchronized boolean containsKey(Object key) {}
    public synchronized V get(Object key) {}
    public synchronized V put(K key, V value) {}
    public synchronized V remove(Object key) {}
    public synchronized void putAll(Map<? extends K, ? extends V> t) {}
    public synchronized void clear() {}
    public synchronized Object clone() {}
    public synchronized String toString() {}
    public synchronized boolean equals(Object o) {}
    public synchronized int hashCode() {}

所以从这个特性上看，Hashtable是通过简单粗暴的方式来保证线程安全的额。所以Hashtable的性能在多线程环境下会非常低效。前面介绍的ConcurrentHashMap其实就是Java开发团队为了替换他而开发的，性能提高了不少。

所以建议大家在多线程环境下使用 ConcurrentHashMap，或者用HashMap配合外部锁，例如ReentrantLock来提高效率。

## 4、Hashtable 与 HashMap 的区别 ##

**不同点：**

1.  HashMap 继承于 AbstractMap抽象类，Hashtable 继承于Dictionay抽象类
2.  HashMap 是非线程安全的，Hashtable是线程安全的，所以Hashtable效率比较低
3.  HashMap 通过key的hashCode()进行hash()得到哈希地址，数组下标=哈希地址 & (容量 - 1)，采用的是与运算，所以容量需要是2的幂次方结果才和取模运算结果一样。而Hashtable则是：数组下标=(key的hashCode() & 0x7FFFFFFF ) % 容量，采用的取模运算，所以容量没要求
4.  HashMap 允许键值为null，而Hashtable不允许键值为null
5.  HashMap 的容量扩容按照原来的容量*2，而Hashtable的容量扩容按照原来的容量*2+1
6.  HashMap 的容量默认值为16，而Hashtable的默认值是11
7.  HashMap 是将节点插入到链表的尾部，而Hashtable是将节点插入到链表的头部
8.  HashMap 采用了数组+链表+红黑树，而Hashtable采用数组+链表

**相同点：**

*  HashMap 和 Hashtable 都实现了Map接口
 *  HashMap 和 Hashtable 的负载因子默认都是0.75
 *  都是采用链地址法即拉链法处理哈希冲突
 *  相同哈希地址可能分配到不同的链表，同一个链表内节点的哈希地址不一定相同：因为HashMap和Hashtable都会扩容，扩容后相同的哈希地址取到的数组下标也就不一样。

[20190818162435118.png]: /images/20211018/94fecbb8a6f74572823b91d80cf211bc.png