我有一个包含100万个id的大数组/列表,需要找到可以使用的第一个空闲id。可以假设有几个模块引用了这个数据结构,并取一个id(此期间应标记为已使用),然后稍后返回它(应标记为可用)。
我想知道可以使用哪些不同的数据结构?以及我可以使用什么算法来在时间和空间上高效地完成此操作(分别)。
如果此问题已经在此处存在,请谅解。
一个天真但高效的方法是将所有id存储在堆栈中。 获取id是一个常数时间操作:弹出列表的第一个项。 当任务完成后,只需将id推到堆栈上。
如果必须返回最低的可用id(而不是任何可用id),则可以使用min heap,插入和弹出最低点档案的时间复杂度为O(log N)。
前言:二叉堆似乎确实是最好的答案。我在这里提出一种替代方案,可能在某些情况下具有优势。
一种可能的方法是使用Fenwick Tree。您可以在每个位置存储0或1,表示该位置已经被使用或未被使用。您可以使用二分查找找到第一个空位置(查找第一个范围[1..n]的和为n-1)。这个操作的复杂度是O(log^2 n),比二叉堆更差,但这种方法还有其他优点:
如果您不需要严格使用最低的ID,可以将模块的ID分批分配为1000个一组。释放ID时,它们可以添加到列表的末尾。偶尔您需要对列表进行排序,以确保再次分配的ID来自低端。
嗯,数组可能不是最好的结构。至少就速度而言,哈希表会更好。至于每个“节点”的结构,我所能看到你需要的只是ID以及它是否被使用。