Hashtable簡介
Hashtable同樣是基於哈希表實現的，同樣每個元素是一個key-value對，其內部也是通過單鏈表解決沖突問題，容量不足（超過了閥值）時，同樣會自動增長。
Hashtable也是JDK1.0引入的類，是線程安全的，能用於多線程環境中。
Hashtable同樣實現了Serializable接口，它支持序列化，實現了Cloneable接口，能被克隆。
HashTable源碼剖析
Hashtable的源碼的很多實現都與HashMap差不多，源碼如下（加入了比較詳細的注釋）：
package java.util;
import java.io.*;
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
// 保存key-value的數組。
// Hashtable同樣采用單鏈表解決沖突，每一個Entry本質上是一個單向鏈表
private transient Entry[] table;
// Hashtable中鍵值對的數量
private transient int count;
// 阈值，用於判斷是否需要調整Hashtable的容量（threshold = 容量*加載因子）
private int threshold;
// 加載因子
private float loadFactor;
// Hashtable被改變的次數，用於fail-fast機制的實現
private transient int modCount = 0;
// 序列版本號
private static final long serialVersionUID = 1421746759512286392L;
// 指定“容量大小”和“加載因子”的構造函數
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 Entry[initialCapacity];
threshold = (int)(initialCapacity * loadFactor);
}
// 指定“容量大小”的構造函數
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
// 默認構造函數。
public Hashtable() {
// 默認構造函數，指定的容量大小是11；加載因子是0.75
this(11, 0.75f);
}
// 包含“子Map”的構造函數
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
// 將“子Map”的全部元素都添加到Hashtable中
putAll(t);
}
public synchronized int size() {
return count;
}
public synchronized boolean isEmpty() {
return count == 0;
}
// 返回“所有key”的枚舉對象
public synchronized Enumeration<K> keys() {
return this.<K>getEnumeration(KEYS);
}
// 返回“所有value”的枚舉對象
public synchronized Enumeration<V> elements() {
return this.<V>getEnumeration(VALUES);
}
// 判斷Hashtable是否包含“值(value)”
public synchronized boolean contains(Object value) {
//注意，Hashtable中的value不能是null，
// 若是null的話，拋出異常!
if (value == null) {
throw new NullPointerException();
}
// 從後向前遍歷table數組中的元素(Entry)
// 對於每個Entry(單向鏈表)，逐個遍歷，判斷節點的值是否等於value
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
public boolean containsValue(Object value) {
return contains(value);
}
// 判斷Hashtable是否包含key
public synchronized boolean containsKey(Object key) {
Entry tab[] = table;
//計算hash值，直接用key的hashCode代替
int hash = key.hashCode();
// 計算在數組中的索引值
int index = (hash & 0x7FFFFFFF) % tab.length;
// 找到“key對應的Entry(鏈表)”，然後在鏈表中找出“哈希值”和“鍵值”與key都相等的元素
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}
// 返回key對應的value，沒有的話返回null
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
// 計算索引值，
int index = (hash & 0x7FFFFFFF) % tab.length;
// 找到“key對應的Entry(鏈表)”，然後在鏈表中找出“哈希值”和“鍵值”與key都相等的元素
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
// 調整Hashtable的長度，將長度變成原來的2倍+1
protected void rehash() {
int oldCapacity = table.length;
Entry[] oldMap = table;
//創建新容量大小的Entry數組
int newCapacity = oldCapacity * 2 + 1;
Entry[] newMap = new Entry[newCapacity];
modCount++;
threshold = (int)(newCapacity * loadFactor);
table = newMap;
//將“舊的Hashtable”中的元素復制到“新的Hashtable”中
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
//重新計算index
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
// 將“key-value”添加到Hashtable中
public synchronized V put(K key, V value) {
// Hashtable中不能插入value為null的元素！！！
if (value == null) {
throw new NullPointerException();
}
// 若“Hashtable中已存在鍵為key的鍵值對”，
// 則用“新的value”替換“舊的value”
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
// 若“Hashtable中不存在鍵為key的鍵值對”，
// 將“修改統計數”+1
modCount++;
// 若“Hashtable實際容量” > “阈值”(阈值=總的容量 * 加載因子)
// 則調整Hashtable的大小
if (count >= threshold) {
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
//將新的key-value對插入到tab[index]處（即鏈表的頭結點）
Entry<K,V> e = tab[index];
tab[index] = new Entry<K,V>(hash, key, value, e);
count++;
return null;
}
// 刪除Hashtable中鍵為key的元素
public synchronized V remove(Object key) {
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
//從table[index]鏈表中找出要刪除的節點，並刪除該節點。
//因為是單鏈表，因此要保留帶刪節點的前一個節點，才能有效地刪除節點
for (Entry<K,V> e = tab[index], 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;
}
// 將“Map(t)”的中全部元素逐一添加到Hashtable中
public synchronized void putAll(Map<? extends K, ? extends V> t) {
for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
put(e.getKey(), e.getValue());
}
// 清空Hashtable
// 將Hashtable的table數組的值全部設為null
// 本欄目
1、二者的存儲結構和解決沖突的方法都是相同的。
2、HashTable在不指定容量的情況下的默認容量為11，而HashMap為16，Hashtable不要求底層數組的容量一定要為2的整數次冪，而HashMap則要求一定為2的整數次冪。
3、Hashtable中key和value都不允許為null，而HashMap中key和value都允許為null（key只能有一個為null，而value則可以有多個為null）。但是如果在Hashtable中有類似put(null,null)的操作，編譯同樣可以通過，因為key和value都是Object類型，但運行時會拋出NullPointerException異常，這是JDK的規范規定的。我們來看下ContainsKey方法和ContainsValue的源碼：
// 判斷Hashtable是否包含“值(value)”
public synchronized boolean contains(Object value) {
//注意，Hashtable中的value不能是null，
// 本欄目
4、Hashtable擴容時，將容量變為原來的2倍加1，而HashMap擴容時，將容量變為原來的2倍。
5、Hashtable計算hash值，直接用key的hashCode()，而HashMap重新計算了key的hash值，Hashtable在求hash值對應的位置索引時，用取模運算，而HashMap在求位置索引時，則用與運算，且這裡一般先用hash&0x7FFFFFFF後，再對length取模，&0x7FFFFFFF的目的是為了將負的hash值轉化為正值，因為hash值有可能為負數，而&0x7FFFFFFF後，只有符號外改變，而後面的位都不變。
