Linear Hashing: A New Tool for File and Table Addressing.

Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223

@inproceedings{DBLP:conf/vldb/Litwin80,
  author    = {Witold Litwin},
  title     = {Linear Hashing: A New Tool for File and Table Addressing},
  booktitle = {Sixth International Conference on Very Large Data Bases, October
               1-3, 1980, Montreal, Quebec, Canada, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1980},
  pages     = {212-223},
  ee        = {db/conf/vldb/Litwin80.html},
  crossref  = {DBLP:conf/vldb/80},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Linear hashing is a hashing in which the address space may grow or shrink dynamically. A file or a table may then support any number of insertions or deletions without access or memory load performance deterioration. A record in the file is, in general, found in one access, while the load may stay practically constant up to 90 %. A record in a table is found in a mean of 1.7 accesses, while the load is constantly 80 %. No other algorithms attaining such a performance are known.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Sixth International Conference on Very Large Data Bases, October 1-3, 1980, Montreal, Quebec, Canada, Proceedings. IEEE Computer Society 1980
Contents

References

[AHO75]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
[BLA77]: Ian F. Blake, Alan G. Konheim: Big Buckets Are (Are Not) Better! J. ACM 24(4): 591-606(1977)
[CAR73]: Carter Bays: The Reallocation of Hash-Coded Tables. Commun. ACM 16(1): 11-14(1973)
[COM79]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[FAG78]: Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979)
[GHO75]: Sakti P. Ghosh, Vincent Y. Lum: Analysis of Collisions when Hashing by Division. Inf. Syst. 1(1): 15-22(1975)
[GUI72]: ...
[GUI73]: ...
[KAR79]: ...
[KNO71]: Gary D. Knott: Expandable Open Addressing Hash Table Storage and Retrieval. SIGFIDET Workshop 1971: 187-206
[KNU74]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
[LAR78]: Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978)
[LAR80]: Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232
[LIT77]: ...
[LIT77a]: ...
[LIT78]: ...
[LIT78a]: Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523
[LIT79]: ...
[LIT79a]: ...
[LIT80]: Witold Litwin: Linear Hashing: A new Algorithm for Files and Tables Addressing. ICOD 1980: 260-276
[LUM73]: Vincent Y. Lum: General Performance Analysis of Key-to-Address Transformation Methods Using an Abstract File Concept. Commun. ACM 16(10): 603-612(1973)
[MAR77]: ...
[ROS77]: Arnold L. Rosenberg, Larry J. Stockmeyer: Hashing Schemes for Extendible Arrays. J. ACM 24(2): 199-221(1977)
[SCH73]: Ben Shneiderman: Optimum Data Base Reorganization Points. Commun. ACM 16(6): 362-365(1973)
[SHO79]: ...
[SPR77]: Renzo Sprugnoli: Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets. Commun. ACM 20(11): 841-850(1977)