Storing a dynamic sparse table
- 1 October 1986
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We present a family of data structures that can process a sequence of insert, delete, and lookup instructions such that each lookup and deletion is done in constant worst-case time and each insertion is done in constant expected time. The amount of space used by each data structure is proportional to the maximal number of elements that need to be stored at any moment in time.Keywords
This publication has 8 references indexed in Scilit:
- Practical Perfect HashingThe Computer Journal, 1985
- Storing a Sparse Table with 0 (1) Worst Case Access TimeJournal of the ACM, 1984
- Data Structures and Algorithms 1Published by Springer Nature ,1984
- Reciprocal hashingCommunications of the ACM, 1981
- Should Tables Be Sorted?Journal of the ACM, 1981
- Variations on the Common Subexpression ProblemJournal of the ACM, 1980
- Storing a sparse tableCommunications of the ACM, 1979
- Perfect hashing functionsCommunications of the ACM, 1977