Что быстрее, хэш-поиск или двоичный поиск?

для очень маленьких коллекций разница будет незначительна. В нижней части вашего диапазона (500k элементов) вы начнете видеть разницу, если вы делаете много поисков. Двоичный поиск будет O (log n), тогда как хэш-поиск будет O(1),амортизированной. Это не то же самое, что действительно константа, но вам все равно придется иметь довольно ужасную хэш-функцию, чтобы получить худшую производительность, чем двоичный поиск.

(когда я говорю "ужасный хэш", я имею в виду что-то вроде:

hashCode()
{
    return 0;
}

Да, он сам пылает быстро, но заставляет вашу хэш-карту стать связанным списком.)

ialiashkevich написал некоторый код C#, используя массив и словарь для сравнения двух методов, но он использовал длинные значения для ключей. Я хотел проверить что-то, что действительно выполняло бы хэш-функцию во время поиска, поэтому я изменил этот код. Я изменил его, чтобы использовать строковые значения, и я вынес заполнения и просмотра разделов в собственные методы, так что это легче увидеть в профилировщике. Я также оставил в коде, который использовал длинные значения, просто как точку сравнения. Наконец, я избавился от пользовательской функции двоичного поиска и использовал ее в 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

и для сравнения, вот результат профилировщика для последнего запуска программы (10 миллионов записей и поисков). Я выделил соответствующие функции. Они довольно близко согласитесь с метриками времени секундомера выше.

вы можете видеть, что поиск по словарю намного быстрее, чем двоичный поиск, и (как и ожидалось) разница более выражена, чем больше коллекция. Итак, если у вас есть разумная функция хэширования (довольно быстрая с несколькими коллизиями), поиск хэша должен бить двоичный поиск коллекций в этом диапазоне.

ответы Бобби, Билла и Корбина неверны. O (1) не медленнее, чем O(log n) для фиксированного/ограниченного n:

log (n) является постоянным, поэтому он зависит от постоянного времени.

и для медленной хэш-функции, когда-нибудь слышали о md5?

алгоритм хэширования строк по умолчанию, вероятно, касается всех символов и может быть легко в 100 раз медленнее, чем среднее сравнение для длинных строковых ключей. Был там, сделал это.

вы могли бы быть в состоянии (частично) используйте корень. Если вы можете разделить на 256 блоков примерно одинакового размера, вы смотрите на 2k-40k двоичный поиск. Это, вероятно, обеспечит гораздо лучшую производительность.

[редактирование] Слишком много людей голосуют против того, что они не понимают.

строка сравнивает для двоичного поиска сортированные наборы имеют очень интересное свойство: они становятся медленнее, чем ближе они добираются до цели. Сначала они разобьются на первого персонажа, в конце только на последнего. Предполагая постоянное время для них это неверно.

единственный разумный ответ на этот вопрос: это зависит. Это зависит от размера ваших данных, формы ваших данных, вашей реализации хэша, вашей реализации двоичного поиска и того, где ваши данные живут (даже если это не упоминается в вопросе). Несколько других ответов говорят об этом, поэтому я мог бы просто удалить это. Тем не менее, было бы неплохо поделиться тем, что я узнал из обратной связи с моим оригинальным ответом.

1. я писал:"хэш-алгоритмы O (1) в то время как двоичный поиск-O (log n). " - как отмечается в комментариях, Big O notation оценивает сложность, а не скорость. Это абсолютно верно. Стоит отметить, что мы обычно используем сложность, чтобы получить представление о временных и пространственных требованиях алгоритма. Поэтому, хотя глупо предполагать, что сложность строго совпадает со скоростью, оценка сложности без времени или пространства в глубине вашего ума необычна. Моя рекомендация: избегайте больших обозначений O.
2. я писал:"так как N подходов бесконечность..."Это самая глупая вещь, которую я мог бы включить в ответ. Бесконечность не имеет ничего общего с вашей проблемой. Вы упомянули верхнюю границу в 10 миллионов. Игнорируйте бесконечность. Как отмечают комментаторы, очень большие числа создадут всевозможные проблемы с хэшем. (Очень большие числа также не делают двоичный поиск прогулкой в парке.) Моя рекомендация: не упоминайте бесконечность, если вы не имеете в виду бесконечность.
3. также из комментариев: остерегайтесь строки по умолчанию хэши (вы хэширование строк? Ты не упоминаешь.), индексы базы данных часто являются b-деревьями (пища для размышлений). Моя рекомендация: рассмотрите все ваши варианты. Рассмотрим другие структуры данных и подходы... как старомодный бор (для хранения и извлечения строк) или R-tree (пространственных данных) или MA-FSA (минимальный ациклический конечный автомат - малый объем памяти).

учитывая комментарии, Вы можете предположить что люди, которые используют хэш-таблицы невменяемы. Являются ли хэш-таблицы безрассудными и опасными? Эти люди сошли с ума?

оказывается, это не так. Так же, как бинарные деревья хороши в определенных вещах (обход данных в порядке, эффективность хранения), хэш-таблицы также имеют свой момент, чтобы сиять. В частности, они могут быть очень хороши в уменьшении количества считываний, необходимых для получения ваших данных. Хэш-алгоритм может генерировать местоположение и переходить прямо к нему в памяти или на диске во время двоичного поиска считывает данные во время каждого сравнения, чтобы решить, что Читать далее. Каждое чтение имеет потенциал для промаха кэша, который на порядок (или более) медленнее, чем инструкция CPU.

Это не значит, что хэш-таблицы лучше, чем бинарный поиск. Это не так. Это также не означает, что все реализации хэш-и двоичного поиска одинаковы. Это не так. Если у меня есть точка зрения, это так: оба подхода существуют по какой-то причине. Это до вас, чтобы решить, что лучше для вашего по необходимости.

оригинальный ответ:

---

хэш-алгоритмы-O(1), а двоичный поиск-O (log n). Так как Н приближается к бесконечности, хэш-производительность улучшается относительно двоичной поиск. Ваш пробег будет варьироваться в зависимости от n, вашего хэша реализация и реализация двоичного поиска.

интересная дискуссия на O (1). Перефразировал:

O (1) не означает мгновенный. Это означает, что производительность не изменение по мере роста размера n. Вы можете разработать алгоритм хэширования это так медленно, что никто никогда не будет использовать его, и он все равно будет O(1). Я уверен, что .NET / C# не страдает от дорогостоящего хэширования, однако ;)

Если ваш набор объектов действительно статичен и неизменен, вы можете использовать идеальный хэш - чтобы получить гарантированную производительность O(1). Я видел gperf упоминалось несколько раз, хотя у меня никогда не было случая использовать его сам.

хэши, как правило, быстрее, хотя двоичный поиск имеет лучшие худшие характеристики. Хэш-доступ обычно представляет собой вычисление для получения хэш-значения, чтобы определить, в каком" ведре " будет находиться запись, и поэтому производительность обычно зависит от того, насколько равномерно распределены записи и метод, используемый для поиска в ведре. Плохая хэш-функция (оставляя несколько ведер с большим количеством записей) с линейным поиском по ведрам приведет к медленному поиску. (По поводу в-третьих, если Вы читаете диск, а не память, хэш-ведра, скорее всего, будут смежными, а двоичное дерево в значительной степени гарантирует нелокальный доступ.)

Если вы хотите вообще быстро, используйте хэш. Если вы действительно хотите гарантированную ограниченную производительность, вы можете пойти с двоичным деревом.

удивительно, что никто не упомянул о хешировании Cuckoo, которое обеспечивает гарантированное O(1) и, в отличие от совершенного хеширования, способно использовать всю выделяемую память, где, как совершенное хеширование, может закончиться гарантированным O(1), но тратить большую часть своего выделения. Предостережение? Время вставки может быть очень медленным, особенно при увеличении количества элементов, так как вся оптимизация выполняется во время фазы вставки.

Я полагаю, что некоторые версии этого используется в оборудование маршрутизатора для ip-поиска.

посмотреть текст ссылки

словарь / Hashtable использует больше памяти и занимает больше времени для заполнения по сравнению с массивом. Но поиск выполняется быстрее по словарю, а не двоичный поиск в массиве.

вот цифры для 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;
        }
    }
}

Я сильно подозреваю, что в проблемном наборе размером ~1 м хэширование будет быстрее.

только для чисел:

двоичный поиск потребует ~ 20 сравнений (2^20 == 1M)

поиск хэша потребует вычисления 1 хэша в ключе поиска и, возможно, нескольких сравнений после этого для разрешения возможных коллизий

Edit: the numbers:

    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 получает memoized under-the-hood

Я бы сказал, что это зависит в основном от производительности хэш-методов и методов сравнения. Например, при использовании строковых ключей, которые являются очень длинными, но случайными, сравнение всегда будет давать очень быстрый результат, но хэш-функция по умолчанию будет обрабатывать всю строку.

но в большинстве случаев хэш-карта должна быть быстрее.

интересно, почему никто не упомянул идеальное хеширование.

Это актуально только в том случае, если ваш набор данных фиксирован в течение длительного времени, но что он делает, он анализирует данные и строит идеальную хэш-функцию, которая не гарантирует никаких коллизий.

довольно аккуратно, если ваш набор данных постоянен и время для вычисления функции мало по сравнению с временем выполнения приложения.

Это зависит от того, как вы обрабатывать дубликаты для хэш-таблиц (если вообще). Если вы хотите разрешить дубликаты хэш-ключей(ни одна хэш-функция не идеальна), она остается O (1) для поиска первичного ключа, но поиск "правильного" значения может быть дорогостоящим. Ответ: тогда, теоретически, большую часть времени, хэши быстрее. YMMV в зависимости от того, какие данные вы туда положите...

здесь описано, как создаются хэши, и поскольку Вселенная ключей достаточно велика, а хэш-функции построены так, чтобы быть "очень инъективными", так что столкновения редко происходят, время доступа к хэш-таблице на самом деле не O(1)... это что-то, основанное на некоторых вероятностях. Но, разумно сказать, что время доступа хэша почти всегда меньше времени O (log_2 (n))

конечно, хэш является самым быстрым для такого большого набора данных.

один из способов ускорить его еще больше, поскольку данные редко меняются,-это программно генерировать специальный код для выполнения первого уровня поиска в виде гигантского оператора switch (если ваш компилятор может его обрабатывать), а затем ветвиться для поиска результирующего ведра.

ответ зависит от того. Давайте подумаем, что количество элементов 'n' очень велико. Если вы хорошо пишете лучшую хэш-функцию, которая меньше коллизий, то хэширование является лучшим. отметим, что Хэш-функция выполняется только один раз при поиске и направляется в соответствующее ведро. Так что это не большие накладные расходы, если n является высокой.
проблема в Hashtable: Но проблема в хэш-таблицах заключается в том, что хэш-функция не очень хороша (больше коллизий происходит), тогда поиск не O (1). Он имеет тенденцию к O (n), потому что поиск в ведре является линейным поиском. Может быть хуже, чем двоичное дерево. проблема в двоичном дереве: В двоичном дереве, Если дерево не сбалансировано, оно также имеет тенденцию к O(n). Например, если вы вставили 1,2,3,4,5 в двоичное дерево, которое было бы более вероятным списком. и Если вы видите хорошую методологию хэширования, используйте хэш-таблицу Если нет, то лучше использовать двоичное дерево.