Page 123 - Bkhargava_-_Grokaem_algoritmy

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

Коэффициент заполнения k'ОЛМЧЕС.Т&О ЭЛЕМЕНТО&

& ХЕ.W-ТАБЛМЦЕ.
Коэффициент заполнения хеш-таблицы вычисляет­
ОБ\4Е.Е. КОЛМЧЕС.Т&О
ся по простой формуле.
ЭЛЕ.МЕ.НТО&
Хеш-таблицы используют массив для хранения данных, поэтому для вы­
числения коэффициента заполнения можно подсчитать количество за­
полненных элементов в массиве. Например, в следующей хеш-таблице
2
коэффициент заполнения равен / , или 0,4.
5
~AHJITЫE. ЭЛЕ.МЕНТЫ
.{, ~
[ \1\ \Ф\

КОЭФ<!>МЦМЕ.НТ
JAПOЛHEHMJI • / 1
5

Скажите, каков коэффициент заполнения этой таблицы?

[ \1Ф\

КОЭФ'11МЦМЕ.НТ
JAПOЛHE.HMJI

1
Если вы ответили " / » - все правильно. По коэффициенту заполнения
3
можно оценить количество пустых ячеек в хеш-таблице.
Предположим, в хеш-таблице нужно сохранить цены 100 товаров и хеш­
таблица состоит из 100 элементов. В лучшем случае каждому товару будет
выделен отдельный элемент.

ЦЕ.НА АПЕ.ЛЬ­
С.МНО&
~
цЕнА [1.4- f О.(),' ~ м. д . ...

МОЛОКА~

www.trk.kg