• 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
И хеш-функция очень простая: элемент массива просто назначается по алфавитному признаку.
Может быть, вы уже поняли суть проблемы. Вы хотите поместить цену апельсинов в хеш. Для этого выделяется первая ячейка.
После апельсинов в хеш заносится цена бананов. Для бананов выделяется вторая ячейка.
Пока все прекрасно! Но теперь в хеш нужно включить цену авокадо. И для авокадо снова выделяется первая ячейка.
О нет! Элемент уже занят апельсинами! Что же делать? Такая ситуация называется коллизией: двум ключам назначается один элемент массива. Возникает проблема: если сохранить в этом элементе цену авокадо, то она запишется на место цены апельсинов. И когда кто-нибудь спросит, сколько стоят апельсины, вы вместо этого сообщите цену авокадо! Коллизии — неприятная штука, и вам придется как-то разбираться с ними. Существует много разных стратегий обработки коллизий. Простейшая из них выглядит так: если несколько ключей отображаются на один элемент, в этом элементе создается связанный список.
В этом примере и «апельсины», и «авокадо» отображаются на один элемент массива, поэтому в элементе создается связанный список. Если вам потребуется узнать цену бананов, эта операция по-прежнему выполнится быстро. Если потребуется узнать цену апельсинов, работа пойдет чуть медленнее. Вам придется провести поиск по связанному списку, чтобы найти в нем «апельсины». Если связанный список мал, это не так страшно — поиск будет ограничен тремя или четырьмя элементами. Но предположим, что вы работаете в специализированной лавке, в которой продаются только продукты на букву «а».
Одну минуту! Вся хеш-таблица полностью пуста, кроме одной ячейки. И эта ячейка содержит огромный связанный список! Каждый элемент этой хеш-таблицы хранится в связанном списке. Ситуация ничуть не лучше той, когда все данные сразу хранятся в связанном списке. Работа с данными замедляется.
Из этого примера следуют два важных урока:
• выбор хеш-функции действительно важен. Хеш-функция, отображающая все ключи на один элемент массива, никуда не годится. В идеале хеш-функция должна распределять ключи равномерно по всему хешу;