Хеш-таблица - это структура данных, в которой хранится набор пар ключ / значение, позволяющий очень эффективно найти их позже.
Почему я должен переживать?
Вы когда-нибудь хотели знать:
- Как хеш-карта, ассоциативный массив или структура данных словаря работают на данном языке?
- Когда уместно использовать хеш-таблицу для хранения предметов?
- Как мы справляемся с «коллизиями» в хеш-таблице?
Представьте, что мы хотим сохранить список пользователей, чтобы впоследствии можно было найти их по именам.
Мы могли бы просто хранить наших пользователей в массиве. Когда нам понадобится найти кого-нибудь позже, мы можем перебрать всех пользователей в поисках подходящего имени.
Это нормально, когда у нас всего 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:
Есть несколько способов справиться с этим:
Мы могли бы использовать алгоритм, чтобы продолжать выбирать новые ведра, пока мы не найдем пустую, а затем сохранить там наш элемент. Подход, когда в каждой корзине всегда есть только один элемент, называется открытой адресацией.
В качестве альтернативы, вместо того, чтобы хранить только один элемент в каждой корзине, мы могли бы хранить коллекцию элементов. Когда мы обнаруживаем столкновение с помощью этого метода, мы просто помещаем оба элемента в одну корзину.
Когда нам понадобится получить элемент позже, мы все равно сможем сразу перейти к правильному ведру. Однако на этот раз корзина может содержать более одного элемента. В этом случае мы по очереди проверяем каждый элемент в корзине в поисках того, который нам нужен.
Это называется раздельной цепочкой и обычно выбирается для реализаций хеш-таблиц.
Это одна из причин, почему хорошие хеш-функции невероятно важны для производительности.
Плохая хеш-функция не распределяет элементы равномерно, поэтому в конечном итоге они концентрируются только в небольшом количестве доступных сегментов.
В худшем случае, когда все оказывается в той же корзине, мы потенциально перебираем каждый элемент, чтобы найти то, что мы ищем. Это то, чего мы пытаемся избежать, в первую очередь используя хеш-таблицу!
Понравилось? Получайте такую статью каждые две недели, подписавшись на мой информационный бюллетень
Хотите узнать больше? Просмотрите эти ссылки:
- Блестящий ответ о переполнении стека для хеш-таблиц
- Серия из трех частей по хеш-таблицам, в которой более подробно рассматривается все вышеперечисленное
- Подробнее о хэш-функциях
- Еще один ответ Stack Overflow о том, как определить количество сегментов
Больше контента на plainenglish.io