(Java) 数据结构，用于快速插入、删除和随机选择

Question

我需要一个数据结构，支持以下操作的时间复杂度为 O(1):

1. myList.add(Item)
2. myList.remove(Item.ID) ==> 实际上需要随机访问

3. myList.getRandomElement()（等概率地）

   --(请注意，getRandomElement() 不意味着随机访问，它只是表示：“随机给我一个元素，概率相等”)

请注意，我的元素是唯一的，因此我不关心使用 List 还是 Set。

我检查了一些 Java 数据结构，但似乎没有一个是解决方案：

1. HashSet 支持 1、2 的时间复杂度为 O(1)，但它无法在 O(1) 的时间内给我一个随机元素。我需要调用 mySet.iterator().next() 来选择一个随机元素，这需要 O(n) 的时间复杂度。
2. ArrayList 支持 1、3 的时间复杂度为 O(1)，但它需要进行线性搜索才能找到要删除的元素，尽管它的时间复杂度为 O(n)

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

如果 Java 没有这样的数据结构，我应该使用哪种算法来实现此目的？

- Ali

Answer 1

您可以使用以下方式结合使用HashMap和ArrayList来存储数字，如果内存容许的话：

1. 将数字作为它们出现时在ArrayList arr中存储。

2. 使用HashMap将映射关系 arr[i] => i 给出。

3. 在生成随机数时从ArrayList中选择随机数。

删除：

1. 在HashMap中检查num => i。

2. 交换(i,arr.size()-1)。

3. HashMap.remove(num)。

4. HashMap(arr[i])=> i。

5. arr.remove(arr.size()-1)。

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

- Vikram Bhat

Answer 2

你可以使用 HashMap（从 ID 映射到数组索引）与数组（或 ArrayList）结合使用。

通过将 ID 和索引添加到 HashMap 中，add 操作可以在 O(1) 时间内完成，只需将元素添加到数组中即可。

通过在 HashMap 中查找（和删除）索引，然后将数组中的最后一个元素移动到该索引位置，并更新该元素在 HashMap 中的索引，减少数组大小一次来完成 remove 操作。

通过从数组返回一个随机元素，getRandomElement 操作可以在 O(1) 时间内完成。 示例:

Array: [5,3,2,4]
HashMap: [5->0, 3->1, 2->2, 4->3]

删除3：

Look up (and remove) key 3 in the HashMap (giving 3->1)
Swap 3 and, the last element, 4 in the array
Update 4's index in the HashMap to 1
Decrease the size of the array by 1

Array: [5,4,2]
HashMap: [5->0, 2->2, 4->1]

添加6：

Simply add it to the array and HashMap

Array: [5,4,2,6]
HashMap: [5->0, 2->2, 4->1, 6->3]

- Bernhard Barker

---

同样的问题，同时给出同样的答案 :) - Vikram Bhat

我最喜欢这个，因为它有例子和更详细的文本。 - Mr00Anderson