本文的目的並不是讓你對 更加瞭解，然後靈活運用；因為 的一個歷史遺留的類，目前並不建議使用，所以本文主要和 對比，感受同樣功能的不同實現，知道什麼是好的代碼；所以在閱讀本文之前最好先瞭解一下 ，可以參考 "HashMap 相關" ； 一、 類定義 可以看到它和 雖然都是哈希表，但是結構完全不一樣，他 ...
本文的目的並不是讓你對Hashtable更加瞭解，然後靈活運用；因為Hashtable的一個歷史遺留的類，目前並不建議使用，所以本文主要和HashMap對比，感受同樣功能的不同實現，知道什麼是好的代碼；所以在閱讀本文之前最好先瞭解一下 HashMap，可以參考 HashMap 相關；
一、 類定義
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable 
可以看到它和HashMap雖然都是哈希表，但是結構完全不一樣，他是繼承於Dictionary；
/**
* Maps the specified <code>key</code> to the specified
* <code>value</code> in this dictionary. Neither the key nor the
* value can be <code>null</code>.
*/
abstract public V put(K key, V value);
abstract public Enumeration<K> keys();
abstract public Enumeration<V> elements();
public interface Enumeration<E> {
boolean hasMoreElements();
E nextElement();
}同AbstractMap相比功能結構基本一樣，但是有兩點很重要的區別：
Hashtable要求 key 和 value，都不能為 null，也就意味著這每次 put 元素的時候都需要判空，真是想想都好痛苦；- 另外 keys 和 elements 返回的居然是
Enumeration，這也是一個比較古老的介面，用於枚舉（一次獲得一個）對象集合中的元素；但是目前大多已經被Iterator給取代了；
二、構造方法和成員變數
private transient Entry<?,?>[] table; // 哈希槽
private int threshold; // 閾值
private float loadFactor; // 負載繫數以上三個應該就是 Map 中最重要的成員變數了，閾值和負載繫數控制擴容時機，同HashMap的作用是一樣的，哈希槽也是一樣的，但是註意Entry<?,?>[]這裡用的居然是通配符，而不是K V，也就意味著在取 entry 的時候，還需要強轉類型，這也是非常神奇的地方；
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)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}如代碼所示四個構造函數，主要就是為了初始化以上三個成員變數，但是註意table的容量；熟悉HashMap的肯定知道，HashMap的容量要求是2的冪，目的是為了使用hash % length = hash & (length-1)，優化哈希槽的定位；但是如上面代碼所示Hashtable的容量卻不是，初始容量預設11，擴容是2倍加1；這樣做的優缺點有什麼呢：
- 缺點，不能利用“與”來優化哈希槽定位；
- 優點，減小了哈希衝突的幾率（hashmap 的容量雖然是偶數，但是對哈希做了高位與低位，以及紅黑樹，使得即使hash衝突十分嚴重，性能也能得以保證），詳情可以參考 為什麼一般hashtable的桶數會取一個素數；
三、重要方法
1. 哈希槽定位
int index = (hash & 0x7FFFFFFF) % tab.length;哈希表中最重要的方法肯定是哈希槽定位，如上面的原因Hashtable定址的時候並不能做優化，所以只是用的典型除留餘數法，(hash & 0x7FFFFFFF)則是為了保證第一位符號位是0，也就是正數，保證最終的餘數是正數；
2. get 方法
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
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 (V)e.value;
}
}
return null;
}註意Hashtable的所有方法都是synchronized修飾的，所以Hashtable是線程安全的容器；
代碼很簡單，就是得到哈希，計算哈希桶，再一次遍歷鏈表；但是需要註意：
int hash = key.hashCode();，這裡是直接取的 key 的 hashCode，所以這裡不能避免極端哈希的情況；- 另外就是不能使用可變 key （所有容器都不能使用可變 key），例如：
private static class A {
String name;
public A(String name) {this.name = name;}
@Override
public boolean equals(Object o) { ... }
@Override
public int hashCode() { ... }
}
private static void test01() {
Map<A, String> map = new Hashtable<>();
A a1 = new A("a");
A a2 = new A("a");
map.put(a1, "a");
map.put(a2, "a");
System.out.println(map.get(a1));
a1.name = "b";
System.out.println(map.get(a1));
}// 列印：
a
null
3. put 方法
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;
}Hashtable的put方法和HashMap相比，就顯得十分清晰，先判空，在查找，找到就替換，找不到就插入新節點；但是在插入順序（後面會講到），紅黑樹性能保證等方面也就不能和HashMap相比了；另外這裡取出來的Entry也是進行了類型強制轉換；
4. addEntry 方法
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++;
}
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;
}
...
}這裡添加元素的時候首先判斷是否擴容，然後添加節點；值得註意的是添加的節點是直接放在哈希槽里的（tab[index] = new Entry<>(hash, key, value, e);）大部分的 Map 實現都是將添加的節點放在鏈表尾部；所以Hashtable中節點的相對順序是不斷變化的；
5. rehash 方法
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;
}
}
}擴容的時候也是，先計算新容量，在得到一個新的哈希槽，然後將節點在依次放入；同添加節點一樣是將節點直接放到哈希槽中，那麼在擴容完畢之後，鏈表的相對順序會反向；
總結
Hashtable的 key 和 value 都不能為 null，在使用的時候需要判空。。。。蛋疼- 哈希值完全依賴 key 的
hashCode方法，所以在使用的時候，需要額外註意 Hashtable的容量可以是任意值，預設是11，不能使用“與”來優化定址Hashtable的節點相對位置是不斷變化的；Hashtable是線程安全的；
