Методы рендомезации или хэширования

Они основаны на вероятностных алгоритмах. Адресная фун-я которая строится на вероят-ых алгоритмах наз-ся хэш-функция.

Методы построения хэш-фун-ий:

- метод квадратов;

- деления;

- умножения;

- сдвига разрядов;

- преобр-я основания счисления;

- деления номиналов;

Метод постр-я хэш-фун-ий выбирают по 2 критериям:

1) плотность заполнения адресного простр-ва;

2) min кол-во поллизионных ситуаций

По этим признакам лучшим явл метод деления.

Метод деления

h(key)=mod(key, m)

h() – хэш-фун-я

key – значение ключа записи

m – число близкое к max размеру адресного пр-ва, отведённого для записи

mod – остаток от деления значения key на m

Метод разрешения коллизий

1. метод открытой адресации

2. метод цепочек

Метод открытой адресации

h(key)=mod(key, 1000)

key1=4957397

key2=0597397

h(key1)=397

h(key2)=397

rh(h(key2))=mod(397/1000)=mod(3970/1000)=970

Недостатки метода повторного хэширования

1) мы имеем фиксир-ый размер таблицы где размещаются значения

2) связан с удалением записи из адресного пр-ва

Если удалить r1 и попытаться найти r2, т о нам будет сказано, что в позиции P такой записи не сущ-ет.

Метод цепочек

В нём исп- ся след струк-ра: