具有快速indexOf的数据结构？

Question

我需要一个具有O(1) indexOf操作的有序数据结构。我在数据结构中存储对象指针。有什么想法吗？某种类型的LinkedHashMap？

请参见"indexOf"的含义：List.indexOf(Object)

- bittersoon

Answer 1

这个问题一开始就存在歧义。

1. 如果您能说明快速的indexOf(..)操作是什么意思，那会很好。
2. 您将在集合中存储哪种类型的对象？
3. 查找indexOf(..)是集合唯一的职责吗？

简单来说，一种方法是维护一个索引表，用于索引每个Object或具有索引列表的键。

HashMap<Object, List<Integer>>

再次强调，这个描述比较模糊，如果您能具体说明您要解决的问题的性质，可能会更有帮助。

- kuriouscoder

---

那为什么不再建立另一个数据结构来存储原列表中每个对象的引用呢？ - kuriouscoder

每次我向主数据结构中插入或删除对象时，都必须维护HashMap<Object，List<Integer>>吗？难道没有一种这样的数据结构可以做到这一点吗？ - bittersoon

如果你指的是Java集合中的数据结构，那么不行。如果你指的是是否有用户自定义的数据结构或者实现它的方法，那当然可以。 - kuriouscoder

Answer 2

听起来你想要一个SortedMap，其中TreeMap是参考实现。性能为log(n)，这可能是使用有序结构进行查找时（至少在标准库中）可以获得的最佳性能。

- Sean Patrick Floyd

Answer 3

如果您使用跳表或平衡树，您可以在insert和indexOf中获得O(log n)的时间复杂度。

如果您维护一个已排序的List<Object>来存储要跟踪的项目，以及一个HashMap<Object, Integer>来存储每个项目的起始位置，您可以在O(n) insert的代价下获得O(1)的indexOf。

我没有深入思考过，但我认为不可能同时实现O(1)的insert和O(log n)的indexOf。

- Ben Karel

Answer 4

将对象作为键和值存储在HashMap中。我假设您最终想要检索对象。

- GauravJ

Answer 5

尝试使用PriorityQueue代替，使其有序...

- Gian Santillan

---

HashMap 不是有序的。 - bittersoon