Хеш таблиця

Кафедра комп'ютерних технологій

Індивідуальне завдання

з дисципліни:« Аналіз алгоритмів і структури даних »

Тема: Хеш таблиця(Hash table)

Коломия 2009

План

1. Структури даних, засновані на хеш-таблицях

2. Відкрите хешування

3. Закрите хешування

4. Оцінка ефективності хеш-функцій

5. Аналіз закритого хешування

6. Випадкові методи дозволу колізій

7. Реструктуризація хеш-таблиць

Література

1. Структури даних, засновані на хеш-таблицях

У реалізації словників за допомогою масивів виконання операторів INSERT, DELETE і MEMBER вимагає в середньому O(N) виконань елементарних інструкцій для словника з N елементів. Подібною швидкістю виконання операторів володіє і реалізація за допомогою списків. При реалізації словників за допомогою двійкових векторів всі ці три оператори виконуються за фіксований час незалежно від розміру множин, але в цьому випадку ми обмежені безліччю цілих чисел з деякого невеликого кінцевого інтервалу.

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

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

2. Відкрите хешування

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

Мал. 1. Організація даних при відкритому хешуванні

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

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

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

Тут же ми введемо хеш-функцію (яка буде "хорошою", але не "відмінною"), визначену на символьних рядках. Ідея побудови цієї функції полягає в тому, щоб представити символи у вигляді цілих чисел, використовуючи для цього машинні коди символів. У мові Pascal є вбудована функція ord(c), яка повертає цілочисельний код символу с. Таким чином, якщо х - це ключ, тип даних ключів визначений як аrrау[1..10] of char (у прикладі 2 цей тип даних названий nametype), тоді можна використовувати хеш-функцію, код якої представлений в прикладі 1. У цій функції підсумовуються всі цілочисельні коди символів, результат підсумовування ділиться на В і береться залишок від ділення, який буде цілим числом з інтервалу від 0 до B - 1.

Лістинг 1. Проста хеш-функція

function h ( х: nametype ) : 0..В-1

var

i, sum: integer;

begin

sum:= 0;

for i:= 1 to 10 do

sum:= sum + ord(x[i]);

h:= sum mod В

end; { h }

У прикладі 1 показані оголошення структур даних для відкритої хеш-таблиці і процедур, що реалізовують оператори, що виконуються над словником. Відзначимо, що в прикладі 2 заголовки списків сегментів зроблені покажчиками на осередки, а не "справжніми" осередками. Це зроблено для економії простору, займаного даними: якщо заголовки таблиці сегментів будуть осередками масиву, а не покажчиками, то під цей масив необхідно стільки ж місця, скільки і під списки елементів. Але за таку економію простору треба платити: код процедури DELETE повинен уміти відрізняти перший осередок від останніх.

Лістинг 2. Реалізація словників за допомогою відкритої хеш-таблиці

const

B = { відповідна константа };

type

celltype = record

element: nametype;

next: Tcelltype

end;

DICTIONARY = array[0..B-l] of ^celltype;

procedure MAKENULL ( var A: DICTIONARY );

var

i:= integer;

begin

for i:= 0 to В - 1 do

А[і]:= nil

end; { MAKENULL }

function MEMBER ( x: name type; var A: DICTIONARY ) : boolean;

var

current: ^celltype;

begin

current:= A[h(x)];

{ початкове значення current рівне заголовку сегменту

якому належить елемент х }

while current <> nil do

if current^.element = x then

return(true) '

else

current := current^.next;

return(false) { елемент x не знайдений }

end; { MEMBER }

procedure INSERT ( x: nametype; var A: DICTIONARY );

var

bucket: integer; { для номера сегменту }

oldheader: ^celltype;

begin

if not MEMBER(x, A) then begin

bucket:= h(x);

oldheader:= A[bucket] ;

new (A [bucket]) ;

A [bucket] ^. element: = x;

A [bucket] ^. next: = oldheader

end

end; { INSERT }

procedure DELETE ( X: nametype; var A: DICTIONARY );

var

bucket: integer;

current: teelltype;

begin

bucket:= h(x);

if A[bucket] <> nil then begin

if A [bucket] ^. element = x then { x в першому осередку }

A[bucket] := A [bucket] ^.next { видалення x із списку }

else begin { x знаходиться не в першому осередку }

current:= A[bucket];

{ current указує на попередній осередок }

while current^.next <> nil do

if current^.next^.element = x then begin

currentt.next:= current^.next^.next;

{ видалення x із списку }

return { зупинка }

end

else { x поки не знайдений }

curгent:= current^. next

end

end

end; { DELETE }

3. Закрите хешування

При закритому хешуванні в таблиці сегментів зберігаються безпосередньо елементи словника, а не заголовки списків. Тому в кожному сегменті може зберігатися тільки один елемент словника. При закритому хешуванні застосовується методика повторного хешування. Якщо ми спробуємо помістити елемент х в сегмент з номером h(x), який вже зайнятий іншим елементом (така ситуація називається колізією), то відповідно до методики повторного хешування вибирається послідовність інших номерів сегментів h1(x), h2(x),…, куди можна помістити елемент х. Кожне з цих місцеположень послідовно перевіряється, поки не буде знайдено вільне. Якщо вільних сегментів немає, то, отже, таблиця заповнена і елемент х вставити не можна.

Приклад 1. Припустимо, що В = 8 і ключі a, b, c і d мають хеш-значення h(a)= 3, h(b)= 0, h(c)= 4 і h(d)= 3. Застосуємо просту методику, яка називається лінійним хешуванням. При лінійному хешуванні hi(x)= (h(x)+ i) mod В. Наприклад, якщо ми хочемо вставити елемент d, а сегмент 3 вже зайнятий, то можна перевірити на зайнятість сегменти 4, 5, 6, 7, 0, 1 і 2 (саме у такому порядку).

Ми припускаємо, що спочатку вся хеш-таблиця порожня, тобто в кожен сегмент поміщено спеціальне значення empty (порожній), яке не співпадає ні з одним елементом словаря. Тепер послідовно вставимо елементи a, b, c і d в порожню таблицю: елемент а потрапить в сегмент 3, елемент b - в сегмент 0, елемент с - в сегмент 4. Для елементу d h(d)= 3, але сегмент 3 вже зайнятий. Застосовуємо функцію h1: h1(d)= 4, але сегмент 4 також зайнятий. Далі застосовуємо функцію h2: h2(d) - 5, сегмент 5 вільний, поміщаємо туди елемент d. Результат заповнення хеш-таблиці показаний на мал. 2.

Мал. 2. Частково заповнена хеш-таблиця

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

Приклад 2. Припустимо, що треба визначити, чи є елемент е в множині, представленій на мал. 2. Якщо h(е)= 4, то треба перевірити ще сегменти 4, 5 і потім сегмент 6. Сегмент 6 порожній, в попередніх проглянутих сегментах елемент е не знайдений, отже, цього елементу в даній множині немає.

Допустимо, ми видалили елемент c і помістили константу deleted в сегмент 4. У цій ситуації для пошуку елементу d ми почнемо з перегляду сегмент h(d) - 3, потім проглянемо сегменти 4 і 5 (де і знайдемо елемент d), при цьому ми не зупиняємося на сегменті 4 - хоча він і порожній, але не помічений як empty.

У лістингу 2 представлені оголошення типів даних і процедури операторів для АТД DICTIONARY з елементами типу nametype і реалізацією, що використовує закриту хеш-таблицю. Процедура INSERT(x, А) використовує функцію locate (місцезнаходження) для визначення, чи присутній елемент х в словнику А чи ні, а також спеціальну функцію locate1 для визначення місцезнаходження елементу х. Останню функцію також можна використовувати для пошуку констант deleted і empty.

Лістинг 3. Реалізація словника за допомогою закритого хешування

const

empty = “ “ ;{ 10 пропусків }

deleted= “ ********** ”; { 10 символів * }**********`л. 4.4и що звільнило````````````````````````````````````````````````````````````````````````````````````````````````

type

DICTIONARY = array[0..B-l] of nametype;

procerude MAKENULL ( var A: DICTIONARY );

var

i: integer;

begin

for i:= 0 to В - 1 do

A[i] := empty

end; { MAKENULL }

function locate ( x: nametype; A: DICTIONARY ): integer;

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

var

initial, i: integer;

begin

initial:= h(x); i:= 0;

while (i < B) and {A[(initial + i) mod B] <> х) and

{A[(initial + i) mod В] <> empty) do

i:= i + 1;

return((initial + i) mod B)

end; { locate }

function locatel ( x: nametype; A: DICTIONARY ): integer;

{ Tе ж саме, що і функція locate, але зупиняється досягши значення deleted }

function MEMBER ( х: nametype; var A: DICTIONARY ): boolean;

begin

if Allocate(x) ] = x then

return(true)

else

return(false)

end; { MEMBER }

procedure INSERT ( x: nametype; var A: DICTIONARY );

var

bucket: integer;

begin

if A[locate(x)] = x then return; { x вже є в A }

bucket:= locatel(x);

if (A[bucket] = empty) or (A[bucket] = deleted) then

A [bucket] := x

else

error('Операція INSERT неможлива: таблиця повна'}

end; { INSERT }

procedure DELETE ( x: nametype; var A: DICTIONARY );

var

bucket: integer;

begin

bucket:_ locate(x);

if Allocate(x)] = x then

A [bucket] := deleted

end; { DELETE }

4. Оцінка ефективності хеш-функцій

Нагадаємо, що хешування - ефективний спосіб представлення словників і деяких інших абстрактних типів даних, заснованих на множинах. У цій роботі ми оцінимо середній час виконання операторів словників для випадку відкритого хешування. Якщо є В сегментів і N елементів, що зберігаються в хеш-таблиці, то кожен сегмент в середньому матиме N/В елементів і ми очікуємо, що оператори INSERT, DELETE і MEMBER виконуватимуться в середньому за час 0(1 + N/В). Тут константа 1 відповідає пошуку сегменту, а N/В - пошуку елементу в сегменті. Якщо В приблизно рівне N, то час виконання операторів стає константою, незалежною від N.

Припустимо, що є програма, написана на мові програмування, подібному Pascal, і ми хочемо всі наявні в цій програмі ідентифікатори занести в хеш-таблицю. Після виявлення оголошення нового ідентифікатора він вставляється в хеш-таблицю, звичайно ж, після перевірки, якщо його ще немає в хеш-таблиці. На етапі перевірки природно припустити, що ідентифікатор з рівною імовірністю може бути в будь-якому сегменті. Таким чином, на процес заповнення хеш-таблиці з N елементами буде потрібно час порядка 0(N(1 + N/В)). Якщо покласти, що В рівне N, то отримаємо час 0(N).

На наступному етапі аналізу програми є видимими ідентифікатори в тілі програми. Після знаходження ідентифікатора в тілі програми, щоб отримати інформацію про нього, його ж необхідно знайти в хеш-таблиці. Який час буде потрібний для знаходження ідентифікатора в хеш-таблиці? Якщо час пошуку для всіх елементів приблизно однаково, то він відповідає середньому часу вставки елементу в хеш-таблицю. Щоб побачити це, досить відмітити, що час пошуку будь-якого елементу рівний часу вставки елементу в кінець списку відповідного сегменту. Таким чином, час пошуку елементу в хеш-таблиці складає 0(1 + N/В).

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

Приклад 3. Припустимо, що функція з лістингу 1. застосовується для занесення в таблицю з 100 сегментів 100 символьних рядків А0, А1 ..., А99. Беручи до уваги, що ord(O), ord(l), …, ord(9) утворюють арифметичну прогресію (це справедливо для всіх таблиць кодувань, де цифри 0, 9 стоять підряд, наприклад для кодування ASCII), легко перевірити, що ці елементи займуть не більше 29 сегментів із ста, найбільший сегмент (сегмент з номером 2) міститиме елементи А18, А27, А36, …, А90, тобто дев'ять елементів із ста. Використовуючи той факт, що для вставки i-го елементу потрібний i + 1 кроків, легко підрахувати, що в даному випадку середнє число кроків, необхідне для вставки всіх 100 елементів, рівне 395. Для порівняння відмітимо, що оцінка N(1 + N/В) припускає тільки 200 кроків.

У приведеному прикладі хеш-функція розподіляє елементи початкової множини по безлічі сегментів не рівномірно. Але можливі "більш рівномірні" хеш-функції. Для побудови такої функції можна скористатися добре відомим методом зведення числа в квадрат і вибору з отриманого квадрата декількох середніх цифр. Наприклад, якщо є число n, що складається з 5 цифр, то після зведення його в квадрат отримаємо число, що складається з 9 або 10 цифр. "Середні цифри" - це цифри, що стоять, наприклад на позиціях від 4 до 7 (відлічуючи справа). Їх значення, залежать від числа п. Якщо В = 100, то для формування номера сегменту досить узяти дві середні цифри, що стоять, наприклад, на позиціях 5 і 6 в квадраті числа.

Цей метод можна узагальнити на випадок, коли В не є степенем числа 10. Припустимо, що елементи початкової множини є цілими числами з інтервалу 0, 1, …, К. Введемо таке ціле число С, що ВС приблизно рівно К?, тоді функція

h(n) - [п?/С] mod В,

де [х] позначає цілу частину числа х, ефективно витягуючи з середини числа п2 цифри, складові яких, не перевищують В.

Приклад 4. Якщо К = 1000 і В = 8, то можна вибрати С = 354. Тоді

Для застосування до символьного рядка описаної хеш-функції треба спочатку в рядку згрупувати символи справа наліво в блоки з фіксованою кількістю символів, наприклад по 4 символи, додаючи при необхідності зліва пропуски. Кожен блок трактується як просте ціле число, з якого шляхом конкатенації (зчеплення) формується двійковий код символів, складовий блок. Наприклад, основна таблиця ASCII кодування символів використовує 7-бітовий код, тому символи можна розглядати як "цифри" 2 в 7 степені, або 128 у 3 степені. Таким чином, символьний рядок abсd можна вважати цілим числом (128)?а + (128)?b + (128)c + d. Після перетворення всіх блоків в цілі числа вони сумуються, а потім виконується вищеописаний процес зведення в квадрат і знаходження середніх цифр.

5. Аналіз закритого хешування

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

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

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

Вірогідність колізії рівна N/В. Припускаючи здійснення колізії, на першому етапі повторного хешування працюємо з В - 1 сегментом, де знаходиться N-1 елемент. Тоді вірогідність виникнення двох підряд колізій рівна N(N - 1)/(B(B - 1)). Аналогічно, вірогідність колізій i рівна:

Якщо значення В і N великі, то ця вірогідність приблизно рівна (N/B). Середнє число проб рівне одиниці плюс сума по всіх і ? 1 вірогідності подій.

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

Мал. 3. Середні числа проб, необхідні для виконання оператора

6. Випадкові методи дозволу колізій

Ми раніше бачили, що методика лінійного повторного хешування приводить до групування заповнених сегментів у великі безперервні блоки. Можна запропонувати хеш-функції з більш "випадковою" поведінкою, наприклад, ввести цілочисельну константу > 1 і визначити h1(x) = (h(x) + сі) mod В. В цьому випадку для В = 8, с = 3 і h(х) = 4 отримаємо "пробні" сегменти в наступному порядку: 4, 7, 2, 5, 0, 3, 6 і 1. Звичайно, якщо В i с мають загальні дільники (відмінні від одиниці), отже ця методика не дозволить отримати всі номери сегментів, наприклад при В = 8 і с = 2. Але навіть якщо В i с взаємно прості числа (тобто не мають загальних дільників), то все одно існує проблема "групування", як і при лінійному хешуванні, хоча тут розділяються блоки заповнених сегментів, відповідні різним константам с. Цей феномен збільшує час виконання операторів словників (як і при лінійному хешуванні), оскільки спроба вставити новий елемент в заповнений сегмент приводить до проглядання ланцюжка заповнених сегментів, різних для різних с, і довжина цих ланцюжків при кожній вставці збільшується на одиницю.

Фактично будь-яка методика повторного хешування, де чергова проба залежить тільки від попередньої (наприклад, як залежність від числа попередніх "невдалих" проб, від початкового значення h(x) або від самого елементу х), знаходить групуючі властивості лінійного хешування. Можлива проста методика, для якої проблема "групування" не існує. Звичайно, такий набір чисел d1, d2, …, dВ-1 повинен використовуватися при реалізації всіх операторів, що виконуються над словниками, а "випадкове" перемішування цілих чисел повинне бути зроблене (вибране) ще при розробці алгоритму хешування.

Генерація "хороших випадкових" чисел - достатньо складне завдання, але, на щастя, існують порівняно прості методи отримання послідовності і "випадкових" чисел шляхом "перемішування" цілих чисел із заданого інтервалу. За наявності такого генератора випадкових чисел можна відтворювати необхідну послідовність d1, d2, …, dВ і при кожному виконанні операторів, що працюють з хеш-таблицею.

7. Реструктуризація хеш-таблиць

При використанні відкритих хеш-таблиць середній час виконання операторів зростає із зростанням параметра N/B і особливо швидко росте при перевищенні числа елементів над числом сегментів. Так само середній час виконання операторів також зростає із збільшенням параметра N/B і для закритих хеш- таблиць, що видно з мал. 3 (але перевищення N над В тут неможливо).

Щоб зберегти постійний час виконання операторів, що теоретично можливо при використанні хеш- таблиць, ми пропонуємо досягши N достатньо великих значень, наприклад при N > 0.9В для закритих хеш- таблиць і N > 2В - для відкритих хеш- таблиць, просто створювати нову хеш-таблицю з подвоєним числом сегментів. Перезапис поточних елементів множини в нову хеш-таблицю в середньому займе менше часу, ніж їх раніше виконана вставка в стару хеш-таблицю меншого розміру. Крім того, витрачений час на перезапис компенсується швидшим виконанням операторів.

Література

1. Зыков А.А. «Теорія кінцевих графів» - Новосибірськ: Наука, 1969р.

2. Хараре Ф. «Теорія графів» - М: Світ, 1973р.

3. Зыков А.А. «Основи теорії графів» - М: Наука, 1987р.

4. Кристофидес Н. «Теорія графів. Алгоритмічний підхід» - М: Світ, 1978р.

5. Майнико З. «Алгоритми оптимізації на мережах і графах» - М: Світ, 1981р.

6. Ловас Л., Пламмер М. «Прикладные задачи теории графов. Теория паросочетаний у математике, физике, химии» - М: Світ, 1998р.