Hashtable 和 HashMap的 keyset 有什么区别？

发表于 更新于 分类于 阅读次数： 本文字数： 5.7k 阅读时长 ≈ 5 分钟

你好，我是猿java。

Hashtable 和 HashMap 是 Java 中最常用的两种哈希表实现，它们都可以用于存储键值对，但在实现细节和使用上有一些显著差异。这篇文章我们从原理、源码来等方面详细的分析它们，以及它们的 keySet 有哪些区别。

Hashtable

Hashtable 的主要特性可以总结成下面 3点：

  1. 线程安全：Hashtable 是线程安全的。它的所有方法都使用 synchronized 关键字进行同步，因此在多线程环境下可以安全使用。
  2. 不允许 null 键和值：Hashtable 不允许任何键或值为 null。如果试图插入 null 键或值，会抛出 NullPointerException。
  3. 哈希冲突解决：使用链表法解决哈希冲突。每个桶（bucket）是一个链表，冲突的元素会被添加到链表的末尾。

源码分析

Hashtable 的主要方法如 put、get 都使用了 synchronized 进行同步。下面代码是put 方法的简化版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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点：

  1. 非线程安全：HashMap 是非线程安全的。在多线程环境下使用时需要手动同步。
  2. 允许 null 键和值：HashMap 允许一个 null 键和多个 null 值。
  3. 哈希冲突解决：同样使用链表法解决哈希冲突，但在 Java 8 之后，当链表长度超过一定阈值（默认是8）时，会将链表转换为红黑树，以提高性能。

HashMap 源码分析

HashMap 的主要方法如 put 和 get 都没有同步机制。下面代码是put 方法的简化版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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. 实现方式

Hashtable 的 keySet

Hashtable的keySet方法返回一个KeySet视图，这个视图是通过 Collections.synchronizedSet 包装而成的，这意味着 keySet 本身是线程安全的。

以下是关键代码片段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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();
    }
}

HashMap 的 keySet

HashMap的keySet方法返回一个KeySet视图，这个视图是非线程安全的。

以下是关键代码片段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 适用于单线程环境或需要手动同步的多线程环境。

学习交流

如果你觉得文章有帮助，请帮忙转发给更多的好友，或关注公众号：猿java，持续输出硬核文章。

drawing