Storing a sparse table with O(1) worst case access time
- 1 November 1982
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 165-169
- https://doi.org/10.1109/sfcs.1982.39
Abstract
We describe a data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time. Both the data structure and the query algorithm are easy to implement.Keywords
This publication has 4 references indexed in Scilit:
- Reciprocal hashingCommunications of the ACM, 1981
- Should Tables Be Sorted?Journal of the ACM, 1981
- Storing a sparse tableCommunications of the ACM, 1979
- Perfect hashing functionsCommunications of the ACM, 1977