0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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

0

Reset to default

Your Answer

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