# Confused about the appropriate slot in linear probing

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$$, $$T$$, $$...$$ 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.

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$$.
• Sorry. $T[(h'(k) + 1) \: \text{mod m}]$ is what I meant. I edited my question.