一、介绍

在往期文章中，我们从源码分析了java集合框架中Map一族的HashMap，它为我们提供了保存键值对的一系列方法，底层是基于哈希表+链表+红黑树实现的，但是在多线程并发的环境下，表现出线程不安全的特性，今天我们介绍另一个同样是保存键值对但底层是基于哈希表+链表 且 线程安全的HashTable。

下面看一下HashTable的UML图

UML图.png

二、类的声明

我们来看一下HashMap的声明，可以大致了解他的功能。

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

继承了Dictionary类，提供了一些字典相关的基本功能如添加、删除、判空、获取元素数量等。
实现了Map接口，说明HashMap是一个以<K，V>键值对存储数据的结构
实现了Cloneable接口，提供了对象克隆方法，但请注意，是浅克隆。
实现了Serializable接口，支持序列化。

Dictionary类是我们在java集合框架学习过程中首次见到的类，我们看一下他是什么

从下面源码中可以看到，Dictionary是一个抽象类，该类中声明的方法全是抽象方法，没有默认实现，且这些抽象方法在Map接口中都有体现，因此我们可以忽略Dictionary类，将注意点都放在HashTable本身。

另外还需要注意到一个事实，在Dictionary的文档中我们看到，jdk已经建议我们忽略它，并且将用Map接口代替它。

/**
 * NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class.
 *
 **/
public abstract class Dictionary<K,V> {
   
   

    public Dictionary() {
   
   
    }

    abstract public int size();
    abstract public boolean isEmpty();
    abstract public Enumeration<K> keys();
    abstract public Enumeration<V> elements();
    abstract public V get(Object key);
    abstract public V put(K key, V value);
    abstract public V remove(Object key);
}

三、底层实现

HashTable的底层实现为哈希表+链表，相较于底层为哈希表+链表+红黑树实现的HashMap，少了红黑树的结构，因此并没有那么复杂，如下图所示

底层实现.png

四、内部类Entry

在HashTable中，将键值对封装成节点的类为其内部类Entry，该内部类继承于Map接口的内部接口Entry，从上面HashTable的UML图中也有所体现。我们看一下该内部类的源码：

private static class Entry<K,V> implements Map.Entry<K,V> {
   
   
    // 键值对节点中key的哈希值
    final int hash;
    // 键值对节点中的key
    final K key;
    // 键值对节点中的value
    V value;
    // 链表中当前节点的下一个节点
    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;
    }
}

从源码可以看出，HashTable中保存键值对的节点类Entry其实与HashMap中保存键值对的节点类Node是完全相同的。

五、成员变量

// 哈希表中的数组
private transient Entry<?,?>[] table;
// 哈希表中键值对节点数量
private transient int count;
// 扩容阈值
private int threshold;
// 加载因子，默认0.75
private float loadFactor;
// 结构性修改次数，用于快速失败
private transient int modCount = 0;

六、构造方法

HashMap提供了以下四个构造方法来创建实例

无参构造

通过默认初始容量11 和 默认加载因子为0.75 构造实例

public Hashtable() {
     
     
    this(11, 0.75f);
}

指定初始容量和加载因子

对指定的初始容量和加载因子进行校验后，设置初始容量大小的数组和加载因子，并计算出扩容阈值。

还记得在HashMap中，数组和扩容阈值都是在第一次扩容时初始化的。而在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;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

指定初始容量

指定初始容量，并使用默认的加载因子0.75。

public Hashtable(int initialCapacity) {
     
     
    this(initialCapacity, 0.75f);
}

通过传入一个Map对象实例化

通过这种方式构造HashTable实例时，会先创建实例，再调用putAll()方法将map中的数据批量保存到实例中。

注意：在构造HashTable实例时，初始容量为 map容量*2+1 和 默认初始容量11的较小值，
```
public Hashtable(Map<? extends K, ? extends V> t) {
     
     
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}
```

七、扩容方法rehash()

该方法的源码如下，相较于HashMap那么长的扩容resize()方法，是否简单了一点呢？在HashMap的扩容resize()方法中，还要一堆判断去确定数组容量、扩容阈值等信息，而且由于HashMap中数组长度为2的n次方，还需要判断哪些键值对在扩容前后的数组下标是否不变等等。

而在HashTable中，由于在扩容前哈希表就已经完成初始化了，且由于哈希表数组长度可能为任意值，也不存在扩容后键值对位于数组的下标不变的情况，因此，简单粗暴的，直接扩容，然后将原哈希表中的键值对重新计算数组下标，放在扩容后的哈希表中。

要注意一点：在HashMap中，原哈希表中链表上的元素采用尾插法放在新哈希表。而在HashTable中采用的是头插法。

protected void rehash() {
   
   
    // 扩容前的哈希数组容量
    int oldCapacity = table.length;
    // 扩容前的哈希数组
    Entry<?,?>[] oldMap = table;

    // 1.计算扩容后的容量，新容量= 原容量*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;

    // 2. 遍历原哈希表，将原哈希表中的键值对重新计算数组下标后，通过头插法，放至新的哈希表中。
    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;
        }
    }
}

八、addEntry()

该方法采用头插法的方式向哈希表中添加元素，在添加元素前，判断是否需要先调用rehash()方法进行扩容。

private void addEntry(int hash, K key, V value, int index) {
   
   
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
   
   
        // 扩容
        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++;
}

有一点需要注意，HashTable不像HashMap那样对hashcode()值的高16位和低16位按位与得到hash值，再对数组长度取余，从而得到数组下标，而是直接通过hashcode()值与 0x7FFFFFFF 按位与，在对数组长度取余，从而得到数组下标。

我们分析一下index = (hash & 0x7FFFFFFF) % tab.length

0x7FFFFFFF为16进制表示法，换成2进制为：0111 1111 1111 1111 1111 1111 1111 1111共32位，其中最高位为0，而我们知道，在二进制表示中，最高位为0表示正数，1表示负数，因此(hash & 0x7FFFFFFF)表示将key的hashcode()值的最高位设置为0，解决了key的hashcode()值为负数的情况，再对数组长度取余，便可得到数组下标。

九、常用方法

size()

获取哈希表中键值对节点的数量。该方法被synchronized修饰，表示线程安全
```
public synchronized int size() {
     
     
    return count;
}
```
isEmpty()

判断哈希表中是否不存在键值对，该方法被synchronized修饰，表示线程安全
```
public synchronized boolean isEmpty() {
     
     
    return count == 0;
}
```

contains() 与 containsValue()

判断哈希表中是否存在指定的value，遍历方式与HashMap相同，该方法被synchronized修饰，表示线程安全

从方法首行的判空语句可知，HashTable中不允许value值为空

public synchronized boolean contains(Object value) {
     
     
    if (value == null) {
     
     
        throw new NullPointerException();
    }

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

public boolean containsValue(Object value) {
     
     
    return contains(value);
}

containsKey()

判断哈希表中是否存在指定的key，遍历方式与HashMap相同，该方法被synchronized修饰，表示线程安全

从方法第二行int hash = key.hashCode();来看，HashTable中不允许key值为空，否则会抛出空指针异常。

逻辑与HashMap相同，都是先通过计算哈希值确认哈希表中数组的下标，再通过遍历链表的形式，查找是否存在键值对的key与指定的key相同。

public synchronized boolean containsKey(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 true;
        }
    }
    return false;
}

get()

根据指定的key，从哈希表中获取该key对应的value，遍历方式与HashMap相同，该方法被synchronized修饰，表示线程安全

public synchronized V get(Object key) {
     
     
    Entry<?,?> tab[] = table;
    // 计算哈希值确认哈希表中数组的下标
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 遍历链表，查找到相同的key的键值对，并返回该键值对的value
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
     
     
        if ((e.hash == hash) && e.key.equals(key)) {
     
     
            return (V)e.value;
        }
    }
    return null;
}

put()

将指定的键值对保存，该方法被synchronized修饰，表示线程安全

从方法首行的判空语句可知，HashTable中不允许value值为空。

public synchronized V put(K key, V value) {
     
     
    // Make sure the value is not null
    if (value == null) {
     
     
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    // 根据参数key计算出对应的数组下标
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    // 对该数组下标上的链表进行遍历，如果存在key相等的键值对，则对其对应的value值进行覆盖
    for(; entry != null ; entry = entry.next) {
     
     
        if ((entry.hash == hash) && entry.key.equals(key)) {
     
     
            V old = entry.value;
            // 覆盖value
            entry.value = value;
            return old;
        }
    }

    // 如果不存在key相等的键值对，则调用addEntry()方法通过头插法保存键值对
    addEntry(hash, key, value, index);
    return null;
}

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];
    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;
}

十、总结

底层结构为数组+单链表实现的哈希表
当出现哈希冲突或扩容，且当前位置为链表时，采用尾插法将节点插入到链表
插入的数据是无序的
线程安全
保存键值对节点的类为Entry，而HashMap中保存键值对节点的类为Node
哈希表数组默认初始容量为11，默认加载因子为0.75
哈希表数组的容量可任意指定，扩容后的容量 为 扩容前容量*2 + 1
哈希表和扩容阈值在构造方法中完成初始化，是即时加载而不是延时初始化
key和value都不允许为空，在HashMap中为key和value都允许为空。
HashTable的扩容方法为rehash()，HashMap的扩容方法为resize()
先扩容，后插入。在HashMap中为先插入后扩容。

纸上得来终觉浅，绝知此事要躬行。

————————————————我是万万岁，我们下期再见————————————————

HashTable源码详解

一、介绍

二、类的声明

三、底层实现

四、内部类Entry

五、成员变量

六、构造方法

七、扩容方法rehash()

八、addEntry()

九、常用方法

十、总结

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

HashTable源码详解

一、介绍

二、类的声明

三、底层实现

四、内部类Entry

五、成员变量

六、构造方法

七、扩容方法rehash()

八、addEntry()

九、常用方法

十、总结

热门文章

最新文章

相关电子书