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

Ответ 1

Хорошо, я постараюсь быть коротким.

Короткий ответ С#:

Проверьте два разных подхода.

.NET дает вам инструменты для изменения вашего подхода с помощью строки кода. В противном случае используйте System.Collections.Generic.Dictionary и обязательно инициализируйте его большим количеством в качестве начальной емкости, иначе вы будете переносить оставшуюся часть своей жизни, вставляя элементы из-за того, что GC должен выполнить сбор старых массивов ковша.

Дольше ответ:

Хэш-таблица имеет ALMOST постоянное время поиска, и получение элемента в хеш-таблице в реальном мире не просто требует вычисления хэша.

Чтобы перейти к элементу, ваша хэш-таблица сделает что-то вроде этого:

• Получить хэш ключа
• Получить номер ведра для этого хэша (обычно функция отображения выглядит так: bucket = hash% bucketsCount)
• Пройдите цепочку элементов (в основном это список элементов, которые разделяют то же самое ведро, большинство хеш-таблиц используют этот метод обработки ковша/хеша столкновения), который начинается с этого ведро и сравнить каждую клавишу с один из предметов, которые вы пытаетесь добавить/удалить/обновить/проверить, если содержатся.

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

Лучшее и более глубокое объяснение: http://en.wikipedia.org/wiki/Hash_table

Ответ 2

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

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

hashCode()
{
    return 0;
}

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

ialiashkevich написал код С#, используя массив и словарь для сравнения двух методов, но использовал длинные значения для ключей. Я хотел проверить что-то, что фактически выполнило бы хэш-функцию во время поиска, поэтому я изменил этот код. Я изменил его на использование значений String, и я переработал разделы заполнения и поиска в свои собственные методы, чтобы их легче было видеть в профилировщике. Я также оставил в коде, который использовал значения 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: 1237
Заглавие Строковый словарь: 46
Сортировка строкового массива: 1755
Поиск Строковый словарь: 27
Поиск Строковый массив: 1569

1000000 Длинные значения...
Заполнять длинный словарь: 58
Заполнение длинного массива: 5
Поиск длинный словарь: 23
Поиск длинного массива: 136

1000000 Строковые значения...
Заполнение массива String: 2070
Заглавие Строковый словарь: 121
Сортировка строкового массива: 3579
Словарь поисковой строки: 58 ​​
Поиск Строковый массив: 3267

3000000 Длинные значения...
Заполняют длинный словарь: 207
Заполнение длинного массива: 14
Поиск длинный словарь: 75
Поиск длинного массива: 435

3000000 Значения строк...
Заполнение массива String: 5553
Пополнить строковый словарь: 449
Sort String Array: 11695
Поиск Словарь по строкам: 194
Поиск Строковый массив: 10594

10000000 Длинные значения...
Заполняют длинный словарь: 521
Заполнение длинного массива: 47
Поисковый длинный словарь: 202
Поиск длинного массива: 1181

10000000 Значения строк...
Заполнение массива String: 18119
Заглавие Строковый словарь: 1088
Sort String Array: 28174
Поиск Строковый словарь: 747
Поиск Строковый массив: 26503

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

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

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

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

Ответ 8

Словарь/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;
        }
    }
}

Ответ 9

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

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

для двоичного поиска потребуется ~ 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);
    }

times: c = "abcde", d = "rwerij" hashcode: 0.0012 секунд. Сравнить: 2,4 секунды.

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

Ответ 10

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

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

Ответ 11

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

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

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

Ответ 12

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

Ответ 13

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

Ответ 14

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

Один из способов ускорить его, поскольку данные редко меняются, заключается в том, чтобы программно генерировать ad-hoc-код для первого уровня поиска в качестве гигантского оператора switch (если ваш компилятор может его обработать), а затем разветвления чтобы выполнить поиск в полученном ведре.

Ответ 15

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

Ответ 16

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

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

Сложность среды выполнения хеш-таблицы (вставка, поиск и удаление)

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

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

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

Ответ 17

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

Но если вы включите оптимизацию компилятора и попробуете тот же тест с меньшим числом выборок, скажем, менее 10 000, бинарный поиск превзошел поиск по хешу, используя преимущества своей структуры данных, удобной для кэша.