我需要在 1 到 2000 万个范围内使用和回收 ID（整数）。
最有效的方法是什么？
我尝试过的东西。
生成一个从 1 到 k 的连续数字序列并存储在一个 地图。在 k 个数字之后，如果让我们说如果 id 2 空闲，我们将其删除 从地图。并从 k+1 继续我们的下一个 id（如果 我可以选择从一开始就释放的 id(2) 而不是 k+1。我怎样才能做到这一点 ？ )
生成介于 1 到 2000 万之间的随机数并检查 如果它已经用于地图查找，如果是，则选择另一个随机 number 或执行 number+1 直到地图查找失败。
将所有从 1 到 2000 万的数字存储在一个集合中并一个一个地使用并在释放时添加回来（这将有更大的 内存占用，不想这样做）
解决这个问题最有效的方法是什么，如果让我们说一下 50% 的 id 会在任何时间点被使用
20M 的整数大约是 80 Mb 的 RAM。如果我们谈论的是 Java，那么根据 this 文章，HashSet<Integer> 最多可以占用 22 倍的空间，所以大约 1.7 Gb，哇。
您可以实现自己的位集，支持快速选择下一个空闲 ID。 Bitset 应该只占用大约 2.4 Mb 的 RAM，我们可以在 O(1) 中找到下一个空闲 ID。没查过代码，主要是一个想法：
int range = 20_000_000;
long[] bitset = new long[range / 64 + 1]; // About 2.4 Mb of RAM,array length is 312501
Stack<Integer> hasFreeIds = new Stack<Integer>(); // Slots in bitset with free IDs
for (int i = 0; i < bitset.length; ++i) { // All slots have free IDs in the beginning
hasFreeIds.push(i);
}
// Now `hasFreeIds` is about (8 + 4) * 312_000 bytes = ~4Mb of RAM
// Our structure should be ~6.4 Mb of RAM in total
// Complexity is O(1),so should be fast
int getNextFreeId() {
// Select the first slot with free IDs
int freeSlotPos = hasFreeIds.pop();
long slot = bitset[freeSlotPos];
// Find the first free ID
long lowestZeroBit = Long.lowestOneBit(~slot);
int lowestZeroBitPosition = Long.numberOfTrailingZeros(lowestZeroBit);
int freeId = 64 * freeSlotPos + lowestZeroBitPosition;
// Update the slot,flip the bit to mark it as used
slot |= lowestZeroBit;
bitset[freeSlotPos] = slot;
// If the slot still has free IDs,then push it back to our stack
if (~slot != 0) {
hasFreeIds.push(freeSlotPos);
}
return freeId;
}
// Complexity is also O(1)
void returnId(int id) {
// Find slot that contains this id
long slot = bitset[id / 64];
boolean slotIsFull = (~slot == 0L); // True if the slot does not have free IDs
// Flip the bit in the slot to mark it as free
int bitPosition = id % 64;
slot &= ~(1 << bitPosition);
bitset[id / 64] = slot;
// If this slot was full before,we need to push it to the stack
if (slotIsFull) {
hasFreeIds.push(id / 64);
}
}
一种节省空间的解决方案是使用位掩码来跟踪空闲条目。 20M 位只有 2.5MB。
如果其中有一半是免费的，那么当你需要分配一个新的ID时，你可以从一个随机的地方开始，向前走，直到找到一个有免费位的条目。
如果您需要有保证的时间限制，那么您可以使用 64 位字的数组作为位掩码，并使用 1/64 大小的位掩码来跟踪哪些字具有空闲条目。重复直到你找到一两个词。
如果空间不是问题，那么最简单的快速方法是将空闲 ID 保存在空闲列表中。这需要一个最多包含 20M 个整数的数组。您记得最后释放的条目，对于每个空闲节点 x，array[x] 是前一个已释放节点的索引，或 -1。
如果您的 ID 实际上指向某个东西，那么通常您可以对空闲列表和指针使用完全相同的数组，因此空闲列表根本不需要额外的内存。
,理论上，最快的方法是将所有空闲 ID 存储在一个链表中。
即把20M个序列号压入链表。要分配一个 ID，从前面弹出它。并且当 ID 空闲时 - 根据您的偏好将其推到顶部或底部（即，您是首先重用已释放的 ID，还是仅在使用每个预分配的 ID 之后）。 这样分配和释放 ID 都是 O(1)。
现在，作为优化，您实际上不需要预先分配所有 ID。您应该只存储分配的最高 ID。当您需要分配一个 ID 并且空闲 ID 列表为空时 - 只需增加最高 ID 变量并返回它。 这样你的列表永远不会达到大数目，除非它们真的被分配和返回。