前面介绍了HashMap，ConcurrentHashMap，我们再来介绍Hashtable的实现原理，也可以先看笔者写的如下文章学习学习。

1、Java集合-类的继承组合关系
2、Java集合-HashMap源码实现深入解析
3、Java集合-LinkedHashMap工作原理
4、Java集合-ConcurrentHashMap工作原理和实现JDK7
5、Java集合-ConcurrentHashMap工作原理和实现JDK8
6、ConcurrentHashMap与红黑树实现分析Java8

Hashtable与HashMap的区别

Hashtable与HashMap都是用来存储key-value类型数据的，两者有如下区别：

1、Hashtable不允许null key和null value，HashMap允许。
2、Hashtable是线程安全的，HashMap不是线程安全的。
3、HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
4、Hashtable继承自Dictionary，HashMap继承自AbstractMap。
5、两者都实现了Map接口。

Hashtable的继承关系

从继承图来看，Hashtable继承自Dictionary，这点与HashMap不同。同时从所拥有的属性也能看出Hashtable的数据结构。

Hashtable的继承关系UML类图

public class Hashtable<K,V> extends Dictionary<K,V> implements 
                    Map<K,V>, Cloneable, java.io.Serializable {
    // 省略
}

Hashtable的数据结构

在Java6中HashMap中采用table数组+链表的方式来实现（Java8中采用数组+链表+红黑树）。Hashtable的数据结构也采用这种结构。

我们先看一段Java代码：

Hashtable<String, String> hashtable = new Hashtable<String, String>();
hashtable.put("语文", "1");
hashtable.put("数学", "2");
hashtable.put("英语", "3");
hashtable.put("物理", "4");
hashtable.put("化学", "5");
hashtable.put("生物", "6");
hashtable.put("政治", "7");
hashtable.put("地理", "8");
hashtable.put("历史", "9");

for (Map.Entry<String, String> entry : hashtable.entrySet()) {
    System.out.println(entry.getKey() + " --> " + entry.getValue());
}

想想输出结果会是什么?输出结果如下：

英语 --> 3
地理 --> 8
物理 --> 4
数学 --> 2
历史 --> 9
化学 --> 5
语文 --> 1
政治 --> 7
生物 --> 6

从输出结果来看，Hashtable put的顺序与读取的顺序和HashMap一样不保证一致。

Hashtable的数据结构如下图所示，和HashMap一样，采用Entry数组+链表的方式实现。

Hashtable数据结构图

根据数据结构图看下源码中支持此数据结构的重要属性：

public class Hashtable<K,V> extends Dictionary<K,V> implements 
                    Map<K,V>, Cloneable, java.io.Serializable {
    
    // 存储元素的table，Entry节点采用内部类实现
    private transient Entry[] table;

    // 已存放元素的计数器
    private transient int count;
    
    // 扩容阈值=table长度 * loadFactor
    // table表的元素（不包含链表中的元素）超过这个阈值将扩容
    private int threshold;
    
    // 负载因子
    private float loadFactor;
    
    // 其他省略
}

其中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的数据结构从源码就能看出来是数组+链表的方式实现了。

Hashtable的初始化

来看下Hashtable的默认构造方法是怎么初始化Hashtable的。

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

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)(initialCapacity * loadFactor);
}

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

Hashtable的put方法的实现

源码实现步骤和HashMap没有任何区别，知识put方法上增加了synchronized关键字，保证线程安全。

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;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<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 the table if the threshold is exceeded
        rehash();

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

    // Creates the new entry.
    Entry<K,V> e = tab[index];
    tab[index] = new Entry<K,V>(hash, key, value, e);
    count++;
    return null;
}

实现步骤和思路：

1、禁止null value插入。
2、根据key的hashCode值 与 0x7FFFFFFF求与后得到新的hash值，然后计算其在table中的索引下标。
3、在索引下标下遍历链表，查找key是否已存在，存在则更新value值。
4、如果不存在，判断table.count是否超过阈值，超过则重新rehash，将原元素全部拷贝到新的table中，并重新计算索引下标。rehash后，容量是以前的2倍+1的大小，这点也和HashMap不同，HashMap是2倍。
5、插入元素时直接插入在链表头部。
6、更新元素计数器。

至于rehash方法的实现还请读者自行阅读源码，比较简单。get等其他方法也不做过多介绍，都比较简单。

Hashtable如何保证线程安全

前面提到的put方法中是通过synchronized来保证线程安全的。查看源码，发现对外提供的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开发团队为了替换他而开发的，性能提高了不少。笔者也建议大家在多线程环境下抛弃Hashtable，改用ConcurrentHashMap，或者用HashMap配合外部锁，例如ReentrantLock来提高效率。

大概是Java团队已经开发出替代者ConcurrentHashMap，所以Hashtable从源码的实现来看，和JDK5相比，没有什么提升，大概是Java团队放弃了这个类的维护了。