Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава

Начнем с пустого массива:

Все цены будут храниться в этом массиве; передадим хеш-функции строку «апельсины».

Хеш-функция выдает значение «3». Сохраним цену апельсинов в элементе массива с индексом 3.

Добавим молоко. Передадим хеш-функции строку «молоко».

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

А теперь вы спрашиваете: сколько стоит авокадо? Искать в массиве ничего не нужно, просто передайте строку «авокадо» хеш-функции.

Результат показывает, что значение хранится в элементе с индексом 4. И оно, конечно, там и находится!

Хеш-функция сообщает, где хранится цена, и вам вообще не нужно ничего искать! Такое решение работает, потому что:

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

• Хеш-функция связывает разные строки с разными индексами. «Авокадо» связывается с индексом 4, а «молоко» — с индексом 0. Для каждой строки находится отдельная позиция массива, в которой сохраняется цена этого товара.

• Хеш-функция знает размер массива и возвращает только действительные индексы. Таким образом, если длина массива равна 5 элементам, хеш-функция не вернет 100, потому что это значение не является действительным индексом в массиве.

Поздравляю: вы создали «Мэгги»! Свяжите воедино хеш-функцию и массив, и вы получите структуру данных, которая называется хеш-таблицей. Хеш-таблица станет первой изученной вами структурой данных, с которой связана дополнительная логика. Массивы и списки напрямую отображаются на адреса памяти, но хеш-таблицы устроены более умно. Они определяют место хранения элементов при помощи хеш-функций.

Вероятно, хеш-таблицы станут самой полезной из сложных структур данных, с которыми вы познакомитесь. Они также известны под другими названиями: «ассоциативные массивы», «словари», «отображения», «хеш-карты» или просто «хеши». Хеш-таблицы исключительно быстро работают! Помните описание массивов и связанных списков из главы 2? Обращение к элементу массива происходит мгновенно. А хеш-таблицы используют массивы для хранения данных, поэтому при обращении к элементам они не уступают массивам.

Скорее всего, вам никогда не придется заниматься реализацией хеш-таблиц самостоятельно. В любом приличном языке существует реализация хеш-таблиц. В Python тоже есть хеш-таблицы; они называются словарями. Новая хеш-таблица создается функцией dict:

>>> book = dict()

book — новая хеш-таблица. Добавим в book несколько цен:

>>> book["apple"] = 0.67      Апельсины стоят 67 центов

>>> book["milk"] = 1.49       Молоко стоит 1 доллар 49 центов

>>> book["avocado"] = 1.49

>>> print book

{'avocado': 1.49, 'apple': 0.67, 'milk': 1.49}

Пока все просто! А теперь запросим цену авокадо:

>>> print book["avocado"]

1.49       Цена авокадо

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

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

Упражнения

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

Какие из следующих функций являются последовательными?

5.1  f(x) = 1 Возвращает "1" для любых входных значений

5.2  f(x) = rand() Возвращает случайное число

5.3  f(x) = next_empty_slot()       Возвращает индекс следующего пустого элемента в хеш-таблице

5.4  f(x) = len(x)      Возвращает длину полученной строки

Примеры использования

Хеш-таблицы повсеместно применяются на практике. В этом разделе представлены некоторые примеры.

Использование хеш-таблиц для поиска

В вашем телефоне есть удобная встроенная телефонная книга.

С каждым именем связывается номер телефона.

Предположим, вы хотите построить такую телефонную книгу. Имена людей в этой книге связываются с номерами. Телефонная книга должна поддерживать следующие функции:

• добавление имени человека и номера телефона, связанного с этим именем;

• получение номера телефона, связанного с введенным именем.

Такая задача идеально подходит для хеш-таблиц! Хеш-таблицы отлично работают, когда вы хотите:

• создать связь, отображающую один объект на другой;

• найти значение в списке.

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

>>> phone_book = dict()

Кстати, в Python предусмотрена сокращенная запись для создания хеш-таблиц: она состоит из двух фигурных скобок:

>>> phone_book = {}   То же,что phone_book = dict()

Добавим в телефонную книгу несколько номеров:

>>> phone_book["jenny"] = 8675309

>>> phone_book["emergency"] = 911

Вот и все! Теперь предположим, что вы хотите найти номер телефона Дженни (Jenny). Просто передайте ключ хешу:

>>> print phone_book["jenny"]

8675309   Номер Дженни

А теперь представьте, что то же самое вам пришлось бы делать с массивом.

Как бы вы это сделали? Хеш-таблицы упрощают моделирование отношений между объектами.

Хеш-таблицы используются