Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$. A hash function $h:[U]\rightarrow[m]$ is truly random if For any set of distincts elements $\{x_{1},...,x_{k}\} \subseteq [U]$ and any set of values $u_{1},...,u_{k} \subseteq [m]$ we have $Pr_{h}[h(x_{1}) = u_{1} \wedge ... \wedge h(x_{k}) = u_{k}] = \frac{1}{m^{k}}$. This of course implies  that $h(x_{i})$ is uniform random and independent of $h(x_{1}),...,h(x_{i-1}),h(x_{i+1}),...,h(x_{k})$.I was trying to understand why this is not possible to implement efficiently in practice, and found this paper where at some point they write in the abstract:Hashing is fundamental to many algorithms and data structures widely  used in practice. For theoretical analysis of hashing, there have been  two main approaches. First, one can assume that the hash function is  truly random, mapping each data item independently and uniformly to  the range. This idealized model is unrealistic because a truly random  hash function requires an exponential number of bits to describe.I do not see how using exponential number of bits can help us come up with a truly random hash function when the universe is $[U]$ and the hash table can store at most $m$ elements.How would you use an exponential number of bits to come up with a function that can guarantee the probabilities described above?
How would you implement truly random hash functions in practice?
algorithms;probability theory;randomized algorithms;hash;hash tables
The number of bits required to describe a function from $[U]$ to $[m]$ is $m \times 2^U$. This is exponential in $U$.