External Hashing Schemes for Collections of Data Structures

Abstract

The use of external hashing schemes for storing broad classes of data structures isstudied 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�n comprising all n-node binary trees. The mare results establish nonconstructively the existenceof an external hashing scheme h, with O(n) storage demand and O(1) expected ccess time that will store any structure in % O q2 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. © 1980, ACM. All rights reserved.