1. ВСТУП.

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

може бути

Перше питання, яке ми можемо задати собі, - чи легко знайти такі функції h? Відповідь, в принципі, досить песимістичний, оскільки якщо взяти за ідеальну ситуацію, що така функція завжди надає різне розташування різним клавішам, і ми думаємо, наприклад, про таблицю розміром 40, де ми хочемо адресувати 30 ключів, ми виявляємо, що в таблиці є 40 30 = 1,15 * 10 48 можливих функцій набору ключів, і лише 40 * 39 * 11 = 40!/10! = 2,25 * 10 41 з них не генерують повторюваних розташувань. Іншими словами, лише 2 з 10 мільйонів таких функцій були б ідеальними для наших цілей. Це завдання здійсненне лише у тому випадку, якщо значення, які належатимуть до хеш-таблиці, відомі апріорі. Існують алгоритми побудови досконалих хеш-функцій, які використовуються для впорядкування ключових слів у компіляторі, щоб пошук будь-якого з цих ключових слів здійснювався у постійний час.

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

Отже, додатки h (k), які відтепер ми будемо називати хеш-функціями, мають ту особливість, що можна очікувати, що h (k i) = h (k j) для досить багатьох різних пар (k i, k j). Отже, метою буде знайти хеш-функцію, яка спричиняє найменшу можливу кількість зіткнень (поява синонімів), хоча це лише один аспект проблеми, інший - розробити методи вирішення колізій, коли вони трапляються.

2. ХЕШ-ФУНКЦІЇ.

Перша проблема, з якою ми маємо вирішити, - це обчислення хеш-функції, яка перетворює ключі в місця розташування таблиці. Більш конкретно, нам потрібна функція, яка перетворює ключі (зазвичай цілі числа або рядки символів) у цілі числа в діапазоні [0.M-1], де M - кількість регістрів, які ми можемо обробити з наявною пам’яттю. до вибору функції h (k) Вони призначені для мінімізації зіткнень та відносно швидкого та простого обчислення, хоча ідеальною ситуацією було б знайти функцію h що генеруватиме випадкові значення рівномірно протягом інтервалу [0.M-1]. Два підходи, які ми побачимо, спрямовані на цю мету, і обидва засновані на генераторах випадкових чисел.

Мультиплікативний хасинг.

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

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

Іншим мультиплікативним методом, який дозволяє уникнути попередніх обмежень, є обчислення h (k) = Int [M * ​​Frac (C * k)], де M - розмір таблиці та 0

Хасінг за відділом.

У цьому випадку функція просто обчислюється як h (k) = k mod M використовуючи 0 як перший індекс хеш-таблиці розміру M.

Хоча формула застосовна до таблиць будь-якого розміру, важливо ретельно вибирати значення М. Наприклад, якби M було парним, усі парні клавіші (непарні відповідно) застосовувалися б до парних місць (непарні відповідно), що могло б становити дуже сильний ухил. Просте правило вибору М - це прийняти його за просте число. У будь-якому випадку існують більш складні правила вибору М (див. Кнут), які базуються на теоретичних дослідженнях роботи конгруентних методів генерації випадкових чисел.

3. ВИРІШЕННЯ КОЛІЗІЙ.

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

Для всіх прикладів розмір таблиці буде M = 13, а хеш-функція h 1 (k), яку ми будемо використовувати, буде такою:

HASH = Ключ Mod M

і значення ключа k, які ми розглянемо, є тими, що показано в наступній таблиці:

Припускаючи, що k = 0 не відбувається природним чином, ми можемо позначити всі місця в таблиці спочатку порожніми, надаючи їм значення 0. Нарешті, і оскільки операції пошуку та вставки тісно пов'язані, будуть представлені алгоритми пошуку при необхідності (якщо ця операція не спричиняє переповнення таблиці), повертаючи розташування елемента або -1 (NULL) у разі переповнення.

Окремий ланцюжок або відкрита хасинг.

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

У будь-якому випадку, якщо списки ведуться в порядку, це можна розглядати як узагальнення методу послідовного пошуку в списках. Різниця полягає в тому, що замість ведення єдиного списку з одним вузлом заголовка, М списки з М вузлами заголовків ведуться таким чином, що кількість порівнянь послідовного пошуку зменшується в коефіцієнт М (в середньому) за допомогою додаткових місце для вказівників M. Для нашого прикладу та з альтернативою LIFO таблиця буде такою, як показано на наступному малюнку:

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

Адресація відкритою або закритою.

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

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

reh i (k) = (h (k) + (i-1)) mod M i = 2.3.

У нашому прикладі після вставки перших 7 клавіш з'являється таблиця А (див. Наступну таблицю). Коли ми збираємося вставити ключ 147, він поміщається в поле 6, (таблиця B), коли поля 4 і 5 не знайдені порожніми. Видно, що до вставки 147 в місцях розташування були групи ключів 4,5 і 7,8, а після вставки ці дві групи об’єдналися, утворюючи більшу первинну групування, це означає, що якщо ви намагаєтесь вставити елемент, який відповідає деяким вікнам, які знаходяться на початку цієї групування, процес перешифрування доведеться пройти всі ці вікна, що погіршить ефективність вставки. Щоб вирішити цю проблему, нам доведеться шукати метод перешифрування, який розподіляє порожні клітинки якомога випадковіше.

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

Щоб спробувати уникнути щойно побаченої проблеми кластеризації, ми могли б скористатися наступною функцією перепрофілювання:

reh i (k) = (h (k) + (i-1) * C) mod M C> 1 і відносний простий знак з M

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

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

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

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

h i (k) = (h i-1 (k) + h 0 (k)) mod M i = 2.3.

з h 0 (k) = 1 + k mod (M-2) та h 1 (k) = h (k).

Існує можливість робити інші варіанти функції h 0 (k), якщо обрана функція не є постійною.

Ця форма подвійного повторного повторення особливо хороша, коли М і М-2 є відносними простими числами. Майте на увазі, що якщо M просте, то певно, що M-2 є його відносним простим (за винятком тривіального випадку, коли M = 3).

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

4. ВИДАЛЕНО ТА РЕЗЕРВОВАНО.

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

5. ОЦІНКА МЕТОДІВ РОЗВ'ЯЗАННЯ.

Найважливішим аспектом пошуку хешування є те, що його ефективність залежить від так званого коефіцієнта зберігання У = n/M з n кількість предметів і М розмір столу.

Ми обговоримо середню кількість випробувань для кожного з методів вирішення зіткнень, які ми бачили, з точки зору БУТИ (успішний пошук) і BF (пошук без успіху). Докази отриманих формул можна знайти у Кнута (див. Бібліографію).

Окремий ланцюжок.

Хоча це може ввести в оману порівняння цього методу з двома іншими, оскільки в цьому випадку може статися, що У> 1, наближеними формулами є:

Ці вирази застосовуються навіть тоді, коли У >> 1, тому для n >> M середня довжина кожного списку буде У, і слід очікувати, що в середньому просканує середина списку, перш ніж знайти певний елемент.

Лінійне покриття.

Приблизними формулами є:

Як бачимо, цей метод, хоча і задовільний для малого пара, дуже поганий, коли У -> 1, оскільки межа середніх значень БУТИ Y BF є відповідно:

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

Подвійне кріплення.

Формули тепер:

із середніми значеннями, коли У -> 1 M та M/2 відповідно.

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

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

У порівнянні з іншими методами пошуку, хешування має переваги та недоліки. Загалом, для великих значень n (і розумні значення У) хороша схема хешування зазвичай вимагає менше тестів (на порядок 1,5 - 2), ніж будь-який інший метод пошуку, включаючи пошук у двійкових деревах. З іншого боку, у гіршому випадку воно може вести себе дуже погано, вимагаючи O (n) тести. Також перевагою можна вважати той факт, що ми повинні мати певну апріорну оцінку максимальної кількості предметів, які ми збираємось розмістити в таблиці, хоча, якщо такої оцінки у нас немає, ми завжди матимемо можливість використання методу окремого ланцюжка, коли переповнення таблиці не є проблемою.

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

6. ВПРОВАДЖЕННЯ ХЕШ-СТОЛІВ.

Впровадження Open Hasing.

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

Можлива реалізація з використанням абстрактного типу даних списку буде наступною:

Для чого ми можемо розробити такі функції створення та знищення:

Як вже згадувалося раніше, буде використана така хеш-функція:

І функції типу HashMember, InsertHash, DeleteHash можна запрограмувати:

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

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

Впровадження закритої Hasing.

У цьому розділі ми будемо робити просту реалізацію закритого хешування. Для цього ми припустимо тип данихchar * як і в попередньому розділі, для якого ми розробимо ту саму хеш-функцію.

Можливим впровадженням структури для досягнення є наступне:

Для чого ми можемо розробити такі функції створення та знищення:

Хеш-функція, яка буде використана, така ж, як та, яку ми вже використовували для реалізації Open Hasing. І функції типу HashMember, InsertHash, DeleteHash Їх можна запрограмувати наступним чином, маючи на увазі, що в цій реалізації ми будемо використовувати лінійне перепрофілювання.

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