前文对 JDK1.8 中的 HashMap 的在原理实现以及相关操作进行了说明，介绍了基于数组（Node）+链表（尾插）+红黑树的数据结构，以及resize()的过程。而本文将介绍与 HashMap 较为相似的HashTable，同样也是基于数组（Entry）+链表实现的，但HashTable是线程同步的（synchroinzed），在某些方面又有一些区别，下面将分别介绍。
总览
HashTable 产生于 JDK1.0，HashMap 产生于 JDK1.2。与 HashMap 相同的是，HashTable 底层同样采用数组+链表的形式，也是 Map 下的核心容器，实现了 Map 、Cloneable 以及 Serializable 接口。但不同的是，HashTable 继承的是抽象类 Dictionary，而 HashMap 继承的是抽象类 AbstractMap。如下所示：
1
2
3
4
5
6
7
|
// HashTable
public class Hashtable<K,V> extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {}
// HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {}
|
成员变量
HashTable 中主要的成员变量与 HashMap 中的基本相同，其中桶数组 table 是用于存储键值对的 Entry 对象，count 表示 Entry 对象的个数，threshold 表示对数组进行扩容的阈值，loadFactor 表示默认值为 0.75 的负载因子，以及结构性修改次数 modCount，此变量用于在并发环境中，如果其他线程对其进行了结构性的修改，则这时迭代器会立马感知并抛出异常，便于快速失败。
1
2
3
4
5
6
7
8
9
|
private transient Entry<?, ?>[] table;
private transient int count;
private int threshold;
private float loadFactor;
private transient int modCount = 0;
|
内部类 Entry
Entry 封装了键值对，其结构与 HashMap 中的相同。但这里 hash 值的计算方法不同于 HashMap，至于不同之处，将在下面的 put() 方法进行介绍。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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 有 4 个构造函数，整体与 HashMap 中的相同，但在初始化容量上有所不同。
- 第一个构造函数：使用指定的初始化容量以及指定的负载因子，构造一个空的 HashTable；
- 第二个构造函数：使用指定的初始化容量以及默认的负载因子 0.75，构造一个空的 HashTable；
- 第三个构造函数：使用默认的初始化容量 11 以及默认的负载因子 0.75，构造一个空的 HashTable；
- 第三个构造函数：使用足以在给定的 Map 中进行映射的初始化容量（不小于 11）以及默认的负载因子 0.75，构造一个空的 HashTable。（HashMap 中的初始容量为 16）
源代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
// 第一个构造函数
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);
}
// 第二个构造函数
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
// 第三个构造函数
public Hashtable() {
this(11, 0.75f);
}
// 第四个构造函数
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
|
注意第一个构造函数中的initialCapacity == 0，其初始容量不必是 2 的整数次幂。其中，扩容阈值threshold使用了 min 函数，用于在initialCapacity * loadFactor和MAX_ARRAY_SIZE + 1中选择最小值，而MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。
put 方法
与 HashMap 不同的是，HashTable 中的 put 方法是线程安全的，即使用了synchronized。其次，通过源码可知，这里对 value 进行了判空操作，即 HashTable 不允许空的 value。
整体流程：
- 首先对新加入的节点的 value 进行判空操作，若为空，则抛出异常；
- 其次根据 key 计算对应的哈希值，定位键值对要插入的桶位置；
- 然后查找该桶位置上是否已经具有相同的键值对，若果存在则直接覆盖对应的 value，否则将新节点插入到链表头部；
- 如果桶位置上没有键值对，则直接保存。
源码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public synchronized V put(K key, V value) {
// Make sure the value is not null
// 不允许 value 为空
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
// 计算 key 的哈希值，此处与 HashMap 的计算方式不同
int hash = key.hashCode();
// 定位桶位置，即桶数组中的索引
// 二进制 0x7FFFFFFF 表示整数的最大值：2147483647
int index = (hash & 0x7FFFFFFF) % tab.length;
// 查找 index 位置上是否具有相同的节点
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
// 若相同，则将对应的 value 进行覆盖
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 如果没有相同的节点，则以头插法的方式插入到链表中
// 如果该桶上是空的，则直接保存
addEntry(hash, key, value, index);
return null;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
// 插入节点前，需要检查是否需要进行扩容
if (count >= threshold) {
// 进行扩容
rehash();
tab = table;
// 重新计算 key 的哈希值
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 方法
整体流程：
- 首先获取旧的桶数组的长度，将长度扩大为原来的两倍再加一，并对新容量进行越界检查；
- 然后创建新的桶数组，并跟新阈值，从旧数组的最后开始往前遍历，计算每个节点的 hash 值，并放到对应的新的桶数组中。
源码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
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;
}
// 没有问题的话，就创建一个 newCapacity 大小的桶数组
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
// 更新阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
// 重新将节点映射到新数组中，从后往前遍历
for (int i = oldCapacity ; i-- > 0 ;) {
// 取出旧数组中 i 位置的节点
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;
}
}
}
|
get 操作
get 方法是同步的，首先计算 key 的哈希值，然后通过再定位到对应的桶位置，通过使用 equals 方法比较对应的 key 是否相同，最后返回响应的 value。这里与 HashMap 有些细微上的差别，HashTable 中如果 get 某个 key 返回的是 null 的话，则表示在 HashTable 中不含有该 key 对应的节点，而 HashMap 中，如果 get 某个 key 返回的是 null，则一种情况是该 key 所对应的 value 就是 null，另一种情况是 HashMap 中不存在该 key。
1
2
3
4
5
6
7
8
9
10
11
|
public synchronized V get(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 (V)e.value;
}
}
return null;
}
|
总结
HashTable 和 HashMap 在具体的细节上还是有一定的差别的，在此总结：
- HashTable 中的 key 和 value 不允许为 null，而 HashMap 可以为 null，这造成 get 返回结果的不同；
- HashTable 中的初始容量为 11，而 HashMap 中为 16；
- HashTable 在插入节点之前需要检查是否需要扩容，而 HashMap 在插入节点之后才会判断是否进行扩容操作；
- HashTable 中计算 hash 的方式与 HashMap 中的不同；
- HashTable 是线程安全的，而 HashMap 不是；
- HashTable 进行 rehash 时会将桶数组扩充为原来的两倍再加一，而 HashMap 会扩充为原来的两倍。