Page 119 - Bkhargava_-_Grokaem_algoritmy

118 Глава 5. Хеш-таблицы

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

А ПЕ.ЛЬ- Q t "'J.. -+---7tА60КА..й.О 1.4'1
--~сины .от

/t
ЦЕ.НА
БАНАНО6

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

О.61 мок~о 1.4q

( ЬСЕ. ЭТИ ЭЛЕ.МЕНТЫ
НЕ. MCПOЛЬJYIOTCJI
D

www.trk.kg