Discussion on Hash Tables

An alternative to hashing with chaining is used by open addressing schemes, where all data is stored directly in an array. These schemes include the LinearHashTable structure. This idea was also proposed, independently, by a group at IBM in the 1950s. Open addressing schemes must deal with the problem of collision resolution: the case where two values hash to the same array location. Different strategies exist for collision resolution; these provide different performance guarantees and often require more sophisticated hash functions than the ones described here.

Yet another category of hash table implementations are the so-called perfect hashing methods. These are methods in which find(x) operations take $O(1)$ time in the worst-case. For static data sets, this can be accomplished by finding perfect hash functions for the data; these are functions that map each piece of data to a unique array location. For data that changes over time, perfect hashing methods include FKSM. L. Fredman, J. Komlo ́s, and E. Szemere ́di. Storing a sparse table with 0 (1) worst case access time. Journal of the ACM, 31(3):538–544, 1984. two-level hash tablesM. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. M. auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic ...