Задачі: Хеш-функції¶

Задачі для закріплення теоретичного матеріалу лекції про хеш-функції.

Формат задач

В задачах на обчислення потрібно показати хід розв'язку. В задачах на C++ — написати реалізацію замість ....

Обчислення хешів¶

Задача 1: Хеш цілих чисел

Нехай $h(x) = x \bmod 11$. Обчисліть хеш для кожного ключа:

$15, \quad 27, \quad 44, \quad 11, \quad 33, \quad 0, \quad -3$

Які з цих ключів утворюють колізії?

Задача 2: Поліноміальний хеш рядка

Обчисліть поліноміальний хеш для рядка "bad" з параметрами $p = 31$, $m = 100$.

Використовуйте формулу: $$h(s) = \left(s_0 \cdot p^0 + s_1 \cdot p^1 + s_2 \cdot p^2\right) \bmod m$$

де $s_i$ — номер букви в алфавіті ($a = 1, b = 2, \ldots$).

Потім обчисліть хеш для "dab". Чи збігаються хеші?

Задача 3: Хеш-функція на C++

Реалізуйте хеш-функцію для цілих чисел, яка використовує формулу:

\[h(x) = ((a \cdot x + b) \bmod p) \bmod m\]

де $a$, $b$ — константи, $p$ — велике просте число.

int hash_linear(int x, int a, int b, int p, int m) {
    ...
}

Протестуйте з $a = 3$, $b = 7$, $p = 101$, $m = 10$ для ключів $0, 1, 2, \ldots, 9$.

Задача 4: Знайти колізії

Нехай $h(x) = x \bmod 5$. Знайдіть три різних натуральних числа, які мають однаковий хеш. Поясніть, чому це завжди можливо.

Задача 5: Принцип Діріхле

В групі 13 студентів. Доведіть, що хоча б двоє з них народилися в одному місяці.

Задача 6: Мінімальна кількість колізій

Хеш-функція має $m = 8$ можливих значень. В таблицю додано 20 ключів.

Задача 7: Ймовірність колізії

Хеш-функція повертає значення з множини $\{0, 1, \ldots, 99\}$ (тобто $m = 100$).

Обчисліть ймовірність того, що серед 5 випадкових ключів не буде жодної колізії. Яка ймовірність того, що колізія буде?

Задача 8: Оцінка кількості елементів

Скільки приблизно елементів потрібно взяти, щоб ймовірність колізії перевищила 50%, якщо:

Використовуйте формулу $k \approx \sqrt{m}$.

Задача 9: Порівняння хеш-функцій

Дано дві хеш-функції для рядків:

Функція A: сума кодів символів mod $m$

Функція B: поліноміальний хеш з $p = 31$ mod $m$

Обчисліть хеш для рядків "abc", "bca", "cab" при $m = 100$ для обох функцій. Яка функція краща і чому?

Задача 10: Хеш-функція для точок

Напишіть хеш-функцію для структури point з полями x та y:

struct point {
    int x;
    int y;
};

int hash_point(const point& p, int m) {
    ...
}

Вимоги:

Лекція: Хеш-функції