Хешовані таблиці та функції хешування

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

r = H(k),

де: r – адреса запису, k – ключ.

Така функція H називається функцією хешування (інші її назви – функція перемішування, функція рандомізації). В нашому випадку дані організовані в пам’яті як массив. Тому дія H– функції полягає в перетворенні ключів в індекси масиву. Звідси ще одна назва методу – перетворення ключів.

При спробі відображення точок з деякого широкого простору у вузьке неминучі ситуації, коли різні точки у вихідному просторі відобразяться в ту саму точку в цільовому просторі (див. рис. 5.3). Ситуація, при якій різні ключі відображаються в ту саму адресу запису, називається колізією чи переповненням, а такі ключі називаються синонімами.

Якщо функція H, що перетворює ключ на адресу, може породжувати колізії, то однозначної зворотної функції:

k = H'(r),

яка дозволяє відновити ключ за відомою адресою, існувати не може. Тому ключ повинен обов'язково входити до складу запису хешованої таблиці як один з її полів.

Рис. 5.3. Колізія. Точки А, В, С відображаються в точку О

До функції хешування в загальному випадку пред'являються наступні вимоги:

– повинна забезпечувати рівномірний розподіл відображень фактичних ключів за простором записів;

– повинна породжувати якнайменше колізій для даної фактичної множини записів;

– не повинна відображати будь-який зв'язок між значеннями ключів у зв'язок між значеннями адрес;

– повинна бути простою і швидкою для обчислення.

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

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

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

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

Функція перетворення системи обчислення. Ключ, записаний як число в деякій системі обчислення P, інтерпретується як число в системі обчислення Q, причому Q>P. Частіше вибирають Q=P+1. Це число переводиться із системи Q назад у систему P, приводиться до розміру простору записів і інтерпретується як адреса.