具有快速索引的數據結構？

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中的鍵和值。我假設你正在尋找最終檢索對象。