1
$\begingroup$

how many uniform hash function I can create when I want to hash elements from $U$ where $|U|=m \cdot r$ , $m,r$ are integers.

a hash function $h:U \rightarrow T $ , $|T|=n$ is uniform if $Prob(h(x)=i)=1/n$ for $i=0,1,...n-1$

I know that functions like $h(x)=a \cdot x +b \space mod \space n$ are uniform and the number of such functions are $|U|* (|U|-1)$ . but are there any other functions? how many?

$\endgroup$
1
$\begingroup$

Assuming there are $n$ total hashes and $|U|=nr$, you can select any $r$ elements to go to the first hash, any $r$ of the rest for the second hash, etc. Then there are $${nr \choose r}{(n-1)r \choose r}{(n-2)r \choose r}\dots {2r \choose r}=\frac {(nr)!}{(r!)^n}$$ different hash functions. Most of them will not be easy to describe. The combinatorial reason is that you can line up $U$ in $(nr)!$ ways. You let the first $r$ go to the first hash, the next $r$ to go to the second hash, etc. Among the ways to order $U$, you can permute the first $r$ elements in $r!$ ways and get the same hash function. You can also reorder the second $r$ elements in $r!$ ways, etc. so you divide by $(r!)^n$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.