Хеш-функції

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

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