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.

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

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.