# Number of uniform hash functions

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?

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$