java - Java中数组太小怎么办？

Question

在 java 中，数组最多可以有 Integer.MAX_VALUE 项，因为它使用整数作为数组的键。当我想使用 long 作为索引时，最好使用什么对象？

例如，如果我想使用素数筛计算 50 亿以下的所有素数，则不能使用数组，因为 5000000000 太大而无法存储在整数中。

Answer 1

包含 5000000000 个元素的筛子不需要包含 5,000,000,000 个值的数组；它需要 5,000,000,000 位。不幸的是，BitSet 也使用 int 索引，但您可以通过分配 5000000000/32 整数，然后使用 bit 来实现自己的位集访问相应位的操作:

• 使用long作为实际位置pos
• int 在 int 数组中的位置是 (int)(pos/32)
• int 中该位的位置为 (int)(pos % 32)

另一种方法是切换到分段筛，这会将内存需求减少到√N。 here 很好地解释了其工作原理。 .