Главная | Обратная связь | Поможем написать вашу работу!

Хешовані таблиці та функції хешування

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

r = H(k),

де: r – адреса запису, k – ключ.

Така функція H називається функцією хешування (інші її назви – функція перемішування, функція рандомізації). В нашому випадку дані організовані в пам’яті як массив. Тому дія H – функції полягає в перетворенні ключів в індекси масиву. Звідси ще одна назва методу – перетворення ключів.

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

Якщо функція H, що перетворює ключ на адресу, може породжувати колізії, то однозначної зворотної функції:

k = H'(r),

яка дозволяє відновити ключ за відомою адресою, існувати не може. Тому ключ повинен обов'язково входити до складу запису хешованої таблиці як один з її полів.

Рис. 5.3. Колізія. Точки А, В, С відображаються в точку О

До функції хешування в загальному випадку пред'являються наступні вимоги:

– повинна забезпечувати рівномірний розподіл відображень фактичних ключів за простором записів;

– повинна породжувати якнайменше колізій для даної фактичної множини записів;

– не повинна відображати будь-який зв'язок між значеннями ключів у зв'язок між значеннями адрес;

– повинна бути простою і швидкою для обчислення.

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

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

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

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

Функція перетворення системи обчислення. Ключ, записаний як число в деякій системі обчислення P, інтерпретується як число в системі обчислення Q, причому Q>P. Частіше вибирають Q=P+1. Це число переводиться із системи Q назад у систему P, приводиться до розміру простору записів і інтерпретується як адреса.

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

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

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

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.

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

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

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

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

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

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

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

Сортування

Для самого загального випадку задача сортування може формулюватися так: мається деяка неупорядкована вхідна множина ключів, необхідно одержати вихідну множину тих же ключів, упорядкованих за зростанням або зменшенням в чисельному чи лексикографічному порядку. З усіх задач програмування, сортування, можливо, має найбільш широкий вибір алгоритмів рішення. У даному розділі будуть розглянуті внутрішні алгоритми сортувань на прикладі масивів; зовнішні сортування (сортування файлів) поки не розглядаються.

Фактори, що впливають на вибір алгоритму сортування:

а) порядок алгоритму: степеневий O(N^a), лінійні O(N) або логарифмічний O(log_a(N));

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

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

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

Класифікація алгоритмів сортування за логічними характеристика-ми. Відповідно до цього підходу виділяють чотири групи алгоритмів сортування.

1) Сортування вибіркою. З вхідної множини вибирається наступний за критерієм упорядкованості елемент і включається у вихідну множину на наступне за номером місце.

2) Сортування включенням. З вхідної множини вибирається наступний за номером елемент і включається у вихідну множину на те місце, яке він повинен займати відповідно до критерію упорядкованості ключів.

3) Сортування розподілом. Вхідна множина розбивається на ряд підмножин (можливо, меншого обсягу) і сортування проводиться усередині кожної такої підмножини.

4) Сортування злиттям. Вихідна множина получається шляхом злиття маленьких упорядкованих підмножин.

Всі алгоритми сортувань розглянуті для прикладі упорядкування за зростанням ключів і наведені мовою Pascal. Тип SEQ визначений як:

type SEQ=array[1..n] of іnteger;

⇐ Предыдущая 123 4 5 6 Следующая ⇒