Введення до хешування
Хешування – перетворення вхідного масиву даних довільної довжини в результуючу послідовність (як правило, фіксованої довжини) таким чином, щоб будь-які зміни вхідних даних приводили до непередбачуваних змін результуючих даних.
Такі перетворення називаються хеш-функціями чи хеш-перетвореннями, а їх результати – хешем, хеш-кодом чи дайджестом повідомлення.
Розрахунок контрольної суми повідомлення – окремий випадок хеш-функції.
Колізії – ситуації, коли для різних вхідних даних формуються однакові хеш-коди. Для якісної функції хешування ймовірність колізій має бути мінімальною.
Хешування використовується у криптографії для перевірки і збереження дайджестів паролів, для пришвидшення операцій пошуку і сортування даних, для контролю на наявність помилок.
10.15. Функції хешування
Алфавітні вказівники, функції розрахунку контрольних кодів є окремими випадками функцій хешування
Поширені функції хешування: CRC, MD2, MD4, MD5, SHA, HAVAL, Whirlpool, ГОСТ Р 34.11-94, Adler-32, N-Hash, RIPEMD-160, Snefru, TTH, PJW-32…
10.16. Проста функція хешування рядків
Розглянемо наступний приклад хешування
Обмеження результуючого діапазону
Проблема – висока ймовірність колізій
Покращення розподілу хеш-кодів
Приклад реалізації функції на C#
10.17. Хеш-таблиці
Якщо хешування використовується для реалізації операції пошуку, то хеш-коди зберігаються у так званих хеш-таблицях, що містять пари хеш-код та значення, для якого він розрахований
Хеш-таблицю можна уявити у вигляді масиву, індекси якої є хеш-кодами, а значення – елементами, для яких здійснюється хешування. Заповнення хеш-таблиці здійснюється шляхом розміщення елементів у місця, яким відповідають певні хеш-коди
В ідеальному варіанті пошук з використанням хеш-таблиці може бути здійснений всього за один крок – для шуканого елементу розраховується хеш-код, за яким з таблиці обирається необхідний елемент, чи визначається його відсутність
Для більшості поширених алгоритмів хешування розмір хеш-таблиці має бути простим числом
Приклад реалізації функції хешування для заповнення хеш-таблиці
10.18. Функції хешування з використанням рандомізації
Рандомізація – процес, який здійснюється над вихідними даними у процесі їх обробки і передбачає, як правило, використання випадкових чисел для формування непередбачуваного результату.
Найпоширеніше застосування рандомізації у криптографії
Рандомізація у хешуванні використовується для скорочення колізій.
PJW-хешування з використанням рандомізації
10.19. Вирішення конфліктів за допомогою лінійного зондування
Лінійне зондування – процес, який дозволяє усувати конфлікти (колізії) за рахунок використання вільних комірок у хеш-таблицях.
Лінійне зондування відноситься до схем з відкритою адресацією.
Алгоритм розміщення елементів у хеш-таблиці з використанням лінійного зондування:
Розрахувати хеш-код елемента і перейти до комірки у таблиці, яка відповідає цьому хеш коду
Якщо комірка вільна, то помістити елемент до неї, у даному разі здійснювати лінійне зондування не потрібно
Якщо комірка зайнята, то необхідно перейти до наступної комірки, доки не буде знайдено вільну комірку. Якщо досягнуто кінець таблиці, то необхідно продовжити пошук вільної комірки з початку до тих пір, доки не буде обійдена вся таблиця. Якщо вільних комірок немає, то припинити роботу і повідомити про помилку. інакше занести елемент до знайденої вільної комірки.
Алгоритм пошуку елементів у хеш-таблиці з використанням лінійного зондування:
Розрахувати хеш-код і перейти до відповідної комірки
10.20. Видалення елементів із хеш-таблиці з лінійним зондуванням
Якщо комірка зайнята, однак елемент шуканому не відповідає, то необхідно переходити до наступного елемента, доки не буде знайдено шуканий елемент, чи не виявиться вільна комірка, чи не буде обійдена вся таблиця (елемент не знайдено)
10.21. Клас хеш-таблиць з лінійним зондуванням
Приклад здійснення лінійного зондування
10.22. Інші схеми відкритої адресації
Існують інші схеми відкритої адресації