哪个更快，哈希查找或二进制search？

当给定一个静态的对象集（静态的意义上，一旦加载它很less如果有变化）需要重复的并发查找与最佳性能，哪个更好，一个HashMap或一个二进制search使用一些自定义比较？

答案是对象或结构types的函数吗？ 哈希和/或相等的function性能？ 哈希唯一性？ 列表大小？ Hashset集大小/集大小？

我正在看的集合的大小可以从500k到10m的任何地方 – 这些信息是有用的。

当我正在寻找C＃答案时，我认为真正的math答案不在于语言，所以我不包括那个标签。 但是，如果有C＃特定的东西需要知道，则需要该信息。

Answer 1

好的，我会尽量缩短。

C＃简答题：

testing两种不同的方法。

.NET为您提供了使用一行代码更改方法的工具。 否则，请使用System.Collections.Generic.Dictionary，并确保使用大量初始化它作为初始容量，否则由于GC需要做的工作来收集旧的存储桶arrays，您将会通过剩余的插入项目。

较长的答案：

哈希表具有几乎不变的查找时间，并且获得真实世界中哈希表中的项目不仅仅需要计算哈希。

要获得一个项目，你的散列表将做这样的事情：

• 获取密钥的哈希值
• 获取该散列的桶号（通常地图函数看起来像这个bucket = hash％bucketsCount）
• 遍历物品链（基本上它是共享同一个桶的物品列表，大多数哈希表使用这种处理桶/哈希碰撞的方法），并且将每个键与您试图添加/删除/更新/检查是否包含。

查找时间取决于“好”（输出如何稀疏）和快速是你的哈希函数，你正在使用的桶的数量和密钥比较器有多快，它并不总是最好的解决scheme。

更好更深的解释： http : //en.wikipedia.org/wiki/Hash_table

Answer 2

对于非常小的集合，差异将是微不足道的。 在你的范围的低端（500k项目），如果你正在做大量的查找，你将会看到不同的结果。 二进制search将是O（log n），而散列查找将是O（1）， 摊销 。 这是不一样的真正恒定，但你仍然必须有一个非常可怕的哈希函数比二元search更糟糕的性能。

（当我说“可怕的哈希”时，我的意思是这样的：

 hashCode() { return 0; } 

是的，它自己的速度很快，但是导致你的哈希映射成为一个链表。）

ialiashkevich编写了一些使用数组和字典的C＃代码来比较这两种方法，但是它使用Long值作为键。 我想在查找过程中testing一些实际执行散列函数的东西，所以我修改了代码。 我改变它使用string值，我重构了填充和查找部分到他们自己的方法，所以在剖析器中更容易看到。 我还留下了使用Long值的代码，只是作为一个比较点。 最后，我摆脱了自定义二进制searchfunction，并使用了Array类中的一个。

这是代码：

 class Program { private const long capacity = 10_000_000; private static void Main(string[] args) { testLongValues(); Console.WriteLine(); testStringValues(); Console.ReadLine(); } private static void testStringValues() { Dictionary<String, String> dict = new Dictionary<String, String>(); String[] arr = new String[capacity]; Stopwatch stopwatch = new Stopwatch(); Console.WriteLine("" + capacity + " String values..."); stopwatch.Start(); populateStringArray(arr); stopwatch.Stop(); Console.WriteLine("Populate String Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); populateStringDictionary(dict, arr); stopwatch.Stop(); Console.WriteLine("Populate String Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); Array.Sort(arr); stopwatch.Stop(); Console.WriteLine("Sort String Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchStringDictionary(dict, arr); stopwatch.Stop(); Console.WriteLine("Search String Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchStringArray(arr); stopwatch.Stop(); Console.WriteLine("Search String Array: " + stopwatch.ElapsedMilliseconds); } /* Populate an array with random values. */ private static void populateStringArray(String[] arr) { for (long i = 0; i < capacity; i++) { arr[i] = generateRandomString(20) + i; // concatenate i to guarantee uniqueness } } /* Populate a dictionary with values from an array. */ private static void populateStringDictionary(Dictionary<String, String> dict, String[] arr) { for (long i = 0; i < capacity; i++) { dict.Add(arr[i], arr[i]); } } /* Search a Dictionary for each value in an array. */ private static void searchStringDictionary(Dictionary<String, String> dict, String[] arr) { for (long i = 0; i < capacity; i++) { String value = dict[arr[i]]; } } /* Do a binary search for each value in an array. */ private static void searchStringArray(String[] arr) { for (long i = 0; i < capacity; i++) { int index = Array.BinarySearch(arr, arr[i]); } } private static void testLongValues() { Dictionary<long, long> dict = new Dictionary<long, long>(Int16.MaxValue); long[] arr = new long[capacity]; Stopwatch stopwatch = new Stopwatch(); Console.WriteLine("" + capacity + " Long values..."); stopwatch.Start(); populateLongDictionary(dict); stopwatch.Stop(); Console.WriteLine("Populate Long Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); populateLongArray(arr); stopwatch.Stop(); Console.WriteLine("Populate Long Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchLongDictionary(dict); stopwatch.Stop(); Console.WriteLine("Search Long Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); searchLongArray(arr); stopwatch.Stop(); Console.WriteLine("Search Long Array: " + stopwatch.ElapsedMilliseconds); } /* Populate an array with long values. */ private static void populateLongArray(long[] arr) { for (long i = 0; i < capacity; i++) { arr[i] = i; } } /* Populate a dictionary with long key/value pairs. */ private static void populateLongDictionary(Dictionary<long, long> dict) { for (long i = 0; i < capacity; i++) { dict.Add(i, i); } } /* Search a Dictionary for each value in a range. */ private static void searchLongDictionary(Dictionary<long, long> dict) { for (long i = 0; i < capacity; i++) { long value = dict[i]; } } /* Do a binary search for each value in an array. */ private static void searchLongArray(long[] arr) { for (long i = 0; i < capacity; i++) { int index = Array.BinarySearch(arr, arr[i]); } } /** * Generate a random string of a given length. * Implementation from https://stackoverflow.com/a/1344258/1288 */ private static String generateRandomString(int length) { var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; var stringChars = new char[length]; var random = new Random(); for (int i = 0; i < stringChars.Length; i++) { stringChars[i] = chars[random.Next(chars.Length)]; } return new String(stringChars); } } 

这里是几个不同大小的集合的结果。 （时间以毫秒为单位）

500000长期值…
填写长词典：26
填充长arrays：2
search长词典：9
search长arrays：80

500000string值…
填充string数组：1237
填充string字典：46
sortingstring数组：1755
searchstring字典：27
searchstring数组：1569

1000000长期值…
填写长词典：58
填充长arrays：5
search长词典：23
search长arrays：136

1000000string值…
填充string数组：2070
填充string字典：121
sortingstring数组：3579
searchstring字典：58
searchstring数组：3267

3000000长期值…
填充长词典：207
填充长arrays：14
search长词典：75
search长arrays：435

3000000string值…
填充string数组：5553
填充string字典：449
sortingstring数组：11695
searchstring词典：194
searchstring数组：10594

10000000长期值…
填写长词典：521
填充长arrays：47
search长词典：202
search长阵：1181

10000000string值…
填充string数组：18119
填充string字典：1088
sortingstring数组：28174
searchstring字典：747
searchstring数组：26503

而为了比较，这里是程序最后一次运行的分析器输出（1000万条logging和查找）。 我强调了相关的function。 他们非常赞同上面的秒表计时指标。

您可以看到，字典查找比二分查找要快得多，并且（如预期的），集合越大，差别就越明显。 所以，如果你有一个合理的哈希函数（相当快速，碰撞less），一个哈希查找应该击败二进制search范围内的集合。

Answer 3

鲍比，比尔和科宾的答案是错误的。 O（1）不会比O（log n）慢一个固定/有界的n：

log（n）是恒定的，所以它取决于恒定的时间。

而对于一个慢哈希函数，听说过md5？

默认的string散列algorithm可能会触及所有字符，对于长string键，可能比平均比较容易100倍。 去过也做过。

您可能能够（部分）使用基数。 如果你可以分成256个大致相同大小的块，你正在寻找2k到40k二进制search。 这可能会提供更好的性能。

[编辑]太多的人投票他们不明白。

string比较二进制searchsorting集有一个非常有趣的属性：越接近目标越慢。 首先，他们将打破第一个字符，最后只是最后一个。 假设它们的持续时间不正确。

Answer 4

这个问题唯一合理的答案是：这取决于。 这取决于你的数据的大小，你的数据的形状，你的散列实现，你的二进制search实现，以及你的数据在哪里（即使没有在问题中提到）。 其他一些答案也是如此，所以我可以删除它。 不过，把我从反馈中学到的东西分享给我原来的答案可能会很好。

1. 我写道：“ 哈希algorithm是O（1），而二进制search是O（log n）。 ” – 正如评论中指出的，大O符号估计的是复杂性，而不是速度。 这是绝对正确的。 值得注意的是，我们通常使用复杂性来了解algorithm的时间和空间要求。 所以，尽pipe假设复杂性与速度是完全一样的，但在你脑海中没有时间和空间的情况下估计复杂性是非常不寻常的。 我的build议：避免大O符号。
2. 我写道：“ 所以当n接近无限时 …” – 这是关于我可以包含在答案中的最愚蠢的事情。 无限与你的问题无关。 你提到一千万的上限。 忽略无限。 正如评论者所指出的，非常多的数字会产生各种各样的问题。 （非常大的数字也不会让二进制search在公园里散步。）我的推荐：除非你的意思是无限，否则不要提无限。
3. 另外从注释：注意默认的string散列（你是哈希string？你不提）。，数据库索引往往是b-树（思考）。 我的build议：考虑你所有的select。 考虑其他的数据结构和方法，比如老式的trie （用于存储和检索string）或者R-tree （用于空间数据）或者MA-FSA （Minimal Acyclic Finite State Automaton – 小存储空间）。

鉴于评论，你可能会认为使用散列表的人是疯了。 哈希表是鲁莽和危险的？ 这些人是疯了吗？

原来他们不是。 就像二叉树在某些事情上（按顺序的数据遍历，存储效率）是好的一样，哈希表也有其闪光的时刻。 特别是，他们可以很好地减less获取数据所需的读取次数。 哈希algorithm可以生成一个位置并直接跳转到内存或磁盘上，而二进制search在每次比较过程中读取数据以决定下一步要读什么。 每次读取都有可能导致caching未命中，这比CPU指令慢了一个数量级（或更多）。

这并不是说哈希表比二进制search更好。 他们不是。 这也不是说所有的哈希和二进制search实现都是一样的。 他们不是。 如果我有一个观点，那就是：这两种方法都是有原因的。 由您决定哪个最适合您的需求。

原始答案：

---

散列algorithm是O（1），而二进制search是O（log n）。 所以当n接近无穷大时，散列performance相对于二分查找而改善。 您的里程将取决于n，您的散列实现和二进制search实现。

关于O（1）的有趣的讨论 。 转述：

O（1）并不意味着即时。 这意味着性能不会随着n的增长而变化。 你可以devise一个很慢的散列algorithm，没有人会使用它，它仍然是O（1）。 我相当确信.NET / C＃不会受到成本过高的哈希，但是;）

Answer 5

如果你的一组对象是真正的静态和不变的，你可以使用一个完美的散列来保证O（1）的性能。 我已经看过几次，但我从来没有机会自己使用它。

Answer 6

哈希值通常更快，尽pipe二进制search具有更好的最坏情况特征。 哈希访问通常是一个计算来获得一个哈希值来确定一个logging将在哪个“桶”，所以性能通常取决于logging分布的均匀程度以及用于search桶的方法。 一个糟糕的散列函数（留下几桶大量的logging）与通过桶的线性search将导致search缓慢。 （另一方面，如果你正在读取一个磁盘而不是内存，哈希桶可能是连续的，而二叉树几乎可以保证非本地访问。）

如果你想快速的使用哈希。 如果你真的想保证有界的性能，你可以去二叉树。

Answer 7

惊讶的没有人提到杜鹃哈希，它提供了保证O（1），而不像完美的哈希，是能够使用所有的内存分配，在完美的哈希可以以保证O（1）结束，但浪费大部分分配。 警告？ 插入时间可能非常缓慢，特别是随着元件数量的增加，因为所有的优化都是在插入阶段进行的。

我相信有一些版本的这个在路由器硬件中用于ip查找。

请参阅链接文字

Answer 8

我强烈怀疑在一个大小为〜1M的问题集合中，哈希会更快。

只是为了数字：

二进制search需要〜20比较（2 ^ 20 == 1M）

散列查找将需要在search关键字上进行1次散列计算，之后可能会进行一些比较来解决可能的冲突

编辑：数字：

  for (int i = 0; i < 1000 * 1000; i++) { c.GetHashCode(); } for (int i = 0; i < 1000 * 1000; i++) { for (int j = 0; j < 20; j++) c.CompareTo(d); } 

次：c =“abcde”，d =“rwerij”哈希码：0.0012秒。 比较：2.4秒。

免责声明：实际上，对散列查找与二进制查找进行比较可能比这个不完全相关的testing更好。 我什至不知道如果GetHashCode得到memo引擎盖

Answer 9

字典/散列表使用更多的内存，需要更多的时间来填充比较数组。 但search是由字典而不是数组中的二进制search更快地完成。

以下是要search和填充的一千万个Int64项目的数字。 再加上你可以自己运行的示例代码。

字典内存： 462,836

arrays内存： 88,376

填充词典： 402

填充数组： 23

search词典： 176

searcharrays： 680

 using System; using System.Collections.Generic; using System.Diagnostics; namespace BinaryVsDictionary { internal class Program { private const long Capacity = 10000000; private static readonly Dictionary<long, long> Dict = new Dictionary<long, long>(Int16.MaxValue); private static readonly long[] Arr = new long[Capacity]; private static void Main(string[] args) { Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); for (long i = 0; i < Capacity; i++) { Dict.Add(i, i); } stopwatch.Stop(); Console.WriteLine("Populate Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); for (long i = 0; i < Capacity; i++) { Arr[i] = i; } stopwatch.Stop(); Console.WriteLine("Populate Array: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); for (long i = 0; i < Capacity; i++) { long value = Dict[i]; // Console.WriteLine(value + " : " + RandomNumbers[i]); } stopwatch.Stop(); Console.WriteLine("Search Dictionary: " + stopwatch.ElapsedMilliseconds); stopwatch.Reset(); stopwatch.Start(); for (long i = 0; i < Capacity; i++) { long value = BinarySearch(Arr, 0, Capacity, i); // Console.WriteLine(value + " : " + RandomNumbers[i]); } stopwatch.Stop(); Console.WriteLine("Search Array: " + stopwatch.ElapsedMilliseconds); Console.ReadLine(); } private static long BinarySearch(long[] arr, long low, long hi, long value) { while (low <= hi) { long median = low + ((hi - low) >> 1); if (arr[median] == value) { return median; } if (arr[median] < value) { low = median + 1; } else { hi = median - 1; } } return ~low; } } } 

Answer 10

我会说这主要取决于散列和比较方法的性能。 例如，使用非常长而随机的string键时，比较总是会产生一个非常快的结果，但默认的散列函数将处理整个string。

但在大多数情况下，哈希映射应该更快。

Answer 11

我想知道为什么没有人提到完美的哈希 。

只有在你的数据集被固定很长一段时间的情况下才有意义，但是它能够分析数据并构build一个完美的散列函数来确保没有冲突。

相当整洁，如果你的数据集是恒定的，计算函数的时间比应用程序运行时间小。

Answer 12

这取决于你如何处理哈希表的重复（如果有的话）。 如果你想允许散列键重复（没有散列函数是完美的），它仍然是O（1）的主键查找，但后面search“正确”的价值可能是昂贵的。 那么答案是，在大多数情况下，哈希值更快。 YMMV取决于你放哪些数据…

Answer 13

这里描述了哈希是如何构build的，因为密钥的Universe是相当大的，并且哈希函数被构build为“非常内射的”，所以碰撞很less发生，哈希表的访问时间实际上不是O（1）…它是基于一些概率的东西。 但是，可以说散列的访问时间几乎总是小于时间O（log_2（n））

Answer 14

当然，散列对于这样一个大数据集来说是最快的。

由于数据很less改变，一种更加快速的方法是以编程方式生成临时代码，将第一层search作为巨大的开关语句（如果编译器可以处理的话），然后分支search由此产生的桶。

Answer 15

答案取决于。 让我们认为元素“n”的数量非常大。 如果你擅长编写一个更好的散列函数，那么碰撞就更less，那么散列是最好的。 请注意，散列函数在search时只执行一次，并指向相应的存储桶。 所以如果n很高，这不是一个很大的开销。
Hashtable中的问题：但是散列表中的问题是如果散列函数不好（更多的冲突发生），那么search不是O（1）。 它倾向于O（n），因为在一个桶中search是一个线性search。 可以比二叉树更糟糕。 二叉树问题：在二叉树中，如果树不平衡，它也倾向于O（n）。 例如，如果将1,2,3,4,5插入到更可能是列表的二叉树中。 所以，如果你能看到一个很好的哈希方法，使用哈希表如果没有，你最好使用二叉树。