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

Неизбежно, каждый будущий студент CS узнает все о структурах данных. Массивы, связанные списки, деревья и хеш-таблицы - это лишь некоторые из тех, из которых вам придется изучать на своем пути к знаниям. Я могу почти гарантировать, что вам потребуется реализовать хеш-таблицу в какой-то момент вашей карьеры программиста, и, вероятно, вам придется создать ее самостоятельно, чтобы узнать о том, как они работают. Самый простой способ создать собственную реализацию - использовать цепочку. Каждая корзина в хеш-таблице указывает на (обычно связанный) список. При поиске, добавлении или удалении определенной пары «ключ-значение» он переходит в корзину, возвращаемую хэш-функцией, а затем выполняет поиск, чтобы найти конкретный ключ. Не имеет значения, что разные ключи возвращают один и тот же сегмент, поскольку все пары независимо помещаются в список сегмента.

Цепь замедляет вас

Так насколько же быстры все эти функции? Хотя точные спецификации будут различаться в зависимости от реализации, время Big O для этих функций будет следовать определенному шаблону при использовании этого типа разрешения конфликтов. Поиск корзины с использованием хэш-функции основан на языке (существует множество различных способов хеширования объектов и данных), но можно с уверенностью предположить, что это операция с почти постоянным временем, и она не будет учитываться во всех будущих вычислениях. Это связано с тем, что при объединении со следующей стратегией разрешения конфликтов эта хеш-функция всегда выполняется один раз. Итак, у нас есть get / contains, set и delete с использованием заданного ключа. Для каждой из этих функций нам нужно просмотреть список. Как долго это займет? Чтобы выяснить это, нам нужно обсудить коэффициент нагрузки, или L. Проще говоря, этот термин представляет собой количество пар ключ-значение в хеш-таблице, деленное на количество сегментов. Обычно хэш-функция назначает сегменты довольно равномерно, поэтому для наших расчетов мы будем использовать среднее значение. Следовательно, в каждом сегменте содержится количество пар "ключ-значение", равное L. Методы get и contain ищут конкретное значение, поэтому хеш-функция может найти сегмент, в котором должен находиться ключ, а затем хеш-таблица будет проверять каждый отдельный узел списка сегментов, пока не найдет ключ или не дойдет до конца. списка. Сценарий среднего случая: требуется O (L / 2), чтобы найти ключ. Это также относится к удалению, которое требует поиска, а затем удаления узла, что опять же займет O (L / 2). А как насчет установки (добавления или обновления значения ключа)? Если ключа нет в хеш-таблице (и ведре), то он может быть добавлен в постоянное время, верно? Нет, поскольку хеш-таблица должна гарантировать отсутствие повторяющихся ключей и должна проверять, обновляет ли она текущий ключ или добавляет новый. Опять же, средний регистр - O (L / 2).

Разорви эти цепи!

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

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

Теперь вернемся к хеш-таблицам, представьте, что все ваши ключи продолжают давать хэш-значение 0. Если объединить пары ключ-значение вместе, все ваши пары ключ-значение будут в одном месте, что замедлит время нахождения определенного ключа. пара значений. Таким образом, вместо того, чтобы постоянно добавлять их к одному и тому же индексу, ваша хеш-таблица решит, будет ли взят этот первичный индекс ближайшего к ванной комнате, она будет перемещать его до тех пор, пока не появится свободный индекс, в котором он останется. Поэтому вместо того, чтобы помещать это 2-я пара "ключ-значение" с индексом 0, ваша хеш-таблица сдвинет ее вниз до индекса 1. Это называется зондированием. В частности, линейное зондирование, хотя есть другие способы зондирования открытого ковша.

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

Если хэш-таблица имеет коэффициент загрузки 0,5, то это означает, что в среднем при выполнении хеш-функции и получении начального сегмента оно будет заполнено на 50%, что означает, что необходимо выполнить зондирование. Тогда есть еще ~ 50% шанс, что следующее ведро будет заполнено, и так далее. Чтобы получить точное число, требуется некоторая математика, но когда коэффициент загрузки меньше 0,75, в среднем придется смотреть на 1 ключ-значение меньше, чем в хеш-таблице с использованием цепочки.

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

Бесконечность не предел!

Так что же происходит, когда ваша хеш-таблица заполнена? Когда в каждом сегменте есть пара "ключ-значение", как вы можете добавить больше? Хорошо…

Хотя не совсем.

Уловка состоит в том, чтобы никогда не позволять вашей хеш-таблице заполняться до отказа. В большинстве языков с коэффициентом загрузки от 0,6 до 0,8 хеш-таблица будет захватывать каждую корзину с данными, (обычно вдвое) увеличивая количество сегментов и повторно хешируя пары ключ-значение. Это невероятно важно при использовании линейного измерения по двум причинам. Во-первых, коэффициент загрузки 1 означает, что хеш-таблица заполнена и больше нельзя добавлять значения. Менее серьезная вторая причина заключается в том, что хеш-таблица с коэффициентом загрузки более ~ 0,8 становится довольно медленной для добавления новых значений.

Хватит предположений, как насчет некоторых примеров? Во-первых, вот мои реализации на Python: Chaining и Linear Probing.

Вот тест:

А результаты?

Цепочка заняла 1,54 секунды, в то время как линейное зондирование заняло всего 0,62 секунды для выполнения той же задачи. Хотя это не исчерпывающее доказательство того, что линейное зондирование выполняется быстрее, это хороший показатель того, что цепочка может быть не лучшей стратегией разрешения конфликтов для всех потребностей вашей хеш-таблицы.

Итак, напомним: цепочка занимает в среднем O (L / 2) для всех операций (хотя я был ленив с моей функцией удаления, поэтому это заняло немного больше времени). При линейном зондировании в среднем проверяется на одну пару сегмент / ключ-значение меньше, чем при сцеплении, пока коэффициент загрузки меньше 0,75, но изменение размера необходимо, когда хеш-таблица начинает заполняться.

GIF из https://imgur.com/gallery/2SPUZLR, из Смысл жизни Монти Пайтона