1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A single function cannot guarantee anything; the probability of any event is either 0 or 1. Rather, you want a distribution over hash functions, i.e., a random hash function chosen according to some law. $\endgroup$ – Yuval Filmus Jun 24 '15 at 14:48
  • $\begingroup$ I'm confused about what your question is. Is your question, a truly random hash function sounds like what I'm looking for, how would I implement something like that in practice? Or, is your question, why does it require an exponential number of bits to implement a truly random hash function? The answers to those two will be super-different. Did Yuval's answer answer your question? $\endgroup$ – D.W. Jun 24 '15 at 18:58
  • $\begingroup$ It was more about why it requires an exponential number of bits to implement such a hash function. $\endgroup$ – jsguy Jun 26 '15 at 17:07
0
$\begingroup$

The number of bits required to describe a function from $[U]$ to $[m]$ is $m \times 2^U$. This is exponential in $U$.

$\endgroup$
  • $\begingroup$ but if I come up with a function h where $h(x) = x$, even though that requires an exponential number of bits, it would not satisfy the probability constraints. $\endgroup$ – jsguy Jun 24 '15 at 14:48
  • $\begingroup$ See my comment to your post. No single function satisfies the probability constraints. The only distribution satisfying them for all $k$ is the uniform distribution over all functions from $[U]$ to $[m]$, and storing a sample from this domain requires $m2^U$ bits. $\endgroup$ – Yuval Filmus Jun 24 '15 at 14:49

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.