Page 124 - Bkhargava_-_Grokaem_algoritmy

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

Коэффициент заполнения этой хеш-таблицы равен 1. А если хеш-таблица
состоит всего из 50 элементов? Тогда ее коэффициент заполнения будет
равен 2. Выделить под каждый товар отдельный элемент ни при каких
условиях не удастся, потому что элементов попросту не хватит! Коэффи­
циент заполнения больше 1 означает, что количество товаров превышает
количество элементов в массиве.

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

[41Зf1f

~
КО'Эфq)МЦМЕ.НТ
3
JАПОЛНЕ.НМА • 1•

Хеш-таблицу необходимо расширить. Расширение начинается с создания
нового массива большего размера. Обычно в таком случае создается массив
вдвое большего размера.

I 1 1 1 1 1

Теперь все эти элементы необходимо заново вставить в новую хеш-таблицу
функцией hash:

[ 14-/ (1/зl

3
КО'Эфq)ИЦИЕ.НТ .3АПОЛНЕ.НИЯ • 1~

Новая таблица имеет коэффициент за~олнения / . Гораздо лучше! С мень­
3
8
шим коэффициентом загрузки число коллизий уменьшается, и ваша табли­
ца начинает работать более эффективно. Хорошее приближенное правило:

www.trk.kg