Java：HashTable类小记
对 Java 中的 HashTable类，做一个微不足道的小小小小记
概述
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
// ...
}
需要说明的是：HashTable 和 HashMap 的实现原理基本一样，差别无非是：
HashTable 不允许 key 和 value 为 null；
-
HashTable 是线程安全的。
但是 HashTable 线程安全的策略实现代价却太大了，简单粗暴，get/put 所有相关操作都是 synchronized 的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。
扩容方式稍有不同，见后续分析
对于 HashMap 的一点记录，见：Java：HashMap类小记
相同点
对比了 HashTable 与 HashMap 的相同点，如下：
- 都可以用来存储键值对
- 底层哈希表结构查询速度都很快
- 内部通过单链表解决冲突问题，容量不足会自动增加
- 都实现了 Map 接口
- 都实现了 Serializable 接口，支持序列化
- 实现了 Cloneable 接口，可以被克隆
不同点
-
HashTable 继承了 Dictionary 类，而 HashMap 是继承了 AbstractMap类。Dictionary 是任何可将键映射到相应值的类的抽象父类，而 AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
...
}
public abstract class AbstractMap<K,V> implements Map<K,V> {
...
} /************************************************/ public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
...
} public abstract
class Dictionary<K,V> {
...
}据说这是因为：历史原因
-
线程安全不一样：Hashtable 是线程安全的，而 HashMap 不是线程安全的，但是我们也可以通过
Collections.synchronizedMap(hashMap)，使其实现同步。//这是Hashtable的put()方法:
public synchronized V put(K key, V value){
...
} /************************************************/ //这是HashMap的put()方法:
public V put(K key, V value) {
...
}从上面的源代码可以看到 Hashtable 的
put()方法是synchronized的，而 HashMap 的put()方法却不是。 -
HashMap 的 key 和 value 都允许为 null，而 Hashtable 的 key 和 value 都不允许为 null。
HashMap 遇到 key 为 null 的时候，调用 putForNullKey 方法进行处理（JDK 8中在hash函数中做了判断），而对 value 没有处理；
Hashtable 遇到 null，直接返回
NullPointerException。// HashMap
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} // 在 hash(key)方法中：对于null做了特殊的处理
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} /************************************************/ // Hashtable
public synchronized V put(K key, V value) {
// Make sure the value is not null
// 1.值为null直接抛出异常
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
// 由于key是null，null当然是没有hashCode()这种方法的
// 因此直接抛出异常NullPointerException
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
// ....
} -
遍历方式的内部实现上不同：HashMap使用 Iterator 遍历，HashTable 使用Enumeration 遍历；
据说这也是因为：历史原因
关于 Iterator 与 Enumeration 的异同，见：Java：Iterator接口与fail-fast小记
-
HashMap 和 HashTable 的初始化方式和扩容方式不同：
HashMap：在构造函数中不创建数组，而是在第一次put时才创建，且初始大小为16；之后每次扩充容量为原来的两倍；
HashTable：在构造函数直接创建hashtable，且其初始大小为11，之后每次扩充2n+1
// hashmap初始化:HashMap hashMap = new HashMap();
// 默认构造函数
public HashMap() {
// 先不创建，在使用的时候再创建
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
// 其中：DEFAULT_LOAD_FACTOR = 0.75f;
// DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
} public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} /************************************************/ // hashtable初始化:Hashtable hashtable = new Hashtable();
public Hashtable() {
// 构造函数直接创建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，获得大小为initialCapacity的table数组
table = new Entry<?,?>[initialCapacity];
// 计算阀值
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
} // hastable扩容：
public synchronized V put(K key, V value) {
// ... // 添加元素，见下面
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++;
} // rehash，扩容操作
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table; // overflow-conscious code
// 这里：新容量=旧容量 * 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;
}
// 新建一个size = newCapacity 的HashTable
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;
}
}
}