Хеш-функція
Хеш-функція — функція, що перетворює вхідні дані будь-якого (як правило, великого) розміру в дані фіксованого розміру. Хешування (іноді гешування, англ. hashing) — перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями або функціями згортки, а їх результати називають хешем, хеш-кодом або дайджестом повідомлення (англ. message digest). Хешування застосовується для порівняння даних: якщо у двох масивів хеш-коди різні, масиви гарантовано розрізняються; якщо однакові - масиви, швидше за все, однакові. У загальному випадку однозначної відповідності між вихідними даними і хеш-кодом немає в силу того, що кількість значень хеш-функцій менше, ніж варіантів вхідного масиву; існує безліч масивів, що дають однакові хеш-коди - так звані колізії. Ймовірність виникнення колізій відіграє важливу роль в оцінці якості хеш-функцій. Існує безліч алгоритмів хешування з різними характеристиками (розрядність, обчислювальна складність, крипостійкість тощо). Вибір тієї чи іншої хеш-функції визначається специфікою розв'язуваної задачі. Найпростішими прикладами хеш-функцій можуть служити контрольна сума або CRC.
Криптографічна хеш-функція повинна забезпечувати:
- стійкість до колізій (два різні набори даних повинні мати різні результати перетворення);
- необоротність (неможливість обчислити вхідні дані за результатом перетворення).
Прискорення пошуку даних [ред.]
Хеш-функції також використовуються в деяких структурах даних — хеш-таблицях і декартових деревах. Вимоги до хеш-функції в цьому разі інші:
- добра перемішуваність даних;
- швидкий алгоритм обчислення.
Наприклад, під час запису текстових полів в базі даних може розраховуватися їх хеш-код і дані можуть поміщатися в розділ, що відповідає цьому хеш-коду. Тоді при пошуку даних треба буде спочатку обчислити хеш-код тексту і відразу стане відомо, в якому розділі їх треба шукати, тобто, шукати треба буде не по всій базі, а тільки по одному її розділу (це сильно прискорює пошук).
Побутовим аналогом хешування в даному випадку може служити розміщення слів у словнику за алфавітом. Перша буква слова є його хеш-кодом, і при пошуку ми переглядаємо не весь словник, а тільки потрібну букву.
Список алгоритмів [ред.]
 |
Ця стаття не містить посилань на джерела. (квітень 2008) |
|
|
|||||
 |
Це незавершена стаття про комп'ютери. Ви можете допомогти проекту, виправивши або дописавши її. |
