Опишите семейство явных универсальных хеш-функций

Question

В этой задаче мне дали следующее отображение

 U = {0, 1, 2, 3, 4, 5, 6, 7} to {0, 1}

Исходя из этого, существует явная универсальная хеш-функция, которая должна быть получена, с подсказкой, что это можно сделать с помощью набора из 4 функций. К сожалению, несмотря на поиск статей о том, как это сделать, я все еще в замешательстве. Будем очень благодарны за любую помощь в понимании того, как найти эту функцию хеширования и двигаться в правильном направлении!

РЕДАКТИРОВАТЬ:

После некоторого обдумывания, это то, что я придумал; это будет правильно?

     0  1  2  3  4  5  6  7
---------------------------
h1 | 1  1  0  0  0  0  0  0 
h2 | 0  0  1  1  0  0  0  0
h3 | 0  0  0  0  1  1  0  0
h4 | 0  0  0  0  0  0  1  1

Answer 1

Используя определение из Википедии:

Семейство функций H = {h: U → [m]} называется универсальным семейством, если, ∀ x, y ∈ U, x ≠ y: Pr _h∈H [h (x) = h (y)] ≤ ¹ / _м

В вашем случае это означает, что для любых двух значений x и y в наборе {0, 1, 2, 3, 4, 5, 6, 7} не более двух из четырех ваших хеш-функций могут отображать их в один и тот же бит,

Ваше предложение:

     0  1  2  3  4  5  6  7
---------------------------
h1 | 1  1  0  0  0  0  0  0 
h2 | 0  0  1  1  0  0  0  0
h3 | 0  0  0  0  1  1  0  0
h4 | 0  0  0  0  0  0  1  1

не работает, потому что есть четыре пары (x, y), а именно (0,1), (2,3), (4,5) и (6,7), где все четыре хэш-функции отображают их в тот же бит.

Вместо этого вот несколько вариантов, которые работают:

     0  1  2  3  4  5  6  7
---------------------------
h1 | 0  0  0  0  1  1  1  1
h2 | 0  0  1  1  0  0  1  1
h3 | 0  1  0  1  0  1  0  1
h4 | 0  1  1  0  1  0  0  1

     0  1  2  3  4  5  6  7
---------------------------
h1 | 0  0  0  1  0  1  1  1
h2 | 0  0  1  0  1  0  1  1
h3 | 0  1  0  0  1  1  0  1
h4 | 1  0  0  0  1  1  1  0