云风的 BLOG: 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 同步。

Comments

”这系统还有个较大问题。假设仅剩一个index，这时反复销毁重建，那么，可用的ID数量仅为2＾(32-n)“ 试试多级索引思路： 1. 将handle的32位数字空间划分为多个层次。比如，你可以将32位划分为前16位作为一级索引，后16位作为二级索引。 2. 一级索引指向一个小型数组或列表，每个小型数组再通过二级索引指向具体的对象。 3. 这种结构允许在更大范围内分布handle，避免单一index的频繁使用。具体实现： 1. 假设有一个16位的一级索引，那么可以管理的一级索引空间是2^16（即65536个）。 2.每个一级索引项指向一个小型数组（或者链表），这个数组的大小也可以是2^16个。这样，实际上扩展了数组的可管理范围，从原来的2^n（固定大小数组）扩展到2^16 * 2^16 = 2^32个可能的handle 3. 这种结构可以在更大范围内分布handle，避免单一index的频繁使用。

Posted by: bruce | (10) August 23, 2024 05:12 PM

云风大大，问个问题。三战那种大世界SLG，从地图左下，寻路到地图右上,估计得耗时多久？

Posted by: guigui | (9) August 22, 2024 11:23 AM

如果数组大小本身不是大问题，回收处理复杂一点，分段、滑动窗口、磨损平衡，应该可以支持远大于预估的容量？用索引时多减个偏移量。数组中的空洞可能多些，缓存不那么友好🤔

Posted by: 怪物公司 | (8) August 19, 2024 11:54 PM

歪个题，c++中弱引用和强引用（侵入式智能指针）在使用上怎么权衡比较好？强引用增加了耦合但是可以直接访问，弱引用便于集中管理资源但是每次都要经过一层查询转换。

Posted by: sylvia | (7) August 19, 2024 12:32 PM

没有普适的算法。了解算法能做什么以及了解需求有哪些约束条件。

Posted by: Cloud | (6) August 19, 2024 10:39 AM

> "如是长期运行的程序，第一和第四个需求不能同时成立。" 应该是第一和第五个需求有矛盾吧.

Posted by: dwing | (5) August 19, 2024 10:07 AM

有点像flash存储芯片的擦写, 只不过没有平衡算法, 有的block(slot)可能会遭到频繁擦写(回收+分配).