Как бы вы это сделали? Хеш-таблицы упрощают моделирование отношений между объектами.
Хеш-таблицы используются для поиска соответствий в гораздо большем масштабе. Например, представьте, что вы хотите перейти на веб-сайт — допустим, http://adit.io. Ваш компьютер должен преобразовать символическое имя adit.io в IP-адрес.
Для любого посещаемого веб-сайта его имя преобразуется в IP-адрес:
Связать символическое имя с IP-адресом? Идеальная задача для хеш-таблиц! Этот процесс называется преобразованием DNS. Хеш-таблицы — всего лишь один из способов реализации этой функциональности.
Исключение дубликатов
Предположим, вы руководите избирательным участком. Естественно, каждый избиратель может проголосовать всего один раз. Как проверить, что он не голосовал ранее? Когда человек приходит голосовать, вы узнаете его полное имя, а затем проверяете по списку уже проголосовавших избирателей.
Если имя входит в список, значит, этот человек уже проголосовал — гоните наглеца! В противном случае вы добавляете имя в список и разрешаете ему проголосовать. Теперь предположим, что желающих проголосовать много и список уже проголосовавших достаточно велик.
Каждый раз, когда кто-то приходит голосовать, вы вынуждены просматривать этот гигантский список и проверять, голосовал он или нет. Однако существует более эффективное решение: воспользоваться хешем!
Сначала создадим хеш для хранения информации об уже проголосовавших людях:
>>> voted = {}
Когда кто-то приходит голосовать, проверьте, присутствует ли его имя в хеше:
>>> value = voted.get("tom")
Функция get возвращает значение, если ключ "tom" присутствует в хеш-таблице. В противном случае возвращается None. С помощью этой функции можно проверить, голосовал избиратель ранее или нет!
Код выглядит так:
voted = {}
def check_voter(name):
if voted.get(name):
print "kick them out!"
else:
voted[name] = True
print "let them vote!"
Давайте протестируем его на нескольких примерах:
>>> check_voter("tom")
let them vote!
>>> check_voter("mike")
let them vote!
>>> check_voter("mike")
kick them out!
Когда Том приходит на участок в первый раз, программа разрешает ему проголосовать. Потом приходит Майк, который тоже допускается к голосованию. Но потом Майк делает вторую попытку, и на этот раз у него ничего не получается.
Если бы имена проголосовавших хранились в списке, то выполнение функции со временем замедлилось бы, потому что функции пришлось бы проводить простой поиск по всему списку. Но имена хранятся в хеш-таблице, а хеш-таблица мгновенно сообщает, присутствует имя избирателя в списке или нет. Проверка дубликатов в хеш-таблице выполняется очень быстро.
Использование хеш-таблицы как кэша
Последний пример: кэширование. Если вы работаете над созданием веб-сайтов, вероятно, вы уже слышали о пользе кэширования. Общая идея кэширования такова: допустим, вы заходите на сайт facebook.com:
1. Вы обращаетесь с запросом к серверу Facebook.
2. Сервер ненадолго задумывается, генерирует веб-страницу и отправляет ее вам.
3. Вы получаете веб-страницу.
Например, на Facebook сервер может собирать информацию о действиях всех ваших друзей, чтобы представить ее вам. На то, чтобы собрать всю информацию и передать ее вам, требуется пара секунд. С точки зрения пользователя, пара секунд — это очень долго. Он начинает думать: «Почему Facebook работает так медленно?» С другой стороны, серверам Facebook приходится обслуживать миллионы людей, и эти пары секунд для них суммируются. Серверы Facebook трудятся в полную силу, чтобы сгенерировать все эти страницы. Нельзя ли как-то ускорить работу Facebook при том, чтобы серверы выполняли меньше работы?
Представьте, что у вас есть племянница, которая пристает к вам с вопросами о планетах: «Сколько километров от Земли до Марса?», «А сколько километров до Луны?», «А до Юпитера?» Каждый раз вы вводите запрос в Google и сообщаете ей ответ. На это уходит пара минут. А теперь представьте, что она всегда спрашивает: «Сколько километров от Земли до Луны?» Довольно быстро вы запоминаете, что Луна находится на расстоянии 384 400 километров от Земли. Искать информацию в Google не нужно… вы просто запоминаете и выдаете ответ. Вот так работает механизм кэширования: сайт просто запоминает данные, вместо того чтобы пересчитывать их заново.
Если вы вошли на Facebook, то весь контент, который вы видите, адаптирован специально для вас. Каждый раз, когда вы заходите на facebook.com, серверам приходится думать, какой контент вас интересует. Если же вы не ввели учетные данные на Facebook, то вы видите страницу входа. Все пользователи видят одну и ту же страницу входа. Facebook постоянно получает одинаковые запросы: «Я еще не вошел на сайт, выдайте мне домашнюю страницу». Сервер перестает выполнять лишнюю работу и генерировать домашнюю страницу снова и снова. Вместо этого он запоминает, как выглядит домашняя страница, и отправляет ее вам.
Такой механизм хранения называется кэшированием. Он обладает двумя преимуществами:
• вы получаете веб-страницу намного быстрее, как и в том случае, когда вы запомнили расстояние от Земли до Луны. Когда племянница в следующий раз задаст вопрос, вам не придется гуглить. Вы можете выдать ответ мгновенно;
• Facebook приходится выполнять меньше работы.
Кэширование — стандартный способ ускорения работы. Все крупные веб-сайты применяют кэширование. А кэшируемые данные хранятся в хеше!
Facebook не просто кэширует домашнюю страницу. Также кэшируются страницы «О нас», «Условия использования» и многие другие. Следовательно, необходимо создать связь URL-адреса страницы и данных страницы.
Когда вы посещаете страницу на сайте Facebook, сайт сначала проверяет, хранится ли страница в хеше.
Вот как это выглядит в коде:
cache = {}
def get_page(url):
if cache.get(url):
return cache[url] Возвращаются кэшированныеданные
else:
data = get_data_from_server(url)
cache[url] = data Данные сначала сохраняются в кэше
return data
Здесь сервер выполняет работу только в том случае, если URL не хранится в кэше. Однако перед тем, как возвращать данные, вы сохраняете их в кэше. Когда пользователь в следующий раз запросит тот же URL-адрес, данные можно отправить из кэша (вместо того чтобы заставлять сервер выполнять работу).
Шпаргалка
Хеши хорошо подходят для решения следующих задач:
• моделирование отношений между объектами;
• устранение дубликатов;
• кэширование/запоминание данных вместо выполнения работы на сервере.
Коллизии
Как я уже сказал, в большинстве языков существуют свои хеш-таблицы. Вам не нужно знать, как написать собственную реализацию, поэтому я не буду надолго останавливаться на внутреннем строении хеш-таблиц. Но быстродействие-то важно всегда! Чтобы понять быстродействие хеш-таблиц, необходимо сначала понять, что такое коллизии. В следующих двух разделах рассматриваются коллизии и быстродействие хеш-таблиц.
Прежде всего, я немножко приукрасил действительность. Я сказал, что хеш-функция всегда отображает разные ключи на разные позиции в массиве.
На самом деле написать такую хеш-функцию почти невозможно. Рассмотрим простой пример: допустим, массив состоит всего из 33 ячеек.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
И хеш-функция очень простая: элемент массива просто назначается по алфавитному признаку.
Может быть, вы уже поняли суть проблемы. Вы хотите поместить цену апельсинов в хеш. Для этого выделяется первая ячейка.
После апельсинов в хеш заносится цена бананов. Для бананов выделяется вторая ячейка.
Пока все прекрасно! Но теперь в хеш нужно включить цену авокадо. И для авокадо снова выделяется первая ячейка.
О нет! Элемент уже занят апельсинами! Что же делать? Такая ситуация называется коллизией: двум ключам назначается один элемент массива. Возникает проблема: если сохранить в этом элементе цену авокадо, то она запишется на место цены апельсинов. И когда кто-нибудь спросит, сколько стоят апельсины, вы вместо этого сообщите цену авокадо! Коллизии — неприятная штука, и вам придется как-то разбираться с ними. Существует много разных стратегий обработки коллизий. Простейшая из них выглядит так: если несколько ключей отображаются на один элемент, в этом элементе создается связанный список.
В этом примере и «апельсины», и «авокадо» отображаются на один элемент массива, поэтому в элементе создается связанный список. Если вам потребуется узнать цену бананов, эта операция по-прежнему выполнится быстро. Если потребуется узнать цену апельсинов, работа пойдет чуть медленнее. Вам придется провести поиск по связанному списку, чтобы найти в нем «апельсины». Если связанный список мал, это не так страшно — поиск будет ограничен тремя или четырьмя элементами. Но предположим, что вы работаете в специализированной лавке, в которой продаются только продукты на букву «а».
Одну минуту! Вся хеш-таблица полностью пуста, кроме одной ячейки. И эта ячейка содержит огромный связанный список! Каждый элемент этой хеш-таблицы хранится в связанном списке. Ситуация ничуть не лучше той, когда все данные сразу хранятся в связанном списке. Работа с данными замедляется.
Из этого примера следуют два важных урока:
• выбор хеш-функции действительно важен. Хеш-функция, отображающая все ключи на один элемент массива, никуда не годится. В идеале хеш-функция должна распределять ключи равномерно по всему хешу;