Storing a dynamic sparse table
Alfred V. Aho, David Lee · 1986
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.