一、Hashtable 概述

Hashtable 底層基于數組與鏈表實現，通過 synchronized 關鍵字保證在多線程的環境下仍然可以正常使用。雖然在多線程環境下有了更好的替代者 ConcurrentHashMap，但是作為一個面試中高頻的知識點，我們還是有必要了解一下其內部實現細節的。

1.1 內部屬性

// 內部數組private transient Entry<?,?>[] table;// 鍵值對數量private transient int count;// 擴容閾值private int threshold;// 加載因子private float loadFactor;

內部屬性與 HashMap 幾乎一致，HashMap 中的 threshold 屬性并不止是擴容閾值，還有另一個作用：哈希表容量大小，這一點要注意區分。

1.2 相關構造函數

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;// 初始化哈希表數組大小，HashMap 中初始化容量大小必須是 2 的冪，但是 Hashtable 沒有這個限制table = new Entry<?,?>[initialCapacity];// 初始化擴容閾值threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);}

默認初始化大小與加載因子的構造函數，HashMap 的默認初始化大小是 16，而 Hashtable 是 11，加載因子默認都是 0.75.

public Hashtable() {this(11, 0.75f);}

1.3 Entry

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;}......}

沒有什么好說的，唯一注意區分的是，在 HashMap 中對應的是 Node 結構。

二、源碼分析

2.1 put 方法

public synchronized V put(K key, V value) {// Make sure the value is not null// key（如果為 null，計算哈希值時會拋異常），value 不允許為 nullif (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];// 如果桶位置上對應的鏈表不為 null，則遍歷該鏈表for(; entry != null ; entry = entry.next) {// key 重復，value 替換，返回老的 valueif ((entry.hash == hash) && entry.key.equals(key)) {V old = entry.value;entry.value = value;return old;}}// 添加新的鍵值對addEntry(hash, key, value, index);// 添加成功返回 nullreturn null;}

put 方法中并沒有直接添加鍵值對，而是通過 addEntry 方法來完成添加的過程。

private void addEntry(int hash, K key, V value, int index) {modCount++;Entry<?,?> tab[] = table;// 延遲 rehash？先判斷是否需要擴容再 count++if (count >= threshold) {// Rehash the table if the threshold is exceededrehash();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++count++;}

添加的鍵值對的方法還是比較簡單的，先根據哈希值計算出在哈希表數組中對應的桶位置，遍歷當前桶位置上的鏈表（如果存在），判斷 key 是否重復，如果重復用新的 value 覆蓋舊的 value，返回 舊的 value。如果 key 不重復，則調用添加鍵值對的方法（addEntry），addEntry 首先判斷了是否需要擴容，如果需要擴容則先進行哈希表的擴容，并重新計算添加的鍵值對的桶位置，如果不需要擴容，則直接在頭節點插入新的鍵值對。

??HashMap 先添加鍵值對，然后判斷是否需要擴容，Hashtable 是先判斷是否需要擴容然后再添加鍵值對，這一點需要區分下。

還有一點需要注意的是:java8 中 HashMap 通過尾插法插入新的鍵值對，Hashtable 通過頭插法插入鍵值對。

2.2 rehash 方法

上面我們提到了擴容機制，下面我們就來看一下其具體實現。

protected void rehash() {// 獲取老哈希表容量int oldCapacity = table.length;Entry<?,?>[] oldMap = table;// overflow-conscious code// 新哈希表容量為原容量的 2 倍 + 1，與 HashMap 不同int newCapacity = (oldCapacity << 1) + 1;// 容量很大特殊處理if (newCapacity - MAX_ARRAY_SIZE > 0) {if (oldCapacity == MAX_ARRAY_SIZE)// Keep running with MAX_ARRAY_SIZE bucketsreturn;newCapacity = MAX_ARRAY_SIZE;}// 初始化新哈希表數組Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];modCount++;// 重置擴容閾值，與 HashMap 不同，HashMap 直接把 threshold 也擴大為原來的兩倍threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);// 重置哈希表數組table = newMap;// 從底向上進行 rehashfor (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;// 獲取在新哈希表中的桶位置，鍵值對逐個進行 rehash// HashMap 會構造一個新的鏈表然后整個鏈表進行 rehashint index = (e.hash & 0x7FFFFFFF) % newCapacity;// 頭插法 rehashe.next = (Entry<K,V>)newMap[index];// 自己做頭節點newMap[index] = e;}}}

與 HashMap 相對比，Hashtable 的 rehash 過程也比較簡單，首先將容量擴大為原來的 2 倍 + 1，接著重置 threshold，賦值新的哈希表數組之后就進行鍵值對 rehash 了。鍵值對 rehash 的時候從老哈希表數組尾部開始，獲取對應桶位置上的鏈表，鍵值對逐個進行 rehash。

2.3 get 方法

相對于上面兩個方法，get 方法相對來說又簡單了很多。

public synchronized V get(Object key) {Entry<?,?> tab[] = table;int hash = key.hashCode();// 計算 key 對應的桶位置int index = (hash & 0x7FFFFFFF) % tab.length;// 遍歷桶位置上的鏈表（如果存在）for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {// 找到對應的 key，直接返回對應的 valueif ((e.hash == hash) && e.key.equals(key)) {return (V)e.value;}}return null;}

2.4 remove 方法

public synchronized V remove(Object key) {Entry<?,?> tab[] = table;int hash = key.hashCode();// 根據 key 的哈希值計算對應的桶位置int index = (hash & 0x7FFFFFFF) % tab.length;@SuppressWarnings("unchecked")// 獲取桶位置上對應的鏈表Entry<K,V> e = (Entry<K,V>)tab[index];for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {if ((e.hash == hash) && e.key.equals(key)) {modCount++;// 移除的非頭節點if (prev != null) {// 斷開要移除的節點 eprev.next = e.next;} else {// 如果要移除的是頭節點則重置后面的節點為頭節點tab[index] = e.next;}count--;V oldValue = e.value;// help GCe.value = null;return oldValue;}}return null;}

根據 key 刪除鍵值對方法也比較簡單，根據哈希值計算出對應的桶位置后，找到對應桶位置上的鏈表，判斷刪除的是不是頭節點，如果是則把后面的節點置為頭節點，如果不是，只要改變前節點的后繼節點為刪除節點的后繼節點就可以了。

三、other

在分析源碼的時候對比了很多與 HashMap 的不同點，在看 Hashtable 源碼的時候建議與 HashMap 對比著看，可以加深對 map 的理解。

Hashtable 的內部實現相對來說比較簡單，數據結構通過數組和鏈表實現。如果你需要在并發編程中使用 map，建議使用 ConcurrentHashMap，性能相對于 Hashtable 要高很多，后面有機會我們再討論 ConcurrentHashMap 的內部實現。

jdk1.8 源碼閱讀：https://github.com/zchen96/jdk1.8-source-code-read
Java8 HashMap 擴容機制與線程安全分析：https://blog.csdn.net/codejas/article/details/85056606

總結

以上是生活随笔為你收集整理的Java8 Hashtable 源码阅读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。