Хеш‑таблица (hash table) — это структура данных для хранения пар «ключ — значение», которая обеспечивает быстрый доступ к элементам за счёт использования хеш‑функции.
Похоже на словарь (структура данных, которая хранит информацию в виде пар «ключ — значение») или даже массив (структура данных, представляющая собой упорядоченный набор элементов одного типа, доступ к которым осуществляется по индексу), если оставить только одну из строк. Все взаимосвязано :)
Но хеш-таблица – это программируемый нами словарь, в который добавляем хеш-функцию. Она служит для преобразования ключа в число, которое и определяет место нашего элемента в массиве.
Кто знаком с Python, наверняка пользовался хеш-таблицей – обычным словарем. Хеш-функция скрыта от нас, но именно она вычисляет расположение элемента в таблице. (Однако не все словари работают на основе работы хеш-функции, например, ее не использует std::map в С++).
Происходит магия! Ключ (в нашем случае строка, например, одна из них «Рис») превращается в число, а это число становится индексом элемента в обычном массиве со значением (здесь это полка).
Появляется логичный вопрос: «для чего такие сложности, если есть массив?». Все дело в скорости поиска информации: массив — это структура данных, в которой есть только индексы и значения в этих индексах. В нашем примере это крупы, пронумерованные индексами от 0 до 4. Чтобы найти булгур, нам придется пройти весь массив целиком, потому что мы не знаем его полку. Дойдя до булгура, мы уже не так рады, так как поиск отнял у нас достаточно времени. В словаре для каждой крупы своя полка и мы не пойдем смотреть другие, поскольку точно знаем ее местоположение, ведь у нас записано: «Булгур»: «Полка 5».
Иногда может потребоваться создать хеш-таблицу вручную, если нам нужно проконтролировать логику распределения данных по массиву для конкретной задачи.
При использовании своей хеш-таблицы можно столкнуться с неприятным моментом — коллизиями. Коллизия – это ситуация, когда разные ключи дают одинаковый хеш‑код при вычислении через функцию hash(). Например, «Макароны» и «Рис» в результате применения хеш-функции дают индекс 5, а в нем значение полки (в то время как в одной ячейке может быть только одно значение!). В словаре Python также встречаются коллизии, но мы этого не заметим, поскольку такие моменты обрабатываются языком программирования самостоятельно. Когда мы делаем хеш-таблицу сами, выбор, каким способом обрабатывать коллизии, остается за разработчиком. С одним из них я познакомлю вас уже на практике.