performance - 查找号码的最快方法是什么？

Question

我正在存储数字（在 1 到小于 100,000 的范围内），然后以数字作为参数被调用，并且必须将其用作查找中的键。过去，当获取短 char* 字符串作为查找键时，我使用了 trie 实现。我想知道我是否也应该使用一个来表示是否有一些更快的方法来调查/考虑/调查？

Answer 1

这真的取决于你想要做什么。

如果您有很多内存，您可以构建一个包含 100,000 个元素的数组，并在查看表格时将其用作索引。这可能是最快的方法（查找都是 O(1) 且常数因子极低），尽管它不是最节省内存的方法。如果内存不足，标准哈希表将是一个很好的折衷方案；您将获得所有操作的预期 O(1) 运行时间。

如果您需要能够执行“哪个数字最接近 x？”形式的查询，那么您可能需要使用包含整数的平衡二叉搜索树。这使您可以在 O(log n) 时间内进行后继和前任搜索和查找。如果您有兴趣尝试更复杂的数据结构，可以使用van Emde Boas 树，它可以在 O(log log U) 时间内进行插入、删除、查找、前任和后继搜索，其中 U 是最大可能值。

希望这可以帮助！

Answer 2

我建议为此使用哈希表。每个值都将放置在一个唯一的存储桶中，您可以使用您的密钥引用该存储桶。如果您的数据可以以这种方式组织，这将是最快的查找。