Page 118 - Bkhargava_-_Grokaem_algoritmy

Коллизии 117

На самом деле написать такую хеш-функцию почти невозможно. Рассмо­
трим простой пример: допустим, массив состоит всего из 33 ячеек.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
О 1 l .'> • 5 6 t & 8 10 11 1l 1.'> 1• 15 16 П 1& 18 lO l1 ll l.'> Н l5 l6 lt l& l8 .'>О .'>1 .'>l

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

l(ЛЮ­
l(ЛЮ- ЧМ НА
ЧУМК~Ау БУК&У l(ЛЮ- l(ЛIO-
Б
•Б•
ЧМ НА ЧМ НА
•А" u КЛЮЧИ НА БУК&У БУК&У
1 j
+ /БУК&У •8• •Ю• ,•Я• J
~ i
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
О 1 l .'> • 5 6 t & 8 10 11 1l 1.'> Н 15 16 П 111 18 lO l1 ll l.'> Н lS l6 lt l& l8 .'>О .'>1 .'>l
Может быть, вы уже поняли суть проблемы. Вы
l 0.61 / хотите поместить цену апельсинов в хеш. Для

АПЕЛЬСИНЫ ..J' этого выделяется первая ячейка.
После апельсинов в хеш заносится цена бананов. Для бананов выделяется
вторая ячейка.

( о.ь1 ( o3q ...

АПЕЛЬСИНЫ J ~БАНАНЫ

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

[ о.ь-r 1 о.зс:~ 1

АПЕЛЬСИНЫ? :/'- "-. БАНАНЫ
А 601<.All.07

www.trk.kg