適用於快速獲取和快速刪除的java集合

我想知道是否有適合快速獲取（通過索引）和「快速」刪除的java界面。「快」我的意思是比O(n)好。適用於快速獲取和快速刪除的java集合

編輯：get方法只需要從集合中隨機選擇一個元素。此外，標題應該說「收集」，而不是「界面」。

2013-10-05 Alexandre Vandermonde

您是否在談論順序容器，其中元素順序在移除過程中不會更改？好吧，存在'java.util.List'接口，但據我所知，沒有Java附帶的實現。 – nosid

是的，沒錯。在移除過程中元素的順序不應該改變。我目前使用的是List，但是對於ArrayList，remove是O（n），對於LinkedList，get是O（n）。 –

@Dave Newton感謝您的編輯！再見，爲什麼Stack Overflow不支持LaTeX？ –

平衡二叉搜索樹有O（log n）「get」和「remove」操作。哈希表在O（1）時間內實現這些相同的操作。在Java中，您可以使用TreeMap或HashMap類。例如：

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

如果您不關心物品的順序，您可以使用ArrayList。自然地「得到」是O（1）。刪除一個項目將最後一個項目移動到您刪除的項目的位置，這會給您一個O（1）「刪除」。那就是：

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

來源

2013-10-05 19:50:05 Joni

這可能是真的，讓我們看看OP是否確認。 – Joni

@Joni感謝您的建議！我不得不考慮如何實現TreeMap，因爲我並不想跟蹤指數，而只是使用get方法進行隨機選擇。關於ArrayList：是移動O（1），然後？ –

@AlexandreVandermonde，通過「移動」我的意思是刪除最後一個項目，並設置您要刪除的索引：兩個操作是O（1）。 – Joni

我不知道我是否理解你是如何推斷出你想從哪個索引獲取對象的。

如果您正在尋找快速get（）和快速remove（）操作 - 標準HashMap<Object, Object>（即將對象本身用作關鍵字）有什麼問題？

那麼你的get（）/刪除（）操作將取決於您的實現的hashCode（）和equals（）方法，可以是O（1）

來源

2013-10-05 20:02:13

這樣的hashCode（）的實現看起來如何？無可否認，我並不習慣使用HashMap：s。 –

閱讀HashMap（Google）的hashCode（）和equals（）實現。理想情況下（對HashMap存儲最好）hashCode（）的實現應返回對象狀態的唯一整數表示，例如：唯一對象ID可能是一個不錯的選擇。然後，hashCode（）將定義對象將存儲在哪個HashMap存儲桶中，因此您將能夠通過存儲桶索引（如數組索引）直接訪問對象 –

好的，謝謝！我會看看它。 –

我不相信存在的實現List在JDK中比查找和刪除的O（n）快。

可能適合您的數據結構是rope，indexable skiplist和。您可能能夠找到可以在網絡上使用的實現，或者在主要集合庫（Guava，Commons Collections，Trove等）中使用這些實現。但是，如果你真正想要的不是快速查找和刪除，而是快速隨機選擇和刪除，那麼你可以使用開放地址的哈希表。你可以通過值來獲得O（1）查找（不是你關心的），O（1）通過值去除，以及O（1）選擇一個隨機值。您可以通過在表中選擇一個隨機插槽並使用其中的條目來選擇一個隨機值;如果它是空的，請再試一次。

來源

2013-10-05 20:35:00

適用於快速獲取和快速刪除的java集合

回答

相關問題