java - 适用于快速获取和快速删除的 java 集合

Question

我想知道是否有适合“快速”获取（按索引）和“快速”删除的 Java 接口。“快”是指比O(n).

编辑： get 方法仅用于从集合中随机选择一个元素。此外，标题应该说“集合”而不是“接口”。

Answer 1

平衡二叉搜索树具有 O(log n) 的“获取”和“删除”操作。哈希表在 O(1) 时间内实现了这些相同的操作。在 Java 中，您可以使用TreeMap或HashMap类。例如：

TreeMap<Integer, String> map = new TreeMap<>();
map.put(0, "hello");
map.put(1, "world");
map.remove(0);

如果您不关心项目的顺序，您可以使用ArrayList. 自然地，“get”是 O(1)。要删除一个项目，请将最后一个项目移动到您删除的那个位置，这会给您一个 O(1) 的“删除”。那是：

temp = list.remove(list.size()-1);
return list.set(index, temp);

Answer 2

我不确定我是否理解您建议如何推断要从中获取对象的索引。

如果您正在寻找快速 get() 和快速 remove() 操作 - 标准有什么问题HashMap<Object, Object>（即使用对象本身作为键）？

然后您的 get()/remove() 操作将取决于您对 hashCode() 和 equals() 方法的实现，并且可以是 O(1)

Answer 3

我不相信ListJDK 中的实现在查找和删除方面都比 O(n) 更快。

可能适合您的数据结构是绳索、可索引的跳过列表和enfilade。您可能可以在网络上或在主要收藏库之一（Guava、Commons Collections、Trove 等）中找到可以使用的实现。

但是，如果您真正想要的不是快速查找和删除，而是快速随机选择和删除，您可以使用开放寻址哈希表。你得到 O(1) 的按值查找（不是你关心的），O(1) 的按值删除，以及 O(1) 的随机值选择。您可以通过在表中选择一个随机槽并使用其中的条目来选择一个随机值；如果它是空的，请再试一次。