Хешування

До цих пір ми розглядали методи пошуку, засновані на порівнянніцього аргументу 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

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

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

rA