7.2.1 Lookup

With open addressing, the lookup logic needs to be changed. We start with the slot at f(k,0). If the slot corresponding to f(k,i) is defined, but the key stored in that slot is not the key being looked up, then we need to consider the slot at f(k,i + 1). This repetition ends when one of the three following conditions is true.

If the key of slot f(k,i) matches the key being looked up, then we can stop.

If slot f(k,i) is not “in use”, then we can stop. This is because if the key we are looking up does exist, this slot would not have been empty.

If i n, we can stop, too. This is because we must have exhausted all the possible slots.