0
$\begingroup$

In a simple uniform hashing with chaining collision, the time complexity of a successful search is: $Θ(1 + (1 + \frac{α}{2} - \frac{α}{2n}))$ where $α=\frac{n}{m}$, but I don't understand how to determine it.

I tried to calculate the cost of access of each node in the list and to divide it by the number of elements of the list, but it doesn't seem correct. $$1+\frac{m}{n}\cdot \sum _{i=0}^{\frac{n}{m}}\frac{n}{m}-i=1+\frac{n+m}{2m}$$

$\endgroup$
1
$\begingroup$

The expected length of a chain when the $i$th element is added is $\frac{i-1}m$. So if we mentally re-order the elements in the hash map to be in order of insertion, we can calculate the expected length of a chain $E[l]$ when performing a search with $n$ elements in the map:

\begin{align} E[l]&=\frac{1}{n}\sum_{i=1}^n \frac{i-1}m = \frac{1}{nm}\left(-n + \sum_{i=1}^n i\right) = \frac{1}{nm}\left(-n + \frac{1}{2}n(n+1)\right)\\ E[l] &= \frac{1}{m}\left(-1 + \frac{1}{2}n+\frac{1}{2}\right) = \frac{n}{2m} - \frac{1}{2m} \end{align}

Now you can substitute $\alpha = \frac n m$ and find $E[l] = \frac \alpha 2 - \frac{\alpha}{2n}$.

$\endgroup$
2
  • $\begingroup$ Is it not clear to me why the element is in position $\frac{i-1}{m}$? What I mean is that, if a list is long $\frac{6}{2}\;(m=6, n=2)$, the element shouldn't be in the position $1, 2, 3$ of the first or second list (therefore in the $\frac{n}{m}-i$ position)? $\endgroup$ – Shyvert Apr 24 '20 at 7:59
  • $\begingroup$ @Shyvert $\frac{i-1}m$ isn't a position, it's an expected chain length. When inserting the $i$th element there are already $i-1$ elements in the hash map, and we assume that these are uniformly distributed. Therefore we expect each cell of the hash map to have $\frac{i-1}{m}$ elements already. $\endgroup$ – orlp Apr 24 '20 at 9:31

Your Answer

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

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