Грокаем а Иллюстрированное пособие для программистов и любопытствующих

КЛЮ­ЧИ на БУШ «А*


I /


клю­чи ни БУКВУ «Б»
КЛЮЧИ НА


у


БУКВУ *в*


КЛЮ- КЛЮ­ЧИ НА ^чи НА БУКВУ

хеш-функция очень простая: элемент массива просто назначается по алфавитному признаку.
0 1 2 3 4 5 6 ? 6 3 10 11 U 13 И 15 16 1? 16 13 20 21 22 23 24 25 26 2? 26 23 30 31 32
М
0,6?
АПЕЛЬСИНЫ ^
ожет быть, вы уже поняли суть проблемы. Вы хотите поместить цену апельсинов в хеш. Для этого выделяется первая ячейка.
После апельсинов в хеш заносится цена бананов. Для бананов выделяется вторая ячейка.
0
АПЕЛЬСИНЫ


БАНАНЫ

.3 я
П
0.6?


03°[

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

ПЕЛЬСИНЫ? ЛвОКАЛО?
О

	С?
/*	LA/ __о
ЦЕНА
БАНАНОВ

апель­
сины


си?


АВОКАДО


14Я

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


АПЕЛЬ­
СИНЫ


о.&т


* АВОКАДО 1.43


АНАНАСЫ


3. яя


АБРИКОСЫ


ЬСЕ ЭТИ ЭЛЕААЕНТЫ НЕ ИСПОЛЬЗУЮТСЯ

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

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

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