Hashing Schemes for Extendible Arrays

Abstract

The use of hashing schemes for storing extendible arrays is investigated. It is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely hashing schemes that utilize storage too conservatively are inevitably poor in expected access time. If requirements for the utilization of storage are relaxed slightly, then one can find rather efficient extendible hashing schemes. Specifically, for any dimensionality of arrays, one can find extendible hashing schemes which at once utilize storage well (fewer than 2p storage locations need be set aside for storing arrays having p or fewer positions) and enjoy good access characteristics (expected access time is O(1), and worst-case access time is O(log log p) for p- or fewer-position arrays). Moreover, at the cost of only a modest additive increase in access time, storage demands can be decreased to (1 + δ)p locations for arbitrary δ > 0. © 1977, ACM. All rights reserved.