Линейное зондирование огромных последовательностей ключей с неравным хешем

Question

В линейном зондировании (хэш-таблицах) есть одна вещь, которая мне не понятна.Если я добавлю ключ 1, результаты которого хешируются, к индексу массива 1. Затем я помещу ключ 2 -> индекс массива 2. Затем я положу ключ 3 -> снова индекс массива 1, это перейдет к индексу массива 3. Затем, когда я ищу ключ 3, я должен идтичерез индексы, которые содержат ключи, которые не имеют такой же хэш, как у меня.Разве это не отходы?Если последовательность действительно большая и содержит много ключей (например, у меня есть 20 элементов, тогда ноль, для любого ключа, который приводит к индексу массива от 0 до 20, я должен просмотреть все индексы, хотя они не имеют тот же хэш, что и мойи я могу устранить это с помощью отдельной цепочки).

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

Answer 1

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

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

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

Есть несколько методов, которые вы можете использовать, чтобы смягчить это.Хэширование Робин Гуда работает, перемещая элементы после того, как они были размещены так, что элементы, которые находятся ближе к дому, отодвигаются дальше, чтобы освободить место для элементов, которые ближе к дому.Это делает среднюю стоимость поиска немного выше, но резко снижает стоимость поиска в худшем случае (другими словами, это уменьшает дисперсию стоимости поиска в обмен на увеличение ожидаемого значения этих затрат поиска).Хеширование в Hopscotch работает, ограничивая максимальное расстояние, на которое элементы могут быть смещены, и поддерживая битовую маску, указывающую, какие элементы рядом могут быть совпадающими, сокращая объем работы, которую вам нужно сделать, чтобы найти вещи.А новый Google flat_map начинается с линейного зондирования и использует действительно умное хеширование и параллельные операции с памятью, чтобы сделать поиск чрезвычайно быстрым.

Answer 2

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

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