用 Java 开发，我需要一个数据结构来选择 0 到 999999 之间的 N 个不同的随机数？
我希望能够快速分配 N 个号码并确保它们不会重复自己。
主要目标是不使用太多内存并保持合理的性能。
我正在考虑使用BitSet但我不确定是否会影响内存。有人可以告诉我这个类的内存要求是否与位数或设置位数有关？设置/测试的复杂性是多少？
更新：感谢到目前为止的所有回复。
我想我在这个 Q 的最初措辞中有这个，但是当我第一次看到 BitSet 类时删除了它。无论如何，我想添加以下信息：目前我正在查看最多几千的 N（很可能在 1000-2000 左右）和 0 到 999999 的数字范围。但我希望我的选择考虑到该选项将范围增加到 8 位（即 0 到 99 999 999），同时将 N 保持在大致相同的范围（可能增加到 5K 或 10K）。因此，“使用值”非常稀疏。
这取决于有多大N。
对于较小的 值N，您可以使用 aHashSet<Integer>来保存您已经发布的数字。这为您提供O(1)查找和O(N)空间使用。
范围 0-999999 的ABitSet将使用大约 125Kb，无论N. 对于足够大的 值N，这将比 更节省空间HashSet。我不确定NaBitSet将使用更少空间的确切值是多少，但我的猜测是 10,000 到 20,000。
有人可以告诉我内存需求
BitSet是否与位数或设置位数有关？
大小由曾经设置的最大位或nBits使用BitSet(int nBits)构造函数的参数确定。
设置/测试的复杂性是多少？
测试位B是O(1).
设置位B是O(1)最好的情况，O(B)如果您需要扩展位集支持数组。但是，由于后备数组的大小是 2 的次幂，因此扩展成本通常可以分摊到多个BitSet操作中。
ABitSet将占用与 1,000,000 个布尔值一样多的空间，即 125,000 字节或大约 122kB，加上一些较小的开销和增长空间。实际数字的数组，即 anint[]将占用 N × 4B 的空间加上一些开销。盈亏平衡点是
4 × N = 125,000
N = 31250
我对 Java 内部结构并不十分熟悉，但我怀疑它分配的实际空间不会超过实际使用空间的两倍，因此您使用的内存少于 250kB 和 bitset。此外，当您需要唯一整数时，数组会使查找重复项变得更加困难，因此我会以任何一种方式使用位集，并可能在最后将其转换为数组，如果这样更方便进一步处理的话。
在 a 中设置/获取一点BitSet将具有恒定的复杂性，尽管它比从 a 中获取更多操作需要一些操作boolean[]。