Шрифт:
Интервал:
Закладка:
Начнем с пустого массива:
Все цены будут храниться в этом массиве; передадим хеш-функции строку «апельсины».
Хеш-функция выдает значение «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 Номер Дженни
А теперь представьте, что то же самое вам пришлось бы делать с массивом.
Как бы вы это сделали? Хеш-таблицы упрощают моделирование отношений между объектами.
Хеш-таблицы используются