HashTable原理和源码分析详解编程语言

上一篇文章《HashMap原理和源码分析》介绍了HashMap。比对着HashMap，来看一下HashTable的特性.

HashTable的特性

1. HashTable 跟HashMap 最大区别是HashMap具备线程安全性，所有的方法都是安全的；

2. HashTable不支持null值和null键；

3. HashTable结构同HashMap产不多：数组 + 链表，而且没有红黑树，相比更简单了：

   

4. 扩容：

   • 初始容量是11
   • newCapacity = (oldCapacity << 1) + 1; 扩大为原来容量两倍 + 1

源码解析

参数：

private transient HashtableEntry<?,?>[] table;// 数组存储 
 
private transient int count; // 结点的总数 
 
private int threshold; // 扩容的临界值 
 
private float loadFactor; // 默认是0.75，到达需要扩容的比例 
 
private transient int modCount = 0; // 修改的次数，例如put、remove、clear等 

从参数就可以看出跟HashMap大同小异，而且简洁了许多。

构造函数

public 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 = new HashtableEntry<?,?>[initialCapacity];// 直接使用初始容量 
        // 原本 threhold = initialCapacity * loadFactor 
        // 但是这里实际上设置threshold 为initialCapacity 
        threshold = (int)Math.min(initialCapacity, MAX_ARRAY_SIZE + 1); 
    } 

从上面构造函数可以看到，默认初始容量 = threshold = 11; 加载因子 = 0.75

put
增加或者修改一个节点

public synchronized V put(K key, V value) {
 
if (value == null) {
 // 不支持value为null 
throw new NullPointerException(); 
} 
// Makes sure the key is not already in the hashtable. 
HashtableEntry<?,?> tab[] = table; 
int hash = key.hashCode(); 
// 直接hash求余 得到hash桶位置 
int index = (hash & 0x7FFFFFFF) % tab.length; 
@SuppressWarnings("unchecked") 
HashtableEntry<K,V> entry = (HashtableEntry<K,V>)tab[index]; 
// 遍历hash桶 
for(; entry != null ; entry = entry.next) {
 
// 找到对应key的节点 
if ((entry.hash == hash) && entry.key.equals(key)) {
 
V old = entry.value; 
entry.value = value; 
return old; 
} 
} 
// 没有存在key，增加节点到一个新的hash桶 
addEntry(hash, key, value, index); 
return null; 
} 
// 没有存在key，增加节点到一个新的hash桶 
private void addEntry(int hash, K key, V value, int index) {
 
modCount++; // 操作数 + 1 
HashtableEntry<?,?> tab[] = table; 
if (count >= threshold) {
 // 大于等于扩容临界值 
// Rehash the table if the threshold is exceeded 
rehash();// 需要扩容 
tab = table; 
hash = key.hashCode(); 
// 同样 直接hash求余 得到hash桶位置 
index = (hash & 0x7FFFFFFF) % tab.length; 
} 
// Creates the new entry. 
@SuppressWarnings("unchecked") 
HashtableEntry<K,V> e = (HashtableEntry<K,V>) tab[index]; 
// 添加节点到一个新的桶中 
tab[index] = new HashtableEntry<>(hash, key, value, e); 
count++; 
} 

remove
移除节点

    public synchronized V remove(Object key) {
 
HashtableEntry<?,?> tab[] = table; 
int hash = key.hashCode(); 
// 同样 直接hash求余 得到hash桶位置 
int index = (hash & 0x7FFFFFFF) % tab.length; 
@SuppressWarnings("unchecked") 
HashtableEntry<K,V> e = (HashtableEntry<K,V>)tab[index]; 
// 遍历hash桶内的链表 
for(HashtableEntry<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; 
} 

扩容

hashTable的扩容

    protected void rehash() {
 
int oldCapacity = table.length; 
HashtableEntry<?,?>[] oldMap = table; 
//新容量 = 旧容量 × 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; 
} 
HashtableEntry<?,?>[] newMap = new HashtableEntry<?,?>[newCapacity]; 
modCount++;// 操作数 +1 
// 这里是符合预期的，threhold = initialCapacity * loadFactor 
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 
table = newMap; 
// 迁移所有旧的节点到新的hash桶中 
for (int i = oldCapacity ; i-- > 0 ;) {
 
for (HashtableEntry<K,V> old = (HashtableEntry<K,V>)oldMap[i] ; old != null ; ) {
 
// 遍历每个节点 
HashtableEntry<K,V> e = old; 
old = old.next; 
// 计算出新的位置，插入到桶的首个节点 
int index = (e.hash & 0x7FFFFFFF) % newCapacity; 
e.next = (HashtableEntry<K,V>)newMap[index]; 
newMap[index] = e; 
} 
} 
} 

扩容：
容量增加为原来2倍+1; 将每个结点重新hash迁移到对应的新的hash桶中
这里的增加节点跟HashMap的链表有点不一样，hashTable是直接插入到链表的头部，hashMap是在尾部。