double arrow

Расстановка записей по числовому значению ключей

Функция преобразования h(Клj) выбирается на основе двух требований:

1) ее результат для возможного диапазона значений ключевого поля должен находиться в пределах диапазона адресов (номеров) области памяти, выделяемой под данные;

2) значение функции в пределах выделенного диапазона адресов должны быть равномерными.

На практике наиболее широкое распространение нашли хеш-функции, основанные на операциях деления по модулю:

h (Кл j) = (Кл j mod M)+1,

где (Кл j mod M) означает операцию деления по модулю М, а число М выбирается исходя из необходимости попадания значений хеш-функции в требуемый диапазон.

Рис. 2.20. Принцип расстановки записей по значению ключей.

Значением операции деления по модулю М является остаток от обычного деления числа на М, например результат деления 213 по модулю 20 равен 13.

Если в качестве М выбрать число, являющееся степенью двух, то подобная хеш-функция эффективно вычисляется процедурами выделения нескольких двоичных цифр.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: