哈希查找和二分查找哪个更快？

Question

当给定一组静态对象时（静态是指一旦加载，它就很少发生变化），需要重复并发查找以实现最佳性能，HashMap 或带有使用一些自定义比较器进行二分搜索？

答案是对象或结构类型的函数吗？ 散列和/或相等函数性能？ 哈希唯一性？ 清单大小？ 哈希集大小/集合大小？

我正在查看的集合的大小可以是 500k 到 10m 之间的任意值 - 如果该信息有用的话。

虽然我正在寻找 C# 答案，但我认为真正的数学答案并不在于语言中，因此我不包含该标签。 但是，如果需要注意 C# 特定的事情，则需要该信息。

Answer 1

这取决于您如何处理哈希表的重复项（如果有的话）。 如果您确实希望允许哈希键重复（没有完美的哈希函数），则主键查找仍然是 O(1)，但后面搜索“正确”值的成本可能会很高。 答案是，理论上大多数时候，哈希更快。 YMMV 取决于您放在那里的数据......

Answer 2

这里 描述了哈希是如何构建的以及键的宇宙相当大，并且哈希函数被构建为“非常单射”，因此很少发生冲突，哈希表的访问时间实际上不是 O(1) ...它是基于某些概率的。
但是，可以合理地说，哈希的访问时间几乎总是小于时间 O(log_2(n))

Answer 3

这更多的是对比尔答案的评论，因为他的答案尽管是错误的，但还是得到了很多支持。 所以我不得不发布这个。

我看到很多关于哈希表中查找的最坏情况复杂性是什么，以及什么被认为是摊销分析/什么不是的讨论。
请检查下面的链接

哈希表运行时复杂性（插入、搜索和删除）

最坏情况的复杂度是 O(n) 而不是 O(1)，这与 Bill 所说的相反。 因此，他的 O(1) 复杂度不会被摊销，因为这种分析只能用于最坏的情况（他自己的维基百科链接也是如此）

https://en.wikipedia.org/wiki/Hash_table

https ://en.wikipedia.org/wiki/Amortized_analysis

Answer 4

当然，对于如此大的数据集，哈希是最快的。

由于数据很少发生变化，一种进一步加快速度的方法是以编程方式生成临时代码，将第一层搜索作为一个巨大的 switch 语句（如果您的编译器可以处理它），然后分支进行搜索由此产生的桶。

Answer 5

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

Answer 6

对于非常小的收藏，差异可以忽略不计。 在范围的低端（500k 项），如果您进行大量查找，您将开始看到差异。 二分查找的时间复杂度为 O(log n)，而哈希查找的时间复杂度为 O(1)，摊销< /a>. 这与真正的常数不同，但您仍然需要一个非常糟糕的哈希函数才能获得比二分搜索更差的性能。

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

hashCode()
{
    return 0;
}

是的，它本身速度非常快，但会导致您的哈希映射成为链接列表。）

ialiashkevich 使用数组和字典编写了一些 C# 代码来比较这两种方法，但它使用 Long 值作为键。 我想测试在查找过程中实际执行哈希函数的东西，所以我修改了该代码。 我将其更改为使用字符串值，并将填充和查找部分重构为它们自己的方法，以便更容易在探查器中查看。 我还保留了使用 Long 值的代码，只是作为比较点。 最后，我摆脱了自定义的二分搜索函数并使用了 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
填充长数组：2
搜索长词典：9
搜索长数组：80

500000 个字符串值...
填充字符串数组：1237
填充字符串字典：46
排序字符串数组：1755
搜索字符串字典：27
搜索字符串数组：1569

1000000 长值...
填充长词典：58
填充长数组：5
搜索长词典：23
搜索长数组：136

1000000 个字符串值...
填充字符串数组：2070
填充字符串字典：121
排序字符串数组：3579
搜索字符串字典：58
搜索字符串数组：3267

3000000 个长值...
填充长词典：207
填充长数组：14
搜索长词典：75
搜索长数组：435

3000000 个字符串值...
填充字符串数组：5553
填充字符串字典：449
排序字符串数组：11695
搜索字符串词典：194
搜索字符串数组：10594

10000000 长值...
填充长词典：521
填充长数组：47
搜索长词典：202
搜索长数组：1181

10000000 字符串值...
填充字符串数组：18119
填充字符串字典：1088
排序字符串数组：28174
搜索字符串词典：747
搜索字符串数组：26503

为了进行比较，这里是程序上次运行的探查器输出（1000 万条记录和查找）。 我强调了相关功能。 他们非常同意上面的秒表计时指标。

您可以看到字典查找比二分搜索快得多，并且（如预期的那样）集合越大，差异越明显。 因此，如果您有一个合理的散列函数（相当快且很少发生冲突），则对于此范围内的集合，散列查找应该胜过二分搜索。

Answer 7

鲍比、比尔和科尔宾的答案是错误的。 对于固定/有界 n，O(1) 并不慢于 O(log n)：

log(n) 是常数，因此它取决于常数时间。

对于慢速哈希函数，听说过 md5 吗？

默认的字符串哈希算法可能涉及所有字符，并且很容易比长字符串键的平均比较慢 100 倍。 去过也做过。

您也许可以（部分）使用基数。 如果您可以分成 256 个大致相同大小的块，那么您正在考虑 2k 到 40k 的二分搜索。 这可能会提供更好的性能。

[编辑]
太多人对他们不理解的事情投了否决票。

用于二分搜索排序集的字符串比较有一个非常有趣的属性：它们越接近目标，它们就越慢。 首先，它们会在第一个字符处中断，最后仅在最后一个字符处中断。 假设它们的时间恒定是不正确的。

Answer 8

这个问题唯一合理的答案是：视情况而定。 这取决于数据的大小、数据的形状、哈希实现、二分搜索实现以及数据所在的位置（即使问题中没有提及）。 其他几个答案也说了这么多，所以我可以删除它。 然而，分享我从原始答案的反馈中学到的东西可能会很好。

1. 我写道，“哈希算法的复杂度为 O(1)，而二分搜索的复杂度为 O(log n)。” - 正如评论中所述，Big O 表示法估计的是复杂性，而不是速度。 这是绝对正确的。 值得注意的是，我们通常使用复杂性来了解算法的时间和空间要求。 因此，虽然假设复杂性与速度完全相同是愚蠢的，但在没有时间或空间的情况下估计复杂性是不寻常的。 我的建议：避免使用 Big O 表示法。
2. 我写道，“因此，当 n 接近无穷大...” - 这是我可以在答案中包含的最愚蠢的事情。 无穷大与你的问题无关。 你提到了1000万的上限。 忽略无穷大。 正如评论者指出的那样，非常大的数字会导致哈希产生各种问题。 （非常大的数字也不会让二分搜索变得轻而易举。）我的建议：不要提及无穷大，除非您指的是无穷大。
3. 另外来自评论：当心默认的字符串哈希（你对字符串进行哈希处理吗？你没有提到。），数据库索引通常是 b 树（值得深思）。 我的建议：考虑你所有的选择。 考虑其他数据结构和方法......比如老式的 trie （用于存储和检索字符串）或 R-tree （用于空间数据）或 MA-FSA（最小非循环有限状态自动机 - 小存储占用）。

鉴于这些评论，您可能会认为使用哈希表的人精神错乱。 哈希表是否鲁莽且危险？ 这些人疯了吗？

事实证明他们不是。 正如二叉树擅长某些事情（有序数据遍历、存储效率）一样，哈希表也有其闪光的时刻。 特别是，它们可以非常擅长减少获取数据所需的读取次数。 哈希算法可以生成一个位置并直接跳转到内存或磁盘中的该位置，而二分搜索在每次比较期间读取数据以决定下一步读取什么。 每次读取都有可能发生缓存未命中，这比 CPU 指令慢一个数量级（或更多）。

这并不是说哈希表比二分搜索更好。 他们不是。 这也不意味着所有哈希和二分搜索实现都是相同的。 他们不是。 如果我有一个观点的话，那就是：这两种方法的存在都是有原因的。 由您决定哪一个最适合您的需求。

原答案：

---

哈希算法的复杂度为 O(1)，而二分查找的复杂度为 O(log n)。 所以当 n
接近无穷大，哈希性能相对于二进制有所提高
搜索。 你的里程将根据你的哈希值n而变化
实现，以及您的二分搜索实现。

关于 O(1) 的有趣讨论。 转述：

O(1) 并不意味着瞬时。 这意味着性能不
随着 n 大小的增长而变化。 您可以设计一个哈希算法
这太慢了，没有人会使用它，而且它仍然是 O(1)。
我相当确定 .NET/C# 不会受到成本过高的哈希的影响，
然而;)

Answer 9

好吧，我会尽量长话短说。

C# 简短回答：

测试两种不同的方法。

.NET 为您提供了通过一行代码来改变您的方法的工具。
否则，请使用 System.Collections.Generic.Dictionary 并确保使用较大的数字作为初始容量对其进行初始化，否则由于 GC 必须执行收集旧存储桶数组的工作，您将在余生中插入项目。

更长的答案：

哈希表的查找时间几乎恒定，并且在现实世界中获取哈希表中的项目不仅仅需要计算哈希值。

要获取某个项目，哈希表将执行以下操作：

• 获取键的哈希值
• 获取该哈希值的存储桶编号（通常映射函数看起来像这个存储桶 = hash % bucketsCount）
• 遍历项目链（基本上它是一个列表）共享的项目数
  大多数哈希表使用相同的存储桶
  这种处理桶/哈希的方法
  碰撞）从那时开始
  桶并将每个键与
  您正在尝试的项目之一
  添加/删除/更新/检查是否
  包含。

查找时间取决于哈希函数的“好”程度（输出的稀疏程度）和速度、您使用的存储桶的数量以及键比较器的速度，这并不总是最好的解决方案。

更好、更深入的解释： http://en.wikipedia.org/wiki /哈希表

Answer 10

尽管二分搜索具有更好的最坏情况特征，但哈希通常更快。 哈希访问通常是一种获取哈希值的计算，以确定记录将位于哪个“桶”中，因此性能通常取决于记录分布的均匀程度以及用于搜索桶的方法。 如果哈希函数不好（留下一些包含大量记录的存储桶），并且对存储桶进行线性搜索，则会导致搜索速度变慢。 （第三方面，如果您正在读取磁盘而不是内存，则哈希桶可能是连续的，而二叉树几乎可以保证非本地访问。）

如果您想要总体快速，请使用哈希。 如果您确实想要保证有限的性能，您可能会选择二叉树。

Answer 11

如果您的对象集确实是静态且不变的，则可以使用 完美哈希 来获得 O( 1）性能有保证。 我曾多次看到 gperf 被提及，但我从未有机会使用它我。

Answer 12

令人惊讶的是没有人提到 Cuckoo 哈希，它提供了有保证的 O(1)，并且与完美哈希不同，它能够使用它分配的所有内存，而完美哈希最终可以保证 O(1)，但浪费了其大部分内存。分配。 警告？ 插入时间可能非常慢，尤其是当元素数量增加时，因为所有优化都是在插入阶段执行的。

我相信它的某些版本在路由器硬件中用于 ip 查找。

请参阅链接文本

Answer 13

与数组相比，字典/哈希表使用更多内存并且需要更多时间来填充。
但是通过字典搜索比数组中的二分搜索更快。

以下是要搜索和填充的 10 百万个 Int64 项的数量。
加上您可以自己运行的示例代码。

字典内存：462,836

数组内存：88,376

填充字典：402

填充数组：23

搜索字典： 176

搜索数组：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 14

我强烈怀疑在大小约为 1M 的问题集中，散列会更快。

仅对于数字：

二分搜索将需要约 20 次比较（2^20 == 1M），

哈希查找将需要对搜索键进行 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秒。

免责声明：实际上，对哈希查找与二进制查找进行基准测试可能比这种不完全相关的测试更好。 我什至不确定 GetHashCode 是否在幕后被记住

Answer 15

我想说这主要取决于哈希和比较方法的性能。 例如，当使用非常长但随机的字符串键时，比较总是会产生非常快的结果，但默认的哈希函数将处理整个字符串。

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

Answer 16

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

仅当您的数据集长期固定时它才有意义，但它的作用是分析数据并构造一个完美的哈希函数以确保不会发生冲突。

如果您的数据集是恒定的并且计算函数的时间与应用程序运行时间相比很短，那么非常简洁。

Answer 17

这个问题比纯粹算法性能的范围更复杂。 如果我们去除二分搜索算法对缓存更友好的因素，那么哈希查找一般意义上会更快。 最好的解决方法是构建一个程序并禁用编译器优化选项，我们可以发现哈希查找速度更快，因为一般意义上其算法时间效率为 O(1)。

但是，当您启用编译器优化，并尝试使用较小数量的样本（例如少于 10,000 个）进行相同的测试时，二分搜索利用其缓存友好的数据结构，其性能优于哈希查找。