algorithm - 在大量随机生成的数字中重复

Question

我们需要根据请求生成随机数，并且这些请求可以由任何用户随时生成。这导致了问题，我们必须检查之前生成的数字是否有重复，因为生成的数字应该是唯一的并且不允许重复。

每批随机生成的数字大约为 2²⁰-2²⁵ 并且生成的数字将检查前一批处理是否重复。无法在特定时间间隔内生成数字。

至于解决方案，我们希望对生成的随机数进行排序，然后与新生成的批处理进行重复比较，但这对于排序算法来说需要相当大的复杂度 O(nlogn)。同样在使用 HashSets 的解决方案中，用于存储数字的内存将非常大。

有什么方法可以提高这样的算法的效率吗？

Answer 1

我认为，您可以对两个批处理使用布隆过滤器 - 当前和之前。并在两者中搜索重复项。如果找到一个重复项(即使它是误报)- 丢弃它，并生成其他随机数，直到生成唯一的。

什么是布隆过滤器:https://en.wikipedia.org/wiki/Bloom_filter

另一种方法:您可以使用混淆非随机。例如 - 在 ECB 模式下使用 AES 加密序列号。这些数字看起来是随机的，但您可以确定 - 加密数字不会重复。