NIST

Pearson's hash

(algorithm)

Definition: A hash function that uses an auxiliary array, but no shift or exclusive-or (xor) operations.

Generalization (I am a kind of ...)
hash function.

Note: This hash function may be particularly fast on computers that don't have hardware support for shifting or xor.

Careful choice of the auxiliary table allows construction of a perfect hashing function, a minimal perfect hashing function, or even an order-preserving minimal perfect hashing function.

Author: PEB

Implementation

(C and Python). (Basic).

More information

Peter K. Pearson, Fast Hashing of Variable-Length Text Strings, CACM, 33(6):677-680, June 1990.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 11 February 2019.
HTML page formatted Tue Feb 12 10:57:43 2019.

Cite this as:
Paul E. Black, "Pearson's hash", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 11 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/pearsonshash.html