Переповнення таблиці і повторне хешування

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

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

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

Вставка:

1. i = 0

2. a = (h(key) + c*i) % N

3. Якщо t(a) = вільно або t(a) = вилучено то t(a) = key, записати елемент і стоп

4. i = i + 1, перейти до кроку 2

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

Вставка:

1. i = 0

2. a = ((h(key) + c*i) / n + (h(key) + c*i) % n) % n

3. Якщо t(a) = вільно або t(a) = вилучено, то t(a) = key, записати елемент і стоп

4. i = i + 1, перейти до кроку 2

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

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

Вставка:

1. i = 0

2. a = ((h(key) + c*i) / n + (h(key) + c*i) % n) % n

3. Якщо t(a) = вільно або t(a) = вилучено, то t(a) = key, записати елемент і стоп

4. Якщо i > m, то стоп – потрібно рехешування

5. i = i + 1, перейти до кроку 2

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

Вилучення:

1. i = 0

2. a = ((h(key) + c*i) / n + (h(key) + c*i) % n) % n

3. Якщо t(a) = key, то t(a) = вилучено і стоп елемент вилучено

4. Якщо t(a) = вільно або i>m, то стоп – елемент не знайдено

5. i = i + 1, перейти до кроку 2

Пошук:

1. i = 0

2. a = ((h(key) + c*i) / n + (h(key) + c*i) % n) % n

3. Якщо t(a) = key, то стоп – елемент знайдено

4. Якщо t(a) = вільно або i>m, то стоп – елемент не знайдено

5. i = i + 1, перейти до кроку 2

Оцінка якості хеш-функції

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

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

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

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

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

Розглянемо більш загальний випадок. Нехай необхідно генерувати ключ із m символів з кодами в неперервному діапазоні від n1 до n2.

for (i=0; i<m; i++)

str[i]:=(char)(rand()%(n2-n1)+n1);

На практиці можливі варіанти, коли символи в одних позиціях ключа можуть належати до різних діапазонів кодів, причому між цими діапазонами може існувати розрив. Наприклад генерація ключа з m символів з кодами в діапазоні від n1 до n4 (діапазон має розрив від n2 до n3).

for (int i=0; i<m; i++)

{

x = rand() % ((n4-n3)+(n2-n1));

if (x<=(n2-n1))

str[i] = (char)(x+n1);

else

str[i] = (char)(x+n1+n3-n2);

}

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

Приклад: довжина ключа 7 символів;

3 великі латинські (коди 65-90);

2 цифри (коди 48-57);

2 малі латинські (коди 97-122).

char key[7];

for (i=0; i<3; i++) key[i] = (char)(rand()%(90-65)+65);

for (i=3; i<5; i++) key[i] = (char)(rand()%(57-48)+57);

for (i=5; i<7; i++) key[i] = (char)(rand{}%(122-97)+97);