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

Почему я должен переживать?

Вы когда-нибудь хотели знать:

  • Как хеш-карта, ассоциативный массив или структура данных словаря работают на данном языке?
  • Когда уместно использовать хеш-таблицу для хранения предметов?
  • Как мы справляемся с «коллизиями» в хеш-таблице?

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

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

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

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

Создание нашей хеш-таблицы

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

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

Хеш-таблица работает путем хранения элементов в ведрах:

Выбор количества ведер - это отдельная тема. Для простого примера мы будем использовать 4 сегмента.

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

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

Хранение предметов в таблице

Давайте сохраним нашего первого пользователя «Аду».

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

Для этого примера мы придумаем простую хеш-функцию. Давайте возьмем каждую букву в имени пользователя и присвоим ей номер; A=0, B=1, C=2 и т. Д. В конце мы можем сложить все значения вместе. Результат - наш хеш.

Для Ada это 3, поэтому мы можем хранить Ada в сегменте 3:

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

Давайте сохраним нашего следующего пользователя, «Грейс»:

Хеш для «изящества» - 29, но у нас нет 29 корзин!

Хранение элементов с использованием только их хешированного значения означало бы, что нам потребуется очень большое количество корзин. Вместо этого нам нужен способ преобразовать хешированное значение (29) в номер сегмента (от 0 до 3).

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

Остаток после деления двух чисел называется модулем. Хэш благодати равен 29, и у нас есть 4 ведра. Остаток после деления 29 на 4 равен 1, поэтому благодать сохраняется в сегменте номер 1.

Эта операция может быть записана как 29 % 4 = 1 или 29 mod 4 = 1.

Вот как выглядит наша хеш-таблица, когда мы вычисляем сегменты таким образом:

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

Хорошая функция хеширования направлена ​​на равномерное распределение элементов по корзинам.

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

Давайте сохраним "Тим":

Теперь у нас есть два пользователя, которых нужно сохранить в корзине 3:

Есть несколько способов справиться с этим:

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

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

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

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

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

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

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

Понравилось? Получайте такую ​​статью каждые две недели, подписавшись на мой информационный бюллетень

Хотите узнать больше? Просмотрите эти ссылки:

Больше контента на plainenglish.io