На этом шаге рассмотрим хеш-функции.
Хеш-функция представляет собой функцию, которая получает строку (любая последовательность байтов) и возвращает число. В научной терминологии говорят, что хеш-функция "отображает строки на числа". Можно подумать, что найти закономерности получения чисел для подаваемых на вход строк невозможно. Однако хеш-функция должна соответствовать некоторым требованиям:
- Она должна быть последовательной. Допустим, вы передали ей строку "апельсины" и получили 4. Это значит, что каждый раз в будущем, передавая ей строку "апельсины", вы будете получать 4. Без этого хеш-таблица бесполезна.
- Разным словам должны соответствовать разные числа. Например, хеш-функция, которая возвращает 1 для каждого полученного слова, никуда не годится. В идеале каждое входное слово должно отображаться на свое число.
Итак, хеш-функция связывает строки с числами.
Начнем с пустого массива:
Все цены будут храниться в этом массиве; передадим хеш-функции строку "апельсины".
Хеш-функция выдает значение "3". Сохраним цену апельсинов в элементе массива с индексом 3.
Добавим молоко. Передадим хеш-функции строку "молоко".
Продолжайте действовать так, и со временем весь массив будет заполнен ценами на товары.
А теперь вы спрашиваете: сколько стоит авокадо? Искать в массиве ничего не нужно, просто передайте строку "авокадо" хеш-функции.
Результат показывает, что значение хранится в элементе с индексом 4.
Хеш-функция сообщает, где хранится цена, и вам вообще не нужно ничего искать! Такое решение работает, потому что:
- Хеш-функция неизменно связывает название с одним индексом. Каждый раз, когда она вызывается для строки "авокадо", вы получаете обратно одно и то же число. При первом вызове этой функции вы узнаете, где следует сохранить цену авокадо, а при последующих вызовах она сообщает, где взять эту цену.
- Хеш-функция связывает разные строки с разными индексами. "Авокадо" связывается с индексом 4, а "молоко" - с индексом О. Для каждой строки находится отдельная позиция массива, в которой сохраняется цена этого товара.
- Хеш-функция знает размер массива и возвращает только действительные индексы. Таким образом, если длина массива равна 5 элементам, хеш-функция не вернет 100, потому что это значение не является действительным индексом в массиве.
Свяжите воедино хеш-функцию и массив, и вы получите структуру данных, которая называется хеш-таблицей. Хеш-таблица станет первой изученной вами структурой данных, с которой связана дополнительная логика. Массивы и списки напрямую отображаются на адреса памяти, но хеш-таблицы устроены более умно. Они определяют место хранения элементов при помощи хеш-функций.
На следующем шаге рассмотрим реализацию хеш-таблицы в языке Python.
