概念
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
- 注：本文中使用的 JDK 版本为 1.8.0_121。
定义
Java 中 Hashtable 的定义如下：
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, Serializable
从代码中可以看出 HashTable 继承了 Dictionary 类，实现了 Map<K,V>、Cloneable、Serializable 三个接口。
Dictionary 类是任何可将键映射到相应值的类（如 HashTable）的抽象父类。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中，每个键至多与一个值相关联。
Map 将键映射到值的对象。Map 中不能包含重复的键；每个键最多可以映射一个值。
从 Hashtable 内部 Entry 的定义可以看出 Entry 实现了 Map 接口的 Entry，所以 HashTable 底层的数据结构是基于数组和单向链表。
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
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 使用了拉链法解决哈希冲突，拉链法是解决哈希冲突的一种行之有效的方法，某些哈希地址可以被多个关键字值共享，这样可以针对每个哈希地址建立一个单链表。
在拉链（单链表）的哈希表中搜索一个记录是容易的，首先计算哈希地址，然后搜索该地址的单链表。
在插入时应保证表中不含有与该关键字值相同的记录，然后按在有序表中插入一个记录的方法进行。针对关键字值相同的情况，现行的处理方法是更新该关键字值中的内容。
删除记录时，应先在该关键字值的哈希地址处的单链表中找到该记录，然后删除之。
初始参数
Hashtable 内部声明了几个重要的参数：
// 定义存放键值对的 Entry[] 数组，每一个 Entry 代表了一个键值对。
private transient Entry<?,?>[] table;
// Hashtable 的大小，注意这个大小并不是 HashTable 的容器大小，而是他所包含 Entry 键值对的数量。
private transient int count;
// 阈值，用于判断是否需要调整 HashTable 的容量。threshold 的值= 容量 * 加载因子。
private int threshold;
// 加载因子。
private float loadFactor;
// 指的是 HashTable 被修改或者删除的次数总数。用来实现“fail-fast”机制的（也就是快速失败）。所谓快速失败就是在并发集合中，其进行迭代操作时，若有其他线程对其进行结构性的修改，这时迭代器会立马感知到，并且立即抛出 ConcurrentModificationException 异常，而不是等到迭代完成之后才告诉你（你已经出错了）。
private transient int modCount = 0;
// 为了序列化时保持版本的兼容性。
private static final long serialVersionUID = 1421746759512286392L;
构造函数
Hashtable 中提供了四个构造函数（旧版本的 JDK 中有五个构造函数）：
// 使用默认初始容量（11）和加载因子（0.75）构造一个新的空 Hashtable。
Hashtable()
// 使用指定的初始容量和默认加载因子（0.75）构造一个新的空 Hashtable。
Hashtable(int initialCapacity)
// 使用指定的初始容量和指定的加载因子构造一个新的空 Hashtable。
Hashtable(int initialCapacity, float loadFactor)
// 使用指定的 Map 构造一个新的 Hashtable。
Hashtable(Map<? extends K,? extends V> t)
Hashtable 和 HashMap 的初始容量有所不同，HashMap 是 16，而 Hashtable 使用的是 11，扩容逻辑是乘 2+1，保证是素数。关于这个问题我去查了些资料，我理解的是 HashMap 对性能更高一些（参考：HashMap requires a better hashCode），所以在 JDK 1.4 以后做出了改进。知乎中也有大神对这个问题进行了解释【为什么 HashTable 的默认大小和 HashMap 不一样？】。
其中 Hashtable() 和 Hashtable(int initialCapacity) 两个构造函数都重载了 Hashtable(int initialCapacity, float loadFactor) 。
public Hashtable(int initialCapacity, float loadFactor) {
// 如果初始容量小于 0 则抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
// 如果加载因子小于 0 或非浮点类型则抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
// 如果初始容量等于 0 则把初始容量设置为 1
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
// 使用初始容量初始化 table 大小
table = new Entry<?,?>[initialCapacity];
// 初始化阈值大小，这里最大值是 Integer.MAX_VALUE + 8 - 1，默认是 8
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
最后一个构造函数 Hashtable(Map<? extends K,? extends V> t) 是使用指定的 Map 构造一个具有相同映射关系的新 Hashtable，然后调用了 putAll() 方法将 Map 中的数据逐一放入 table 中。
public Hashtable(Map<? extends K, ? extends V> t) {
// 调用 Hashtable(int initialCapacity, float loadFactor) 初始化，默认容器大小是指定 Map 容量大小 * 2
this(Math.max(2*t.size(), 11), 0.75f);
// 调用内部 putAll() 方法将 Map 中的数据放入 table
putAll(t);
}
主要方法
Hashtable 中比较常用的方法就是 put、get 和 remove，下面分别来看一下每个方法的内部实现。
put 方法
public synchronized V put(K key, V value) {
// 确保 value 不为 null，若为空则抛出异常
if (value == null) {
throw new NullPointerException();
}
// 确保 key 不在哈希表中
Entry<?,?> tab[] = table;
// 计算 key 的 hashCode
int hash = key.hashCode();
// 计算索引
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 遍历 e 和 e 的下一个节点，寻找该 key
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
在 Java Docs 中描述如下：
This class implements a hash table, which maps keys to values. Any non-null object can be used as a key or as a value.
大概意思是：这个类实现了一个哈希表，它将键映射到值。任何非 null 对象都可以用作键或值。
注意后面的说明了必须是非空的对象。
如果向 Hashtable 中添加了一个空的 key。程序会抛出如下异常：
java.lang.NullPointerException
这个异常是 Hashtable 在计算 key 的 hashCode 时导致的。同样在插入时也对 value 进行了检查，同样会抛出上面的异常。
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;
}
// 创建新的 entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
// 增加 Entry 数量
count++;
}
get 方法
Hashtable 的 get 方法中很多代码都与 put 方法相似，很好理解。
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
// 计算索引
int index = (hash & 0x7FFFFFFF) % tab.length;
// 遍历 e 和 e 的下一个节点，寻找该 key
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
// 判断 hash 和 key 是否想等
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
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;
}
addEntry 方法
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++;
}
rehash 方法
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
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;
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;
}
}
}
其他
SuppressWarnings 注解
在源码中有很多地方使用了 @SuppressWarnings 注解，@SuppressWarnings 注解作用抑制编译器产生警告信息，unchecked 表示抑制没有进行类型检查操作的警告。在使用 @SuppressWarnings 来排除警告和 Java Docs 描述 有描述 @SuppressWarnings 注解的使用方法。