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

Хешування

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

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

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

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

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

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

Парадокс днів народження служить для нас пересторогою, що, ймовірно, знайдуться різні ключі Ki