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?

  • 1
    $\begingroup$ What do you mean with "linear probing function $P(x)$" and what do you mean "must it be the same for insertion and searching"? Linear probing is linear probing there are no variants and it's not a function, it's a scheme to resolve collisions. If you're looking for different probing schemes, check out (e.g.) Quadratic Probing and Double Hashing. If you were wondering if you can use e.g. Linear Probing for searching and Double Hashing for insertion, the answer is evidently no. $\endgroup$ – Auberon Sep 12 '18 at 12:16

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.


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.