Fast hashing of variable-length text strings

ABSTRACT

Using only a few simple and commonplace instructions, this algorithm efficiently maps variable-length text strings small integers.

REFERENCES

• 1: Richard J. Cichelli, Minimal perfect hash functions made simple, Communications of the ACM, v.23 n.1, p.17-19, Jan. 1980 [doi>10.1145/358808.358813]
• 2: ldnnlt G_ 13 Ha~hin~ fllnctlnn.~_ Cnmnut I ?,q .q fl Q74~_ 2Fi5-27R
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: Meyer, C., and Matyas, S. Cryptography. John Wiley & Sons, New York, 1982.
• 5: Renzo Sprugnoli, Perfect hashing functions: a single probe retrieving method for static sets, Communications of the ACM, v.20 n.11, p.841-850, Nov. 1977 [doi>10.1145/359863.359887]
• 6: J. D. Ullman, A Note on the Efficiency of Hashing Functions, Journal of the ACM (JACM), v.19 n.3, p.569-575, July 1972 [doi>10.1145/321707.321722]

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design

Keywords:
scatter storage