Does this excerpt from the linear probing Wikipedia page make an assumption?

Question

Here is the excerpt from the linear probing page at Wikipedia.

To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and continuing to the adjacent cells h(x) + 1, h(x) + 2, ..., until finding either an empty cell or a cell whose stored key is x. If a cell containing the key is found, the search returns the value from that cell. Otherwise, if an empty cell is found, the key cannot be in the table, because it would have been placed in that cell in preference to any later cell that has not yet been searched. In this case, the search returns as its result that the key is not present in the dictionary.

Does this assume that the linear probing function let's say P(x) is the same for insertion and searching? Must your linear probing function be consistent throughout the hash table? Is there a combination of linear probing functions that work best together?

Answer 1

Yes, it is assumed that probing sequences are identical during the search and insertion. In theory you could use a different probing sequence (e. g. check h(x) index first, then h(x) + 2, and only then h(x) + 1), but it doesn't make any sense - you are better off always using the same sequence to have the minimal expected number of probes.