具有快速索引的数据结构？

Question

我需要一个带有O（1）indexOf操作的有序数据结构。我将对象指针存储在数据结构中。有任何想法吗？某种LinkedHashMap？

看什么 “的indexOf” 是指：List.indexOf(Object)

Answer 1

这个问题是含糊不清的开始。

1. 这将是很好，如果你可以通过快速indexOf(..)操作来限定你的意思。
2. 你要在集合中存储什么样的对象？
3. 发现indexOf(..)集合的唯一责任。

简而言之，做到这一点的一种方法是维护一个将索引每个Object或键索引的索引。

HashMap<Object, List<Integer>> 

再一次，这是模糊的，如果你指定了你正试图解决的问题的确切性质，可能会有所帮助。

Answer 2

尝试使用的PriorityQueue，而不是让它oredered ...

Answer 3

如果您使用跳过列表或平衡树，您可以获得O（log n）insert和indexOf。

如果你保持一个排序List<Object>来存储你想跟踪，具有HashMap<Object, Integer>一起存储每个项目的起始位置的项目，你可以得到O（1）indexOf换取O（n）的insert。

我还没有深入考虑过，但我不认为有可能获得O（1）插入和O（log n）indexOf。

Answer 4

听起来像你想SortedMap,TreeMap是参考实现。性能为log(n)，这可能是您使用有序结构查找（至少在标准库中）的最佳选择。

Answer 5

将对象存储为HashMap中的键和值。我假设你正在寻找最终检索对象。