1

Тема: Колізії хеш функцій

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

c++ code

int h(int a) { return abs(a)%8*12 + abs(a)%12 }

Я знаю наступне:

int h(int a) { return abs(a)%8 }

ця функція поверне колізію на 9, тобто мінімум 9 аргументів.

А от як бути з з множенням

abs(a)%8*12

як тут рахується?

І як бути з додаванням? Типу перший доданок поверне колізії через 8 елементів, другий через 12. В результаті як?


Чесно, я гуглив. Вткніть носом в матеріал, якщо знаєте де знайти?

2

Re: Колізії хеш функцій

Q-bart написав:

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

Не зрозумів питання. Зформуйте чіткіше.

Q-bart написав:

Я знаю наступне:

int h(int a) { return abs(a)%8 }

ця функція поверне колізію на 9, тобто мінімум 9 аргументів.

Чому на 9 ?

3

Re: Колізії хеш функцій

Завдання звучить так:

Для цієї хеш-функції сказати, яка мінімальна к-сть аргументів гарантовано призведе до колізії.

Оця ф-я:

int h(int a) { return abs(a)%8*12 + abs(a)%12 }

4 Востаннє редагувалося Q-bart (05.07.2018 20:56:37)

Re: Колізії хеш функцій

leofun01 написав:
Q-bart написав:

Я знаю наступне:

int h(int a) { return abs(a)%8 }

ця функція поверне колізію на 9, тобто мінімум 9 аргументів.

Чому на 9 ?

Підставимо в а:

а=1 h(1) = 1
а=2 h(2) = 2
а=3 h(3) = 3
а=4 h(4) = 4
а=5 h(5) = 5
а=6 h(6) = 6
а=7 h(7) = 7
а=8 h(8) = 8
а=9 h(9) = 1 <<<< тут

5

Re: Колізії хеш функцій

Q-bart написав:

Підставимо в а:

а=1 h(1) = 1
а=2 h(2) = 2
а=3 h(3) = 3
а=4 h(4) = 4
а=5 h(5) = 5
а=6 h(6) = 6
а=7 h(7) = 7
а=8 h(8) = 8
а=9 h(9) = 1 <<<< тут

h(8) = 0
І чому ви почали з 1, а не з 0 ?
а=0 h(0) = 0
а=1 h(1) = 1
а=2 h(2) = 2
...

Подякували: Q-bart1

6

Re: Колізії хеш функцій

По-перше, згадуємо принцип Діріхле:  неможливо посадити n+1 кроля в n кліток так, щоб у кожній клітці було не більше 1 кроля.
Тепер дивимося на першу формулу. Ми маємо купу кролів (вхідні числа) і обмежену кількість кліток (вихідних чисел). Скільки у нас кліток? Стільки, скільки можливо залишків від ділення на 8 - тобто знову ж таки 8.
"Кролі" 0, 8, 16, ..., 8n підуть у клітку №0.
"Кролі" 1, 9, 17, ..., 8n+1 підуть у клітку №1.
"Кролі" 2, 10, 18, ..., 8n+2 підуть у клітку №2.
...
"Кролі" 7, 15, 23, ..., 8n підуть у клітку №7.
Все, клітки скінчилися, кріль №8 знову потрапляє у клітку №0. І яких би кролів ми не брали, якщо їх буде 8, то може статися так, що вони розійдуться по різних клітках, але якщо їх буде 9, то за принципом Діріхле хоча б два потраплять до однієї клітки, тобто буде колізія.

Тепер розглянемо другу формулу. a%12 дає нам 12 різних значень, a%8 - 8, а коефіціент 12 не дозволяє цим залишкам накладатися (можна сказати, що в нас двозначне 12-ичне число з першою цифрою, меншою за 8). На перший погляд - 8*12=96 кліток.
Але не все так просто. Біда в тому, що 8 і 12 - не взаємно прості числа, вони разом діляться на 4. Через це деякі комбінації залишків неможливі - наприклад, неможливо, щоб a%8==0 і при цьому a%12==1, бо тоді залишок від ділення на 4 буде суперечливий. НСК(8,12)=24; саме стільки буде у нас "кліток":
a = 24n => h = 0
a = 24n+1 => h = 9
a = 24n+2 => h = 26
...
a = 24n+8 => h = 8
...
a = 24n+12 => h = 48
...
a = 24n+23 => h = 139
все, наступне значення 24n+24 знову потрапляє в h=0.

А тепер самостійно розрахуйте, скільки буде "кліток" (і коли станеться колізія) при формулі a%3+a%5.

Подякували: ReAl, Q-bart2

7

Re: Колізії хеш функцій

НСК(3,5)=15?

8

Re: Колізії хеш функцій

НСК - так. Відповідь - ні.

Подякували: Q-bart1

9 Востаннє редагувалося Q-bart (05.07.2018 23:33:57)

Re: Колізії хеш функцій

Дякую, зрозумів, здається.

А як з double? Напр. ф-я:

fun (double a) {(int)round(sin(a)*100)}

10

Re: Колізії хеш функцій

І що ж ви зрозуміли?

11

Re: Колізії хеш функцій

Як ні? НСК(3,5)=15. Відповідь: 16

12

Re: Колізії хеш функцій

А "кліток" скільки? 0, 1, 2... яка межа?

13

Re: Колізії хеш функцій

Доступні значення:

h(0) = 0
h(1) = 2
h(2) = 4
h(3) = 3
h(4) = 5
h(5) = 2  (5%3 + 5%5 = 2+0=2) <<< хіба не тут колізія?


Йо, я остаточно заплутався.

14

Re: Колізії хеш функцій

А як з double? Напр. ф-я:

fun (double a) {(int)round(sin(a)*100)}

Чого питаю: на вхід ж може поступати 0,0000001, і відразу наступне значення 0,0000002 буде колізією ?

15

Re: Колізії хеш функцій

по a%3+a%5: ви неправильно сприйняли моє пояснення. Послідовні значення я наводив для того, щоб перебрати всі клітки, а не для того, щоб знайти колізію, хоча й так сталося, що для тих формул колізія стається лише після перебору. Але тут h(6)=1 - знову нема колізії, що повертає нас до питання, скільки там кліток? Яка множина значень цієї функції?
по double - так, гугліть геометричне хешування. От тільки не треба вважати значення 1e-7 та 2e-7 "послідовними", між ними стільки ж чисел, скільки й поза ними (ну добре, для конкретного типу double все ж менше, але все одно дуже багато).

16

Re: Колізії хеш функцій

a%3 ∈ {0,1,2}. a%5 ∈ {0,1,2,3,4}. Відповідно, a%3+a%5 ∈ {0,1,2,3,4,5,6} - всього 7 значень. Отже, для гарантованої колізії необіхдно 8 вхідних значень.

Подякували: leofun011