In this problem, I was given the follow mapping
U = {0, 1, 2, 3, 4, 5, 6, 7} to {0, 1}
From this, there is an explicit universal hashing function that must be derived, with the hint that this can be done with a set of 4 functions. Unfortunately, despite searching through articles on how to do this, I am still confused. Any help in understanding how to find this hashing function and moving towards the right direction is greatly appreciated!
EDIT:
After some deliberation, this is what I came up with; would this be correct?
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
Using the definition from Wikipedia:
A family of functions H = {h: U → [m]} is called a universal family if, ∀ x,y ∈ U, x ≠ y : Prh∈H[h(x) = h(y)] ≤ 1/m.
In your case, this means that for any two values x and y in the set {0, 1, 2, 3, 4, 5, 6, 7}, at most two of your four hash functions can map them to the same bit.
Your suggestion:
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
does not work, because there are four pairs (x, y) — namely (0,1), (2,3), (4,5), and (6,7) — where all four hash functions map them to the same bit.
Instead, here are some options that do work:
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