32 位 handle 的一种生成方法

我倾向于在 C 程序里使用整数 handle ，而不是指针。尤其是需要做弱引用的时候。

我认为，一个好的 handle 生成算法，应该满足：

即使 handle 被销毁了，它这个数字也应该被保留，不应该被新的 handle 复用。posix api 里的文件 id 就不符合这一点。 提供一个 api 可以判断一个 handle 是否有效，其时间复杂度为 O(1) 。 从 handle 对应为对象的内存地址的时间复杂度应该为 O(1) ，不应该比指针有明显的性能问题。虽然 hash 表理论上可以满足 O(1) 的时间复杂度，但在糟糕的场景（hash 碰撞发生时）并不能保证这一点。 构造 handle 时间复杂度也为 O(1) 。 handle 的数字位宽最好不要超过 32 bit 。

如是长期运行的程序，第一和第四个需求不能同时成立。但对于非长期程序，理论上 32bit 的数字应该是够用了。

比较简单的实现方案是用一个自增 id ，然后用一张 hash 表来保存 id 到指针的映射。但 hash 表不是严格的 O(1) 复杂度。在 skynet 中，我使用了一个简单的方法：自增 id 后，如果发现 hash 冲突，就再加一，直到不冲突为止。这个方法不能满足第 4 点需求。

当然，同时满足 5 点需求未必有多大的意义，但我最近想到一个有趣的方案，稍微实现了一下，感觉可以做到。

前提是：为了让 32bit 数字就够用，同时有效的 handle 不能太多（大多数场景是这样的）或是在同时有效的 handle 很多时，不要过于频繁销毁和创建很少的几个 handle 。

我们用一个固定 size 为 2^n 的整数数组来管理所有的 handle 。handle 对 size 取模，就是它在这个数组所在的 slot 。然后，我们只需要维护一个完美 hash 表，所有分配出去有效的 handle 都不在这张 hash 表中发生碰撞。这是可以用 O(1) 时间做到的：方法是，每次回收 handle ，都把该 slot 的高 (32-n) bits 加一，这个新的待分配的 id 绝对不会和已分配过的 id 重复。

和简单的循环自增 id 检查冲突的算法相比较，不仅仅是时间上更稳定。最主要的好处是，这个算法更难耗尽 32bit 的空间（发生回绕）。尤其在有效 handle 数量较多时，一旦发生碰撞，自增 id 的方式一下子就会跳过很多数字，而这些数字中大部分是从来没有使用过，本可以安全的分配出去的。

在 handle 销毁（回收时），同时把 handle 串在该数组里的 free list 即可保证下次 O(1) 时间就能完成新 handle 的分配。

举个例子：

如果我们限制最大有效 handle 数为 4 ，如果把 0 保留为无效 id ，那么分配四次后，handle 分别为 1 2 3 4 。

这时，如果我们把 2 销毁，重新分配的话，新的 handle 是 6 而不是 5 （因为 5 和 1 会发生 hash 碰撞）。这时，再销毁 6 然后分配一个新 handle ，这个新的 handle 会是 6+4 = 10 。

在这个算法中，是不是之后所有新增 handle 都比 10 大呢？并不是。如果销毁 1 ，再分配的话，会得到 5 ，5 比 10 小。

这个算法获得的 handle 的数值并非单调递增的，它比自增方案更节省全部的数字空间。

如果这个数组满了怎么办？一般我们不用考虑这种情况，应该一开始规划好上限（例如 posix 的同时打开文件数就有上限）。但若是想解决，也可以倍增 size 。只不过 rehash 的过程比较复杂：不光是要把已有的有效 handle 重新填在新数组中，还需要额外标记那些可能用过的 slots 。

我写了一个简单的实现：https://gist.github.com/cloudwu/dcbf583f7034ef6c0f8adec3f76860f0

借助这个数据结构，我们就可以把同类对象分配在一个大数组中，然后用 handle 索引它们，和指针相比，几乎没有额外的开销。并且有如下好处：

可以简单的判断一个 handle 是否有效（指针无法安全的做到这点），容易写出健壮的代码。 方便做持久化。 handle 可以用于 C/S 同步。