字節一面：Hashtable 和 HashMap的 keyset 有什么區別？
Hashtable 和 HashMap 是 Java 中最常用的兩種哈希表實現，它們都可以用于存儲鍵值對，但在實現細節和使用上有一些顯著差異。這篇文章我們從原理、源碼來等方面詳細的分析它們，以及它們的 keySet 有哪些區別。
Hashtable
Hashtable 的主要特性可以總結成下面 3點：
- 線程安全：Hashtable 是線程安全的。它的所有方法都使用 synchronized 關鍵字進行同步，因此在多線程環境下可以安全使用。
- 不允許 null 鍵和值：Hashtable 不允許任何鍵或值為 null。如果試圖插入 null 鍵或值，會拋出 NullPointerException。
- 哈希沖突解決：使用鏈表法解決哈希沖突。每個桶（bucket）是一個鏈表，沖突的元素會被添加到鏈表的末尾。
源碼分析
Hashtable 的主要方法如 put、get 都使用了 synchronized 進行同步。下面代碼是put 方法的簡化版本：
public synchronized V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException();
}
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % table.length;
for (Entry<K, V> e = table[index]; e != null; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}HashMap
HashMap 的主要特性可以總結成下面 3點：
- 非線程安全：HashMap 是非線程安全的。在多線程環境下使用時需要手動同步。
- 允許 null 鍵和值：HashMap 允許一個 null 鍵和多個 null 值。
- 哈希沖突解決：同樣使用鏈表法解決哈希沖突，但在 Java 8 之后，當鏈表長度超過一定閾值（默認是8）時，會將鏈表轉換為紅黑樹，以提高性能。
HashMap 源碼分析
HashMap 的主要方法如 put 和 get 都沒有同步機制。下面代碼是put 方法的簡化版本：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab; Node<K, V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}keySet 的區別
在分析了 Hashtable 和 HashMap之后，我們再來對比兩者keySet的差異，總結如下：
- Hashtable 的 keySet 返回一個 KeySet 視圖，它是一個同步的集合視圖。當你對這個集合進行操作時，會同步到原始的 Hashtable。
- HashMap 的 keySet 返回一個 KeySet 視圖，它是非同步的集合視圖。如果在多線程環境下使用，需要手動同步。
為了更詳細地探討 Hashtable 和 HashMap 的 keySet 的區別，我們需要從 實現方式、線程安全性、性能影響和使用場景幾個方面來分析。
1. 實現方式
(1) Hashtable 的 keySet
Hashtable的keySet方法返回一個KeySet視圖，這個視圖是通過 Collections.synchronizedSet 包裝而成的，這意味著 keySet 本身是線程安全的。
以下是關鍵代碼片段：
public synchronized Set<K> keySet() {
if (keySet == null)
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}
private class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return getIterator(KEYS);
}
public int size() {
return count;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return Hashtable.this.remove(o) != null;
}
public void clear() {
Hashtable.this.clear();
}
}(2) HashMap 的 keySet
HashMap的keySet方法返回一個KeySet視圖，這個視圖是非線程安全的。
以下是關鍵代碼片段：
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K, V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (Node<K, V> e : tab) {
while (e != null) {
action.accept(e.key);
e = e.next;
}
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}2. 線程安全性
- Hashtable：由于 Hashtable 本身是線程安全的，其 keySet 也是線程安全的。通過 Collections.synchronizedSet 包裝的 KeySet 確保了對 keySet 的所有操作都是同步的。
- HashMap：HashMap 本身不是線程安全的，其 keySet 也不是。這意味著在多線程環境中使用 HashMap.keySet() 需要外部同步。
3. 性能影響
- Hashtable：由于 Hashtable 和其 keySet 的所有操作都是同步的，這會帶來一定的性能開銷。每次訪問或修改 keySet 都需要獲取鎖，這在高并發環境下會導致鎖競爭和性能下降。
- HashMap：HashMap 的 keySet 是非同步的，因此在單線程環境下性能更高。然而，在多線程環境下，開發者需要手動同步，增加了代碼復雜性和潛在的錯誤風險。
4. 使用場景
- Hashtable：適用于需要線程安全的場景，特別是在多線程環境下使用較小的數據集時。其 keySet 適合在需要線程安全的情況下使用。
- HashMap：適用于單線程環境或開發者能夠確保手動同步的多線程環境。其 keySet 在單線程環境下性能更好，但在多線程環境下使用時需要額外的同步措施。
為什么 Hashtable 哈希沖突不使用紅黑樹？
Hashtable 和 HashMap 在處理哈希沖突時采用了不同的方法，盡管 HashMap 在 Java 8 之后引入了紅黑樹來處理高沖突鏈表的性能問題，但 Hashtable 并沒有做出類似的改動。這背后有幾個原因：
1. 歷史原因
Hashtable 是 Java 1.0 引入的類，而 HashMap 則是在 Java 1.2 中引入的。Hashtable 的設計和實現非常早，那個時候紅黑樹等高級數據結構還沒有廣泛應用于標準庫中。而且，早期的 Java 版本對性能的關注點和現在有所不同。
2. 線程安全的復雜性
Hashtable 是一個線程安全的集合類，其所有方法都使用了 synchronized 關鍵字來保證線程安全。如果在這種同步機制下再引入紅黑樹，增加的復雜性和同步開銷可能會導致性能下降，而不是提升。
紅黑樹的操作（插入、刪除、旋轉等）比鏈表復雜得多，在多線程環境下需要更加精細的同步機制。為了維護紅黑樹的平衡性，操作過程中需要頻繁地進行結構調整，這在高并發環境下可能會引入額外的鎖競爭和性能瓶頸。
3. 維護成本
引入紅黑樹不僅會增加實現的復雜性，還會增加維護成本。Hashtable 作為一個已經穩定使用多年的類，任何大的改動都可能帶來不可預測的風險和兼容性問題。對于已經被廣泛使用和測試的類，保持其現有的實現是一個更為保守和安全的選擇。
4. 使用場景的不同
Hashtable 的主要使用場景是多線程環境下的小規模數據存儲。在這種情況下，鏈表法已經足夠應對大多數情況。而且，隨著數據規模的增長，開發者通常會選擇更為合適的數據結構和并發容器，如 ConcurrentHashMap，而不是依賴傳統的 Hashtable。
總結
本文對 Hashtable 和 HashMap進行了詳細的分析，整理總結如下：
- 線程安全：Hashtable是線程安全的，HashMap不是.
- null 值支持：Hashtable 不允許 null 鍵和值，HashMap 允許。
- keySet 的線程安全：Hashtable 的 keySet 是同步的，而 HashMap 的 keySet 不是。
- 性能：Hashtable 的 keySet 在多線程環境下有性能開銷，而 HashMap 的 keySet 在單線程環境下性能更好。
- 使用場景：Hashtable 適用于需要線程安全的場景，而 HashMap 適用于單線程環境或需要手動同步的多線程環境。
