Колізії при хешуванні (алгоритми виключення колізій)

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

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

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

Тоді для зберігання всього файлу буде достатньо|досить| масиву з|із| 1000 елементів. Цей масив індексується цілим числом в діапазоні від 0 до 999 включно. Як індекс запису про виріб в цьому масиві використовуються три останні цифри номера виробу.

Мал.1 Записи про деталі

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

Хешування - це спосіб зведення зберігання однієї великої множини|безлічі| до більш меншої.

Функція, яка трансформує ключ|джерело| в деякий індекс в таблиці, називається хеш-функцією|.

В даному випадку h(key|):= key| mod| 1000;

Хеш-таблиця - це звичайний|звичний| масив з|із| незвичайною|незвичною| адресацією|, що задається хеш-функцієй.

Цей метод має один недолік|нестача|. Давайте додамо|добавлятимемо| в таблицю запис з|із| ключем|джерелом| 0596397. Побачимо, що дана чарунка вже зайнята|позичати|.

Ситуація, коли два або більше ключа|джерело| асоціюються з|із| однією і тією ж чарункою називається колізією при хешуванні.

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

Досконала|довершена| хеш-функція - це функція, яка не породжує колізій.

Вирішити колізії при хешуванні можна 2 методами:

· методом відкритої|відчиняти| адресації (закрите хешування)

· методом ланцюжків (відкрите хешування)

Дозвіл колізій при хешуванні методом відкритої|відчиняти| адресації

Подивимося|поглянемо|, що відбудеться, якщо ми захочемо|схочемо| ввести|запроваджувати| в таблицю деякий новий номер виробу 0596397. Використовуючи хеш-функцію h(key|):=key mod| 1000, ми знайдемо, що h (0596397) =397 і що запис для цього виробу повинен знаходитися|перебувати| у позиції 397 в масиві. Проте|однак| позиція 397 вже зайнята|позичати|, оскільки там знаходиться|перебуває| запис з|із| ключем|джерелом| 4957397. Отже, запис з|із| ключем|джерелом| 0596397 має бути вставлено в таблицю у іншому місці.

Найпростішим методом дозволу колізій при хешуванні є|з'являється| переміщення|помешкання| даного запису в наступну|таку| вільну позицію в масиві. Наприклад, запис з|із| ключем|джерелом| 0596397 поміщається в чарунку|чарунку| 398, яка поки вільна, оскільки 397 вже зайнята|позичати|. Коли цей запис буде вставлений, інший запис, який хешується| в позицію 397 (з|із| таким ключем|джерелом|, як 8764397) або в позицію 398 (з|із| таким ключем|джерелом|, як 2194398), вставляється в наступну|таку| вільну позицію, яка в даному випадку дорівнює 400.

Якщо чарунка|чарунка| масиву h(key|) вже зайнята|позичати| деяким записом з|із| іншим ключем|джерелом|, то функція rh| застосовується до значення h(key|) для того, щоб знайти іншу чарунку|чарунку|, куди може бути поміщений цей запис. Якщо чарунка|чарунка| rh|(h(key|)) також зайнята|позичати|, то хешування виконується ще раз і перевіряється чарунка|чарунка| rh|(rh|(h(key|))). Цей процес продовжується|триває| до тих пір, поки не буде знайдена порожня|пустий| чарунка|чарунка|. Rh| - це функція повторного хешування, яка сприймає один індекс в масиві і видає інший індекс.

Var|

K: array| [0...999] of| integer|;

Function| h(key|: integer|): integer|;

Begin|

h := key| mod| 1000;

End|;

Function| rh|(i: integer|): integer|;

Begin|

rh:=i+1| mod| 1000;

End|;

Procedure| insert|(key|: integer|);

Var|

I: integer|;

begin|

I := h(key|); {хешуємо| ключ|джерело|}

while| ((до(i)< >key|) and| (до(i)< >0)) do|

i := rh|(i); {ми повинні виконати повторне хешування}

if| до(i)=0 then| {вставляємо запис в порожню|пусту| позицію}

до(i)=key

end|;

Недоліки|нестачі| методу

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

По-друге|, з|із| такої таблиці важко видалити|знищувати| запис.

Поиск по сайту: