Java 数据结构：IndexedSet 或 HashList

Question

是否有Java数据结构满足以下要求？

1. 索引访问。 （即，我应该能够使用 get(i) 检索对象）
2. 恒定时间 get() & contains() 方法
3. 应强制排序（由 Comparator 强制执行）
4. 应该是可变的

我在 Oracle's JDK 或 Guava 中找不到任何开箱即用的上述功能

List 提供索引访问和某种排序但不提供恒定时间 contains()。 SortedSet 和 SortedMap 提供恒定时间 contains() 和排序但不提供索引访问！

我是不是遗漏了什么或者是否有任何数据结构可以被操纵以提供上面列出的功能？

我目前的解决方案：

HashMap 和 ArrayList 的组合 => 我使用 ArrayList 来存储提供索引访问的排序键，并使用 HashMap 用于恒定时间 contains() 方法。我只是想确保我不是在尝试重新发明已经完成的东西

为什么我需要这个：

我们称这个数据结构为SortedDataStore 我正在开发一个 Android 应用程序，其中的大部分 UI 是一个项目列表，这些项目是从本地数据库中提取的。 （本地数据库从远程服务器获取数据）。 UI 使用 RecyclerView 填充，我需要恒定时间索引访问以从我的 SortedDataStore 获取对象并填充视图。由于项目的顺序是根据其属性决定的，因此需要进行排序。数据也得到了很多更新（项目被修改、删除和新项目被添加）。当新数据进来时，我检查我的 SortedDataStore 是否应该删除、添加或修改（并移动到另一个索引），为此我需要恒定时间 contains() 和可变性。

Answer 1

一个ArrayList满足三个要求：

• 索引访问，使用 get(int i)
• 恒定时间访问，使用get(int i)
• 按插入排序，使用 add(Object o)

Answer 2

• 根据您所描述的预期数据大小，ArrayList 似乎在实践中实际上没问题——您的数据不够大，线性时间因素无关紧要就这么多。
• 否则，你做的是正确的解决方案；没有提供一次性完成所有这些的可变数据结构。
• 只要能避免变异，Guava的ImmutableSet就可以满足你剩下的要求。您可以使用 ImmutableSet.asList().get(index) 在 O(1) 时间内按索引获取元素，否则它支持 O(1) 包含和插入顺序。

Answer 3

Java's LinkedHashMap 如果您使用索引作为键，则满足您的要求。

1. 索引访问：使用get(i)
2. 恒定时间 get() 和 contains() 方法：使用 get(i) 和 containsKey()
3. 应该强制排序（由比较器强制执行）：见注释
4. 应该是可变的：是

备注

如果您想要自定义比较器，请在子对象的 class 上扩展 Comparable 接口和 @Override compareTo() 方法。

comparator for LinkedHashMap