Consider a hash table with $m$ buckets, with chaining as collision resolution policy. Given the set $S$ that will be stored in the hash table, let $X_i$ be the number of buckets whose chain length is $i$. Then the cardinality $s = |S|$ of the set $S$ is $$ s = X_1 + 2 X_2 + \cdots + i X_i + \cdots \enspace. $$ Clearly the summation can end at $i=s$. The number of non-empty buckets $s_m$ is $$ s_m = X_1 + X_2 + \cdots + X_s \enspace.$$ I am interested in upper bounding $s-s_m$ for my application. $$ s-s_m = X_2 + 2 X_3 + \cdots + (i-1)X_i + \cdots \enspace.$$ In the previous equation:

  1. $s_m$ is known by $s$ isn't. However, $s$ is fixed and is not a random variable.
  2. $X_i$ for $i\geqslant 2$ is also the number of $i$-wise collisions.

For $i=2$, if we are using k-independent hash functions with $k$ at least 4, we know the mean and variance of $X_2$ as a random variable [1, Lemmas 1 and 2]. Therefore we can bound $X_2$ from above w.h.p. using Chebyshev's inequality: $X_2\leqslant s_m^2/m$.

I am asking whether other works discussed the mean/variance of $X_i$ for $i>2$, or whether it possible to bound the quantity above with other means.

I can already generalise lemma 1:

Lemma Suppose that $s$ elements, denoted by $e_1,\ldots,e_s$, are hashed into a table of size $m=\beta s$ by a random function $h$ is a $k$-independent class $H_k$, $k\geqslant t$ for $t\geqslant s$. Let $Y_{i_1\cdots i_t}$ be an indicator variant whose balues is $1$ if and only if elements $e_{i_1},\ldots,e_{i_t}$ hash to the same
location. That is $h(e_{i_1})=\cdots=h(e_{i_t})$. Let $X$ be the
random variable whose value is the number of $t$-wise collisions
between elements, that is, $$X=\sum_{1\leqslant i_1 < i_2 <\cdots < i_t \leqslant s} Y_{i_1\cdots i_t} \enspace.$$ Then $$ \mathbb E[X] = \binom{s}{t} \frac{1}{m^{t-1}} = \binom{s}{t} \frac{1}{(\beta s)^{t-1}} \enspace. $$

Proof Since $H$ is $k$-independent for some $k\geqslant t$, $$\mathbb E[Y_{i_1 \cdots i_t}] = 1/m^{t-1} \enspace.$$ Hence $$ \mathbb E[X] = \sum_{1\leqslant i_1 < i_2 < \cdots < i_t \leqslant s} \mathbb E[Y_{i_1\cdots i_t}] = \binom{s}{t} \frac{1}{m^{t-1}} = \binom{s}{t} \frac{1}{(\beta s)^{t-1}} \enspace. $$

Probably Lemma 2 can be generalised as well, although the combinatoric counting will be a little bit more challenging. However, is there a solution that we can stick only with 4-independent hash function not with s-independent hash functions, since $s$ is unknown?

UPDATE: A generalisation of Lemma 2 may be obtained. The combinatoric counting is shown here.

Thank you,

1 Broder, A., & Karlin, A. R. (1990). Multilevel Adaptive Hashing. SODA'90. http://dl.acm.org/citation.cfm?id=320181.

  • 1
    $\begingroup$ The calculation in [1] concerns the number of collisions, which is $\sum \binom{k}{2} X_k$. It shows that the expected number of collisions is roughly $s^2/(2m)$, and the variance is at most $s^2/(2m)$. Note that these formulas depend on $s$ rather than on $s_m$. In fact, you can't bound the number of collisions as a function of $s_m$, since for large $s$ you will get $s^2/(2m)$ collisions, a quantity growing to infinity, but $s_m$ is bounded by $m$. $\endgroup$ May 12, 2016 at 19:33
  • $\begingroup$ @YuvalFilmus Would kindly elaborate why $\binom{k}{2}$ is a factor in the sum? $\endgroup$ May 12, 2016 at 20:03
  • 1
    $\begingroup$ The number of collisions is the number of unordered pairs of inputs which map to the same hash value. Given this description, it's an exercise to derive my formula. $\endgroup$ May 12, 2016 at 20:10


Your Answer

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

Browse other questions tagged or ask your own question.