Хеш-функція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Хеш-функція — функція, що перетворює вхідні дані будь-якого (як правило, великого) розміру в дані фіксованого розміру. Хешування (іноді гешування, англ. hashing) — перетворення вхідного масиву даних довільної довжини у вихідний бітовий рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями або функціями згортки, а їх результати називають хешем, хеш-кодом або дайджестом повідомлення (англ. message digest).

Опис[ред.ред. код]

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

  • стійкість до колізій (два різні набори даних повинні мати різні результати перетворення);
  • необоротність (неможливість обчислити вхідні дані за результатом перетворення).

Прискорення пошуку даних[ред.ред. код]

Докладніше: Хеш-таблиця

Хеш-функції також використовуються в деяких структурах даних — хеш-таблицях і декартових деревах. Вимоги до хеш-функції в цьому разі інші:

  • добра перемішуваність даних;
  • швидкий алгоритм обчислення.

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

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

Список алгоритмів[ред.ред. код]




Комп'ютер Це незавершена стаття про комп'ютери.
Ви можете допомогти проекту, виправивши або дописавши її.