java - 数据结构推荐

Question

用 Java 开发，我需要一个数据结构来选择 0 到 999999 之间的 N 个不同的随机数？

我希望能够快速分配 N 个数字并确保它们不会重复。

主要目标是不使用太多内存并仍然保持合理的性能。

我正在考虑使用 BitSet但我不确定内存是否有影响。 有人可以告诉我这个类的内存需求是否与位数或设置位数有关？设置/测试的复杂性是多少？

更新: 感谢迄今为止所有的回复。

我认为我在这个问题的最初措辞中已经提到了这一点，但当我第一次看到 BitSet 类时将其删除。 无论如何，我想添加以下信息: 目前我正在查看最多几千个中的 N 个(最有可能在 1000-2000 左右)，数字范围为 0 到 999999。 但我希望我的选择考虑将范围增加到 8 位数字(即 0 到 99 999 999)，同时将 N 保持在大致相同的范围(可能增加到 5K 或 10K)。 所以“使用值”非常稀疏。

Answer 1

这取决于有多大N是。

对于 N 的小值，您可以使用 HashSet<Integer>保存您已经发出的号码。这给你O(1)查找和 O(N)空间使用情况。

一个BitSet对于范围 0-999999 将使用大约 125Kb，无论 N 的值如何。对于足够大的 N 值，这将比 HashSet 更节省空间。 。我不确定 N 的具体值是什么是 BitSet将使用更少的空间，但我的估计是 10,000 到 20,000。

<小时/>

Can someone tell me if the memory requirements of BitSet are related to the number of bits or to the number of set bits?

大小由曾经设置的最大位或nBits决定。参数，如果您使用 BitSet(int nBits)构造函数。

and what is the complexity to setting/testing a bit ?

测试位B是 O(1) .

设置位B是 O(1)最好的情况，和O(B)如果您需要扩展位集支持数组。然而，由于后备阵列的大小是 2 的下一个最大幂，因此扩展成本通常可以分摊到多个 BitSet 上。操作。