Перелік усіх робіт

Алгоритми хешування

Мета роботи

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

Обладнання

Персональний комп’ютер, IDE Microsoft Visual Studio або інша середа розробки для мови C++.

Теоретичні відомості

Хешування — це процес перетворення вхідних даних довільної довжини у фіксоване значення (хеш-код).
Хеш-функції широко застосовуються для зберігання паролів, перевірки цілісності даних, пошуку та індексації.

Властивості гарної хеш-функції

• Детермінованість — однаковий вхід → однаковий вихід.
• Рівномірність — результати рівномірно розподілені у просторі хешів.
• Стійкість до колізій — малоймовірно, що два різні входи матимуть однаковий хеш.
• Неможливість відновлення — з хешу неможливо відновити початкові дані.

Основні типи хеш-функцій

1. Прості числові хеші (mod-hash)
   Використовують операції додавання, множення та модуль.
   Приклад:
   hash = (a * x + b) mod m

2. Поліноміальний хеш (Rolling Hash)
   Використовується у пошуку підрядків (наприклад, алгоритм Рабіна–Карпа):
   hash = s₀·p⁰ + s₁·p¹ + s₂·p² + ...

3. Криптографічні хеші (MD5, SHA-1, SHA-256)
   Стійкі до колізій, використовуються у безпеці та перевірці цілісності.

4. Комбіновані хеші (Murmur, CityHash)
   Використовуються у великих системах і базах даних для швидкої індексації.

Порівняння алгоритмів

Алгоритм	Швидкість	Стійкість до колізій	Використання
Простий mod-hash	Висока	Низька	Таблиці, навчальні приклади
Поліноміальний	Висока	Середня	Пошук у тексті
MD5	Середня	Низька	Перевірка цілісності
SHA-1	Середня	Середня	Старі системи
SHA-256	Низька	Висока	Безпека, криптографія

Хід роботи

1. Створити новий консольний проєкт C++ у Visual Studio.
2. Реалізувати три типи хешування:
   • простий числовий хеш;
   • поліноміальний хеш (Rolling Hash);
   • криптографічний SHA-256.
3. Реалізувати функцію порівняння хешів.
4. Додати функцію перевірки колізій для набору рядків.
5. Вивести результати у форматі:

input: Hello world
simple hash: 4512
rolling hash: 128947123
sha256: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
time: 0.00073 s

1. Провести експеримент із кількома різними рядками.
2. Побудувати таблицю результатів (час виконання, кількість колізій).
3. Реалізувати класи Hasher, SimpleHasher, RollingHasher, SHA256Hasher, Timer.
4. Зробити висновки про ефективність і стійкість алгоритмів.

Контрольні запитання

1. Що таке хеш-функція?
2. Які властивості має гарна хеш-функція?
3. У чому полягає відмінність між криптографічними та некриптографічними хешами?
4. Як обчислюється поліноміальний хеш?
5. Що таке колізія і як її можна зменшити?
6. У яких галузях застосовуються хеш-функції?
7. Чому SHA-256 вважається безпечним?
8. Які операції найчастіше використовуються в хешуванні?
9. Як перевірити рівномірність розподілу хешів?
10. Чому не можна використовувати MD5 для безпеки?

Приклади

1. Простий числовий хеш C++
2. Поліноміальний хеш C++
3. SHA-256 через бібліотеку C++
4. Вимірювання часу роботи C++

Додаткові матеріали

1. Hash Functions (Wikipedia)
2. SHA-256 Explained (GeeksforGeeks)
3. Rabin–Karp Algorithm and Rolling Hash