Скорее всего, вам никогда не придется заниматься реализацией хеш-таблиц самостоятельно. В любом приличном языке существует реализация хеш-таблиц. В 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. Хеш-таблицы — всего лишь один из способов реализации этой функциональности.
Исключение дубликатов
Предположим, вы руководите избирательным участком. Естественно, каждый избиратель может проголосовать всего один раз. Как проверить, что он не голосовал ранее? Когда человек приходит голосовать, вы узнаете его полное имя, а затем проверяете по списку уже проголосовавших избирателей.