Compact Hash Tables Using Bidirectional Linear Probing

1 September 1984

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-33 (9) , 828-834
https://doi.org/10.1109/tc.1984.1676499

Abstract

An algorithm is developed which reduces the memory requirements of hash tables. This is achieved by storing only a part of each key along with a few extra bits needed to ensure that all keys are stored unambiguously. The fraction of each key stored decreases as the size of the hash table increases. Significant reductions in total memory usage can be achieved especially when the key size is not much larger than the size of a memory index and when only a small amount of data is stored with each key. The algorithm is based on bidirectional linear probing. Search and insertion times are shown by simulation to be similar to those for ordinary bidirectional linear probing.

Keywords

This publication has 6 references indexed in Scilit:

Universal classes of hash functions
Journal of Computer and System Sciences, 1979
Hash Table Methods
ACM Computing Surveys, 1975
Hashing functions
The Computer Journal, 1975
Ordered hash tables
The Computer Journal, 1974
Comment on Brent's scatter storage algorithm
Communications of the ACM, 1973
General performance analysis of key-to-address transformation methods using an abstract file concept
Communications of the ACM, 1973