用于快速添加、获取和删除随机元素的集合

Question

真的不是什么大问题。什么集合适合快速添加、获取和删除随机元素？

项目不必保留任何类型的顺序。

我正在开发一个贪吃蛇游戏，我正在跟踪游戏区域中未被占用的单元格（以便能够在苹果被吃掉后快速为苹果选择一个新位置）。

这里"fast"可以是O(log n)或O(1)。

Answer 1

我推荐平衡二叉树。插入/删除将是 O(log(n))，选择一个随机元素将是随机沿着树枝走到叶子的问题，O(log(n))。

如果与 adding/removing 个占用的单元格相比，查找苹果的未占用位置是一个相对不常见的操作，我会选择 LinkedHashSet:

让一个单元格空闲：unoccupied.add(pos)，O(1)（摊销）
让一个单元格被占用：unoccupied.remove(pos)，O(1)

随机找到一个未被占用的单元格：

if (unoccupied.isEmpty()) throw something;
int i = random.nextInt(unoccupied.size());
Iterator<Pos> iter = unoccupied.iterator();
while (i-- > 0)
    iter.next();
return iter.next();

（使用 LinkedHashMap 而不是 HashMap 确保最后一个操作的 O(n)。）

一个 ArrayList 的移除时间复杂度为 O(n)。 LinkedList 或 HashSet 查找随机元素的时间复杂度为 O(n)。

Answer 2

最好的List是LinkedList 删除和插入发生在 O(1) 中，但检索位置发生在 O(n) 中。检索位置n的元素复杂度为O(n).

否则你可以使用 TreeSet。所有操作都在 O(log n) 中授予。

如果您可以使用键来检索元素，则可以使用 Map。 HashMap 在 O(1)

中插入检索删除

Answer 3

HashMap，它对所有三个（在大多数情况下）的复杂度为 O(1)： http://en.wikipedia.org/wiki/Hash_table

用于快速添加、获取和删除随机元素的集合

Collection for fast add, get and remove random element

java

collections