Skip to main content
3 of 3
edited title

Why does the hashfamily of all functions with $\{h \in H_0 | h:U \rightarrow V\}$ satisfy universal hashing?

I read in our university lecture on hashing that it would be good (even though it is way to space intensive) if we could take the set of all function from $U \rightarrow V$ to satisfy the following universal hashing condition: for all $\forall x,y\in U$ so that $x≠y$, we have $Pr[h(x)=h(y)]≤\frac{1}{|V|}$

I actually don´t understand why the set of all functions would satisfy our condition. I can definitively see that there are some function which fit this condition, but I can think of other functions which dont meet the condition. So I would have to make a statement about average probabilty over the set of all functions, but how could something like this be defined precisely?

Or am I taking something wrong here and the Set of all functions wouldn´t meet the condition, but would actually be better that the condition taking the case that h is taking randomly from H? Even if so it seems to come down to the same problem.