查找数字最快的方法是什么？

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

来源

2013-10-03 Palace Chan

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

如果你有很多内存，你可以建立一个包含100,000个元素的数组，并且只需要在查看表时使用该数字作为索引。这可能是最快的方法（查找都是具有极低常数因子的O（1）），尽管它并不是最高的内存效率。如果内存稀少，一个标准的哈希表将是一个很好的折衷;您将获得所有操作的预期O（1）运行时间。

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

希望这会有所帮助！

来源

2013-10-03 00:18:45 templatetypedef

哦直线阵列不是一个坏主意！我其实知道100000是一个合理的上限 –

你必须考虑到，如果多个对象有一个共同的密钥，碰撞解决的成本可能会相当大。 – 3yakuya

哦不，这是不是这种情况..对象的钥匙是唯一的 –

我会建议使用散列表。每个值都将放置在一个可以使用密钥引用的独特存储区中。如果您的数据可以按照这种方式进行组织，这将是最快的查找方式。

来源

2013-10-03 00:18:11 TGH

事情是散列的代价是非平凡的，即使我使用超快速哈希像FNV，而通常与短的字符串或知道我的密钥的属性（他们是小数字）我可以利用小试避免缓存未命中的跳转很少 –

散列表版本之一是直接寻址表，其中“散列”成本实际上是微不足道的。它可以正常工作，除非有多个对象具有相同的密钥的可能性很高。 – 3yakuya

价值的关键是独一无二的，直接寻址表是一样的上述答案是的，我同意将是最快的方式 –

查找数字最快的方法是什么？

回答

相关问题