Который быстрее, поиск Хеша или Двоичный поиск?

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

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

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

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

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

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

Я сильно подозреваю, что в проблемном наборе размера ~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 мемоизованным под капотом

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

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

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

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

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

См. текст ссылки

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

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

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

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

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

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

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

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

Исходный ответ:

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

Интересное обсуждение O (1) . Перефразируемый:

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

Ответы Bobby, Bill и Corbin являются неправильными. O (1) не медленнее, чем O (зарегистрируйте n) для фиксирования/ограничивания n:

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

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

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

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

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

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

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

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

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);
    }
}

Вот результаты с несколькими различными размерами наборов. (Времена находятся в миллисекундах.)

500 000 значений Long...
Заполняют Словарь Long: 26
Заполняют Массив Long: 2
Поиск Словарь Long: 9
Поиск Массив Long: 80

500 000 Строковых значений...
Заполняют Массив строк: 1237
Заполняет Строковый Словарь: 46
Массив строк Вида: 1755
Словарь Строки поиска: 27
Массив Строки поиска: 1569

1 000 000 значений Long...
Заполняют Словарь Long: 58
Заполняют Массив Long: 5
Поиск Словарь Long: 23
Поиск Массив Long: 136

1 000 000 Строковых значений...
Заполняют Массив строк: 2070
Заполняет Строковый Словарь: 121
Массив строк Вида: 3579
Словарь Строки поиска: 58
Массив Строки поиска: 3267

3 000 000 значений Long...
Заполняют Словарь Long: 207
Заполняют Массив Long: 14
Поиск Словарь Long: 75
Поиск Массив Long: 435

3 000 000 Строковых значений...
Заполняют Массив строк: 5553
Заполняют Строковый Словарь: 449
Массив строк Вида: 11695
Словарь Строки поиска: 194
Массив Строки поиска: 10594

10 000 000 значений Long...
Заполняют Словарь Long: 521
Заполняют Массив Long: 47
Поиск Словарь Long: 202
Поиск Массив Long: 1181

10 000 000 Строковых значений...
Заполняют Массив строк: 18119
Заполняют Строковый Словарь: 1088
Массив строк Вида: 28174
Словарь Строки поиска: 747
Массив Строки поиска: 26503

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

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