Hashtable 和 HashMap 是 Java 中最常用的兩種哈希表實(shí)現(xiàn)，它們都可以用于存儲(chǔ)鍵值對(duì)，但在實(shí)現(xiàn)細(xì)節(jié)和使用上有一些顯著差異。這篇文章我們從原理、源碼來(lái)等方面詳細(xì)的分析它們，以及它們的 keySet 有哪些區(qū)別。

Hashtable

Hashtable 的主要特性可以總結(jié)成下面 3點(diǎn)：

• 線程安全：Hashtable 是線程安全的。它的所有方法都使用 synchronized 關(guān)鍵字進(jìn)行同步，因此在多線程環(huán)境下可以安全使用。
• 不允許 null 鍵和值：Hashtable 不允許任何鍵或值為 null。如果試圖插入 null 鍵或值，會(huì)拋出 NullPointerException。
• 哈希沖突解決：使用鏈表法解決哈希沖突。每個(gè)桶（bucket）是一個(gè)鏈表，沖突的元素會(huì)被添加到鏈表的末尾。

源碼分析

Hashtable 的主要方法如 put、get 都使用了 synchronized 進(jìn)行同步。下面代碼是put 方法的簡(jiǎn)化版本：

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 的主要特性可以總結(jié)成下面 3點(diǎn)：

• 非線程安全：HashMap 是非線程安全的。在多線程環(huán)境下使用時(shí)需要手動(dòng)同步。
• 允許 null 鍵和值：HashMap 允許一個(gè) null 鍵和多個(gè) null 值。
• 哈希沖突解決：同樣使用鏈表法解決哈希沖突，但在 Java 8 之后，當(dāng)鏈表長(zhǎng)度超過(guò)一定閾值（默認(rèn)是8）時(shí)，會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)，以提高性能。

HashMap 源碼分析

HashMap 的主要方法如 put 和 get 都沒(méi)有同步機(jī)制。下面代碼是put 方法的簡(jiǎn)化版本：

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 的區(qū)別

在分析了 Hashtable 和 HashMap之后，我們?cè)賮?lái)對(duì)比兩者keySet的差異，總結(jié)如下：

• Hashtable 的 keySet 返回一個(gè) KeySet 視圖，它是一個(gè)同步的集合視圖。當(dāng)你對(duì)這個(gè)集合進(jìn)行操作時(shí)，會(huì)同步到原始的 Hashtable。
• HashMap 的 keySet 返回一個(gè) KeySet 視圖，它是非同步的集合視圖。如果在多線程環(huán)境下使用，需要手動(dòng)同步。

為了更詳細(xì)地探討 Hashtable 和 HashMap 的 keySet 的區(qū)別，我們需要從 實(shí)現(xiàn)方式、線程安全性、性能影響和使用場(chǎng)景幾個(gè)方面來(lái)分析。

1. 實(shí)現(xiàn)方式

(1) Hashtable 的 keySet

Hashtable的keySet方法返回一個(gè)KeySet視圖，這個(gè)視圖是通過(guò) Collections.synchronizedSet 包裝而成的，這意味著 keySet 本身是線程安全的。

以下是關(guān)鍵代碼片段：

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方法返回一個(gè)KeySet視圖，這個(gè)視圖是非線程安全的。

以下是關(guān)鍵代碼片段：

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 也是線程安全的。通過(guò) Collections.synchronizedSet 包裝的 KeySet 確保了對(duì) keySet 的所有操作都是同步的。
• HashMap：HashMap 本身不是線程安全的，其 keySet 也不是。這意味著在多線程環(huán)境中使用 HashMap.keySet() 需要外部同步。

3. 性能影響

• Hashtable：由于 Hashtable 和其 keySet 的所有操作都是同步的，這會(huì)帶來(lái)一定的性能開(kāi)銷。每次訪問(wèn)或修改 keySet 都需要獲取鎖，這在高并發(fā)環(huán)境下會(huì)導(dǎo)致鎖競(jìng)爭(zhēng)和性能下降。
• HashMap：HashMap 的 keySet 是非同步的，因此在單線程環(huán)境下性能更高。然而，在多線程環(huán)境下，開(kāi)發(fā)者需要手動(dòng)同步，增加了代碼復(fù)雜性和潛在的錯(cuò)誤風(fēng)險(xiǎn)。

4. 使用場(chǎng)景

• Hashtable：適用于需要線程安全的場(chǎng)景，特別是在多線程環(huán)境下使用較小的數(shù)據(jù)集時(shí)。其 keySet 適合在需要線程安全的情況下使用。
• HashMap：適用于單線程環(huán)境或開(kāi)發(fā)者能夠確保手動(dòng)同步的多線程環(huán)境。其 keySet 在單線程環(huán)境下性能更好，但在多線程環(huán)境下使用時(shí)需要額外的同步措施。

為什么 Hashtable 哈希沖突不使用紅黑樹(shù)？

Hashtable 和 HashMap 在處理哈希沖突時(shí)采用了不同的方法，盡管 HashMap 在 Java 8 之后引入了紅黑樹(shù)來(lái)處理高沖突鏈表的性能問(wèn)題，但 Hashtable 并沒(méi)有做出類似的改動(dòng)。這背后有幾個(gè)原因：

1. 歷史原因

Hashtable 是 Java 1.0 引入的類，而 HashMap 則是在 Java 1.2 中引入的。Hashtable 的設(shè)計(jì)和實(shí)現(xiàn)非常早，那個(gè)時(shí)候紅黑樹(shù)等高級(jí)數(shù)據(jù)結(jié)構(gòu)還沒(méi)有廣泛應(yīng)用于標(biāo)準(zhǔn)庫(kù)中。而且，早期的 Java 版本對(duì)性能的關(guān)注點(diǎn)和現(xiàn)在有所不同。

2. 線程安全的復(fù)雜性

Hashtable 是一個(gè)線程安全的集合類，其所有方法都使用了 synchronized 關(guān)鍵字來(lái)保證線程安全。如果在這種同步機(jī)制下再引入紅黑樹(shù)，增加的復(fù)雜性和同步開(kāi)銷可能會(huì)導(dǎo)致性能下降，而不是提升。

紅黑樹(shù)的操作（插入、刪除、旋轉(zhuǎn)等）比鏈表復(fù)雜得多，在多線程環(huán)境下需要更加精細(xì)的同步機(jī)制。為了維護(hù)紅黑樹(shù)的平衡性，操作過(guò)程中需要頻繁地進(jìn)行結(jié)構(gòu)調(diào)整，這在高并發(fā)環(huán)境下可能會(huì)引入額外的鎖競(jìng)爭(zhēng)和性能瓶頸。

3. 維護(hù)成本

引入紅黑樹(shù)不僅會(huì)增加實(shí)現(xiàn)的復(fù)雜性，還會(huì)增加維護(hù)成本。Hashtable 作為一個(gè)已經(jīng)穩(wěn)定使用多年的類，任何大的改動(dòng)都可能帶來(lái)不可預(yù)測(cè)的風(fēng)險(xiǎn)和兼容性問(wèn)題。對(duì)于已經(jīng)被廣泛使用和測(cè)試的類，保持其現(xiàn)有的實(shí)現(xiàn)是一個(gè)更為保守和安全的選擇。

4. 使用場(chǎng)景的不同

Hashtable 的主要使用場(chǎng)景是多線程環(huán)境下的小規(guī)模數(shù)據(jù)存儲(chǔ)。在這種情況下，鏈表法已經(jīng)足夠應(yīng)對(duì)大多數(shù)情況。而且，隨著數(shù)據(jù)規(guī)模的增長(zhǎng)，開(kāi)發(fā)者通常會(huì)選擇更為合適的數(shù)據(jù)結(jié)構(gòu)和并發(fā)容器，如 ConcurrentHashMap，而不是依賴傳統(tǒng)的 Hashtable。

總結(jié)

本文對(duì) Hashtable 和 HashMap進(jìn)行了詳細(xì)的分析，整理總結(jié)如下：

• 線程安全：Hashtable是線程安全的，HashMap不是.
• null 值支持：Hashtable 不允許 null 鍵和值，HashMap 允許。
• keySet 的線程安全：Hashtable 的 keySet 是同步的，而 HashMap 的 keySet 不是。
• 性能：Hashtable 的 keySet 在多線程環(huán)境下有性能開(kāi)銷，而 HashMap 的 keySet 在單線程環(huán)境下性能更好。
• 使用場(chǎng)景：Hashtable 適用于需要線程安全的場(chǎng)景，而 HashMap 適用于單線程環(huán)境或需要手動(dòng)同步的多線程環(huán)境。