二进制搜索和哈希表搜索

我想找出一个字典查找和一个数组的二进制搜索查找之间的权衡点。 我期待着字典的恒定时间查找，以及二进制搜索的对数时间查找，具体取决于集合的大小，二进制搜索对于较小的集合表现更好。

但是，当我看到以下结果时，我感到很惊讶：

我很惊讶：1。二进制搜索首先以对数方式增长，然后增长得更快。 哈希起初非常一致，但随后开始慢慢增长。 3.二进制搜索永远不会比哈希查找更好。 以下是我的代码。 我做错了什么？

class Program { static void Main(string[] args) { var r = new Random(); var targets = Enumerable.Range(0, 1000 * 1000).Select(_ => r.Next(int.MaxValue)).ToList(); for (int totalCount = 1; totalCount  r.Next(int.MaxValue)).Distinct().Select(v => new thing(v)).OrderBy(t => t.value).ToArray(); var d = a.ToDictionary(t => t.value); var watch = new System.Diagnostics.Stopwatch(); { watch.Start(); var found = targets.Select(t => BinarySearch(t, a)).Where(t => t != null).Count(); watch.Stop(); Console.WriteLine(string.Format("found {0} things out of {2} in {1} ms with binary search", found, watch.ElapsedMilliseconds, a.Length)); } { watch.Restart(); var found = targets.Select(t => HashSearch(t, d)).Where(t => t != null).Count(); watch.Stop(); Console.WriteLine(string.Format("found {0} things out of {2} in {1} ms with hash search", found, watch.ElapsedMilliseconds, d.Keys.Count)); } } Console.ReadLine(); } static thing HashSearch(int needle, Dictionary hash) { if (!hash.ContainsKey(needle)) return null; return hash[needle]; } static thing BinarySearch(int needle, thing[] sortedHaystack) { return BinarySearch(needle, sortedHaystack, 0, sortedHaystack.Length - 1); } static thing BinarySearch(int needle, thing[] sortedHaystack, int minimum, int maximum) { if (minimum > maximum) return null; var middle = (minimum + maximum) / 2; if (needle == sortedHaystack[middle].value) return sortedHaystack[middle]; if (needle < sortedHaystack[middle].value) return BinarySearch(needle, sortedHaystack, minimum, middle - 1); return BinarySearch(needle, sortedHaystack, middle + 1, maximum); } class thing { public int value; public thing(int v) { value = v; } } } 

Answer 1

（几乎在评论中指出。）

我怀疑你大多看到缓存未命中的影响。 当集合很大时，你会得到很多缓存未命中 – 特别是二进制搜索，它可能需要触及集合中的许多点来查找元素。

在较小的大小，我怀疑你也看到缓存未命中，但这次是在targets列表上 – 以及LINQ本身的开销。 LINQ很快，但是当你所做的只是在中间执行一个小集合的单一搜索时，它仍然很重要。

我建议将你的循环重写为：

 { // Use the same seed each time for consistency. Doesn't have to be 0. Random random = new Random(0); watch.Start(); int found = 0; for (int i = 0; i < 1000 * 1000; i++) { if (BinarySearch(t, random.Next(int.MaxValue)) != null) { found++; } } watch.Stop(); Console.WriteLine(string.Format "found {0} things out of {2} in {1} ms with binary search", found, watch.ElapsedMilliseconds, a.Length)); } 

当然，你已经遇到了在循环中包含随机数生成的问题......你可能想看看使用比System.Random更快的随机数生成器，如果你能找到一个。 或者使用其他方法来确定要查找的元素。

哦，我个人重写二进制搜索使用迭代而不是递归，但这是另一回事。 我不希望它产生重大影响。