我正在开发一款游戏，并且为了安全起见，任何用户（程序员）只允许将ID存储到对象而不是指针，并且必须使用此ID来获取指向对象的指针，以便独立于它一定的质量。快速64位整数ID查找/搜索
让我们使用最糟糕的情况：每个ID都在使用中。它是64位，所以你去：18446744073709551616 ID来搜索。很多数据都存储在数据库中，我们的程序查找要么返回一个指针，要么返回一个空指针。空指针表示程序必须访问数据库才能加载对象，之后它将有一个指针。
想法： 所以我知道的唯一真正的技巧是二进制搜索。因此，在最糟糕的情况下，这意味着每次ID查找需要64次比较。
我的另一个想法是创建一个静态空间分区，一棵树，每个分支分裂成2个分支的权力，但只有一个合理的深度。在ID上使用一个按位运算符而不是模运算符来查找它在每个级别上属于哪个分支。树中的每个可能的分支总是存在，但是在某个深度它们停止并且仍然需要二分搜索，因为确切数量的值仍然是未知的。
你有什么想法？
这是散列图的经典案例。首先，了解您实际上可以在任何时间激活多少个ID。 2^64是无稽之谈，因为即使只是保存这些ID和指向对象的指针的数据结构已经至少为268'435'456 TB。现在，使用64位ID没什么问题，但是要弄清楚在任何时候你会有多少活动对象，选择一个合理的数字，比如说5'000，并使用一个散列图，例如10倍的对象数。如果你的负载因子足够低，你的散列函数足够好，你将得到一个分期的O（1）访问时间。
即使活动对象的数量要大得多，例如100万，仍然可以使用相对较小的哈希映射，例如大小为10000的映射。映射的每个元素都指向ID的链接列表。这些列表使用简单的线性搜索进行搜索。如果散列函数选择得当，那么ID将在散列映射中的10000个条目上均匀分布（或接近）。因此散列表的每个条目将包含大约100个ID。线性搜索这样的列表平均需要50比较。
在我的一个应用程序中，符号的数量大约是1000.我只用了简单的线性搜索。性能分析表明90％的CPU时间用在表查找中。接下来我做了一个只有32个条目的哈希表 - >查表的CPU负载降到4％以下。问题解决了。扩大散列表对速度没有明显影响（小于4％），因此我将其保留为32的大小。
结论：您可以使用小于元素数的散列表。这需要平均数量的比较（ID的总数/散列表的大小/ 2）选择足够大的散列表大小以将表查找的CPU时间减少到总CPU时间的很小部分。
+1指出了更高负载因素下的一个很好的解决方案。应该注意的是，链表需要额外增加一个间接级别，从而导致更多的缓存未命中。这是可用内存与性能要求之间的平衡。 – wich 2011-01-28 13:13:49
是的，现在我明白我的想法是多么愚蠢是：或许ID空间允许2^64的可能性，但所有的对象永远不会全部加载到内存中的所有方式。谢谢，现在我感到有些惭愧;（对不起， – Xilliah 2011-01-28 18:36:47