I'm seeking some clarification on the proof of the expected number of probes in an unsuccessful search in open addressing hashing. The proof is given in CLRS on page 275, section 11.4 (Open addressing).

Specifically, why is the higher bound of an expectation (of unsuccessful probes) in search is $\infty$? What is the rational behind this?

$E[X] = \sum_{i=1}^{\infty} Pr\{X \geq i \}$ $(1)$ p. 275 CLRS

My understanding is that the maximum possible amount of probes in the worst case scenario is $n$. So, the expectation in this case is

$E[X] = \sum_{i=1}^{n} Pr\{X \geq i \}$ $(2)$

where n is the number of elements in a table of size m.

Of course, we can assume that $n \rightarrow \infty$, then $(1)$ makes sense. However, open addressing hashing is not recommended for large data sets. So, these two concepts contradict each other.

  • $\begingroup$ So what is recommended for large data sets? $\endgroup$
    – gnasher729
    Jun 15, 2018 at 22:56
  • $\begingroup$ Chaining can be an effective solution for large data sets $\endgroup$
    – molexi
    Jun 16, 2018 at 23:33


Your Answer

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