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

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

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

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