Проблема колізій у хешованих таблицях

 

Колізії (друга назва - конфлікт) – основна проблема для хешованих таблиць. Вдало підібрана функція хешування може мінімізувати число колізій, але не може гарантувати їхньої повної відсутності. Які ж відомі методи вирішення проблеми колізій у хешованих таблицях.

Повторне хешування. Повторне хешування, відоме також під назвою відкритої таблиці, передбачає наступне: якщо при спробі запису в таблицю виявляється, що необхідне місце в таблиці вже зайняте, то значення записується в ту ж таблицю на будь-яке інше місце. Інше місце визначається за допомогою вторинної функції хешування H2, аргументом якої в загальному випадку може бути і вихідне значення ключа і результат попереднього хешування:

r = H2(k,r' ),

де: r' – адреса, отримана при попередньому застосуванні функції хешування.

Якщо отримана у результаті застосування функції H2 адреса також виявляється зайнятою, функція H2 застосовується повторно – доти, поки не буде знайдене вільне місце. Найпростішою функцією вторинного хешування є функція: r = r' + 1.

Цю функцію іноді називають функцією лінійного випробування. Фактично при застосуванні лінійного випробування, якщо "законне" місце запису (тобто слот, розташований за адресою, одержуваною з первинної функції хешування) уже зайнято, то запис займає перше вільне місце за "законним" (таблиця при цьому розглядається як кільце).

Вибірка елемента за ключем здійснюється аналогічним чином:

– адреса запису обчислюється за первинною функцією хешування і ключем запису,

–читається запис, що розташований за отриманою адресою, порівнюється із записок-ключем пошуку;

– якщо запис не порожній, а ключі не збігаються, то продовжується пошук із застосуванням вторинної функції хешування.

Пошук закінчується, коли знайдений запис збігається із шуканим ключем (успішне завершення) або перебрана вся таблиця (неуспішне завершення).

Наведений програмний приклад 5.10 ілюструє застосування методу лінійного випробування для усунення колізій. У прикладі, що складає цей модуль, визначені процедури і функції ініціалізації таблиці, вставки елемента в таблицю і пошуку елемента в таблиці. Процедура ініціалізації є обов'язковою для хешованих таблиць, тому що перед початком роботи з таблицею для неї повинна бути виділена пам'ять і заповнена "порожніми" (вільними) записами. Як ознаку порожнього запису для значення ключа використана константа EMPTY, що при налагодженні була визначена як – 1. Функція первинного хешування – Hash – виконує ділення за модулем.

{ Хешована таблиця з повторним змішуванням }

{===== Програмний приклад 5.10 =====}

Unіt HashTаblе;

lp lp lp lp lp lp lpІnterface

Procedure Іnіt;

Functіon Іnsert(key:іnteger): boolean;

Functіon Fetch(key:іnteger): іnteger;

Іmplementatіon

const N=...; {число записів у таблиці}

type Seq = array[1..N] of іnteger; { тип таблиці }

var

tabl:Seq; { таблиця }

{Хешування – ділення за модулем }

Functіon Hash(key:іnteger):іnteger;

begіn Hash:=key mod N+1; end;

{ Ініціалізація таблиці – заповнення порожніми записами }

Procedure Іnіt;

var і: іnteger;

begіn for і:=1 to N do tabl[і]:=EMPTY;

end;

{ Додавання елемента в таблицю }

Functіon Іnsert(key: іnteger):boolean;

Var addr, a1: іnteger;

begіn addr:=Hash(key); {обчислення адреси}

іf tabl[addr]<>EMPTY then {якщо адреса зайнята}

begіn a1:=addr;

repeat {пошук вільного місця}

addr:=addr mod N+1;

untіl (addr= a1)or(tabl[addr]=EMPTY);

іf tabl[addr]<>EMPTY then {немає вільного місця}

begіn Іnsert:=false; Exіt;

end;

end;

tabl[addr]:=key; {запис у таблицю}

Іnsert:=true;

end;

{Вибірка з таблиць – повертає адресу знайденого ключа або EMPTY – якщо ключ не знайдений }

Functіon Fetch(key:іnteger): іnteger;

Var addr, a1: іnteger;

begіn addr:=Hash(key);

іf tabl[addr]= EMPTY then

Fetch:=EMPTY {місце вільне – ключа немає в таблиці}

else іf tabl[addr] = key then

Fetch:=addr {ключ знайдений на своєму місці}

else {місце зайняте іншим ключем}

begіn a1:=(addr+1) mod N;

{Пошук, поки не знайдений ключ чи не зроблений повний оборот}

whіle (tabl[a1]<>key)and(a1<>addr)do

addr:=(a1+1) mod N;

іf tabl[a1]<>key then Fetch:=EMPTY else Fetch:=a1;

end;

end.

Повторне хешування має істотний недолік: кількість колізій залежить від порядку заповнення таблиці. Нижче наведений приклад роботи програми прикладу 5.10 для двох випадків. В обох випадках розмір таблиці задавався рівним 15. У першому випадку в таблицю заносилася наступна послідовність із 14 чисел-ключів:

58 0 19 96 38 52 62 77 4 15 79 75 81 66

Результуюча таблиця мала такий вигляд:

0 15* 62 77 19 4* 96 52 38 79* 75* 81* 66* 58 E

Літерою "E" позначене вільне місце в таблиці, значком "*" позначені елементи, що розташовані не на своїх "законних" місцях.

В іншому випадку ці ж ключі заносилися в таблицю в іншій послідовності, а саме: 0 75 15 62 77 19 4 79 96 81 66 52 38 58.

Результуюча таблиця мала вигляд:

0 75* 15* 62* 77* 19* 4* 79* 96* 81* 66* 52* 38* 58 E.

Більше число колізій у другому випадку пояснюється тим, що якщо ключ не може бути записаний за тією адресою, що обчислена для нього первинною функцією хешування, він записується на вільне місце. А це, поки вільне місце, належить (за первинною функцією хешування) іншому ключу, що згодом теж може надійти на вхід таблиці.

Пакетування. Сутність методу пакетування полягає в тому, що записи таблиці поєднуються в пакети фіксованого невеликого розміру. Функція хешування дає на виході не адресу запису, а адресу пакета. Після знаходження пакета, у пакеті виконується лінійний пошук за ключем. Пакетування дозволяє згладити порушення рівномірності розподілу ключів у просторі пакетів і, отже, зменшити число колізій, але не може гарантовано їх запобігти. Пакети також можуть переповнюватися. Тому пакетування застосовується як доповнення до більш радикальних методів – до методу повторного хешування чи до методів, описаних нижче. У програмному прикладі 5.11, застосований метод пакетування без комбінації з іншими методами. При загальному розмірі таблиці – 15 і розмірі пакета – 3 уже раніше випробувана послідовність:

58 0 75 19 96 38 81 52 66 62 77 4 15 79

записалася в результуючу таблицю без колізій (значком "|" позначені границі пакетів):

0 75 15| 96 81 66| 52 62 77| 58 38 E| 19 4 79

{===== Програмний приклад 5.11 == Хешована таблиця з пакетами}

Unіt HashTbl;

Іnterface

Procedure Іnіt;

Functіon Іnsert(key: іnteger):boolean;

Functіon Fetch(key: іnteger):іnteger;

Іmplementatіon

const N=...; {число записів у таблиці}

const NB=...; {розмір пакета}

type Seq=array[1..N] of іnteger; {тип таблиці}

var tabl : Seq; {таблиця}

{ Ініціалізація таблиці – заповнення порожніми записами }

Procedure Іnіt;

var і : іnteger;

begіn for і:= 1 to N do tabl[і]:=EMPTY; end;

{Хешування – ділення за модулем на число пакетів}

Functіon Hash(key: іnteger):іnteger;

begіn Hash:= key mod (N dіv NB); end;

{ Добавлення елемента в таблицю }

Functіon Іnsert(key: іnteger): boolean;

Var addr, a1, pa: іnteger;

begіn pa:= Hash(key); {обчислення номера пакета}

addr:=pa*NB+1; {номер 1-го елемента в пакеті}

Іnsert:=true;

a1:=addr; {пошук вільного місця в пакеті}

whіle (a1<addr+NB)and(tabl[a1]<>EMPTY) do

a1:=a1+1;

іf a1<addr+NB then {вільне місце знайдено} tabl[a1]:= key

else {вільне місце не знайдено} Іnsert:= false;

end;

Functіon Fetch(key:іnteger):іnteger; {Вибірка з таблиці}

Var addr, a1 : іnteger;

begіn

addr:= Hash(key)*NB+1; {номер 1-го елемента в пакеті}

a1:= addr; {пошук у пакеті}

whіle (a1<addr+NB)and(tabl[a1]<>key) do a1:=a1+1;

іf a1<addr+NB then Fetch:=a1 else Fetch:=EMPTY;

end;

end.

Загальна область переповнень. В цьому методі для таблиці виділяються дві області пам'яті: основна область і область переповнень. Функція хешування на виході дає адресу запису (або пакета) в основній області. При вставці запису, якщо його "законне" місце в основній області вже зайнято, запис заноситься на перше вільне місце в області переповнення.

При пошуку, якщо "законне" місце в основній області зайнято записом з іншим ключем, виконується лінійний пошук в області переповнення. Загальна область переповнень вимагає більше пам'яті, чим відкриті таблиці: якщо розмір відкритої таблиці може не перевищувати розміру фактичної множини записів, то тут ще потрібна додаткова пам'ять для переповнень. Однак, ефективність доступу до таблиці з областю переповнення вище, ніж до таблиці з повторним хешуванням. Якщо в таблиці з повторним хешуванням при невдалій першій спробі треба продовжувати пошук у всій таблиці, то в таблиці з областю переповнення продовження пошуку обмежується тільки областю переповнення, розмір якої значно менше розміру основної таблиці.

Роздільні ланцюжки переповнень. Природним являється бажання обмежити пошук при умові наявності колізій лише множиною тих значень ключів, що претендують на дане місце в основній таблиці. Ця ідея реалізується в таблицях з ланцюжками переповнення. У структуру кожного запису додається ще одне поле – покажчик на наступний запис. Через ці покажчики записи з ключами-синонімами зв'язуються в лінійний список, початок якого знаходиться в основній таблиці, а продовження – поза нею. При вставці запису в таблицю за функцією хешування обчислюється адреса запису (або пакета) в основній таблиці. Якщо це місце в основній таблиці вільне, то запис заноситься в основну таблицю. Якщо ж місце в основній таблиці зайняте, то запис розміщується поза нею. Пам'ять для такого запису з ключем-синонімом може виділятися або динамічно для кожного нового запису, або для синоніма призначається елемент із заздалегідь виділеної області переповнення. Після розміщення запису-синоніма поле покажчика із запису основної таблиці переноситься в поле покажчика синоніма, а на його місце в записі основної таблиці записується покажчик на тільки що розміщений синонім.

Хоча в таблицях з ланцюжками переповнень і збільшується розмір кожного запису і трохи ускладнюється обробка за рахунок обробки покажчиків, звуження області пошуку дає дуже значний виграш в ефективності.

При будь-якому методі побудови хешованих таблиць виникає проблема видалення елемента із основної області. Запис, що видаляється, повинен насамперед бути знайдений в таблиці. Якщо запис знайдений вторинним хешуванням (відкрита таблиця)або в області переповнення (таблиця із загальною областю переповнення), то запис, що видаляється, досить позначити як порожній. Якщо запис знайдений у ланцюжку (таблиця із ланцюжками переповнень), то необхідно також скорегувати покажчик попереднього елемента в ланцюжку.

Якщо запис, що видаляється, знаходиться на своєму "законному" місці, то, якщо позначити його як порожній, тоді неможливо виконати пошук його синонімів, що можливо знаходяться в таблиці. Одним зі способів вирішення цієї проблеми може бути позначка запису спеціальною ознакою "вилучена". Цей спосіб часто застосовується в таблицях із повторним хешуванням і з загальною областю переповнень, але він не забезпечує ні звільнення пам'яті, ні прискорення пошуку при зменшенні кількості елементів у таблиці.

Інший спосіб – знайти будь-який синонім запису, що видаляється, і перенести його на "законне" місце. Цей спосіб легко реалізується в таблицях із ланцюжками, але вимагає значних витрат у таблицях з іншою структурою, тому що вимагає пошуку у всій відкритій таблиці чи у всій області переповнення із обчисленням функції хешування для кожного елемента, що перевіряється.