0
$\begingroup$

The following paragraph is from the book CLRS:

Given an ordinary hash function $h' : U \rightarrow \{0, 1, ..., m - 1\}$, which we refer to as an auxiliary hash function, the method of linear probing uses the hash function $h(k, i) = (h'(k) + i) \; \text{mod m}$ for $i = 0, \: 1,\: ... ,\: m - 1$. Given key $k$, we first probe $T[h'(k)]$, i.e., the slot given by the auxiliary hash function. We next probe slot $T[h'(k) + 1]$, and so on up to slot $T[m - 1]$. Then we wrap around to slots $T[0]$, $T[1]$, $...$ until we finally probe slot $T[h'(k) - 1]$. Because the initial probe determines the entire probe sequence, there are only $m$ distinct probe sequences.

Now, in the fourth line I think we should probe $T[(h'(k) + 1) \: \text{mod m}]$ other than $T[h'(k) + 1]$ because we are setting $i = 1$. Actually, if $0 \leqslant h'(k) \leqslant m - 2$, then these two are the same, but if $h'(k) = m - 1$, then they aren't. We simply should iterate over the probe sequence to find an empty slot for insertion but I don't know what's happening here.

$\endgroup$

1 Answer 1

0
$\begingroup$

You should probe $T[h'(k)+1 \bmod m]$, not $T[h'(k)+1] \bmod m$. This is already explained in the part you quoted: it says "up to slot $T[m-1]$. Then we wrap around..." -- and that is exactly the same as doing modular arithmetic, mod $m$.

$\endgroup$
1
  • $\begingroup$ Sorry. $T[(h'(k) + 1) \: \text{mod m}]$ is what I meant. I edited my question. $\endgroup$
    – Emad
    Commented Jan 31, 2022 at 9:02

Your Answer

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

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