Пошук хеш-функції

Поиск хеш-функции.

ХЕШИРОВАНИЕ.

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

К жалю, знаходити подібні функції f (K) дуже складно.

Функции, дають неповторювані значення, несподівано рідкісні навіть тоді досить великий таблиці. Наприклад, знаменитий парадокс днів народження стверджує, що, тоді як кімнаті присутній щонайменше 23 людина, хороший шанс те що, що з двох співпаде дня народження! Інакше кажучи, коли ми вибираємо випадкову функцію, отображающую 23 ключа в 365-элементную таблицю, те з ймовірністю 0.4927 (менше половини) все ключі потраплять у різні місця.

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

Можно отримати значно більше гнучкий метод, якщо відкинути ідею однозначності, допускаючи збіги значень f (K) щодо різноманітних аргументів, і використовувати особливий метод дозволу невизначеності після обчислення f (K).

Наші розгляду призводять до широко відомому класу методів, зазвичай званих хешированием чи розсіяною пам’яттю. Англійський дієслово «to hash «можна буде нарізати, розкришити щось або з цього місиво; ідея хеширования у тому, щоб узяти деякі характеристики ключа і використовувати отриману часткову інформацію як основи пошуку. Ми рахуємо хеш-функцию h (K) і беремо це значення як адреси початку пошуку.

Парадокс днів народження служить нам застереженням, що, мабуть, знайдуться різні ключі Ki? Kj, котрим h (Ki)=h (Kj). Таке подія називається колізією; до розв’язання колізій розробили цікаві підходи. Щоб використовувати розсіяну таблицю, програміст має взяти два майже незалежних рішення: він має вибрати хеш-функцию h (K) і метод дозволу колізій. Ці дві аспекти завдання пошуку ми бачимо розглянемо почергово.

Хеш-функции. Для визначеності будемо думати, що хеш-функция h (K) має більш M різних значень і що ці значення задовольняють умові.

0? h (K) h (K) обчислюється так.

rX? K.

rA? 0 (3).

rA? K mod 1009.

Мультипликативную схему хеширования також легко реалізувати, але трохи важче описати, оскільки потрібно надати, що ми з дробами, а чи не з цілими числами. Нехай w є розмір машинного слова; ціла кількість A можна як дріб A/w, якщо подумки поставити десяткову (чи двійкову) точку зліва машинного слова, у якому записано A. Метод у тому, аби вибрати A взаємно простим з w і покласти.

h (K)=[M (((A/w)K) mod 1)]. (4).

В двоичной системі M зазвичай беруть рівним ступеня двійки, отже h (K) складається з старших бітов правої значущою половини твори AK. У двоичном вигляді при M=2m мультипликативная хеш-функция обчислюється так:

rA ?K.

rAX ?AK. (5).

rAX? AK mod w.

Сдвиг rAX на m бітов вліво.

Результат виходить в регістрі A.

Один із привабливих чорт мультипликативной схеми у тому, що у (5) немає втрати інформації; ми могли знову знайти K, знаючи лише вміст rAX після виконання інструкцій (5). Річ у тім, що A взаємно просто з w, і з допомогою алгоритму Евкліда можна знайти Константу A ": AA «mod w = 1; це означає, що K=(A «(AK mod w)) mod w. Інакше кажучи,.

K1? K2 тягне f (K1)? f (K2). (6).

Конечно, f (K)принимает значення діапазоні від 0 до w-1 не є скільки-небудь підходящої хеш-функцией, але вона може бути дуже корисною як рассеивающей функції, саме функції, задовольняє (6) і звичайно що призводить до рандомизации ключів.

Хороша хеш-функция має відповідати двом вимогам:

a)ее обчислення має бути дуже швидким;

b)она повинна мінімізувати число колізій.

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

До цього часу ми розглядали змішування ключів, які з слова. З ключами, які з кількох слів чи мають зміну довжину, можна працювати з представленими з многократной точністю числами і застосувати до них розглянуті методи. Проте зазвичай виявляється достатньої швидша процедура, коли окреме слово спочатку комбінуються за одну, та був виробляється єдине множення чи розподіл. Для комбінування можна використовувати складання по модулю w чи проведення операції «який виключає чи «(на двійкових ЕОМ). Перевагою обох операцій був частиною їхнього оборотність, тобто. їх результат залежить від усіх бітов аргументів, причому «який виключає чи «іноді краще, бо можуть призвести до арифметичному переповненню. Зауважимо, що обидві операції коммутативны, тому ключі (X, Y) і (Y, X) будуть «кинуті «за адресою. Щоб уникнути цього, Г. Д. Кнотт запропонував попередньо робити циклічний зрушення.

Из інших випробуваних методів хеширования, мабуть, найцікавішим є спосіб, заснований на алгебраїчній теорії кодування. Ідея аналогічна методу розподілу, лише замість розподілу на ціла кількість використовується розподіл на багаточлен по модулю 2. Для запропонованого методу M має бути ступенем 2: M=2m; ще, використовується багаточлен m-й ступеня.

P (x)=xm + pm-1 xm-1 + … + p0.

Двоїчний ключ K=(kn-1 … k1 k0)2 можна як багаточлен K (x)=kn-1 xn-1+…+ k1x+ k0, і обчислити залишок.

K (x) mod P (x) = hm-1 xm-1+…+ k1 x+ k0,.

используя полиномиальную арифметику по модулю 2: h (K)=(hm-1… h1 h0)2. При правильному виборі P (x) така хеш-функция дозволяє уникнути колізій, між майже рівними ключами.

Дозвіл колізій методом ланцюжків. Ми згадували, деякі адреси можуть породжуватися кількома ключами. Мабуть, найочевидніший засіб розв’язання проблеми у тому, щоб підтримувати M пов’язаних списків, за одним за кожен можливий хеш-адрес. Усі записи повинні містити поля LINK; ще, треба мати M головних вузлів списків HEAD[i], де і змінюється від 1 до M. Після хеширования.

.

Рис. Роздільні ланцюжка.

ключа просто виконуємо послідовний пошук у списку з номером h (K)+1.

Рисунок ілюструє ця проста метод ланцюжків при M=9 для послідовності семи ключів.

K=|EN|, |TO|, |TRE|, |FIRE|, |FEM|, |SEKS|, |SYV|.

(так називаються числа від 1 до 7 по-норвезьки), мають відповідні хеш-коды.

h (K)+1 = 3, 1, 4, 1, 5, 9, 2.

Первый список містить два елемента, три списку порожні.

Метод ланцюжків є дуже швидким, оскільки списки короткі. Якщо однієї кімнаті зібрати 365 людина, то багато знайдеться пар, що мають одну і того самого дня народження, але цей дня народження загалом має лише одне людина! Взагалі, якщо є N ключів і M списків, середня площа списку дорівнює N/M; в такий спосіб, змішування зменшує кількість роботи, необхідну на послідовний пошук, приблизно M раз.

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

Иногда можна зробити один прохід за даними і з’ясувати, які головні вузли використовуватимуться, вставляючи ось на чому проході «що переповнюють «запис у вільні щілини. Часто, проте, це небажано чи неможливе; нам хотілося хотів би мати метод, у якому кожна запис обробляється лише одне раз, з першого вступі до систему. Наступний алгоритм, приналежний Ф. Уильямсу, є загальновизнаним засобом для вирішення це завдання.

alg C.(Поиск з вставкою по розсіяною таблиці з ланцюжками.) Запропонований алгоритм дозволяє відшукати в таблиці з M елементів даний ключ K.

Если K немає у таблиці вона сповнена, K вставляється у ній. Елементи таблиці позначаються через TABLE[i], 0? i? M, і може бути двох різних типів: вільний і зайнятий. Замотаний вузол містить ключове полі KEY[i], полі посилання LINK[i] і, можливо, інші поля.

Алгоритм використовує хеш-функцию h (K). Для полегшення пошуку вільного простору використовується допоміжна змінна R; якщо таблиця порожня, R=M+1; принаймні проведення вставок залишатиметься у силі твердження, що вузли TABLE|[j] зайняті всім j буде в діапазоні R? j?M.

Домовимося, що вузол TABLE[0] завжди буде вільний.

C1. Хеширование.] Встановити i? h (K)+1. (Тепер 1? i?M.).

C2. Список?] Якщо вузол TABLE[i] вільний, то перейти на C6.

(В іншому разі цей вузол зайнятий, і ми підемо на наявний тут список зайнятих вузлів).

C3. Сравнение.] Якщо K=KEY[i], пошук завершено вдало.

C4. Переход ось до чого.] Якщо LINK[i]?0, встановити i? LINK[i] і повернутися в C3.

C5. Найти вільний вузол.] (Пошук був невдалим, і хочемо знайти у таблиці вільне місце.) Зменшувати R до того часу, поки що не отримано таке значення, що вузол TABLE[R] вільний. Якщо R=0, алгоритм закінчується по переповненню (вільних вузлів більше немає); інакше встановити LINK[i]?R, i? R.

C6. Вставить новий ключ.] Позначити TABLE[i] як зайнятий вузол З KEY[i]?K і LINK[i]?0.

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

.

рис. Поєднані списки.

На погляд крок C5 може бути неефективним, позаяк у ньому пошук вільної позиції виробляється послідовно. Але насправді у процесі заповнення таблиці сумарна кількість проб за крок C5 вбирається у кількості елементів в таблиці; отже, загалом кожну вставку витрачається трохи більше однієї такої проби!

Разрешение колізій «відкритої адресацією ». Інший засіб розв’язання проблеми колізій у тому, аби повністю відмовитися від заслань та просто переглядати одна одною різні елементи таблиці, коли будуть знайдено ключ K чи вільна позиція. Не погано було хотів би мати правило, за яким кожний ключ K визначає послідовність проб, тобто. послідовність позицій в таблиці, потрібно переглядати щоразу при вставці чи пошуку K. Якщо ми, використовуючи котру визначаємо K послідовність проб, наштовхнемося на вільну позицію, можна дійти невтішного висновку, що K немає у таблиці, оскільки той самий послідовність проб виконується щоразу при обробці даного ключа. Цей загальний клас методів У. Петерсон назвав відкритої адресацією.

Простейшая схема відкритої адресації, відома як лінійне.

опробование, використовує циклічну послідовність.

h (K), h (K)-1,…, 0, M-1, M-2,…, h (K)+1 (*).

и описується так.

alg L.(Поиск з вставкою у відкритій розсіяною таблиці.).

Алгоритм дозволяє розшукати даний ключ K в таблиці з M вузлів.

Если K немає у таблиці вона сповнена, ключ K вставляється.

Узлы таблиці позначаються через TABLE[i], 0? i.