Page 79 - 4656

Алгоритми і структури даних. Лабораторний практикум.

вірогідність виконання операторів за час, більший за фіксований,
буде малим.
Ми розглянемо дві різні форми хешування. Одна з них
називається відкритим, або зовнішнім, хешуванням і дозволяє
зберігати множини в потенційно нескінченному просторі,
знімаючи тим самим обмеження на розмір множин. Інша
називається закритим, або внутрішнім, хешуванням і
використовує обмежений простір для зберігання даних,
обмежуючи таким чином розмір множин
На рис. 10.1 показана базова структура даних при
відкритому хешуванні. Основна ідея полягає в тому, що
потенційна множина (можливо, скінченна) розбивається на
кінцеве число класів. Для В класів, пронумерованих від 0 до В -
1, будується хеш-функція h, яка для будь-якого елементу х
початкової множини функція Н(х) приймає ціле значення з
інтервалу 0, В - 1, яке, природно, відповідає класу, якому
належить елемент х. Елемент х часто називають ключем, Н(х)-_
хеш-значенням х, а "класи" - сегментами.. Ми говоритимемо, що
елемент х належить сегменту Н(х).

Рисунок 10.1 - Організація даних при відкритому хешуванні

Масив, названий таблицею сегментів і проіндексований
номерами сегментів 0,1,…,B - 1, містить заголовки для В списків.
Елемент х i-го списку - це елемент початкової множини, для
якого h(х)=i.

77