c++ - 快速 64 位整数 ID 查找/搜索

Question

我正在开发一款游戏，为了安全起见，任何用户(程序员)都只能将 ID 存储到对象而不是指针，并且必须使用此 ID 获取指向对象的指针，以便必须有一定的独处时间。

让我们使用最坏的情况:每个 ID 都在使用中。它是 64 位的，所以你可以:18446744073709551616 要搜索的 ID。很多数据都存储在数据库中，我们的程序查找要么返回一个指针，要么返回一个空指针。空指针意味着程序必须访问数据库才能加载对象，之后它将有一个指针。

想法:所以我在这里知道的唯一真正的技巧是二进制搜索。所以在最坏的情况下，这意味着每次 ID 查找都要进行 64 次比较。

我的另一个想法是创建一个静态空间分区，这是一棵树，其中每个分支都 split 成 2 次幂的分支数量，但仅限于合理的深度。在 ID 上使用按位运算符而不是模数运算符来找出它在每个级别上属于哪个分支。树中每个可能的分支始终存在，但在某个深度它们停止并且仍然需要二分查找，因为值的确切数量仍然未知。

你有什么想法？

Answer 1

这是 HashMap 的经典案例。首先，了解您实际上可以同时激活多少个 ID。 2^64 是无意义的，因为即使是仅用于保存这些 ID 的数据结构和指向对象的指针也至少已经达到 268'435'456 TB。现在，使用 64 位 ID 没有任何问题，但要弄清楚在任何时候您将激活多少个对象，选择一个合理的数字，比如 5'000，并使用对象数量的 10 倍的 HashMap 。如果您的负载因子足够低并且您的哈希函数足够好，您将获得分摊的 O(1) 访问时间。