6

我知道有关linkedHashSet的以下内容

  • 它维护插入顺序
  • 使用 LinkedList 保持顺序
  • 我的问题是散列是如何出现的？

我明白如果使用散列，那么桶的概念就会出现

但是，通过检查JDK中的代码， LinkedHashSet的实现似乎只包含构造函数而没有实现，所以我猜所有的逻辑都发生在HashSet中？

  • 所以 hashSet 默认使用 LinkedList 吗？

让我这样提出我的问题......如果目标是写一个集合

  1. 保持独特的价值观
  2. 使用链表保留插入顺序 THEN ...无需散列即可轻松完成...也许我们可以将此集合称为 LinkedSet

看到了一个类似的问题，HashSet 和 LinkedHashSet 有什么区别，但不是很有帮助

如果我需要更多解释我的问题，请告诉我

4

5 回答 5

1

如果您仔细观察，您会发现它实际上在 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<K,V>）

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)，因为您必须迭代整个列表以检查重复项。

于 2013-02-01T04:18:21.987 回答
1

错误的。的实现LinkedHashSet真的全在LinkedHashMap. （而且实施HashSet真的全在HashMap.Le喘气！）

HashSet根本没有链表。

完全有可能编写一个LinkedSet由链表支持的集合，以保持元素的唯一性——只是它的性能会很糟糕。

于 2013-02-01T04:12:28.583 回答
1

这是一个“有趣”的实现。LinkedHashSet 的构造函数遵循包私有构造函数，在HashSet该构造函数中设置数据结构（LinkedHashMap）以维护迭代顺序。

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

API 设计者可以简单地将这个构造函数公开，并带有适当的文档，但我猜他们希望代码更加“自我记录”。

于 2013-02-01T04:14:22.713 回答
1

代码示例

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

Line2的解释。

  1. 计算注册对象的 hashCode
  2. 在registerationSet中搜索hashCode来定位bucket
  3. 检查入围存储桶中的相等对象
    • 3.1。如果找到相等，则将其替换为新对象引用
    • 3.2. 如果没有找到，在桶中追加/添加注册对象的引用

与之平行，

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

  1. 总是，在末尾添加新的引用
  2. 在替换的情况下（上面的 3.1.），删除以前的事件。
于 2017-09-10T19:13:40.563 回答
0

对于您的问题的具体答案

  • 哈希是如何出现的？（在 LinkedHashSet 中）

Java 文档怎么说...

  • 与 HashSet 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数在桶中正确地分散元素。
  • 该链表定义了迭代顺序，即元素插入集合的顺序（插入顺序）。

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

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

于 2013-02-01T05:13:18.477 回答