Упражнения: Hash Таблици и Криптографски Hash Функции

Напредък

0%

✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

---

ℹ️Информация за упражненията

Този набор от упражнения покрива:

• Криптографски hash функции и техните свойства
• Приложения на hash функции в реалния свят
• Hash таблици и collision resolution strategies
• Имплементация на hash таблици в C++
• Performance анализ и оптимизация

Общо упражнения: 20 задачи в 5 нива на сложност

---

Лесни упражнения (EASY)

Фундаментални концепции и базови разбирания

Упражнение

ЛЕСНО

Задача 1: Приложения на Hash Функции

Задача: Изброете три ежедневни ситуации, където се използват hash функции. За всяка, обяснете дали използва криптографски или некриптографски hashing и защо.

Помислете за:

• Логване в уебсайтове
• Изтегляне на файлове/софтуер
• Търсене в контакти или речник

Примерен отговор:

1. Логване в уебсайт (напр. Gmail)

   • Тип: Криптографски hash (SHA-256)
   • Защо: Необходима е сигурност - паролите трябва да бъдат необратими. Ако базата данни бъде компрометирана, атакуващи не трябва да могат да възстановят паролите.

2. Изтегляне на Ubuntu ISO

   • Тип: Криптографски hash (SHA-256)
   • Защо: Трябва да се гарантира интегритет на данните. Дори един променен бит ще доведе до различен hash, което показва корупция или tamper.

3. Търсене в телефонен указател (contacts app)

   • Тип: Некриптографски hash (просто modulo или polynomial rolling)
   • Защо: Целта е скорост, не сигурност. Hash таблицата трябва бързо да картографира име към entry, така че се използва прост, бърз hash.

Ключова разлика:

• Криптографски: Приоритет на сигурност, интегритет
• Некриптографски: Приоритет на скорост, ефективност

Упражнение

ЛЕСНО

Задача 2: Hash Function Properties - Multiple Choice

Въпрос: Коя от следните свойства гарантира, че същият вход винаги произвежда същия hash output?

• A) Устойчивост на колизии (Collision resistance)
• B) Детерминизъм (Deterministic)
• C) Avalanche effect
• D) Pre-image resistance

Отговор: B) Детерминизъм (Deterministic)

Обяснение:

• Deterministic означава, че hash функцията винаги дава същия резултат за същия вход:

  hash("password") → "abc123..." // Винаги същото!
  hash("password") → "abc123..." // Пак същото!

Защо другите отговори са грешни:

• A) Collision resistance: Трудно е да се намерят два различни входа със същия hash
• C) Avalanche effect: Малка промяна във входа води до радикално различен изход
• D) Pre-image resistance: Даден hash, невъзможно е да се намери оригиналният вход

Упражнение

ЛЕСНО

Задача 3: Времева Сложност на Hash Таблици

Въпрос: Каква е идеалната времева сложност за търсене в hash таблица?

• A) O(n²)
• B) O(n log n)
• C) O(n)
• D) O(1)

Отговор: D) O(1)

Обяснение:

Hash таблиците са проектирани да осигуряват константна средна сложност O(1) за:

• Search (търсене)
• Insert (вмъкване)
• Delete (изтриване)

Как работи O(1)?

1. Hash функцията изчислява index: index = hash(key) % capacity
2. Директен достъп до масива: table[index]
3. Ако няма колизия → O(1)!

Важно:

• Average case: O(1) с добра hash функция и нисък load factor
• Worst case: O(n) ако всички елементи колидират в един slot (много лоша hash функция!)

Сравнение:

Структура	Average Search	Worst Case Search
Array (unsorted)	O(n)	O(n)
Array (sorted)	O(log n)	O(log n)
Binary Search Tree	O(log n)	O(n)
Hash Table	O(1)	O(n)

Упражнение

ЛЕСНО

Задача 4: Load Factor Calculation

Задача: Hash таблица има 100 slots и съдържа 75 елемента. Изчислете load factor. Счита ли се за висок, нисък или умерен?

Load Factor = (Брой елементи) / (Брой slots)

Обмислете:

• Load factor < 0.5 → нисък
• Load factor 0.5-0.75 → умерен (оптимален)
• Load factor > 0.75 → висок

Изчисление:

Load Factor (α) = n / m

където:
- n = брой елементи = 75
- m = брой slots (capacity) = 100

α = 75 / 100 = 0.75

Оценка: УМЕРЕН/ВИСОКО (на границата)

Обяснение:

• 0.75 е критичната точка за повечето hash таблици
• Много имплементации (Java HashMap, C++ unordered_map) resize-ват при α = 0.75
• Над 0.75 → по-много колизии → по-бавни операции

Препоръка за тази таблица:

• Ако се очаква да се добавят още елементи → resize сега!
• Resize обикновено удвоява capacity: 100 → 200
• Нов load factor след resize: 75/200 = 0.375 (отличен!)

При различни strategies:

• Separate Chaining: може да работи добре дори при α > 1.0
• Linear Probing: започва да се забавя при α > 0.7
• Quadratic Probing: обикновено resize при α ≈ 0.7-0.75

Упражнение

ЛЕСНО

Задача 5: Идентифициране на Hash Алгоритми

Задача: Съпоставете всеки hash алгоритъм със съответния му статус на сигурност:

Алгоритми:

1. MD5
2. SHA-256
3. SHA-1
4. SHA-3

Опции:

• A) Компрометиран - НЕ използвайте
• B) Силен - широко използван
• C) Силен - най-нов стандарт

Отговори:

1. MD5 → A) Компрометиран - НЕ използвайте
2. SHA-256 → B) Силен - широко използван
3. SHA-1 → A) Компрометиран - НЕ използвайте
4. SHA-3 → C) Силен - най-нов стандарт

Обяснение:

Алгоритъм	Размер	Статус	Забележки
MD5	128 бита	❌ Компрометиран	Collision attacks demonstrated in 2004
SHA-1	160 бита	❌ Компрометиран	Google collision attack in 2017
SHA-256	256 бита	✅ Силен	Bitcoin, SSL/TLS, широко използван
SHA-3	224-512 бита	✅ Силен	NIST стандарт от 2015, различна от SHA-2

Защо MD5 и SHA-1 са компрометирани?

• Атакуващи могат да намерят колизии (два различни входа със същия hash)
• Праг на сигурност е прекрачен чрез birthday attacks
• НЕ използвайте за:
  • Съхранение на пароли
  • Цифрови подписи
  • Сертификати

Кога е ОК да използваш MD5/SHA-1?

• Non-security checksums (напр., file integrity в локална система)
• Git commit IDs (SHA-1) - приемливо защото context е различен

Best Practice:

• Нови проекти: Използвай SHA-256 или SHA-3
• Legacy системи: Мигрирай от MD5/SHA-1 колкото е възможно по-скоро

---

Лесни-Средни упражнения (EASY-MEDIUM)

Изграждане на разбиране и приложение на концепциите

Упражнение

ЛЕСНО-СРЕДНО

Задача 6: Simple Hash Function Computation

Задача: Дадена е hash функцията h(x) = x % 11, изчислете hash стойностите за следните ключове: 23, 45, 67, 89. Кои ключове ще колидират?

Изчислете всеки hash:

• h(23) = ?
• h(45) = ?
• h(67) = ?
• h(89) = ?

Колизия възниква когато два различни ключа имат същия hash.

Изчисления:

h(23) = 23 % 11 = 1
h(45) = 45 % 11 = 1  // КОЛИЗИЯ с 23!
h(67) = 67 % 11 = 1  // КОЛИЗИЯ с 23 и 45!
h(89) = 89 % 11 = 1  // КОЛИЗИЯ с 23, 45, 67!

Резултат:

• 23 → hash = 1
• 45 → hash = 1
• 67 → hash = 1
• 89 → hash = 1

Всички четири ключа колидират! 😱

Защо?

Всички ключове имат остатък 1 при деление на 11:

23 = 2 × 11 + 1
45 = 4 × 11 + 1
67 = 6 × 11 + 1
89 = 8 × 11 + 1

Последици:

В hash таблица с capacity 11:

• Separate Chaining: Всички 4 елемента ще са в chain на index 1

  [0] → null
  [1] → [23] → [45] → [67] → [89] → null  // Long chain!
  [2] → null
  ...

• Linear Probing: Елементите ще се разпределят последователно

  [0] → _
  [1] → 23
  [2] → 45  // Probed from 1
  [3] → 67  // Probed from 1
  [4] → 89  // Probed from 1
  ...

Урок: Дори прости modulo hash функции могат да доведат до много колизии при неблагоприятни входни данни!

Упражнение

ЛЕСНО-СРЕДНО

Задача 7: Avalanche Effect Demonstration

Задача: Обяснете защо промяната на "password" на "Password" (главна буква на първия символ) трябва да произведе напълно различен hash в криптографска hash функция. Коя свойство демонстрира това?

Помислете за:

• Каква е разликата между двата входа?
• Как трябва да се променят bit-овете в hash-а?
• Коя криптографска свойство описва това поведение?

Отговор: Avalanche Effect (Лавинен Ефект)

Дефиниция: Avalanche Effect е свойство на криптографски hash функции, при което малка промяна във входа (дори един бит!) води до голяма, непредвидима промяна в изхода.

Пример с SHA-256:

$ echo -n "password" | sha256sum
5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8

$ echo -n "Password" | sha256sum
e7cf3ef4f17c3999a94f2c6f612e8a888e5b1026878e4e19398b23bd38ec221a

Анализ:

• Вход: Променен само първият символ (p → P)
• Разлика: Само един бит в ASCII (p = 01110000, P = 01010000)
• Изход: Напълно различни hash-ове (различават се в ~50% от битовете!)

Защо е важно?

1. Сигурност срещу pattern analysis:

   • Атакуващи не могат да предскажат промени в hash-а
   • Малки вариации на пароли дават напълно различни hash-ове

2. Password security:

   "password123" → hash1
   "password124" → hash2 (напълно различно!)

   Атакуващи не могат да използват близки hash-ове за да намерят близки пароли

3. Integrity checking:

   • Дори един променен байт във файл се открива веднага
   • Hash-ът се променя драстично

Противоположен пример (лоша hash функция):

// ❌ ЛОША hash функция - няма avalanche effect
int bad_hash(string s) {
    return s[0];  // Само първият символ!
}

bad_hash("password") = 'p' = 112
bad_hash("Password") = 'P' = 80
// Разликата е предвидима и малка!

Заключение:

Avalanche Effect е критична защита срещу:

• Differential cryptanalysis
• Pattern recognition attacks
• Brute force optimization

Упражнение

ЛЕСНО-СРЕДНО

Задача 8: Password Storage Scenario

Задача: Уебсайт съхранява потребителски пароли по следните начини:

• Option A: Plaintext пароли в база данни
• Option B: Hash на паролите в база данни
• Option C: Hash(password + salt) в база данни

Подредете опциите от най-малко до най-много сигурни и обяснете защо Option C е superior на Option B.

Помислете за:

• Какво се случва при data breach?
• Могат ли атакуващи да възстановят паролите?
• Какво са rainbow tables?
• Как salt помага?

Подредба от най-малко до най-много сигурни:

A (Plaintext) < B (Hash) < C (Hash + Salt)

---

Задача 9: Option A: Plaintext Storage ❌❌❌

Най-малко сигурно!

CREATE TABLE users (
    username VARCHAR(50),
    password VARCHAR(50)  -- "MyPassword123"
);

При breach:

• ✅ Атакуващи веднага виждат всички пароли
• ✅ Могат да се логнат като всеки потребител
• ✅ Ако потребители използват същата парола на други сайтове → breach на множество акаунти

Никога не правете това!

---

Задача 10: Option B: Hashed Passwords ⚠️

По-добро, но уязвимо на rainbow tables!

CREATE TABLE users (
    username VARCHAR(50),
    password_hash VARCHAR(64)  -- SHA-256 hash
);

-- Пример:
-- password "password123" → hash "ef92b778..."

При breach:

• ✅ Атакуващи не виждат директно паролите
• ❌ НО: Могат да използват rainbow tables

Какво е Rainbow Table?

Предварително изчислена таблица: hash → password

ef92b778... → "password123"
5e884898... → "password"
e7cf3ef4... → "Password"
...

Атака:

1. Атакуващ изтегля rainbow table (напр., 100GB с милиарди hash-ове)
2. За всеки hash от breach-а, търси в rainbow table
3. Мигновено намира паролата, ако е в таблицата!

Резултат: Популярни пароли се разбиват веднага

---

Задача 11: Option C: Hashed with Salt ✅✅✅

Най-сигурно!

CREATE TABLE users (
    username VARCHAR(50),
    password_hash VARCHAR(64),
    salt VARCHAR(32)  -- Random salt за ВСЕКИ потребител
);

Как работи:

// Регистрация:
string password = "password123";
string salt = generate_random_salt();  // "a3f9d2..."
string hash = sha256(password + salt);

// Съхрани: hash, salt (НЕ паролата!)

// Login:
string input_password = "password123";
string stored_salt = get_salt_from_db(username);
string computed_hash = sha256(input_password + stored_salt);

if (computed_hash == stored_hash) {
    login_success();
}

Пример:

User	Password	Salt	Hash (SHA-256)
Alice	password123	a3f9	hash("password123a3f9") = xyz1...
Bob	password123	7b2c	hash("password1237b2c") = abc2...

Забележка: Alice и Bob имат същата парола, но различни hash-ове! 🎉

Защо това побеждава rainbow tables?

Rainbow tables съдържат hash-ове за популярни пароли:

hash("password123") = "ef92b778..."
hash("admin") = "abc123..."

Но те НЕ съдържат:

hash("password123a3f9") = ???
hash("password1237b2c") = ???

За всяка парола + salt комбинация, атакуващият трябва да изчисли нова rainbow table → невъзможно за уникални salts!

---

Задача 12: Защо Option C > Option B:

Критерий	Option B (Hash)	Option C (Hash + Salt)
Rainbow table атака	❌ Уязвим	✅ Защитен
Dictionary атака	❌ Бърза	⚠️ Бавна (трябва да hash всеки опит със salt)
Защита на идентични пароли	❌ Същия hash	✅ Различни hash-ове
Storage overhead	Малко	Малко повече (salt)

Best Practice:

• Използвай SHA-256 или bcrypt (по-добре!)
• Salt трябва да е random и уникален за всеки user
• Salt може да се съхранява plaintext (не е таен)
• Понякога се добавя и pepper (глобална тайна за целия сайт)

---

Средни упражнения (MEDIUM)

Приложение и анализ на концепциите

Упражнение

СРЕДНО

Задача 13: Collision Resolution Strategy Selection

Задача: Проектирате hash таблица за spell-checker, който ще съхранява 50,000 английски думи. Таблицата има 60,013 slots (просто число).

1. Изчислете очаквания load factor
2. Препоръчахте ли separate chaining или linear probing?
3. Обосновете отговора си с поне три конкретни причини

Помислете за:

• Load factor = n / m
• Какви операции ще се извършват често?
• Frequency на deletion операции?
• Trade-offs между memory и speed?

Задача 14: 1. Изчисление на Load Factor:

α = n / m

където:
- n = 50,000 думи
- m = 60,013 slots

α = 50,000 / 60,013 ≈ 0.833

Load Factor: α ≈ 0.83

---

Задача 15: 2. Препоръка: SEPARATE CHAINING 🔗

---

Задача 16: 3. Обосновка (3+ причини):

Причина 1: Load Factor е Висок (0.83)

• Linear Probing започва да се забавя драстично при α > 0.7
• При α = 0.83:
  • Expected probes per search (Linear): ~5.5 проверки
  • Expected chain length (Chaining): ~0.83 елемента

Separate Chaining работи добре дори при α > 1.0!

Separate Chaining: O(1 + α) = O(1 + 0.83) ≈ O(1.83) → още бързо!
Linear Probing: O(1/(1-α)) = O(1/0.17) ≈ O(5.9) → значително по-бавно!

Причина 2: Spell-checker има СТАТИЧЕН Речник

• Думите се зареждат веднъж при стартиране
• НЕ се очакват чести вмъквания или изтривания по време на работа
• Операции:
  • Load: Еднократно (може да е бавна, не е критична)
  • Lookup: Много често (трябва да е бърза!)
  • Insert/Delete: Рядко или никога

Separate Chaining:

• ✅ Lookup е винаги бърз (O(1 + α))
• ✅ Не се нуждае от tombstones (deletion е лесна, ако е нужна)

Linear Probing:

• ❌ Clustering се натрупва при load
• ❌ Deletion изисква tombstones → усложнява кода

Причина 3: Memory Overhead е Приемлив

За 50,000 думи:

Linear Probing:

struct Entry {
    string word;      // ~24 bytes (pointer + size)
    bool occupied;    // 1 byte
    bool deleted;     // 1 byte (tombstone)
};
// Total per slot: ~26 bytes
// Total: 60,013 × 26 ≈ 1.56 MB

Separate Chaining:

struct Node {
    string word;   // ~24 bytes
    Node* next;    // 8 bytes
};
// Total per element: ~32 bytes
// Total: 50,000 × 32 ≈ 1.6 MB

Разлика: ~40 KB (пренебрежимо!)

За съвременна система, 40 KB е нищо → Memory overhead не е проблем

Бонус Причина 4: Робастност към Лоша Hash Функция

Ако hash функцията за strings не е перфектна (напр., много anagrams):

• Separate Chaining: Просто по-дълги chain-ове, но все още работи
• Linear Probing: Clustering експлодира → огромни probe sequences

Бонус Причина 5: Predictable Performance

• Separate Chaining: Винаги O(1 + α) → предвидимо
• Linear Probing: Може да има outliers (дълги probe sequences) → unpredictable

---

Задача 17: Заключение:

Избери SEPARATE CHAINING защото:

1. ✅ Load factor (0.83) е над оптималното за linear probing
2. ✅ Spell-checker е lookup-intensive (няма чести deletions)
3. ✅ Memory overhead е пренебрежимо малко
4. ✅ По-robustна и предвидима производителност

Имплементация:

class SpellChecker {
private:
    vector<list<string>> table;  // Separate chaining
    int capacity = 60013;        // Prime number

    int hash(const string& word) {
        // Polynomial rolling hash
        int h = 0;
        for (char c : word) {
            h = (h * 31 + tolower(c)) % capacity;
        }
        return h;
    }

public:
    SpellChecker() {
        table.resize(capacity);
    }

    bool is_word(const string& word) {
        int idx = hash(word);
        for (const auto& w : table[idx]) {
            if (w == word) return true;
        }
        return false;
    }

    void load_dictionary(const vector<string>& words) {
        for (const auto& word : words) {
            int idx = hash(word);
            table[idx].push_back(word);
        }
    }
};

Упражнение

СРЕДНО

Задача 18: Linear Probing Trace

Задача: Дадена е hash таблица с размер 7, използваща linear probing с h(x) = x % 7. Вмъкнете следните ключове в този ред: 10, 22, 31, 4, 15, 28, 17.

1. Покажете състоянието на таблицата след всяко вмъкване
2. Идентифицирайте къде възникват колизии и как се разрешават

Linear probing formula:

index = (hash(key) + probe) % table_size

където probe = 0, 1, 2, 3, ...

Ако slot е зает, опитай следващия (с wrap-around).

Задача 19: Step-by-Step Insertion:

Начално състояние:

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value:  _    _    _    _    _    _    _

---

1. Insert 10

h(10) = 10 % 7 = 3

Slot 3 е свободен → insert directly

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value:  _    _    _   [10]  _    _    _

---

2. Insert 22

h(22) = 22 % 7 = 1

Slot 1 е свободен → insert directly

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value:  _   [22]  _   [10]  _    _    _

---

3. Insert 31

h(31) = 31 % 7 = 3

КОЛИЗИЯ! Slot 3 е зает (10)

Linear probing:

• Try slot 3: occupied (10)
• Try slot 4: FREE → insert here

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value:  _   [22]  _   [10] [31]  _    _

Probe count: 1

---

4. Insert 4

h(4) = 4 % 7 = 4

КОЛИЗИЯ! Slot 4 е зает (31)

Linear probing:

• Try slot 4: occupied (31)
• Try slot 5: FREE → insert here

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value:  _   [22]  _   [10] [31] [4]   _

Probe count: 1

---

5. Insert 15

h(15) = 15 % 7 = 1

КОЛИЗИЯ! Slot 1 е зает (22)

Linear probing:

• Try slot 1: occupied (22)
• Try slot 2: FREE → insert here

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value:  _   [22] [15] [10] [31] [4]   _

Probe count: 1

---

6. Insert 28

h(28) = 28 % 7 = 0

Slot 0 е свободен → insert directly

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value: [28] [22] [15] [10] [31] [4]   _

---

7. Insert 17

h(17) = 17 % 7 = 3

КОЛИЗИЯ! Slot 3 е зает (10)

Linear probing:

• Try slot 3: occupied (10)
• Try slot 4: occupied (31)
• Try slot 5: occupied (4)
• Try slot 6: FREE → insert here

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value: [28] [22] [15] [10] [31] [4]  [17]

Probe count: 3 (най-дългата!)

---

Задача 20: Final State:

Index: [0]  [1]  [2]  [3]  [4]  [5]  [6]
Value: [28] [22] [15] [10] [31] [4]  [17]
       h=0  h=1  h=1  h=3  h=3  h=4  h=3

---

Задача 21: Collision Summary:

Key	Hash (h(x))	Collision?	Final Index	Probes
10	3	❌ No	3	0
22	1	❌ No	1	0
31	3	✅ Yes (10)	4	1
4	4	✅ Yes (31)	5	1
15	1	✅ Yes (22)	2	1
28	0	❌ No	0	0
17	3	✅ Yes (10, 31, 4)	6	3

Общо колизии: 4 / 7 insertions (57%!)

---

Задача 22: Забележки:

1. Clustering: Виждаме образуване на cluster от index 3-5 (три consecutive occupied slots)

2. Probe sequences:

   • 31: проба 1 slot
   • 4: проба 1 slot
   • 15: проба 1 slot
   • 17: проба 3 slots (най-дълга!)

3. Load Factor:

   α = 7 / 7 = 1.0 (ПЪЛНА ТАБЛИЦА!)

   Следващото вмъкване би fail-нало или би изисквало resize!

4. Performance degradation:

   • Expected probes за search (Linear Probing at α=1.0): ∞ (безкрайно!)
   • Това е защо при α > 0.7-0.75, таблицата трябва да се resize

---

(Продължава във втората част...)

Упражнение

СРЕДНО

Задача 23: Birthday Paradox Application

Задача: Hash функция произвежда 64-битов изход. Приблизително колко hash изчисления биха били нужни преди да има 50% вероятност за намиране на колизия? Обяснете разсъжденията си използвайки birthday paradox принципа.

Birthday Paradox формула:

Приблизително 2^(n/2) операции за 50% вероятност за колизия

където n = брой битове в изхода

Задача 24: Birthday Paradox за Hash Функции:

Формула:

За hash функция с n-битов изход, очакваният брой hash изчисления за 50% вероятност за колизия е приблизително:

≈ 2^(n/2)

---

Задача 25: Изчисление за 64-битов изход:

n = 64 бита

Очакван брой hash-ове ≈ 2^(64/2) = 2^32

2^32 = 4,294,967,296 (около 4.3 милиарда)

---

Задача 26: Защо 2^(n/2)?

Birthday Paradox обяснение:

Въпросът: "Колко души трябва да има в стая за да има 50% вероятност двама от тях да имат същия рожден ден?"

Отговор: Само 23 души!

• Възможни рождени дни: 365
• √365 ≈ 19.1 → около 23 души

Интуиция:

• Първият човек: 365 свободни дни
• Вторият човек: 364 свободни дни
• Третият човек: 363 свободни дни
• ...
• Вероятността за collision расте квадратично!

За hash функции:

• Възможни hash стойности: 2^n
• √(2^n) = 2^(n/2)

---

Задача 27: Примери:

Битове (n)	Възможни стойности (2^n)	Колизия при (~2^(n/2))
16 бита	65,536	~256 hash-a
32 бита	4.3 billion	~65,536 hash-a
64 бита	18 quintillion	~4.3 billion hash-a
128 бита	340 undecillion	~18 billion billion hash-a
256 бита	Огромно	~3.4 × 10^38 hash-a

---

Задача 28: Практическо Значение за 64-битов Hash:

Колко време за 4.3 милиарда hash-а?

Допуснете компютър, който изчислява 1 милион hash-а в секунда:

4,294,967,296 hashes / 1,000,000 hashes/sec ≈ 4,295 seconds ≈ 72 минути

С модерна GPU (1 милиард hash/sec):

4.3 billion / 1 billion ≈ 4.3 секунди!

Заключение: 64-битов hash НЕ е достатъчно сигурен за криптография!

---

Задача 29: Защо SHA-256 (256 бита)?

2^(256/2) = 2^128 ≈ 3.4 × 10^38 hash-a

Дори с всички компютри на света, това би отнело милиарди години!

---

Задача 30: Резюме:

Hash Функция	Битове	Колизия при	Време (1 billion hash/sec)
CRC32	32	2^16 = 65K	< 1 милисекунда
64-bit hash	64	2^32 = 4.3B	~4 секунди
SHA-1	160	2^80	~38 милиона години
SHA-256	256	2^128	~10^22 години

Best Practice:

• Не използвай <128 бита за криптография
• SHA-256 или SHA-3 са безопасни

Упражнение

СРЕДНО

Задача 31: Hash Function Design for Strings

Задача: Проектирайте hash функция за strings, която е подходяща за hash таблица (не криптографска). Функцията трябва да:

• Процесира всеки символ
• Произвежда reasonably uniform разпределение
• Бъде ефективна за изчисляване

Напишете pseudocode и обяснете защо направихте тези дизайн избори.

Помислете за:

• Polynomial rolling hash
• Избор на multiplier (31, 33, 37?)
• Modulo операция
• Overflow handling

Задача 32: Проектиране на String Hash Функция:

Pseudocode:

int hash_string(const string& s, int table_size) {
    const int MULTIPLIER = 31;  // Prime multiplier
    unsigned long long hash = 0;

    for (char c : s) {
        hash = (hash * MULTIPLIER + c);
    }

    return hash % table_size;
}

---

Задача 33: Обяснение на Дизайн Изборите:

1. Polynomial Rolling Hash

Формула:

hash = c₀ × P^(n-1) + c₁ × P^(n-2) + ... + c_(n-1) × P^0

където:
- cᵢ = ASCII стойност на i-тия символ
- P = prime multiplier (31)
- n = дължина на string

Пример за "abc":

hash("abc") = 'a' × 31² + 'b' × 31¹ + 'c' × 31⁰
            = 97 × 961 + 98 × 31 + 99
            = 93217 + 3038 + 99
            = 96354

Защо polynomial?

• ✅ Различни strings почти винаги дават различни hash-ове
• ✅ Anagrams ("listen" vs "silent") имат различни hash-ове
• ✅ Position на символите има значение

Сравнение с наивен подход:

// ❌ ЛОШО - anagrams имат същия hash!
int bad_hash(const string& s) {
    int sum = 0;
    for (char c : s) {
        sum += c;
    }
    return sum;
}

bad_hash("listen") = 'l'+'i'+'s'+'t'+'e'+'n' = 666
bad_hash("silent") = 's'+'i'+'l'+'e'+'n'+'t' = 666  // КОЛИЗИЯ!

---

2. Избор на Multiplier: 31

Защо 31?

1. Просто число → по-добро разпределение
2. Близо до степен на 2 (32 = 2^5) → компилаторът може да оптимизира:

   hash * 31 = (hash << 5) - hash  // Бърза bit операция!

3. Исторически доказано (използва се в Java String.hashCode())

Алтернативи:

• 33: Използван в djb2 hash (Dan Bernstein)
• 37, 41, 43: Други прости числа
• Избягвай малки (напр., 2, 3) → много колизии

---

3. Unsigned Long Long за Overflow Handling

Проблем с overflow:

int hash = 0;
hash = hash * 31 + c;  // Може да overflow при дълги strings!

Решение: Използвай unsigned long long (64 бита)

unsigned long long hash = 0;
hash = (hash * MULTIPLIER + c);  // Wraps around при overflow

Забележка: Modulo операцията (% table_size) ще върне резултата в range [0, table_size)

---

4. Modulo със Table Size

return hash % table_size;

Best Practice: table_size трябва да е просто число!

Защо prime?

• По-равномерно разпределение
• Намалява clustering

---

Задача 34: Пълна Имплементация в C++:

#include <string>
#include <iostream>
using namespace std;

class StringHash {
private:
    int table_size;

public:
    StringHash(int size) : table_size(size) {}

    int hash(const string& s) {
        const int MULTIPLIER = 31;
        unsigned long long h = 0;

        for (char c : s) {
            h = (h * MULTIPLIER + static_cast<unsigned char>(c));
        }

        return static_cast<int>(h % table_size);
    }

    // Алтернативен variant с case-insensitive hash
    int hash_case_insensitive(const string& s) {
        const int MULTIPLIER = 31;
        unsigned long long h = 0;

        for (char c : s) {
            h = (h * MULTIPLIER + tolower(c));
        }

        return static_cast<int>(h % table_size);
    }
};

int main() {
    StringHash hasher(101);  // Prime table size

    cout << "hash('hello') = " << hasher.hash("hello") << endl;
    cout << "hash('world') = " << hasher.hash("world") << endl;
    cout << "hash('listen') = " << hasher.hash("listen") << endl;
    cout << "hash('silent') = " << hasher.hash("silent") << endl;
    // ^ Трябва да са различни!

    return 0;
}

---

Задача 35: Тестване на Разпределението:

void test_distribution() {
    StringHash hasher(100);
    vector<int> counts(100, 0);

    // Тест с 1000 random strings
    for (int i = 0; i < 1000; i++) {
        string s = generate_random_string(10);
        int h = hasher.hash(s);
        counts[h]++;
    }

    // Провери distribution
    int min_count = *min_element(counts.begin(), counts.end());
    int max_count = *max_element(counts.begin(), counts.end());

    cout << "Min collisions in bucket: " << min_count << endl;
    cout << "Max collisions in bucket: " << max_count << endl;
    cout << "Average per bucket: " << 1000.0 / 100 << endl;

    // Ideal: min ≈ avg ≈ max
}

---

Задача 36: Резюме на Дизайн Изборите:

Избор	Причина
Polynomial rolling	Различни strings → различни hash-ове
Multiplier = 31	Просто число, близо до 2^5 (оптимизация)
unsigned long long	Избягва overflow problems
Modulo table_size	Маппинг към [0, table_size)
Prime table_size	По-добро разпределение

Time Complexity: O(n) където n = дължина на string

Best for: Hash таблици, НЕ за криптография!

---

Средни-Трудни упражнения (MEDIUM-HARD)

Напреднало приложение и експериментиране

Упражнение

СРЕДНО-ТРУДНО

Задача 37: Clustering Analysis

Задача: Hash таблица, използваща linear probing, показва следния distribution pattern:

Slots: [_, _, X, X, X, X, X, _, _, _, X, _, _, _]
       [0] [1] [2][3][4][5][6][7] [8] [9][10][11][12][13]

1. Обяснете какво е clustering и защо е проблематично
2. Изчислете средния брой probes нужни за да се намери празен slot от позиция 2
3. Как би помогнало quadratic probing в тази ситуация?

Задача 38: 1. Какво е Clustering и Защо е Проблематично?

Clustering (grouping) е феномен при linear probing, където запълнени slots се натрупват в съседни позиции, образувайки дълги вериги.

Пример в задачата:

[_, _, X, X, X, X, X, _, _, _, X, _, _, _]
      ↑_____________↑
       Cluster от 5!

Защо е проблематично?

1. Increased probe sequences:

   • Ако hash(key) = 2, трябва да probe позиции 2, 3, 4, 5, 6 → 5 проверки!
   • Без clustering: само 1 проверка

2. Snowball effect:

   • Колкото по-дълъг е cluster-а, толкова по-вероятно е нов елемент да се добави към него
   • Cluster-ите растат експоненциално!

3. Performance degradation:

   • Average search time расте от O(1) към O(n)
   • При load factor 0.9 + clustering → неприемлива производителност

---

Задача 39: 2. Среден Брой Probes от Позиция 2:

Scenario: Търсим празен slot започвайки от позиция 2

Probing sequence от pos 2:

Start: [2]
       X (occupied) → probe 1

Try:   [3]
       X (occupied) → probe 2

Try:   [4]
       X (occupied) → probe 3

Try:   [5]
       X (occupied) → probe 4

Try:   [6]
       X (occupied) → probe 5

Try:   [7]
       _ (FREE!) → SUCCESS

Общо probes: 5 проби

---

За различни start позиции:

Start Pos	Проби до празен slot
0	1 (slot 0 е свободен)
1	1 (slot 1 е свободен)
2	5 (слотове 2-6 заети)
3	4 (слотове 3-6 заети)
4	3 (слотове 4-6 заети)
5	2 (слотове 5-6 заети)
6	1 (slot 7 е свободен)
7	1 (slot 7 е свободен)
8-9	1 (свободни)
10	1 (slot 11 е свободен)
11-13	1 (свободни)

Average probes:

(1+1+5+4+3+2+1+1+1+1+1+1+1+1) / 14 = 24 / 14 ≈ 1.71 probes

Но ако hash-ваме само в cluster zone (slots 2-6):

(5+4+3+2+1) / 5 = 15 / 5 = 3.0 probes

Заключение: Clustering утройява средния брой probes!

---

Задача 40: 3. Как Quadratic Probing Помага?

Quadratic Probing формула:

index = (hash(key) + i²) % table_size

където i = 0, 1, 2, 3, ...

Пример: hash(key) = 2

i	Offset (i²)	Index	Status
0	0	2	X (occupied)
1	1	3	X (occupied)
2	4	6	X (occupied)
3	9	11	_ (FREE!) ✅

Проби: само 3 вместо 5!

---

Защо е по-добре?

1. Разпръсква probe sequence:

   Linear:    2 → 3 → 4 → 5 → 6 → 7 (sequential)
   Quadratic: 2 → 3 → 6 → 11 (jumps over cluster!)

2. Намалява secondary clustering:

   • Linear: Елементи с hash 2, 3, 4 всички probe същата последователност
   • Quadratic: Различни hash-ове probe различни последователности

3. Performance:

   Linear at α=0.7:    ~3.6 probes average
   Quadratic at α=0.7: ~2.2 probes average

---

Visualization:

Linear Probing:
[_, _, X, X, X, X, X, _, _, _, X, _, _, _]
      ↓  ↓  ↓  ↓  ↓  ← Sequential probing
      
Quadratic Probing:
[_, _, X, X, X, X, X, _, _, _, X, _, _, _]
      ↓     ↓        ↓              ↓    ← Jumps over cluster!

---

Недостатъци на Quadratic:

• ❌ По-сложна имплементация
• ❌ Може да не намери празен slot дори ако има (при пълна таблица)
• ❌ По-лоша cache locality (random jumps)

Trade-off:

• Linear: Отлична cache locality, но vulnerable to clustering
• Quadratic: По-добро collision handling, но по-лоша cache performance

---

Заключение:

При сценарий с clustering:

• ✅ Quadratic/Double Hashing намалява probe count
• ✅ Separate Chaining напълно избягва clustering
• ❌ Linear Probing страда най-много

Препоръка: Ако load factor > 0.5 и се очаква clustering → използвай Quadratic или Separate Chaining

Упражнение

СРЕДНО-ТРУДНО

Задача 41: Separate Chaining Performance

Задача: Hash таблица със separate chaining има 1000 slots и 5000 елемента.

1. Изчислете load factor
2. Каква е очакваната средна дължина на chain ако елементите са uniform distributed?
3. В най-лошия случай (лоша hash функция), всички елементи hash-ват към същия slot. Каква би била времевата сложност за search операции?

Задача 42: 1. Изчисление на Load Factor:

α = n / m

където:
- n = брой елементи = 5000
- m = брой slots = 1000

α = 5000 / 1000 = 5.0

Load Factor: α = 5.0

Забележка: За separate chaining, load factor може да надхвърля 1.0! Това е нормално и приемливо.

---

Задача 43: 2. Очаквана Средна Дължина на Chain (Uniform Distribution):

При uniform distribution, елементите се разпределят равномерно между slot-овете.

Формула:

Average chain length = Total elements / Number of slots = α

Average chain length = 5000 / 1000 = 5.0 елемента на chain

Обяснение:

Ако всички slot-ове имат приблизително еднакъв брой елементи:

• Total elements: 5000
• Total slots: 1000
• Elements per slot: 5000 / 1000 = 5 елемента

Distribution:

[0] → [a] → [b] → [c] → [d] → [e] → null (5 elements)
[1] → [f] → [g] → [h] → [i] → [j] → null (5 elements)
[2] → [k] → [l] → [m] → [n] → [o] → null (5 elements)
...
[999] → [x] → [y] → [z] → [w] → [v] → null (5 elements)

Performance при α = 5.0:

Operation	Average Time	Explanation
Search	O(1 + α) = O(6)	Hash + traverse 5 elements
Insert	O(1)	Hash + append to chain
Delete	O(1 + α) = O(6)	Hash + search + remove

Забележка: Дори при α = 5.0, търсенето е все още бързо (средно 6 операции)!

---

Задача 44: 3. Worst Case: Всички Елементи в Един Slot

Scenario: Лоша hash функция → всички 5000 елемента hash-ват към slot 0

Distribution:

[0] → [a]→[b]→[c]→...→[z]→...→[5000th element] → null
      ↑___________________________________↑
                5000 elements!

[1] → null
[2] → null
...
[999] → null

Performance:

Operation	Worst Case Time	Explanation
Search	O(n) = O(5000)	Traverse entire chain of 5000 elements
Insert	O(1) or O(n)*	Depends if checking for duplicates
Delete	O(n) = O(5000)	Search + delete requires full traversal

*If insert checks for existing key → O(n); if just appends → O(1)

---

Comparison:

Scenario	Load Factor (α)	Avg Chain Length	Search Time
Uniform Distribution	5.0	5	O(6) ≈ constant
Worst Case (1 slot)	5.0*	5000	O(5000) ≈ linear

*Load factor е misleading при worst case - всички елементи са в един chain!

---

Задача 45: Защо Separate Chaining е Устойчива?

Дори при α = 5.0:

• ✅ Average case: Все още бързо (O(6))
• ✅ Graceful degradation: Производителността пада постепенно с α
• ✅ No hard limit: Може да надхвърли capacity без crash

Сравнение с Linear Probing:

Strategy	α = 5.0	Search Time
Separate Chaining	✅ Works	O(6)
Linear Probing	❌ IMPOSSIBLE	Table must resize! (α > 1.0 = full)

---

Задача 46: Practical Implications:

Ако видите α > 2.0 в реална система:

1. Option 1: Resize таблицата

   if (load_factor() > 2.0) {
       resize(capacity * 2);  // Удвои capacity
   }

   След resize:

   New capacity: 2000
   New α = 5000 / 2000 = 2.5 (по-добро, но още високо)

2. Option 2: Подобри hash функцията

   • Провери дали има clustering
   • Тествай с различни multipliers (31, 33, 37)

3. Option 3: Hybrid approach

   • Switch to balanced BST за long chains (Java 8 HashMap)
   • Ако chain > 8 елемента → convert to tree

---

Задача 47: Формули за Separate Chaining:

Average successful search:

Θ(1 + α)

Average unsuccessful search:

Θ(1 + α)

Worst case search:

O(n)  // Всички елементи в един chain

Best case search:

O(1)  // Директен hash, chain length = 1

---

Задача 48: Заключение:

1. α = 5.0 е висок, но separate chaining го толерира добре
2. Uniform distribution → средно 5 елемента на chain → приемлива производителност
3. Worst case → O(n) (всички в един slot) → катастрофално, но рядко при добра hash функция

Best Practice:

• Maintain α < 2.0 за оптимална производителност
• Monitor worst-case chain lengths
• Resize ако longest chain > 10× average

---

Трудни упражнения (HARD)

Комплексен анализ и решаване на проблеми

Упражнение

ТРУДНО

Задача 49: File Deduplication System Design

Задача: Проектирайте система за file deduplication за cloud storage сървис, който управлява 1 милион файла.

1. Изберете подходяща криптографска hash функция и обосновете избора си
2. Обяснете вашия дизайн на hash таблицата включително:
   • Начален размер на таблицата и защо
   • Collision resolution strategy
   • Load factor threshold за resizing
3. Изчислете вероятността за hash collision (false positive) с избраната hash функция
4. Опишете как бихте се справили с рядкия случай на истинска колизия (различни файлове, същия hash)

Помислете за:

• Trade-off между сигурност и производителност
• Вероятност за collision при милион файлове
• Как да се handle false positives?
• Cost на съхранение vs. computation

Задача 50: Система за File Deduplication - Complete Design

---

1. Избор на Криптографска Hash Функция

Задача 51: Избор: SHA-256

Обосновка:

Критерий	SHA-256	SHA-1	SHA-3	MD5
Сигурност	✅ Силна	❌ Компрометирана	✅ Силна	❌ Компрометирана
Скорост	✅ Бърза	✅ По-бърза	⚠️ По-бавна	✅ Много бърза
Output size	256 бита (32 байта)	160 бита	224-512 бита	128 бита
Collision resistance	✅ Отлична	❌ Уязвима	✅ Отлична	❌ Компрометирана
Industry adoption	✅ Широко използвана	⚠️ Deprecated	⚠️ Нова	❌ Deprecated

Защо SHA-256?

1. ✅ Достатъчна сигурност: 2^128 complexity за collision
2. ✅ Добра производителност: Hardware acceleration (AES-NI)
3. ✅ Industry standard: Git, Bitcoin, AWS S3
4. ✅ Balance: Не е overkill като SHA-512, но по-сигурна от SHA-1

Алтернативи:

• BLAKE3: По-бърза от SHA-256, но по-малко adopted
• SHA-512/256: Truncated SHA-512 (добра за 64-bit системи)

---

2. Дизайн на Hash Таблицата

Задача 52: A. Начален Размер:

Избор: 1,500,007 slots

Обосновка:

Expected files: 1,000,000
Target load factor: α ≤ 0.67

Minimum capacity = 1,000,000 / 0.67 ≈ 1,492,537

Next prime number: 1,500,007

Защо просто число?

• По-равномерно разпределение
• Намалява clustering

Защо α = 0.67 (2/3)?

• Добър баланс между memory и speed
• Среден chain length ≈ 0.67 елемента

---

Задача 53: B. Collision Resolution Strategy:

Избор: Separate Chaining

Обосновка:

Критерий	Separate Chaining	Linear Probing
Load factor tolerance	✅ α > 1.0 OK	❌ α < 0.7 required
Deletion	✅ Лесна	❌ Tombstones
Cache locality	⚠️ Pointer chasing	✅ Sequential access
Predictability	✅ Consistent O(1+α)	❌ Clustering
Memory overhead	⚠️ Pointers	✅ No pointers

За deduplication:

• Файлове се добавят/изтриват динамично
• Load factor може да варира
• Predictable performance е критично

Имплементация:

struct FileEntry {
    string sha256_hash;    // 64 hex chars (32 bytes binary)
    string file_path;      // Path to actual file
    size_t file_size;      // File size in bytes
    time_t last_accessed;  // Timestamp
};

class DeduplicationTable {
private:
    vector<list<FileEntry>> table;
    int capacity = 1500007;
    int size = 0;

    int hash_index(const string& sha256) {
        // SHA-256 is already a good hash, just modulo it
        unsigned long long hash_val = 0;
        for (int i = 0; i < 16; i++) {  // Use first 16 hex chars
            hash_val = (hash_val * 16 + hex_to_int(sha256[i]));
        }
        return hash_val % capacity;
    }

public:
    DeduplicationTable() {
        table.resize(capacity);
    }

    // Check if file already exists
    FileEntry* find_file(const string& sha256) {
        int idx = hash_index(sha256);
        for (auto& entry : table[idx]) {
            if (entry.sha256_hash == sha256) {
                return &entry;
            }
        }
        return nullptr;
    }

    // Add new file
    void add_file(const string& sha256, const string& path, size_t size) {
        if (find_file(sha256)) {
            // Duplicate! Don't store again
            cout << "Duplicate detected: " << path << endl;
            return;
        }

        int idx = hash_index(sha256);
        table[idx].push_back(\{sha256, path, size, time(nullptr)\});
        size++;

        // Check if resize needed
        if (load_factor() > 0.75) {
            resize();
        }
    }

    double load_factor() {
        return (double)size / capacity;
    }
};

---

Задача 54: C. Load Factor Threshold:

Resize при α > 0.75

Resizing Strategy:

void resize() {
    int new_capacity = next_prime(capacity * 2);
    vector<list<FileEntry>> new_table(new_capacity);

    // Rehash all entries
    for (auto& chain : table) {
        for (auto& entry : chain) {
            int new_idx = hash_index(entry.sha256_hash) % new_capacity;
            new_table[new_idx].push_back(entry);
        }
    }

    table = move(new_table);
    capacity = new_capacity;
}

Timeline:

Files	Capacity	α	Resize?
0	1,500,007	0.00	No
500,000	1,500,007	0.33	No
1,000,000	1,500,007	0.67	No
1,130,000	1,500,007	0.75	Yes! → 3,000,017

---

3. Вероятност за Hash Collision (False Positive)

SHA-256 Collision Probability:

Формула (Birthday Paradox):

P(collision) ≈ n² / (2 × 2^256)

където n = брой файлове = 1,000,000

Изчисление:

P(collision) = (10^6)² / (2 × 2^256)
             = 10^12 / (2 × 1.16 × 10^77)
             = 10^12 / (2.32 × 10^77)
             ≈ 4.3 × 10^-66

Резултат: P ≈ 0.000...00043 (66 нули!)

Интерпретация:

• Практически невъзможно!
• Повече вероятност за:
  • Asteroid удря земята (10^-8)
  • Печелене на лотария 10 пъти (10^-70)

Сравнение:

Hash	Битове	Collision при 1M файлове
MD5	128	10^-21 (възможно при hardware errors)
SHA-1	160	10^-36 (много малка вероятност)
SHA-256	256	10^-66 (практически невъзможно)

---

4. Handling на Истинска Collision (False Positive)

Дори при P ≈ 10^-66, robust система трябва да handle collision-и.

Задача 55: Strategy: Secondary Verification

При подозрение за collision:

1. Hash collision detected:

   if (sha256(new_file) == sha256(existing_file)) {
       // Potential collision!
   }

2. Byte-by-byte comparison:

   bool are_files_identical(const string& file1, const string& file2) {
       ifstream f1(file1, ios::binary);
       ifstream f2(file2, ios::binary);
   
       char buf1[4096], buf2[4096];
       while (f1 && f2) {
           f1.read(buf1, sizeof(buf1));
           f2.read(buf2, sizeof(buf2));
   
           if (f1.gcount() != f2.gcount()) return false;
           if (memcmp(buf1, buf2, f1.gcount()) != 0) return false;
       }
   
       return f1.eof() && f2.eof();  // Both reached end
   }

3. Decision:

   if (sha256_match) {
       if (are_files_identical(new_file, existing_file)) {
           // True duplicate → deduplicate
           create_reference(new_file, existing_file);
       } else {
           // FALSE POSITIVE COLLISION! (extremely rare)
           alert_admin("SHA-256 collision detected!");
           store_separately(new_file);  // Store as unique
       }
   }

Cost Analysis:

• Byte comparison cost: O(file_size)
• Frequency: Веднъж на ~10^66 файлове
• Amortized cost: Negligible

---

Задача 56: Additional Safety Measures:

1. Multi-hash verification:

struct FileSignature {
    string sha256;
    string sha3_256;  // Secondary hash
};

bool is_collision(FileSignature sig1, FileSignature sig2) {
    return (sig1.sha256 == sig2.sha256) &&
           (sig1.sha3_256 != sig2.sha3_256);  // Collision!
}

2. Logging:

if (collision_detected) {
    log_error("CRITICAL: Hash collision detected!");
    log_error("File 1: " + file1);
    log_error("File 2: " + file2);
    log_error("SHA-256: " + sha256);
    alert_security_team();
}

---

Complete System Architecture:

┌─────────────────┐
│   New File      │
└────────┬────────┘
         │
         ▼
┌─────────────────┐
│ Compute SHA-256 │
└────────┬────────┘
         │
         ▼
┌─────────────────────┐
│ Hash Table Lookup   │
└──────┬──────────────┘
       │
       ├─ Not Found ─────► Store file + Add to hash table
       │
       └─ Found ─────┬─► Byte-by-byte comparison
                     │
                     ├─ Match ─────► Deduplicate (reference)
                     │
                     └─ No Match ──► COLLISION! Store separately + Alert

---

Performance Metrics:

Storage Savings:

Assuming 30% of files are duplicates:

Original: 1,000,000 files × 1MB avg = 1TB
After dedup: 700,000 unique files = 700GB

Savings: 300GB (30%)

Hash Table Memory:

Hash table: 1,500,007 slots × 8 bytes (pointer) ≈ 12 MB
File entries: 1,000,000 × 120 bytes ≈ 120 MB

Total: ~132 MB (negligible compared to file storage!)

---

Заключение:

✅ SHA-256: Optimal choice (сигурност + скорост)
✅ Separate Chaining: Robust и flexible
✅ α ≤ 0.75: Optimal load factor threshold
✅ Collision handling: Secondary verification ensures correctness
✅ P(collision) ≈ 10^-66: Практически невъзможно

System готова за production! 🚀

---

Допълнителни ресурси

ℹ️Полезни ресурси за практика

Инструменти:

• Hash Table Visualizer - Визуализация на hash таблици
• Compiler Explorer - Анализ на assembly код за hash функции
• OpenSSL - Command-line tools за hash изчисления

Практически съвети:

• Винаги тествайте hash функциите с adversarial input
• Измервайте collision rates в реални условия
• Профилирайте производителността при различни load factors
• Използвайте prime numbers за table capacity

✅Ключови точки за запомняне

• Криптографски vs. Hash Table Hash: Различни цели → различни функции
• Load Factor Management: α = 0.5-0.75 е optimal за повечето случаи
• Collision Strategy: Separate chaining е robust, linear probing е cache-friendly
• SHA-256: Industry standard за сигурност (не MD5/SHA-1!)
• Birthday Paradox: 2^(n/2) операции за collision → използвай достатъчно битове

За изпита:

• Знайте как да изчислявате load factor
• Разбирайте trade-offs между collision strategies
• Можете да trace insertion/search operations
• Обяснете защо prime numbers са важни

---

Успех с упражненията! 🎯