Хешування 27

Спеціальне кодування даних (слів, текстів, повідомлень і інш.) за допомогою функцій, алгоритмів і т.д. зветься хешуванням. А відповідні функції (алгоритми) – хеш-функціями (хеш-алгоритмами).

Наприклад, символи (А, Б, В, Г, . . .) можливо закодувати за допомогою хеш-функції – Віжинера: «код довільної букви алфавіту + код фіксованої букви»

Хеш-таблиця

ключ дані

Як правило хеш-таблиця (hash table) має виликі розміри порядку , тому прямі методи пошуку неприйнятні.

У більшості додатків ключ забезпечує непряме посилання на дані. Ключ відображається в множині цілих чисел за допомогою хеш-функції (hash function). Отримане в результаті значення потім використовується для доступу до даних.

Припустимо, є множина записів з цілочисельними ключами. Хеш-функція HF відображає ключ у цілочисельний індекс з діапазону 0…n-l. З хеш-функцією пов'язана хеш-таблиця, осередки якої пронумеровані від 0 до n-1 і зберігають самі дані або посилання на дані.

Наприклад, якщо Key - позитивне ціле, a HF (Key) – значення молодшої цифри числа Key, Тоді діапазон індексів дорівнює 0 – 9.

Наприклад, якщо Key = 49, HF (Key) = HF (49) = 9. Тобто Хеш-функція повертає значення залишку від ділення на 10.