Exercises 22. 4. 2021: Hash functions
\(
\def\H{\mathcal{H}}
\def\U{\mathcal{U}}
\def\B{\mathcal{B}}
\)
Notation:
- \(\U\) : universe
- \(U = |\U|\)
- \(\B\) : buckets
- \(m = |\B|\)
Ex. 1: Universality and independence
- Recall the definition of c-universality and (k,c)-independence.
- Consider a family \(\mathcal{H}_1 = \{h(x) = x\}\) that contains a single hash
function \(h(x) = x\) (that is, \(\B = \U\). Is family
\(\H_1\) c-universal for some c? Is it (k,c)-independent for some k and c?
- Show that family \(\H_2 = \{h_a(x) = a | a\in\B\}\) of all constant functions is
(1,1)-independent. Also show \(\H_2\) is not (2,c)-independent nor c-universal for any c.
- Prove the following claim from the lecture
- \(\H\) is (k,c)-independent \(\Rightarrow\) \(\H\) is (k-1,c)-independent (\(k
> 1\))
- \(\H\) is (2,c)-independent \(\Rightarrow\) \(\H\) is c-universal