КЛЮЧИ на БУШ «А*
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. яя
АБРИКОСЫ
ЬСЕ ЭТИ ЭЛЕААЕНТЫ НЕ ИСПОЛЬЗУЮТСЯ
этом примере и «апельсины», и «авокадо» отображаются на один элемент массива, поэтому в элементе создается связанный список. Если вам потребуется узнать цену бананов, эта операция по-прежнему выполнится быстро. Если потребуется узнать цену апельсинов, работа пойдет чуть медленнее. Вам придется провести поиск по связанному списку, чтобы найти в нем «апельсины». Если связанный список мал, это не так страшно — поиск будет ограничен тремя или четырьмя элементами. Но предположим, что вы работаете в специализированной лавке, в которой продаются только продукты на букву «а».
Одну минуту! Вся хеш-таблица полностью пуста, кроме одной ячейки. И эта ячейка содержит огромный связанный список! Каждый элемент этой хеш-таблицы хранится в связанном списке. Ситуация ничуть не лучше той, когда все данные сразу хранятся в связанном списке. Работа с данными замедляется.
Из этого примера следуют два важных урока:
выбор хеш-функции действительно важен. Хеш-функция, отображающая все ключи на один элемент массива, никуда не годится. В идеале хеш-функция должна распределять ключи равномерно по всему хешу;
если связанные списки становятся слишком длинными, работа с хеш- таблицей сильно замедляется. Но они не станут слишком длинными при использовании хорошей хеш-функции\
Хеш-функции играют важную роль. Хорошая хеш-функция создает минимальное число коллизий. Как же выбрать хорошую хеш-функцию? Об этом в следующем разделе!
Быстродействие
Глава началась с примера магазинчика. Вы хотели построить механизм, который мгновенно выдает цены на продукты. Что ж, хеш-таблицы работают очень быстро.
Do'stlaringiz bilan baham: |