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

• моделирование отношений между объектами;

• устранение дубликатов;

• кэширование/запоминание данных вместо выполнения работы на сервере.

Коллизии

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

Прежде всего, я немножко приукрасил действительность. Я сказал, что хеш-функция всегда отображает разные ключи на разные позиции в массиве.

На самом деле написать такую хеш-функцию почти невозможно. Рассмотрим простой пример: допустим, массив состоит всего из 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

И хеш-функция очень простая: элемент массива просто назначается по алфавитному признаку.

Может быть, вы уже поняли суть проблемы. Вы хотите поместить цену апельсинов в хеш. Для этого выделяется первая ячейка.

После апельсинов в хеш заносится цена бананов. Для бананов выделяется вторая ячейка.

Пока все прекрасно! Но теперь в хеш нужно включить цену авокадо. И для авокадо снова выделяется первая ячейка.

О нет! Элемент уже занят апельсинами! Что же делать? Такая ситуация называется коллизией: двум ключам назначается один элемент массива. Возникает проблема: если сохранить в этом элементе цену авокадо, то она запишется на место цены апельсинов. И когда кто-нибудь спросит, сколько стоят апельсины, вы вместо этого сообщите цену авокадо! Коллизии — неприятная штука, и вам придется как-то разбираться с ними. Существует много разных стратегий обработки коллизий. Простейшая из них выглядит так: если несколько ключей отображаются на один элемент, в этом элементе создается связанный список.

В этом примере и «апельсины», и «авокадо» отображаются на один элемент массива, поэтому в элементе создается связанный список. Если вам потребуется узнать цену бананов, эта операция по-прежнему выполнится быстро. Если потребуется узнать цену апельсинов, работа пойдет чуть медленнее. Вам придется провести поиск по связанному списку, чтобы найти в нем «апельсины». Если связанный список мал, это не так страшно — поиск будет ограничен тремя или четырьмя элементами. Но предположим, что вы работаете в специализированной лавке, в которой продаются только продукты на букву «а».

Одну минуту! Вся хеш-таблица полностью пуста, кроме одной ячейки. И эта ячейка содержит огромный связанный список! Каждый элемент этой хеш-таблицы хранится в связанном списке. Ситуация ничуть не лучше той, когда все данные сразу хранятся в связанном списке. Работа с данными замедляется.

Из этого примера следуют два важных урока:

• выбор хеш-функции действительно важен. Хеш-функция, отображающая все ключи на один элемент массива, никуда не годится. В идеале хеш-функция должна распределять ключи равномерно по всему хешу;

• если связанные списки становятся слишком длинными, работа с хеш-таблицей сильно замедляется. Но они не станут слишком длинными при использовании хорошей хеш-функции!

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

Быстродействие

Глава началась с примера магазинчика. Вы хотели построить механизм, который мгновенно выдает цены на продукты. Что ж, хеш-таблицы работают очень быстро.

В среднем хеш-таблицы выполняют любые операции за время O(1). Время O(1) называется постоянным. Ранее примеры постоянного времени вам еще не встречались. Оно не означает, что операции выполняются мгновенно; просто время остается постоянным независимо от размера хеш-таблицы. Например, вы знаете, что простой поиск выполняется за линейное время.

Бинарный поиск работает быстрее — за логарифмическое время:

Поиск данных в хеш-таблице выполняется за постоянное время.

Видите горизонтальную линию? Она означает, что при любом размере хеш-таблицы — 1 элемент или 1 миллиард элементов — выборка данных займет одинаковое время. На самом деле вы уже сталкивались с постоянным временем: получение элемента из массива выполняется за постоянное время. От размера массива оно не зависит. В среднем случае хеш-таблицы работают действительно быстро.

В худшем случае все операции с хеш-таблицей выполняются за время O(n) (линейное время), а это очень медленно. Сравним хеш-таблицы с массивами и списками.