About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
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.