java - (Java) 快速插入、删除和随机选择的数据结构

Question

我需要一个支持O(1)以下操作的数据结构:

1. myList.添加(项目)
2. myList.remove(Item.ID) ==> 它实际上需要随机访问

3. myList.getRandomElement()(等概率)

   --(请注意，getRandomElement() 并不意味着随机访问，它只是意味着:“随机给我一个项目，概率相等”)

   <

请注意，我的项目是唯一的，所以我不关心是否使用了 List 或 Set。我检查了一些java数据结构，但似乎没有一个是解决方案:

1. HashSet 在 O(1) 中支持 1,2，但它不能在 O(1) 中给我一个随机元素。我需要调用 mySet.iterator().next() 来选择一个随机元素，这需要 O(n)。
2. ArrayList 在 O(1) 中执行 1,3，但它需要进行线性搜索才能找到我要删除的元素，尽管它需要 O(n)

有什么建议吗？请告诉我应该调用哪些函数？

如果 java 没有这样的数据结构，我应该使用哪种算法来达到这样的目的？

Answer 1

如果内存允许，您可以使用 HashMap 和 ArrayList 的组合，如下所示:-

1. Store numbers in ArrayList arr as they come.
2. Use HashMap to give mapping arr[i] => i
3. While generating random select random form arrayList

删除:-

1. check in HashMap for num => i
2. swap(i,arr.size()-1)
3. HashMap.remove(num)
4. HashMap(arr[i])=> i
5. arr.remove(arr.size()-1)

所有操作都是O(1) 但额外的O(N) 空间