зивається методом поділу. На практиці метод поділу використовується в більшості додатків, що працюють з хешуванням.
Приклади хеш-функцій
f (x)=x mod 4 (функція mod повертає залишок від ділення)
Рис. 1
Ще приклад: X - знову цілі невід'ємні числа. Функція f бере першу цифру x. У цьому випадку N=10.
Хешування застосовується для швидкого пошуку в структурах даних і в криптографії. При цьому хеш-функції, хороші для першого, навряд чи гарні для другого застосування, і навпаки. хеш-функції, застосовувані в криптографії, також називаються функціями криптографічного хешування. Як правило, хеш-функції у сфері структур досить прості, функції криптографічного хеширования мають досить складне тіло.
Вимоги до хеш-функцій
Прийнято вважати, що гарною, з точки зору практичного застосування, є така хеш-функція , яка задовольняє таким умовам:
· функція повинна бути простою з обчислювальної точки зору;
· функція повинна розподіляти ключі в хеш-таблиці найбільш рівномірно;
· функція не повинна відображати будь-який зв'язок між значеннями ключів у зв'язок між значеннями адрес;
· функція повинна мінімізувати число колізій - тобто ситуацій, коли різним ключам відповідає одне значення хеш-функції (ключі в цьому випадку називаються синонімами ).
При цьому перша властивість хорошої хеш-функції залежить від характеристик комп'ютера, а другий - від значень даних.
Якби всі дані були випадковими, то хеш-функції були б дуже прості (наприклад, кілька бітів ключа). Однак на практиці випадкові дані зустрічаються досить рідко, і доводиться створювати функцію, яка залежала б від усього ключа. Якщо хеш-функція розподіляє сукупність можливих ключів рівномірно по безлічі індексів, то хеширование ефективно розбиває безліч ключів. Найгірший випадок - коли всі ключі хешіруются в один індекс.
Хеш-таблиці
Наприклад у нас є база рядків причому рядки довгі і їх багато.
Тобто ми маємо велику базу цих рядків.
Щоб знайти певний рядок порівнювати з усіма рядками в базі досить довго.
Для прискорення пошуку використовують хеширование рядків.
Адже числові значення порівнюються набагато швидше, ніж рядкові.
Тому ми кожному рядку зіставимо числове значення і будемо шукати саме по ньому. Така таблиця називається хеш-таблицею.
Дозвіл колізій
Незважаючи на те, що два або більше ключів можуть хешировані однаково, вони не можуть займати в хеш-таблиці одну і ту ж комірку. Нам залишаються два шляхи: або знайти для нового ключа іншу позицію в таблиці, або створити для кожного значення хеш-функції окремий список, в якому будуть всі ключі, які відображаються при хешуванні в це значення. Обидва варіан...
