前言
注意是 Hashtable 不是 HashTable (t為小寫)虏束，這不是違背了駝峰定理了嘛灯抛？這還得從 Hashtable 的出生說(shuō)起随橘，
Hashtable 是在Java1.0的時(shí)候創(chuàng)建的蕴坪，而集合的統(tǒng)一規(guī)范命名是在后來(lái)的Java2開始約定的还栓，而當(dāng)時(shí)又發(fā)布了新的集合代替它碌廓，所以這個(gè)命名也一直使用到現(xiàn)在，
所以 Hashtable 是一個(gè)過(guò)時(shí)的集合了蝙云，不推崇大家使用這個(gè)類氓皱，雖說(shuō) Hashtable 是過(guò)時(shí)的了路召，我們還是有必要分析一下它勃刨，以便對(duì)Java集合框架有一個(gè)整體的認(rèn)知。
HashTable 比較古老股淡， 是JDK1.0就引入的類身隐，而HashMap 是 1.2 引進(jìn)的 Map 的一個(gè)實(shí)現(xiàn)。
HashTable 是線程安全的唯灵，能用于多線程環(huán)境中贾铝。
Hashtable 同樣也實(shí)現(xiàn)了 Serializable 接口，支持序列化埠帕，也實(shí)現(xiàn)了 Cloneable 接口垢揩，能被克隆。
成員變量
//為什么要用int最大值-8敛瓷，官方解釋：有些虛擬機(jī)在數(shù)組中保留了一些頭信息叁巨。避免內(nèi)存溢出！
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//table是一個(gè)Entry[]數(shù)組類型呐籽，而Entry實(shí)際上就是一個(gè)單向鏈表锋勺。哈希表的"key-value鍵值對(duì)"都是存儲(chǔ)在Entry數(shù)組中的蚀瘸。
private transient Entry[] table;
// Hashtable中元素的實(shí)際數(shù)量
private transient int count;
// 閾值，用于判斷是否需要調(diào)整Hashtable的容量（容量*加載因子 >= threshold 是需要調(diào)整容量）
private int threshold;
// 加載因子 默認(rèn)0.75f
private float loadFactor;
// Hashtable被改變的次數(shù) 是Hashtable被修改或者刪除的次數(shù)總數(shù)庶橱。用來(lái)實(shí)現(xiàn)“fail-fast”機(jī)制的
private transient int modCount = 0;
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);
//初始容量最小為1
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
PUT方法
線程安全
key value 都不能為null
hash & 0x7FFFFFFF 是為了避免負(fù)數(shù)贮勃，為什么不用abs（絕對(duì)值）？涉及一個(gè)int負(fù)數(shù)最大值問(wèn)題
如果key已存在會(huì)返回老的value
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
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) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
addEntry方法
如果hashtable 當(dāng)前數(shù)量>=閾(愈)值苏章，需要擴(kuò)容
鏈表疊加
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方法
容量擴(kuò)大兩倍+1
需要將原來(lái)HashTable中的元素一一復(fù)制到新的HashTable中寂嘉，這個(gè)過(guò)程是比較消耗時(shí)間的
鏈表順序變了
@SuppressWarnings("unchecked")
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;
}
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;
}
}
}
remove方法
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
//遍歷Entry鏈表，e為當(dāng)前節(jié)點(diǎn)布近，prev為上一個(gè)節(jié)點(diǎn)
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
//為什么不直接只用 e.key.equals(key) 來(lái)判斷垫释，因?yàn)閑.hash == hash性能更優(yōu)
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
//如果是鏈表的中間值
prev.next = e.next;
} else {
//如果是鏈表的第一個(gè)
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
return oldValue;
}
}
return null;
}
