Java中哈希和LinkedHashSet的意义是什么？

Question

我知道关于LinkedHashSet以下几点：

• 它维护插入顺序
• 使用LinkedList来保持顺序
• 我的问题是哈希如何应用？

我了解如果使用哈希，则会涉及到桶的概念。

然而，从JDK中检查代码来看，LinkedHashSet实现仅包含构造函数，没有实现，所以我猜所有逻辑都在HashSet中发生了?

• 那么，默认情况下HashSet使用LinkedList吗？

让我这样问… 如果目标是编写一个集合：

1. 维护唯一值
2. 使用链表保留插入顺序 那么…可以轻松地在不使用哈希的情况下完成，也许我们可以称这个集合为LinkedSet

我看到了一个类似的问题HashSet和LinkedHashSet之间的区别是什么但并没有太大的帮助。

请让我知道是否需要进一步解释我的问题。

- Lav

---

@JanDvorak：你为什么这么说？“public”“HashSet”构造函数都将“HashSet”初始化为由非链接的“HashMap”支持，然后“LinkedHashSet”只是调用一个特殊的、包私有的构造函数，该构造函数使用“LinkedHashMap”代替。 - Louis Wasserman

Answer 1

代码示例

Set<Registeration> registerationSet = new LinkedHashSet<>();
registerationSet.add(new Registeration());

Line2的解释。

1. 计算Registeration对象的hashCode。
2. 在registerationSet中搜索hashCode以定位桶。
3. 检查短列表桶中是否有相等的对象。
   • 3.1.如果找到相等的对象，则用新对象的引用替换它。
   • 3.2.如果没有找到，则在桶中追加/添加Registeration对象的引用。

与此并行，

列表维护所有插入元素的条目顺序/队列

1. 始终将新引用添加到末尾
2. 在替换的情况下（上述3.1），删除先前的出现。

- Akshat Gupta

Answer 2

这是一种“有趣”的实现方式。LinkedHashSet的构造函数引用了HashSet中的包私有构造函数，该构造函数设置了维护迭代顺序的数据结构（即LinkedHashMap）。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

API的设计者可以将此构造函数公开为public，并提供适当的文档，但我猜他们希望代码更加“自我说明”。

- Perception

---

为什么要将此公开？这些是实现细节，可能不应该公开。 - Louis Wasserman

@LouisWasserman 为什么不将其链接能力作为合同的一部分？ - John Dvorak

@JanDvorak：链接功能是LinkedHashSet合同的一部分，而不是HashSet的。为什么要混淆这两个呢？当然，将它们混合在一起对于_实现_来说很方便，但这并不是用户需要了解的内容。此外，未来该实现可能需要更改，如果JDK锁定自己公开支持该构造函数，则无法更改。 - Louis Wasserman

为什么不公开呢？当然，boolean dummy 需要改成 boolean sorted（或类似的），并且逻辑需要稍微改一下，以便在 sorted=false 时调用现有的 HashSet(int, float)。 - Perception

@Perception 因为如果这样，每个实现（Sun、OpenJDK、MsJava...）都需要提供那个构造函数，只因为一个实现可以这样做。 - John Dvorak

Answer 3

如果你仔细观察，你会发现它实际上使用了一些HashSet上的受保护构造函数，这些构造函数只是为了它而存在，不是常规的构造函数。例如：

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

因此，用于支持LinkedHashSet的keySet实际上来自于LinkedHashMap的实现，而不是像普通的HashSet一样来自于常规HashMap。它实际上并不使用java.util.LinkedList，而是在桶内容（Map.Entry）的实现中维护形成列表的指针。

316    private static class Entry<K,V> extends HashMap.Entry<K,V> {
317        // These fields comprise the doubly linked list used for iteration.
318        Entry<K,V> before, after;
319
320        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
321            super(hash, key, value, next);
322        }

散列技术的出现是因为它能够轻松地创建一个强制唯一性并且在大多数操作中提供常数时间性能的集合。当然，我们可以只使用链接列表来添加唯一性检查，但是几个操作的时间复杂度将变为O（N），因为您必须迭代整个列表以检查重复项。

- Affe

Answer 4

错误。 LinkedHashSet 的实现实际上全部在 LinkedHashMap 中。(而 HashSet 的实现实际上全部在 HashMap 中。惊讶！) HashSet 没有任何链接列表。

完全可以编写由链接列表支持的 LinkedSet 集合，使元素保持唯一 - 只是其性能会非常差。

- Louis Wasserman

---

我在实现方面观察到了一些不同之处：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedHashSet.java#LinkedHashSet.%3Cinit%3E%28%29 - John Dvorak

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashSet.java#HashSet.%3Cinit%3E%28int%2Cfloat%2Cboolean%29 - John Dvorak

@JanDvorak：追溯到实际调用的HashSet构造函数。 HashSet只是作为一个围绕Map的包装器实现的，而LinkedHashSet只是确保该映射是LinkedHashMap。 - Louis Wasserman

因此，LinkedHashSet 的实现实际上在 HashSet 类中，而 LinkedHashSet 类本身只是一个薄包装器。 - John Dvorak

实现实际上是在LinkedHashMap和HashMap中完成的，HashSet本身只是大多数情况下包装了HashMap.keySet()。 - Affe

@JanDvorak：LinkedHashSet只是一个薄包装，但更重要的是，HashSet也是一个围绕Map的薄包装。 - Louis Wasserman

Answer 5

针对你的问题，有一个具体的答案：

• 哈希如何在 LinkedHashSet 中发挥作用？

Java文档是这样说的...

• 和 HashSet 一样，它提供了基本操作（add、contains 和 remove）的常数时间性能，假设哈希函数将元素适当地分散在桶中。
• 这个链表定义了迭代顺序，即元素插入集合的顺序（插入顺序）。

哈希码访问的桶用于加速随机访问，LinkedList 实现用于返回一个按插入顺序排列的元素迭代器。

希望我已经回答了你的问题？

- austindz