管理可用资源的最优数据结构选型与复杂度分析

针对0~N-1范围的ID资源池，要实现get()取可用ID、free(id)归还ID的能力，选型完全取决于N的规模，核心是平衡时间、空间开销：

常规规模场景（N为百万级及以下） #

优先选空闲栈/队列+布尔标记数组的实现：

• 初始化时把0~N-1所有ID压入栈（或队列），额外开一个长度为N的布尔数组标记ID的占用状态
• get()直接弹出栈/队首的ID，标记为占用后返回，时间复杂度O(1)
• free(id)时先校验ID确实处于占用状态，避免重复释放，再把ID压回栈/队列、标记为可用，时间复杂度O(1)
• 空间复杂度O(N)，N为百万级时内存仅占1MB左右（布尔数组按1字节/ID算），完全可以接受。

如果N到千万到十亿级，内存放不下全量布尔数组，可以换成位图+偏移指针的方案：

• 用1个bit标记1个ID的占用状态，空间占比直接降到原来的1/8，N=10亿时位图大小约125MB，常规服务器完全可以承载
• 维护一个偏移指针记录上次分配到的位置，get()时从指针位置开始找第一个未占用的bit位，标记为占用后返回，更新指针到下一个位置；free(id)时把对应bit位清零，如果释放的ID比当前指针位置小，直接把指针挪到这个ID位置，均摊时间复杂度O(1)。

超大规模场景（N达10亿到万亿级） #

这个时候哪怕是位图也占不住——N=1万亿时位图需要125GB内存，预分配全量状态完全不现实，要换稀疏存储的空闲区间结构：

• 核心逻辑是不存单个ID的状态，只存连续的空闲ID区间，用有序平衡树（类似Java的TreeSet、C++的std::set）维护这些区间，每个区间只需要存[start, end]两个整数，初始化时整个集合里只有一个区间[0, N-1]
• get()操作：直接取集合里第一个空闲区间，如果区间长度为1，就把这个区间从集合里删掉，返回start值；如果区间长度大于1，把区间的start值加1更新区间边界，返回原来的start值，时间复杂度O(logK)，K是当前空闲区间的总数量，远小于N
• free(id)操作：先检查id左右相邻的位置有没有已经存在的空闲区间，比如左边有没有[x, id-1]、右边有没有[id+1, y]，把相邻的碎区间和当前释放的id合并成一个大的连续区间，删掉旧的碎区间、插入新的合并后区间，时间复杂度也是O(logK)
• 空间复杂度O(K)，和总N的大小无关，只和当前空闲区间的碎片化程度有关：如果是连续分配、连续释放的场景，K始终维持在个位数，内存开销可以忽略。
• 可选优化：如果业务有明显的热点（刚释放的ID很快会被再次分配），可以额外加一个容量几十到几百的小栈存最近释放的ID，get()时优先从这个小栈里取，把热点路径的时间复杂度降到O(1)，小栈空了再去有序区间结构里取资源。

不同方案适配场景对比

实现方案	get()时间复杂度	free()时间复杂度	空间复杂度	适配N规模
空闲栈+布尔标记数组	O(1)	O(1)	O(N)	百万级及以下，追求极致性能
位图+偏移指针	均摊O(1)	O(1)	O(N/8)	千万到十亿级，可容纳位图
有序空闲区间树	O(logK)	O(logK)	O(K)	万亿级及以上，无法预分配全量状态

内容的提问来源于stack exchange，提问作者ProtossShuttle