Expected Worst-case Performance of Hash Files

The following problem is studied: consider a hash file and the longest probe sequence that occurs when retrieving a record. How long is this probe sequence expected to be? The approach taken differs from traditional worst-case considerations, which consider only the longest probe sequence of the worst possible file instance. Three overflow handling schemes are analysed: uniform hashing (random probing), linear probing and separate chaining. The numerical results show that the worst-case performance is expected to be quite reasonable. Provided that the hashing functions used are well-behaved, extremely long probe sequences are very unlikely to occur.