java - 有没有像ListHashMap这样的数据结构？

Question

我一直在努力寻找一种数据结构:

1. 让我在 O(1) 时间内检查重复项 (HashSet)，
2. 保留插入顺序，并且
3. 请允许我获取该有序列表的一个子集。

我发现的最接近的东西是 LinkedHashSet，但它没有实现 List 接口(interface)并允许我调用 List 函数(如 subList)。我找不到这样的结构有什么原因吗？我即将实现我自己的 LinkedHashSet 版本，但使用的是 ArrayList(与支持链接列表的 LinkedHashSet 形成对比)。我还从 org.antlr.misc 库中找到了 OrderedHashSet ，但是由于没有实现所需的 subList 函数，这也不够......所以我真的很困惑为什么这还没有被需要？或者我只是没有想到要搜索的正确名称？

编辑:我不仅试图找到可以满足此要求的现有结构，而且在没有结构的情况下，我试图找出它不存在的原因。谁能回答这个问题就可以获得已接受的答案，因为我已经知道如何实现它了:)

编辑 2:抱歉抱歉，我应该更清楚我的第一个要求，我真的只需要非常有效地检查重复项。对我来说已经晚了。

Answer 1

基本上，您找到的是提供 O(1) 点查找但提供高效范围扫描(迭代)的东西。在数据库领域，这种东西有时被称为clustered-index。 ，其中数据使用一些查找结构进行组织，例如 B-Tree或 hash index ，但叶节点或索引的条目按某种特定顺序排序(在您的情况下，它按插入顺序排序)。下面显示了一个聚簇 B 树的示例，其中@Itay Maman 的解决方案是一个聚簇哈希索引的示例。

在 Java 中，没有这样的类本身就可以满足您的需求，这可能是因为它的复杂性——很难(或几乎不可能)有一个这样的实现最适合所有工作负载(例如您发布的频率范围扫描，你多久发布一次点查找，它是否允许多读者和多作者？......等等)但是，这里有一些可能的解决方案，取决于你的用例。

1. 如果在大多数情况下您并不真正关心第 3 项，则使用 LinkedHashMap，并使用 LinkedHashMap 提供的正常迭代来执行第 3 项。

2. 如果您关心所有项目的性能并且从不执​​行删除/更新，那么最简单的方法可能是同时使用 HashMap 和 ArrayList 将您的数据表示为聚簇索引。每次插入都是对HashMap的插入+对ArrayList的追加，HashMap的值就是ArrayList的索引。这可为您提供最佳读取性能，但您需要解决更新/删除问题(如果有)，可能是通过将 ArrayList 替换为子数组的链表。

3. 在极端情况下，你确实有删除/更新，想要支持多线程访问，你甚至想要持久化，那么最好的可能是使用开源的嵌入式持久化键值存储，比如作为RocksDB或 LevelDB ，一个嵌入式键值存储，用于快速存储，如 RAM 或闪存(它也适用于磁盘工作负载。)虽然它们都是用 C++ 实现的，但它们确实具有 Java 绑定(bind)(例如，Java 中 RocksDB 的介绍 page。)

当然，如果您愿意重新实现某些东西，那么定制的 LinkedHashMap 可能是最简单的。只需添加一个不同的迭代器构造函数，它允许您使用 O(1) 哈希在位于任何特定条目处开始迭代。