Линейное зондирование огромных последовательностей ключей с неравным хешем
В линейном зондировании (хэш-таблицах) есть одна вещь, которая мне не понятна. Если я добавлю ключ 1, результаты которого хешируются, к индексу массива 1. Затем я помещу ключ 2 -> индекс массива 2. Затем я положу ключ 3 -> снова индекс массива 1, это перейдет к индексу массива 3. Затем, когда я ищу ключ 3, я должен идти через индексы, которые содержат ключи, которые не имеют такой же хэш, как у меня. Разве это не отходы? Если последовательность действительно большая и содержит много ключей (например, у меня есть 20 элементов, тогда ноль, для любого ключа, который приводит к индексу массива от 0 до 20, я должен просмотреть все индексы, хотя они не имеют тот же хэш, что и мой и я могу устранить это с помощью отдельной цепочки).
Или это смягчается тем фактом, что наша функция хеширования (если она написана достаточно хорошо) распределяет ключи поровну между индексами, и мы постоянно изменяем размер массива, чтобы он был максимально наполовину полон?
2 ответа
Линейное зондирование является субоптимальным, когда имеется много столкновений. Обратите внимание, что количество коллизий зависит не только от хеша, но и от количества слотов в таблице (обычно это простое число), поскольку индекс является остатком от целочисленного деления хеша на длину таблицы.
Обратите внимание, однако, что наличие коллизирующих ключей, расположенных рядом друг с другом, может также использовать преимущества кэшей ЦП, которые будут извлекать из ОЗУ много элементов за одно чтение. Таким образом, не думайте (в принципе), что время, необходимое для проверки 20 проб, в 20 раз больше времени, необходимого для проверки одного, потому что то, что происходит внутри ЦП и его кешей, намного быстрее, чем обращение к ОЗУ. Там нет магии, хотя. Если вычисление каждого сравнения выбрасывает то, что находится в кеше, то часть экономии будет потеряна.
Проблема, которую вы определили, действительно может повлиять на производительность линейного зондирования. Когда вы пытаетесь найти какой-то элемент, вам, возможно, придется посмотреть довольно далеко от того места, где начальный хэш-тест начался, чтобы найти ваш элемент.
Тем не менее, линейное зондирование на практике чрезвычайно быстро, и это в основном из-за местоположения ссылки. Стоимость поиска чего-либо в памяти не одинакова - если вы ищите адрес рядом с тем, что вы уже недавно читали, есть вероятность, что область памяти была извлечена в кэш, а стоимость поиска очень мала. В результате стоимость таких проб на практике часто оказывается ниже, чем вы, естественно, можете ожидать, поскольку эти пробники, вероятно, довольно быстрые.
Однако это не значит, что вы можете игнорировать этот факт. Есть ряд вопросов, за которыми нужно следить. Во-первых, с увеличением коэффициента загрузки таблицы наступает момент, когда стоимость попадания в другие элементы начинает заставлять поиск занимать все больше и больше времени. Обычно вы видите, как люди перерабатывают в большой стол при коэффициенте загрузки 75%. Во-вторых, вам нужна довольно хорошая хеш-функция, поскольку, если у вас хеш-код низкого качества, который сбрасывает множество элементов в одинаковые места, вы получите действительно ужасную производительность по той причине, о которой вы упомянули.
Есть несколько методов, которые вы можете использовать, чтобы смягчить это. Хэширование Робин Гуда работает, перемещая элементы после того, как они были размещены так, что элементы, которые находятся ближе к дому, отодвигаются дальше, чтобы освободить место для элементов, которые ближе к дому. Это делает среднюю стоимость поиска немного выше, но резко снижает стоимость поиска в худшем случае (другими словами, это уменьшает дисперсию стоимости поиска в обмен на увеличение ожидаемого значения этих затрат поиска). Хеширование в Hopscotch работает, ограничивая максимальное расстояние, на которое элементы могут быть смещены, и поддерживая битовую маску, указывающую, какие элементы рядом могут быть совпадающими, сокращая объем работы, которую вам нужно сделать, чтобы найти вещи. И новый Google flat_map начинается с линейного зондирования и использует действительно умные хеширование и параллельные операции с памятью, чтобы сделать поиск чрезвычайно быстрым.