External Hashing Schemes for Collections of Data Structures
Richard J. Lipton, Arnold L. Rosenberg, Andrew Chi-Chih Yao · Journal of the ACM · 1980
The use of external hashing schemes for storing broad classes of data structures is studied The general framework of the paper considers a class of data structures parutioned into smaller classes by the number of positions m the structure For instance, one could start with the class of all binary trees and partiuon that class into the subclasses ~, % ..... each q¢~ comprising all n-node binary trees.The mare results establish nonconstructively the existence of an external hashing scheme h,, with O(n) storage demand and O(1) expected access time that will store any structure in % O q¢2 U ... U %, provtded ten contains a number of structures growing at most exponenttally m n Classes of data structures subsumed by these results include ragged arrays, binary trees, stringindexed arrays, and refmable arrays