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

Плюсы и минусы хэш-таблицы

Плюсы

  • Быстрый поиск
  • Быстрая вставка
  • Быстрое удаление

Минусы

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

Выполнение

Начните с массива

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

Хеширование

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

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

Столкновения

Поскольку столкновения практически неизбежны, нам нужен способ с ними справляться. Как правило, есть два способа обработки коллизий.

Отдельная цепочка

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

Открытая адресация

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

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

Код

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

«Ковши» — это термин, который используется для серии пар ключей и значений, хранящихся в индексе. В отдельной цепочке в корзине может храниться более одной пары ключ-значение, при открытой адресации в корзине хранится только 1 пара ключ-значение.

Теперь нам нужна наша хэш-функция.

Я получил эту хеш-функцию по ссылке выше, кредит принадлежит Марку Уилбуру. Я не совсем понимаю, почему это дает нам такое хорошее распределение. Я попытался объяснить как можно больше в комментариях к коду. Самая важная часть, которую вы увидите в большинстве (если не во всех) функциях хеширования, — это использование модуля (оператор %). Это гарантирует, что число находится в пределах индексов нашего массива.

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

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

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

Здесь наш код становится немного сложнее. Сначала нам нужно определить индекс ведра. Затем мы смотрим, существует ли еще ведро (если в нем ничего нет, при доступе к этому индексу будет возвращено undefined). Если он не существует, создайте пустой массив для хранения наших пар ключа и значения.

Оттуда мы можем получить сам bucket (даже если это просто пустой массив). Если мы уже вставили пару ключ-значение с этим ключом, нам нужно перезаписать связанное с ним значение. Если нет, нам нужно вставить его в ведро.

Мы храним наши пары ключей и значений в виде кортежа. Кортеж — это массив, содержащий 2 элемента. Из-за этого мы знаем, что наш ключ всегда имеет индекс 0, а наше значение — индекс 1. Таким образом, наши ведра представляют собой массивы, заполненные кортежами.

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

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

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

Давайте посмотрим на метод resize.

Эта функция берет текущие сегменты и сохраняет их во временной переменной (tempBuckets). Оттуда мы сбрасываем размер до 0 и очищаем текущие сегменты. Мы повторяем наш tempBuckets и добавляем каждую пару ключ-значение обратно в хеш-таблицу измененного размера. Мы запускаем его через наш метод set, потому что он использует getIndex, который запускает нашу функцию хеширования. Нам нужно сделать это снова, потому что результаты нашей хеш-функции зависят от максимального размера хеш-таблицы. Таким образом, наши старые индексы не будут соответствовать новым.

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

Получив ключ, мы получаем ведро. Мы перебираем пары ключей и значений в этом сегменте и возвращаем значение, связанное с данным ключом. Если сегмента нет, значит, мы никогда не вставляли этот ключ в нашу хеш-таблицу, поэтому возвращаем undefined.

Мы можем get и set элементов. Давайте создадим метод remove!

Для remove это та же концепция, что и для get. Мы находим правильное ведро и перебираем ведро, пока не найдем правильный ключ. Вместо того, чтобы просто вернуть его, мы будем splice ведро, чтобы удалить из него эту пару ключ-значение. Если коэффициент загрузки низкий, мы изменим размер нашей хеш-таблицы. Затем мы возвращаем значение узла, который мы удалили.

Вот и все! Мы можем вставлять, извлекать и удалять элементы из хеш-таблицы.

Сложность времени и пространства

Сложность времени

Вы можете задаться вопросом, со всей дополнительной сложностью, как это быстрее, чем массив? Мы перебираем список, содержащий списки (сегменты), чтобы найти правильную пару ключ-значение!

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

Давайте посмотрим на временные сложности описанных выше методов:

  • HashFunction, getIndex и getBucket все равны O(1). Время выполнения HashFunction определяется длиной ключа, поэтому оно не зависит от размера самой хеш-таблицы.
  • Худший случай для get заключается в том, что каждая пара ключ-значение хранится в одном и том же сегменте, а тот, который мы ищем, находится в конце. Это приведет к временной сложности O (n). Однако, как уже говорилось, это очень редко. Обычно get занимает O(1) времени.
  • set, при условии, что нам не нужно изменять размер нашей хэш-таблицы, аналогичен get. В худшем случае все пары находятся в одном ведре, и нам нужно добавить его в конец. Однако в большинстве случаев это займет время O (1).
  • remove, в худшем случае O(n). Это потому, что если нам нужно удалить последнюю пару в ведре, содержащем все пары. Сначала мы пройдемся по всем из них, чтобы получить правильную пару, а затем воспользуемся splice, что равно O(n). Итак, это O(n + n), упрощенное до O(n). Однако в большинстве случаев в ведре будет только одна пара, поэтому потребуется O (1).
  • resize всегда будет принимать O(n). Потому что нам нужно скопировать каждую пару в хеш-таблицу с измененным размером.

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

Космическая сложность

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

В заключении

Хеш-таблицы — это полезные структуры данных, которые используются для решения многих реальных проблем. Вот некоторые из вариантов их использования: компиляторы используют их для определения ключевых слов, кэширования и индексации базы данных. Хеш-таблицы отлично подходят, когда у вас есть большой набор связанных данных, где порядок не имеет значения. Я думаю, что буду придерживаться встроенных структур данных JavaScript, но всегда интересно посмотреть, как все работает внутри. Вы можете найти код из этого блога в этом репозитории GitHub.