Comment by pkhuong

With linear probing RH, a failed lookup can stop as early as a successful one, as long as you also store the hash (useful for fast insertion): stop looking when you'd insert the key you're looking for before the current entry.