Hashtable简介

声明

Hashtable声明

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

Hashtable和HashMap一样也是散列表，存储元素也是键值对；
Hashtable继承于Dictionary类（Dictionary类声明了操作键值对的接口方法），实现Map接口（定义键值对接口）；
Hashtable大部分类用synchronized修饰，证明Hashtable是线程安全的；

Hashtable基本数据结构

• private transient Entry<?,?>[] table：键值对/Entry数组，每个Entry本质上是一个单向链表的表头

• private int threshold：rehash阈值

• private float loadFactor：装填因子

• private transient int modCount = 0： Hashtable结构化修改次数，用来实现fail-fast机制；

• private transient volatile Set<Map.Entry<K,V>> entrySet：Hastable视图，键值对集合；

• private transient volatile Set<K> keySet：Hastable视图，key集，Hashtable中key不可重复；

• private transient volatile Collection<V> values：Hastable视图，value集合，可重复；

  • Hashtable中key和value是一对多关系；

键值对/Entry

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K, V> next;
    ...
    // 计算键值对的hashCode
    public int hashCode() {
        // "^" 按位异或, hash在调用构造器时传入
        return hash ^ Objects.hashCode(value);
    }
}

Hash函数

键值对

Hashtable方法分析

public synchronized boolean contains(Object value)

public boolean containsValue(Object value)内部调用contains(value);

判断是否含有该value的键值对，在Hashtable中hashCode相同的Entry用链表组织，hashCode不同的存储在Entry数组table中；

// in contains() method.
Entry<?,?> tab[] = table;
// 查找：遍历所有Entry链表
for (int i = tab.length ; i-- > 0 ;) {
    for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
        if (e.value.equals(value)) {
            return true;
        }
    }
}
return false;

public synchronized boolean containsKey(Object key)

散列分布策略

int index = (hash & 0x7FFFFFFF) % tab.length;
计算键值对的桶位（本质是键值对在tab数组中的索引），Hashtable本质上采用除数取余法进行散列分布，模运算效率较低

Hash函数

int hash = key.hashCode() Hashtable直接调用key的hashCode()计算hashCode；

containsKey方法体

Entry<?,?> tab[] = table;
int hash = key.hashCode();
/**
 * 计算index, % tab.length防止数组越界
 * index表示key对应entry所在链表表头
 */
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 true;
    }
}
return false;

public synchronized V get(Object key)：根据指定key查找对应value，查找原理与containsKey相同，查找成功返回value，否则返回null；

public synchronized V put(K key, V value)

设置键值对，key和value都不可为null，设置顺序:

1. 如果Hashtable含有key，设置(key, oldValue) -> (key, newValue)；

2. 如果Hashtable不含有key, 调用addEntry(...)添加新的键值对；

private void addEntry(int hash, K key, V value, int index)

当键值对个数超过阈值，先进行rehash然后添加entry，否则直接添加entry；

public synchronized V remove(Object key)

remove操作，计算key所在链表表头table[index]，然后进行单向链表的节点删除操作

public synchronized Object clone()

对Hashtable的浅拷贝操作，浅拷贝所有bucket（单向链表组织形式）的表头；

protected void rehash()

当Hashtable中键值对总数超过阈值（容量*装载因子）后，内部自动调用rehash()增加容量，重新计算每个键值对的hashCode;
int newCapacity = (oldCapacity << 1) + 1计算新容量 = 2 * 旧容量 + 1；并且根据新容量更新阈值；

...
for (int i = oldCapacity ; i-- > 0 ;) {
    // 拷贝每个Entry链表
    for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
        Entry<K,V> e = old;
        old = old.next;
        // 重新计算每个Entry链表的表头索引（rehash）
        int index = (e.hash & 0x7FFFFFFF) % newCapacity;
        // 开辟链表节点
        e.next = (Entry<K,V>)newMap[index];
        // 拷贝
        newMap[index] = e;
    }
}