哪个更快,哈希查找或二进制搜索？

Question

当给定一组静态对象(在某种意义上是静态的,一旦加载它很少会发生变化),需要重复的并发查找以及最佳性能,哪个更好,一个HashMap或一个二进制搜索使用一些自定义比较器的数组？

答案是对象或结构类型的函数吗？哈希和/或平等功能表现？哈希的独特性？清单大小？ Hashset尺寸/尺寸？

我正在看的集合的大小可以是500k到10m之间的任何地方 - 这些信息很有用.

虽然我正在寻找一个C#答案,但我认为真正的数学答案不在于语言,所以我不包括那个标签.但是,如果需要注意C#特定的事情,那么需要该信息.

Answer 1

对于非常小的收藏品,差异可以忽略不计.在您的范围的低端(500k项目),如果您正在进行大量查找,您将开始看到差异.二进制搜索将为O(log n),而哈希查找将为O(1),并进行摊销.这与真正的常量不同,但是你仍然必须有一个相当糟糕的哈希函数来获得比二分搜索更差的性能.

(当我说"可怕的哈希"时,我的意思是:

hashCode()
{
    return 0;
}

是的,它本身就很快,但会导致你的哈希映射成为一个链表.)

ialiashkevich使用数组和字典来编写一些C#代码来比较这两种方法,但它使用了Long值作为键.我想测试在查找期间实际执行散列函数的东西,所以我修改了那段代码.我将其更改为使用String值,并将populate和lookup部分重构为自己的方法,以便在分析器中更容易看到.我还留下了使用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 String values ...
Populate String Array:1237
Populate String Dictionary:46
Sort String Array:1755
Search String Dictionary:27
Search String Array:1569

1000000长值...
填充长字典:58
填充长数组:5
搜索长字典:23
搜索长数组:136

1000000 String values ...
Populate String Array:2070
Populate String Dictionary:121
Sort String Array:3579
Search String Dictionary:58
Search String Array:3267

3000000 Long values ...
Populate Long Dictionary:207
Populate Long Array:14
Search Long Dictionary:75
Search Long Array:435

3000000 String values ...
Populate String Array:5553
Populate String Dictionary:449
Sort String Array:11695
Search String Dictionary:194
Search String Array:10594

10000000长值...
填充长字典:521
填充长数组:47
搜索长字典:202
搜索长数组:1181

10000000 String values ...
Populate String Array:18119
Populate String Dictionary:1088
Sort String Array:28174
Search String Dictionary:747
Search String Array:26503

为了比较,这是程序最后一次运行的分析器输出(1000万条记录和查找).我强调了相关的功能.他们非常赞同上面的秒表计时指标.

您可以看到字典查找比二进制搜索快得多,并且(如预期的那样)收集越大,差异越明显.因此,如果你有一个合理的散列函数(相当快的几次冲突),哈希查找应该胜过这个范围内的集合的二进制搜索.

Answer 2

Bobby,Bill和Corbin的回答是错误的.对于固定/有界n,O(1)不比O(log n)慢:

log(n)是常量,因此它取决于常量时间.

对于缓慢的哈希函数,有没有听说过md5？

默认的字符串哈希算法可能会触及所有字符,并且比长字符串键的平均比较速度慢100倍.去过也做过.

您可能(部分)使用基数.如果您可以拆分256个大致相同的块,那么您可以查看2k到40k的二进制搜索.这可能会提供更好的性能.

[编辑]太多人投票他们不理解的东西.

二进制搜索的字符串比较有序集合具有非常有趣的属性:它们越接近目标就越慢.首先,他们将打破第一个角色,最后只打破最后一个角色.假设它们的恒定时间是不正确的.

Answer 3

好的,我会尽量做空.

C#简答:

测试两种不同的方法.

.NET为您提供了使用一行代码更改方法的工具.否则使用System.Collections.Generic.Dictionary并确保使用较大的数字初始化它作为初始容量,或者由于GC必须执行的工作来收集旧的存储区阵列,您将终生插入项目.

更长的回答:

散列表具有ALMOST常量查找时间,并且在现实世界中到达散列表中的项目不仅需要计算散列.

要获取项目,您的哈希表将执行以下操作:

• 获取密钥的哈希值
• 获取该哈希的桶号(通常地图函数看起来像这个桶=哈希%bucketsCount)
• 遍历项目链(基本上是共享相同存储桶的项目列表,大多数哈希表使用这种处理存储桶/哈希冲突的方法)从该存储桶开始并将每个键与您尝试添加的项目之一进行比较/删除/更新/检查是否包含.

查找时间取决于"好"(输出的稀疏程度)和快速是您的哈希函数,您使用的桶数以及密钥比较器的速度,它并不总是最佳解决方案.

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

Answer 4

这个问题唯一合理的答案是:这取决于.这取决于数据的大小,数据的形状,哈希实现,二进制搜索实现以及数据的存在位置(即使问题中未提及).其他几个答案也说了,所以我可以删除它.但是,将我从反馈中学到的东西分享到原来的答案可能会很好.

1. 我写道," 哈希算法是O(1)而二进制搜索是O(log n). " - 如评论中所述,Big O表示法估计复杂性,而不是速度.这绝对是真的.值得注意的是,我们通常使用复杂性来了解算法的时间和空间要求.因此,虽然假设复杂性与速度完全相同是愚蠢的,但是在脑海中没有时间或空间的情况下估计复杂性是不寻常的.我的建议:避免使用Big O表示法.
2. 我写道," 所以当n接近无穷大 ......" - 这是关于我可以在答案中包含的最愚蠢的事情.无限与你的问题无关.你提到1000万的上限.忽略无限.正如评论者指出的那样,非常大的数字会产生哈希的各种问题.(非常大的数字也不能让二元搜索在公园散步.)我的建议:除非你的意思是无穷大,否则不要提及无穷大.
3. 另外从评论:当心默认字符串哈希(你是否哈希字符串？你没有提到.),数据库索引往往是b-trees(值得深思).我的建议:考虑所有选择.考虑其他数据结构和方法......如旧式trie(用于存储和检索字符串)或R树(用于空间数据)或MA-FSA(最小非循环有限状态自动机 - 小存储空间).

鉴于这些评论,您可能会认为使用哈希表的人是疯狂的.哈希表是鲁莽和危险的吗？这些人疯了吗？

事实证明他们不是.正如二叉树在某些事物上的优点(有序数据遍历,存储效率)一样,哈希表也有其发光的时刻.特别是,它们可以非常好地减少获取数据所需的读取次数.哈希算法可以生成一个位置并在内存或磁盘上直接跳转到它,而二进制搜索在每次比较期间读取数据以决定接下来要读取什么.每次读取都有可能发生缓存未命中,这比CPU指令慢一个数量级(或更多).

这并不是说哈希表比二进制搜索更好.他们不是.它也不是建议所有哈希和二进制搜索实现都是相同的.他们不是.如果我有一个观点,就是这样:两种方法都存在是有原因的.由您决定哪种方法最适合您的需求.

原始答案:

散列算法是O(1),而二进制搜索是O(log n).因此当n接近无穷大时,相对于二进制搜索,散列性能得到改善.您的里程将根据n,您的哈希实现和二进制搜索实现而有所不同.

关于O(1)的有趣讨论.转述:

O(1)并不意味着瞬间.这意味着随着n的大小增加,性能不会改变.您可以设计一个非常慢的散列算法,没有人会使用它,它仍然是O(1).我很确定.NET/C#不会遭受成本过高的散列,但是;)

Answer 5

如果您的对象集是真正静态且不变的,则可以使用完美的哈希来保证O(1)性能.我见过gperf几次提到,虽然我从来没有机会自己使用它.

Answer 6

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

如果您通常需要快速,请使用哈希.如果你真的想要保证有限的性能,你可以使用二叉树.

Answer 7

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

以下是要搜索和填充的1000万个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 8

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

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

请参阅链接文字