article

Free access

Weighted increment linear search for scatter tables

Author:

Fabrizio LuccioAuthors Info & Claims

Communications of the ACM, Volume 15, Issue 12

Pages 1045 - 1047

https://doi.org/10.1145/361598.361617

Published: 01 December 1972 Publication History

PDF eReader

Abstract

A new linear search for hash tables whose increment step is a function of the key being addressed is presented. Comparisons with known methods are given, in terms of efficiency and computation complexity. In particular, the new method applies to tables of size n = 2^r. It allows full table searching, and practically eliminates primary clustering at a very low cost.

References

[1]

Morris, R. Scatter storage techniques. Comm. ACM 11, 1 (Jan. 1968), 38-43.

Digital Library

Google Scholar

[2]

Bell, J. R. The quadratic quotient method: a hash code eliminating econdary clustering. Comm. ACM 13, 2 (Feb. 1970), 107-109.

Digital Library

Google Scholar

[3]

Maurer, W.D. An improved hash code for scatter storage. Comm. ACM 11, 1 (Jan. 1968), 35-38.

Digital Library

Google Scholar

[4]

Radke, C.E. The use of quadratic residue research. Comm. ACM 13, 2 (Feb. 1970), 103-105.

Digital Library

Google Scholar

[5]

Day, A. Colin. Full table quadratic searching for scatter storage. Comm. ACM 13, 8 (Aug. 1970), 481-482.

Digital Library

Google Scholar

[6]

Bell, J. R. and Kaman, C. H. The linear quotient hash code. Comm. ACM 13, 11 (Nov. 1970), 675-677.

Digital Library

Google Scholar

Cited By

View all

Ausiello GGambosi G(2021)Theoretical Computer Science in Italy: The Early YearsIEEE Annals of the History of Computing10.1109/MAHC.2021.309987843:3(44-56)Online publication date: 1-Jul-2021
https://doi.org/10.1109/MAHC.2021.3099878
Tai YHuang SXia HZhou YTian X(2020)The mechanism of decrease in bearing capacity and performance evaluation of the yielding bolt in coal mineEnergy Science & Engineering10.1002/ese3.7558:9(3072-3086)Online publication date: 8-Jun-2020
https://doi.org/10.1002/ese3.755
Aoe J(1990)A compendium of key search referencesACM SIGIR Forum10.1145/101306.10130824:3(26-42)Online publication date: 1-Nov-1990
https://dl.acm.org/doi/10.1145/101306.101308
Show More Cited By

Recommendations

Full table quadratic searching for scatter storage

The quadratic residue search method for hash tables avoids much of the clustering experienced with a linear search method. The simple quadratic search only accesses half the table. It has been shown that when the length of the table is a prime of the ...
An improved hash code for scatter storage
Special 25th Anniversary Issue

Introduced is a hash coding method based on fixed-point division rather than multiplication or logical operations. This new method allows the hash table to have almost any length. Also a new method of handling collisions is discussed. Known as quadratic ...
Comment on weighted increment linear search for scatter tables

I would like to comment on an article by Fabrizio Luccio [1] which discusses weighted increment linear search for scatter tables.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 15, Issue 12

Dec. 1972

117 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/361598

Editor:
M. Stuart Lynn
Rice Univ., Houston, TX

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1972

Published in CACM Volume 15, Issue 12

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
290
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)9

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ausiello GGambosi G(2021)Theoretical Computer Science in Italy: The Early YearsIEEE Annals of the History of Computing10.1109/MAHC.2021.309987843:3(44-56)Online publication date: 1-Jul-2021
https://doi.org/10.1109/MAHC.2021.3099878
Tai YHuang SXia HZhou YTian X(2020)The mechanism of decrease in bearing capacity and performance evaluation of the yielding bolt in coal mineEnergy Science & Engineering10.1002/ese3.7558:9(3072-3086)Online publication date: 8-Jun-2020
https://doi.org/10.1002/ese3.755
Aoe J(1990)A compendium of key search referencesACM SIGIR Forum10.1145/101306.10130824:3(26-42)Online publication date: 1-Nov-1990
https://dl.acm.org/doi/10.1145/101306.101308
Lins CLins C(1990)Double HashingThe Modula-2 Software Component Library10.1007/978-1-4684-6371-2_7(101-125)Online publication date: 1990
https://doi.org/10.1007/978-1-4684-6371-2_7
Lodi ELuccio F(1985)Split sequence hash searchInformation Processing Letters10.1016/0020-0190(85)90079-120:3(131-136)Online publication date: Apr-1985
https://doi.org/10.1016/0020-0190(85)90079-1
Mühlbacher J(1981)Full table scatter storage parallel searchingParalleles Suchen über die gesamte Länge einer HashtabelleComputing10.1007/BF0224341926:1(9-18)Online publication date: Mar-1981
https://doi.org/10.1007/BF02243419
Bandyopadhyay S(1977)Comment on weighted increment linear search for scatter tablesCommunications of the ACM10.1145/359461.35947920:4(262-263)Online publication date: 1-Apr-1977
https://dl.acm.org/doi/10.1145/359461.359479
Santoro N(1976)Full table search by polynomial functionsInformation Processing Letters10.1016/0020-0190(76)90067-35:3(72-74)Online publication date: Aug-1976
https://doi.org/10.1016/0020-0190(76)90067-3
Maurer WLewis T(1975)Hash Table MethodsACM Computing Surveys10.1145/356643.3566457:1(5-19)Online publication date: 1-Mar-1975
https://dl.acm.org/doi/10.1145/356643.356645
Luccio F(1975)Parking Functions and Information StructuresTopics in Combinatorial Optimization10.1007/978-3-7091-3291-3_10(165-180)Online publication date: 1975
https://doi.org/10.1007/978-3-7091-3291-3_10
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Full table quadratic searching for scatter storage

An improved hash code for scatter storage

Comment on weighted increment linear search for scatter tables

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations