To be somewhat less sloppy, a search has Θ(1 + α) average-case performance independent of search success, assuming the hash indices are uniformly distributed over the scatter table.
This page last modified on 24 January 2006.