Hashtable

Hashtable 是个过时的集合类，不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换。但这并不是我们不去了解它的理由。最起码 Hashtable 和 HashMap 的面试题在面试中经常被问到。

一、前言

Hashtable和HashMap，从存储结构和实现来讲基本上都是相同的。

它和HashMap的最大的不同是它是线程安全的，另外它不允许key和value为null。

为了能在哈希表中成功地保存和取出对象，用作key的对象必须实现hashCode方法和equals方法。

二、fail-fast机制

iterator方法返回的迭代器是fail-fast的。如果在迭代器被创建后hashtable被结构型地修改了，除了迭代器自己的remove方法，迭代器会抛出一个ConcurrentModificationException异常。

因此，面对在并发的修改，迭代器干脆利落的失败，而不是冒险的继续。

关于这个的理解，其实在上一章讲LinkedHashMap中的第八点提到：

值得注意的是，afterNodeAccess() 函数中，会修改modCount,因此当你正在accessOrder=true的模式下,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。

简单说，就是两个线程同时分别进行修改和遍历时，会抛出这个异常。

面试题：集合在遍历过程中是否可以删除元素，为什么迭代器就可以安全删除元素？

集合在使用 for 循环迭代的过程中不允许使用，集合本身的 remove 方法删除元素，如果进行错误操作将会导致 ConcurrentModificationException 异常的发生

Iterator 可以删除访问的当前元素(current)，一旦删除的元素是Iterator 对象中 next 所正在引用的，在 Iterator 删除元素通过 修改 modCount 与 expectedModCount 的值，可以使下次在调用 remove 的方法时候两者仍然相同因此不会有异常产生。

迭代器的fail-fast机制并不能得到保证，它不能够保证一定出现该错误。一般来说，fail-fast会尽最大努力抛出ConcurrentModificationException异常。因此，为提高此类操作的正确性而编写一个依赖于此异常的程序是错误的做法，正确做法是：ConcurrentModificationException 应该仅用于检测 bug。

Hashtable是线程安全的。如果不需要线程安全的实现是不需要的，推荐使用HashMap代替Hashtable。如果需要线程安全的实现，推荐使用java.util.concurrent.ConcurrentHashMap代替Hashtable。

二、继承关系

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

• extends Dictionary<K,V>：Dictionary类是一个抽象类，用来存储键/值对，作用和Map类相似。
• implements Map<K,V>：实现了Map，实现了Map中声明的操作和default方法。

hashMap以及TreeMap的源码，都没有继承于这个类。不过当我看到注释中的解释也就明白了，其 Dictionary 源码注释是这样的：NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class. 该话指出 Dictionary 这个类过时了，新的实现类应该实现Map接口。

三、属性

//哈希表
private transient Entry<?,?>[] table;

//记录哈希表中键值对的个数
private transient int count;

//扩容的阈值
private int threshold;

//负载因子
private float loadFactor;

//hashtable被结构型修改的次数。
private transient int modCount = 0;

HashTable并没有像HashMap那样定义了很多的常量，而是直接写死在了方法里。

Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。

四、构造函数

/**
 * 使用默认初始化容量（11）和默认负载因子（0.75）来构造一个空的hashtable.
 * 
 * 这里可以看到，Hashtable默认初始化容量为16，而HashMap的默认初始化容量为11。
 */
public Hashtable() {
    this(11, 0.75f);
}

我们可以获取到这些信息：HashTable默认的初始化容量为11（与HashMap不同），负载因子默认为0.75（与HashMap相同）。而正因为默认初始化容量的不同，同时也没有对容量做调整的策略，所以可以先推断出，HashTable使用的哈希函数跟HashMap是不一样的（事实也确实如此）。

五、重要方法

5.1 get方法

public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //通过哈希函数，计算出key对应的桶的位置
    int index = (hash & 0x7FFFFFFF) % tab.length;
    //遍历该桶的所有元素，寻找该key
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

这里可以看到，Hashtable和HashMap确认key在数组中的索引的方法不同。

• Hashtable通过index = (hash & 0x7FFFFFFF) % tab.length;来确认
• HashMap通过i = (n - 1) & hash;来确认

跟HashMap相比，HashTable的get方法非常简单。我们首先可以看见get方法使用了synchronized来修饰，所以它能保证线程安全。并且它是通过链表的方式来处理冲突的。另外，我们还可以看见HashTable并没有像HashMap那样封装一个哈希函数，而是直接把哈希函数写在了方法中。而哈希函数也是比较简单的，它仅对哈希表的长度进行了取模。

5.2 put方法

public synchronized V put(K key, V value) {
    // 确认value不为null
    if (value == null) {
        throw new NullPointerException();
    }

    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //找到key在table中的索引
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    //获取key所在索引的entry
    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;
        }
    }
    //如果key在hashtable不是已经存在，就直接将键值对添加到table中，返回null
    addEntry(hash, key, value, index);
    return null;
}


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

    Entry<?,?> 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")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    //把新节点插入桶中（头插法）
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

从代码中可以总结出Hashtable的put方法的总体思路：

• 确认value不为null。如果为null，则抛出异常
• 找到key在table中的索引，获取key所在位置的entry
• 遍历entry，判断key是否已经存在
• 如果key已经存在，替换value，返回旧的value
• 如果key在hashtable不是已经存在，就直接添加，否则直接将键值对添加到table中，返回null

在方法中可以看到，在遍历桶中元素时，是按照链表的方式遍历的。可以印证，HashMap的桶中可能为链表或者树。但Hashtable的桶中只可能是链表。

5.3 remove方法

public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    //计算key在hashtable中的索引
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    //遍历entry，如果entry中存在key为参数key的键值对，就删除键值对，并返回键值对的value
    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;
        }
    }
    //如果不存在key为参数key的键值对，返回value
    return null;
}

从代码中可以总结出Hashtable的remove方法的总体思路：

• 找到key在table中的索引，获取key所在位置的entry
• 遍历entry，判断key是否已经存在
• 如果key存在，删除key映射的键值对，返回旧的value
• 如果key在hashtable不存在，返回null

5.4 rehash方法

/**
 * 增加hashtable的容量，为了更有效地存放和找到它的entry。
 * 当键值对的数量超过了临界值（capacity*load factor）这个方法自动调用
 * 长度变为原来的2倍+1
 * 
 */
@SuppressWarnings("unchecked")
protected void rehash() {
    //记录旧容量
    int oldCapacity = table.length;
    //记录旧桶的数组
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    //新的容量为旧的容量的2倍+1
    int newCapacity = (oldCapacity << 1) + 1;
    //如果新的容量大于容量的最大值MAX_ARRAY_SIZE 
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        //如果旧容量为MAX_ARRAY_SIZE，容量不变，中断方法的执行
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        //如果旧容量不为MAX_ARRAY_SIZE，新容量变为MAX_ARRAY_SIZE
        newCapacity = MAX_ARRAY_SIZE;
    }
    //创建新的数组，容量为新容量
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    //结构性修改次数+1
    modCount++;
    //计算扩容的临界值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    //将旧的数组中的键值对转移到新数组中
    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;
        }
    }
}

看完代码，我们可以总结出rehash的总体思路为：

• 新建变量新的容量，值为旧的容量的2倍+1
• 如果新的容量大于容量的最大值MAX_ARRAY_SIZE
  • 如果旧容量为MAX_ARRAY_SIZE，容量不变，中断方法的执行
  • 如果旧容量不为MAX_ARRAY_SIZE，新容量变为MAX_ARRAY_SIZE
• 创建新的数组，容量为新容量
• 将旧的数组中的键值对转移到新数组中

这里可以看到，一般情况下，HashMap扩容后容量变为原来的两倍，而Hashtable扩容后容量变为原来的两倍加一。

HashTable的rehash方法相当于HashMap的resize方法。跟HashMap那种巧妙的rehash方式相比，HashTable的rehash过程需要对每个键值对都重新计算哈希值，而比起异或和与操作，取模是一个非常耗时的操作，所以这也是导致效率较低的原因之一。

六、遍历

可以使用与HashMap一样的遍历方式，但是由于历史原因，多了Enumeration的方式。

针对Enumeration，这里与iterator进行对比一下。

相同点

• Iterator和Enumeration都可以对某些容器进行遍历。
• Iterator和Enumeration都是接口。

不同点

• Iterator有对容器进行修改的方法。而Enumeration只能遍历。
• Iterator支持fail-fast，而Enumeration不支持。
• Iterator比Enumeration覆盖范围广，基本所有容器中都有Iterator迭代器，而只有Vector、Hashtable有Enumeration。
• Enumeration在JDK 1.0就已经存在了，而Iterator是JDK2.0新加的接口。

七、Hashtable与HashMap对比

HashTable的应用非常广泛，HashMap是新框架中用来代替HashTable的类，也就是说建议使用HashMap。

下面着重比较一下二者的区别：

1.继承不同

Hashtable是基于陈旧的Dictionary类的，HashMap是java1.2引进的Map接口的一个实现。

2.同步

Hashtable 中的方法是同步的，保证了Hashtable中的对象是线程安全的。

HashMap中的方法在缺省情况下是非同步的,HashMap中的对象并不是线程安全的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。

3.效率

单线程中, HashMap的效率大于Hashtable。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合，HashMap是Hashtable的轻量级实现，这样可以避免由于同步带来的不必要的性能开销，从而提高效率。

4.null值

Hashtable中，key和value都不允许出现null值，否则出现NullPointerException。

在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。

5.遍历方式

Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable可以使用Enumeration的方式。

6.容量

Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。

HashTable中hash数组默认大小是11，增加的方式是 old*2+1。

HashMap中hash数组的默认大小是16，而且一定是2的指数。

八、总结

无论什么时候有多个线程访问相同实例的可能时，就应该使用Hashtable，反之使用HashMap。非线程安全的数据结构能带来更好的性能。

如果在将来有一种可能—你需要按顺序获得键值对的方案时，HashMap是一个很好的选择，因为有HashMap的一个子类 LinkedHashMap。

所以如果你想可预测的按顺序迭代（默认按插入的顺序），你可以很方便用LinkedHashMap替换HashMap。反观要是使用的Hashtable就没那么简单了。

如果有多个线程访问HashMap，Collections.synchronizedMap（）可以代替，总的来说HashMap更灵活，或者直接用并发容器ConcurrentHashMap。

整理自：

• http://blog.csdn.net/panweiwei1994/article/details/77428710
• http://blog.csdn.net/u013124587/article/details/52655042