1. Hashtable概述

Hashtable和HashMap解决Hash Collision的方法相同, 都使用Separate Chaining. 但Hashtable使用synchronized保证线程安全, 使得效率上插入删除效率上略低于HashMap

2. 重要参数

/* Hashtable主体 */
private transient Entry<?,?>[] table;

/* hash table中entry的个数 */
private transient int count;

/* table容量的阈值, 超过这个值就需要rehash */
private int threshold;

/* 负载因子 threshold = loadFactor * table.length */
private float loadFactor;

/* Hashtable修改的次数 */
private transient int modCount = 0;

/* table的最大长度(部分VM会在Array前保留几个字节, 所以需要-8) */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3. 初始化函数

3.1 无参数初始化函数

Hashtable的默认大小为11, 而HashMap的默认大小为16. 因为HashMap获得table的index操作为 hash_value & table.length - 1 . 这时就需要HashMap的长度始终保持在2n, 而Hashtable的长度则需要一个质数, 因为Hashtable获得table的index操作为 hash_value % table.length, 这就需要 hash_value 和 table.length 的GCD(Greatest Common Divisor, 最大公约数)为1, 这样才能保证index的分布平均, 证明如下:

index的求解公式: index = N % M (N为hash_value, M为table的长度, index为余数)
假设N = kn, M = km. k为N和M的GCD
所以index求解公式可转换为: kn = km × q + r
这么看来, r的取值范围为[0, M - 1]
但当公式两边除k后: n = m × q + r / k
r的取值范围变为[0, k, 2k, 3k ... m*k], 缩小了k倍, 导致分布不平均.
所以简单的方法就是将M设置为质数, 保证N和M的GCD为1

/* 默认table长度为11, load factor为0.75 */
public Hashtable() {
this(11, 0.75f);
}

3.2 带参数初始化函数

public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}

/* Hashtable中对table的长度没有要求 */
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; /* 设置loadfactor */
table = new Entry<?,?>[initialCapacity]; /* 初始化table */
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

4. table的组成单元 - Entry

/* Hashtable中table的组成单元 */
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;
}

@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash,
key,
value,
(next == null ? null : (Entry<K,V>) next.clone())
);
}

public K getKey() { return key; }

public V getValue() { return value; }

public V setValue(V value) {
if (value == null) /* Hashtable中的key和value不可设置为null */
throw new NullPointerException();

V oldValue = this.value;
this.value = value;
return oldValue;
}

public boolean equals(Object o) {
if (!(o instanceof Map.Entry)) /* 先判断类型是否正确 */
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;

/* 再判断key和value是否匹配 */
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}

public int hashCode() {
return hash ^ Objects.hashCode(value);
}

public String toString() {
return key.toString() + "=" + value.toString();
}
}

5. table扩容函数

table长度的增长规律为 nn+1 = 2×nn + 1, 这样虽然不能保证nn为质数, 但可保证nn一直为odd number, 避免了nn与hash value的公约数为2.

/* 扩容table, 并重新组织table中的Entry 
* 该函数会在Entry数量达到threshold时自动调用
*/
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;

/* 以下几行代码是overflow-conscious code, 因为一共有以下几种情况:
* 1. newCapacity > MAX_ARRAY_SIZE: oldCapacity位于[1073741820, 1073741823]
* 2. newCapacity == MAX_ARRAY_SIZE: oldCapacity为1073741819
* 3. newCapacity < MAX_ARRAY_SIZE: oldCapacity位于[1073741824, 2147483647]或[1, 1073741818]
* 由于初始化函数中没有对initialCapacity做任何限制, 所以oldCapacity可能为[1, 2147483647]中的任意值
* 所以唯一会导致溢出的oldCapacity区间为[1073741824, 2147483647]
* 此时 newCapacity < 0 且 newCapacity > MAX_ARRAY_SIZE 不成立
*
* 但由于减法运算存在溢出情况, 所以oldCapacity位于区间[1073741824, 2147483642]时
* newCapacity + MAX_ARRAY_SIZE > 0 就会成立, newCapacity被替换为MAX_ARRAY_SIZE
*
* 最后就剩下一种情况: oldCapacity位于区间[2147483643, 2147483647]
* 此时 newCapacity + MAX_ARRAY_SIZE > 0 不成立, 且 newCapacity < 0, 溢出发生
*
* 但其实并不会发生, 因为当你调用 new Hashtable(Integer.MAX_VALUE) 时, 会出现溢出(OutOfMemoryError)
*/
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) { /* 无溢出情况 */
if (oldCapacity == MAX_ARRAY_SIZE)
return;
newCapacity = MAX_ARRAY_SIZE;
}

/* 初始化新的table
* 并设置新的threshold和modCount
*/
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;

/* 两层for循环将每个Entry都移动到了newMap中
* 第一层for针对table中的每条链表
* 第二层for针对每条链表中的每个Entry
*/
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;
}
}
}

6. put()

/**
* 往table中插入key和value, key和value都不能为null
* @param key key of Entry
* @param value value of Entry
* @return the previous value of key or null
* @exception NullPointerException key is null
*/
public synchronized V put(K key, V value) {
if (value == null) {
throw new NullPointerException();
}

// 判断key是否已经存在
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) { /* 反复查询table, 直到entry为null */
if ((entry.hash == hash) && entry.key.equals(key)) { /* 替换entry的value */
V old = entry.value;
entry.value = value;
return old;
}
}

addEntry(hash, key, value, index); /* 插入一个新的entry */
return null;
}


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

Entry<?,?> tab[] = table;
if (count >= threshold) { /* 检查是否进行扩容 */
rehash();

/* 重新计算key的hash value */
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}

/* 将新建的Entry放入table中, 且指向之前的Entry */
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}

7. get() 查找元素

/**
* 查询并返回key所对应的value, 如果未找到则返回null
* @param key the key whose associated value is to be returned
* @return return the value to which the specified key is mapped, or null
* @throws NullPointerException key == null
*/
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

/* 在tab[index]开头的链表上进行查找 */
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}

8. remove()

/**
* 删除与key匹配的Entry, 如果没找到key直接退出
* @param key
* @return 被删除Entry的value
* @throws NullPointerException key == null
*/
public synchronized V remove(Object key) {
/* 步骤与HashMap基本相同:
* 1. 根据hash value找到table中的某个链表
* 2. 根据key在链表中找到要被删除的Entry, 并删除
*/
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; /* 未找到要被删除的元素 */
}