我經常*發現自己在需要具有下述性能的數據結構組成：無需更換採摘在Java
- 可以與n個對象中的O（N）的數組進行初始化。
- 可以獲得O（1）中的隨機元素，在此操作之後，從結構中移除摘取的元素 。 （沒有替換）
- 一個可以撤消p操作 '無需更換採摘' 在O（P）
- 一個可以從該結構中O上卸去的特定對象（例如，通過ID）（的log（n））
- 可以獲得當前在 O（n）中的結構中的對象的數組。
複雜其他行動（甚至可能）（例如插入）沒有關係。除了複雜性之外，它還應該對少量的n有效。
任何人都可以給我指導實施這樣的結構嗎？我目前實現了一個具有以上所有屬性的結構，除了元素的挑選需要O（d）和d過去的選擇數（因爲我明確地檢查它是否'尚未挑選'）。我可以找出允許在O（1）中選擇的結構，但這些結構至少在其他一個操作中具有更高的複雜性。
BTW： 請注意，上面的O（1）意味着複雜度獨立於#earlier選取的元素並且獨立於總的#elements。
*蒙特卡洛算法（從n個元素的'集合'中迭代選擇p個隨機元素）。
好的，與0verbose的答案相同，只需要一個簡單的修復以獲得O（1）隨機查找。創建一個存儲相同n個對象的數組。現在，在HashMap中，存儲這些對。例如，假設你的對象（字符串爲簡單起見）有：
{"abc" , "def", "ghi"}
創建
List<String> array = ArrayList<String>("abc","def","ghi")
具有以下值創建一個HashMap地圖：
for (int i = 0; i < array.size(); i++)
{
map.put(array[i],i);
}
O（1）隨機查找很容易通過選擇數組中的任何索引來實現。出現的唯一複雜情況是當你刪除一個對象時。爲此，請執行以下操作：
在map中查找對象。獲取它的數組索引。可以稱爲索引i（map.get(i)） - O（1）
將數組[數組大小-1]（數組中的最後一個元素）進行交換數組[i]。由1減少陣列的大小（因爲少了一個數量現在） - O（1）
更新新對象的在陣列的位置i在map（map.put索引（數組[I ]，I）） - O（1）
我對Java和CPP符號的混合道歉，希望這有助於
HashMap的複雜度爲O（1），用於插入和刪除。 您指定了很多工作，但所有的人都沒什麼然後在插入，刪除和遍歷：
可以用n個對象的數組初始化爲O（N）。
n * O（1）插入。 HashMap中是細
一個可以在 O（1），此操作之後的拾取 元件從結構中除去得到一個隨機元素。 （無替代）
這是唯一需要O（n）的操作。
一個可以復原中的p O（P）操作 '沒有 更換採摘'
它是一個插入操作：O（1）。
一個可以刪除一個特定的對象（例如通過 id）的從該結構中爲O（log（N））
O（1）。
可以獲得當前在O（n）結構中的對象數組 。
可以遍歷爲O的HashMap中（N）
編輯：拾取在O隨機元素（n）的 例如：
HashMap map ....
int randomIntFromZeroToYouHashMapSize = ...
Collection collection = map.values();
Object[] values = collection.toArray();
values[randomIntFromZeroToYouHashMapSize];
如何的陣列（或ArrayList ）分爲「挑選」和「未挑選」？你跟蹤邊界的位置，然後選擇，在邊界下方生成一個隨機索引，然後（因爲你不關心訂單），將該索引處的項目與最後一個未選中的項目交換，並減小邊界。要取消，只需增加邊界。
更新：忘記O（log（n））去除。但是，如果您將ID號的HashMap保留爲索引，那麼不那麼難，只需要一點點內存 - 很貴。
如果你在線上探討，你會發現各種IndexedHashSet實現，所有的工作或多或少的這個原則 - 一個數組或ArrayList加HashMap。
（我喜歡看到一個更優雅的解決方案，但是，如果存在的話）
更新2：嗯......或者再次進行實際的去除變成爲O（n），如果你必須重新複製數組或將它們轉移？
一個非常有趣的結構。雖然刪除不能保證是O（log（n）），但O（n）據我所知。它實際上類似於thrashgod的方法，但更有效率，因爲內存分配一次。另外，如果O（1）被索引，則可以在O（1）中刪除未使用的元素。 – codelidoo
@codelidoo：由於'subList（）'返回一個視圖，我更喜歡'ArrayList'。正如你注意到的，移除仍然是O（n）。 – trashgod
啊，我忘記了刪除部分。如果你想在O（log（n））中刪除，你可以添加一個從對象（或ID）到索引的HashMap。雖然對於實際的移除，你必須複製陣列以縮小間距（或者移動到新的陣列，或者移動所有的東西，最後留下「死亡」空間）。 –
這是我的上ArrayList使用Collections.shuffle()的分析：
✔可以與n個對象中的O（N）的數組進行初始化。
是的，雖然成本是攤銷除非預先知道n。
✔可以獲得O（1）中的隨機元素，在此操作之後，拾取的元素將從結構中移除，而不需要替換。
是的，選擇混洗陣列中的最後一個元素;用剩餘元素的subList()替換陣列。
✔可以在O（p）中取消p'picking without replacement'操作。
是的，通過add()將元素附加到此列表的末尾。
❍可以從O（log（n））中的結構中刪除特定對象（例如通過id）。
不，它看起來像O（n）。
✔可以獲取O（n）中結構中當前對象的數組。
是的，使用toArray()看起來很合理。
什麼是N，p，和d的一些值？ – Ron