c# - 字典(哈希表)和列表查找之间的权衡点

Question

简短的问题:列表中可以包含多少个元素才能进行线性搜索(例如列表 O(n))比字典(O(1))更快？

我似乎记得在大学(和高中)时，在比较搜索技术(二进制与线性)时，总有一个点是线性更快。这是 O(n) 与 O(log)

我无法在这里绘制图表。但为了持续的性能必须有一些开销。所以问题是，如果我有 10 个项目，List.Find 是否更有意义

if (Dictionary.Contains(x))
    value = Directiory[x]

或者 value = Hashtable[x] 的哈希表不会失败，但需要装箱

Answer 1

我问了自己同样的问题，并运行了一个基准来找出答案。我发现字典的速度在查找大约 3-4 个元素时已经优于列表。

基于字典的开销，这对我来说似乎很少，所以我四处查看是否有其他人得到了相同的结果，这似乎也是其他人发现的结果。 http://dotnetperls.com/dictionary-time

这并不意味着将数十个字典放入您的代码中，因为它们没有意义 - 还需要处理内存开销和构建时间。但是，如果您有一组适当大小的键控数据，请利用该结构。