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?

Improve this question
$\endgroup$
3
  • $\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
    Commented Jun 24, 2015 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. ♦
    Commented Jun 24, 2015 at 18:58
  • $\begingroup$ It was more about why it requires an exponential number of bits to implement such a hash function. $\endgroup$
    – jsguy
    Commented Jun 26, 2015 at 17:07

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jun 24, 2015 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
    Commented Jun 24, 2015 at 14:49
  • $\begingroup$ Sorry for bringing that up, but what am I missing here? There are $m^U$ functions, so I can store a description with $U\log m$ bits. $\endgroup$
    – Ariel
    Commented Jun 25, 2020 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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