10 (1). Хешування. Пошуку, включення і виключення елементів. Рандомізують функція (хеширования) і її властивості.
Розглянуті раніше колекції на основі дерев пошуку дозволяють будувати абстрактний тип даних «Таблиця». Але ці колекції мають логарифмічною трудомісткістю операцій, що залежить від числа елементів в таблиці. Зустрічаються програми, що вимагають швидкого і гарантованого за часом виконання, не залежного від обсягу даних в таблиці. У цьому випадку використовується спеціальна організація таблиці з постійним часом виконання операцій - хеш-таблиця.
Хеш-таблиця вимагає пам'яті О (# 9474; m # 9474;), де m - безліч включених до таблиці записів. Час пошуку в хеш-таблиці як і раніше О (1).
У хеш-таблиці елементу відводиться індекс h (k), де k - ключ елемента h (k) - хеш функція (або рандомізують функція). Число h (k) називають хеш-значенням ключа k. Процес перетворення ключа елемента в індекс хеш - таблиці називається хешированием.
Функція хешування (рандомізують функція) і її властивості
1. Хороша хеш-функція повинна забезпечувати рівномірне змішування, тобто для будь-якого ключа все m хеш-значень повинні бути рівноймовірно.
2. рандомізують функція не повинна зберігати будь-який зв'язок між значеннями ключів. Виконання цієї вимоги виключає (або хоча б зменшує) залежність "якості" рандомізації від використовуваних значень ключа.
4. Хеш - функція повинна бути детермінованою в тому сенсі, що при повторних викликах з одним і тим же ключем вона повинна повертати один і той же хеш-значення.
Схема дії рандомізують функції представлена на рис.
· Метод розподілу із залишком (модульне хешування) дає прості та ефективні хеш-функції. Ключу k ставиться у відповідність залишок від ділення k на m. Хеш-функція обчислюється, як рівняння h (k) = k mod m.
Наприклад, якщо m = 13, k = 100, то h (k) = 9.
· Метод множення (мультиплікативний) обчислює хеш - функцію по формулі
де A- деяка константа, яка задовольнить умові 0 Гідність методу множення полягає в тому, що якість хеш-функції мало залежить від вибору m. Але зазвичай в якості m вибирають ступінь двійки, так як в більшості комп'ютерів множення на ступінь двійки реалізується швидко, як зрушення слова. Метод множення працює при будь-якому виборі константи А. але деякі значення А можуть бути краще за інших. Вдалим значенням є число Фібоначі. А = +0,6180339887 Проілюструємо метод на конкретному прикладі. Нехай розмір хеш - таблиці m = 10000. При вставці ключа 123456 вийде хеш - значення: function hash (key. string [4]): integer; f: = ord (key [1]) - ord (key [2]) + ord (key [3]) - ord (key [4]); f: = (f * 10000) div (255 * 4); Методи вирішення колізій Процедура видалення з таблиці зводиться до пошуку елемента і його видалення з ланцюжка переповнення. Рис.3.2. Різновиди методів вирішення колізій Рис.3.3. Дозвіл колізій при додаванні елементів методом ланцюжків Лінійне випробування зводиться до послідовного перебору елементів таблиці з деяким фіксованим кроком де i - номер спроби дозволити колізію. При кроці рівному одиниці відбувається послідовний перебір всіх елементів після поточного. Квадратичне випробування відрізняється від лінійного тим, що крок перебору елементів не лінійно залежить від номера спроби знайти вільний елемент Включення і пошук Наведемо алгоритми вставки і пошуку для методу лінійне випробування. · A = h (key) + i * c · Якщо t (a) = вільно, то t (a) = key. записати елемент, стоп елемент доданий · I = i + 1, перейти до кроку 2 · A = h (key) + i * c · Якщо t (a) = key. то стоп елемент знайдений · Якщо t (a) = вільно, то стоп елемент не знайдений · I = i + 1, перейти до кроку 2 Вибираємо крок q. При спробі додати елемент в зайняту комірку починаємо послідовно переглядати осередки і так далі, поки не знайдемо вільну комірку. У неї і запишемо елемент. По суті послідовний пошук - окремий випадок лінійного, де q = 1. Крок q не фіксований, а змінюється квадратично: q = 1,4,9,16. Відповідно при спробі додати елемент в зайняту комірку починаємо послідовно переглядати осередки і так далі, поки не знайдемо вільну комірку. подвійне хешування Показана хеш-таблиця розміром 13 осередків, в якій використовуються допоміжні функції: Ми хочемо вставити ключ 14. Спочатку i = 0. Тоді. Але осередок з індексом 1 зайнята, тому збільшуємо i на 1 та перераховуємо значення хеш-функції. Робимо так, поки не дійдемо до порожнього вічка. При i = 2 отримуємо. Осередок з номером 9 вільна, значить записуємо туди наш ключ. (Крок 2). З процедурою видалення справа йде не так просто, так як вона в даному випадку не буде зворотної процедури вставки. Справа в тому, що елементи таблиці знаходяться в двох станах: вільно і зайнято. Якщо видалити елемент, перевівши його в стан вільно, то після такого видалення алгоритм пошуку буде працювати некоректно. Припустимо, що ключ видаляється елемента має в таблиці ключі синоніми. У тому випадку, якщо за видаляється елементом в результаті вирішення колізій були розміщені елементи з іншими ключами, то пошук цих елементів після видалення завжди буде давати негативний результат, так як алгоритм пошуку зупиняється на першому елементі, що знаходиться в стані вільно. Скорегувати цю ситуацію можна різними способами. · Найпростіший з них полягає в тому, щоб виробляти пошук елемента не до першого вільного місця, а до кінця таблиці. Однак така модифікація алгоритму зведе нанівець весь виграш в прискоренні доступу до даних, який досягається в результаті хешування. · Існує підхід, який вільний від перерахованих недоліків. Його суть полягає в тому, що для елементів хеш-таблиці додається стан видалено. Даний стан в процесі пошуку інтерпретується, як зайнято, а в процесі запису як вільно. Сформулюємо алгоритми вставки пошуку і видалення для хеш-таблиці, що має три стану елементів. 2. a = h (key) + i * c 3. Якщо t (a) = вільно або t (a) = видалено, то t (a) = key. записати елемент, стоп елемент доданий 4. i = i + 1, перейти до кроку 2 · A = h (key) + i * c · Якщо t (a) = key. то t (a) = видалено. стоп елемент видалений · Якщо t (a) = вільно, то стоп елемент не знайдений · I = i + 1, перейти до кроку 2 · A = h (key) + i * c · Якщо t (a) = key. то стоп елемент знайдений · Якщо t (a) = вільно, то стоп елемент не знайдений · I = i + 1, перейти до кроку 2 Алгоритм пошуку для хеш-таблиці, що має три стану, практично не відрізняється від алгоритму пошуку без урахування вилучень. Різниця полягає в тому, що при організації самої таблиці необхідно відзначати вільні і вилучені елементи. Це можна зробити, зарезервувавши два значення ключового поля. Інший варіант реалізації може передбачати введення додаткового поля, в якому фіксується стан елемента. Довжина такого поля може складати всього два біта, що цілком достатньо для фіксації одного з трьох станів.