JDK源碼分析（10）之 Hashtable 相關

本文的目的并不是讓你對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沖突十分嚴重，性能也能得以保證）；

三、重要方法

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是線程安全的。