External perfect hashing
Per-Åke Larson, M. V. Ramakrishna · 1985
A hashing functton 1s perfect if tt does not create any overflow records The use of perfect hashing functions has previously been studied only for small static sets stored m mam memory In this paper we describe a perfect hashing scheme for large external files which we are currently mvestigatmg The scheme guarantees retrieval of any record m a single disk access This 1s achieved at the cost of a small m-core table and increased cost of insertions We also suggest a pohcy for limrtmg the cost of msertrons and we study the tradeoff between expected storage utthzatron, size of the internal table and cost of msertrons under this pohcy The results obtained so far are very promrsmg They indicate that it may indeed by posstble to destgn practical perfect hashing schemes for external files based on the suggested approach Electronic mad uucp {decvax,allegra,lhnp4] ~watmath~watdalsy~(palarson,mvramalmshn) csnet {palarson,mvramakruhn)% watdauy@ Waterloo csnet Permtsston to copy wtthout fee all or part of this matenal IS granted prowled that the coplea are not made or dlstrlbuted for dwect commercial advantage, the ACM copyright nouce and the tnle of the pubhcatlon and its date appear, and nottcc IS gwen that copymg IS by permlsslon of the Assoclatlon for Computing Machmery To copy otherwse, or to repubhsh, reqmres a fee and/or specific permIssIon