Thumbnail
Access Restriction
Subscribed

Author Nishihara, Seiichi ♦ Ikeda, Katsuo
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Collision resolution ♦ Predictor ♦ Searching ♦ Hashing ♦ Chaining ♦ Synonym ♦ Clustering ♦ Open addressing ♦ Scatter storage
Abstract Many methods for resolving collisions in hashing techniques have been proposed. They are classified into two main categories: open addressing and chaining. In this paper, other methods are presented that are intermediate between the two categories. The basic idea of our methods is the use of one or more predictors reserved per cell instead of a link field as in the chaining method. The predictors are used to maintain loose synonym chains. After describing the methods, the efficiencies are estimated theoretically and verified experimentally. In comparison with the chaining method, we prove that our methods significantly reduce the average number of probes necessary to retrieve a key without expending extra space.
Description Affiliation: Univ. of Tsukuba, Ibaraki, Japan (Nishihara, Seiichi; Ikeda, Katsuo)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 26
Issue Number 12
Page Count 7
Starting Page 1082
Ending Page 1088


Open content in new tab

   Open content in new tab
Source: ACM Digital Library