Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Fast hashing of variable-length text strings
Pearson P. Communications of the ACM33 (6):677-680,1990.Type:Article
Date Reviewed: Dec 1 1990

A simple, fast, interesting, apparently effective, and apparently new hashing function for strings of text is based on iterated use of the exclusive OR (XOR) operation and avoids the use of multiplication, division, and long register shifts; it is therefore suitable for use on small microprocessors. The function’s main defect is that it requires storage of an auxiliary array T[256] of bytes: T contains a pseudorandom permutation of the codes 0–255. The function normally hashes into the range 0–255 but can be modified to yield smaller or larger ranges; a judicious choice of the array T even yields minimal perfect hashing in some cases. Since standard hashing schemes can be modified to deal with variable-length strings just as this approach does, the method’s main interest appears to be its ease of use on microprocessors; “Fast hashing for microprocessors” would thus have been a preferable title.

Reviewer:  W. F. Smyth Review #: CR123455
Bookmark and Share
 
Hash-Table Representations (E.2 ... )
 
 
Probabilistic Algorithms (Including Monte Carlo) (G.3 ... )
 
 
Sorting And Searching (F.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Hash-Table Representations": Date
On the use of extendible hashing without hashing
Bechtold U., Kuspert K. Information Processing Letters 19(1): 21-26, 1984. Type: Article
Mar 1 1985
Analysis of new variants of coalesced hashing
Chen W., Vitter J. (ed) ACM Transactions on Database Systems 9(4): 616-645, 1984. Type: Article
Jun 1 1985
A polynomial time generator for minimal perfect hash functions
Sager T. Communications of the ACM 28(5): 523-532, 1985. Type: Article
Jun 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy