Грокаем алгоритмы

Вероятно, хеш-таблицы станут самой полезной из сложных структур данных, с которыми вы познакомитесь. Они также известны под другими названиями: «ассоциативные массивы», «словари», «отображения», «хеш-карты» или просто «хеши». Хеш-таблицы исключительно быстро работают! Помните описание массивов и связанных списков из главы 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   Номер Дженни

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

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

Хеш-таблицы используются для поиска соответствий в гораздо большем масштабе. Например, представьте, что вы хотите перейти на веб-сайт — допустим, http://adit.io. Ваш компьютер должен преобразовать символическое имя adit.io в IP-адрес.

Для любого посещаемого веб-сайта его имя преобразуется в IP-адрес:

Связать символическое имя с IP-адресом? Идеальная задача для хеш-таблиц! Этот процесс называется преобразованием DNS. Хеш-таблицы — всего лишь один из способов реализации этой функциональности.

Исключение дубликатов

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

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

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