algorithm - 是否有可能在恒定时间内找到 Set 中的随机元素？

Question

因此，我遇到了使用 getRandomElement() 函数构建集合的问题。乍一看很容易。但是我越想这个，就越觉得在 O(1) 时间复杂度内做这件事是不可能的。没有给定时间的要求，但是集合的所有主要功能都是在常数时间内完成的，所以我觉得这意味着这也应该在常数时间内完成。

集合的目标是散列函数减少冲突。现在的问题是，如果您只是生成随机整数并尝试使用该随机整数选择索引，您很可能会遇到集合中的“空”槽……在这种情况下，您必须生成一个新的随机数然后再试一次。从本质上讲，您的哈希函数越好，您的 getRandomElement 使用这种方法的性能就越差。

然后我想......好吧，为什么不在每次插入后存储索引？然后，生成一个随机数并从该索引集合中选择一个索引。我认为这是个好主意，但随之而来的是删除元素的问题。我们还必须从我们的索引列表中删除相应的索引，以及从我们的集合中删除元素本身。我们如何找到正确的索引以比线性时间更快地删除？？？

无论如何，从一组感觉中获取随机元素可以在比线性时间更好的时间内完成。顺便说一句，我正在通过链接处理碰撞。我不想浪费时间尝试做数学上不可能的事情，但我也不是数学家，我不想放弃实际上可能的事情。

Answer 1

是的，可以构建一个支持 O(1) getRandomElement 操作的类似集合的数据结构。关于将元素存储在数组中，您是正确的。删除元素的问题并不太难。

秘诀是一旦孔的数量太大(例如，超过数组大小的一半)就压缩数组。这样，分摊删除时间仍然是 O(1)。

当执行 getRandomElement() 时，只需重复直到您碰到一个实际元素。平均重复次数不超过 2 次，因为数组始终至少是半满的，所以 getRandomElement() 的平均时间仍然为 O(1)。

编辑:也许更简单的删除元素的方法是将最后一个元素移动到空出的位置。