Thumbnail
Access Restriction
Subscribed

Author Rosenberg, Arnold L. ♦ Stockmeyer, Larry J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1977
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
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 $2\textit{p}$ storage locations need be set aside for storing arrays having $\textit{p}$ or fewer positions) and enjoy good access characteristics (expected access time is $\textit{O}(1),$ and worst-case access time is $\textit{O}(log$ log $\textit{p})$ for $\textit{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 + $δ)\textit{p}$ locations for arbitrary δ > 0.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1977-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 24
Issue Number 2
Page Count 23
Starting Page 199
Ending Page 221


Open content in new tab

   Open content in new tab
Source: ACM Digital Library