Pearson hashing

Pearson hashing"Fast Hashing of Variable-Length Text Strings". Peter K. Pearson, "Communications of the ACM" 33(6), 677 (1990) — [http://portal.acm.org/citation.cfm?id=78978 ACM full text (requires subscription)] ] is a hash function designed for fast execution on processors with 8-bit registers. Given an input consisting of any number of bytes, it produces as output a single byte that is strongly dependent on every byte of the input. Its implementation requires only a few instructions, plus a 256-byte lookup table containing a permutation of the values 0 through 255.

This hash function is a CBC-MAC that uses an 8-bit random block cipher implemented via the permutation table. An 8-bit
block cipher has negligible cryptographic security, so the Pearson hash function is not cryptographically strong; but it offers these benefits:

* It is extremely simple.
* It executes quickly on resource-limited processors.
* There is no simple class of inputs for which collisions (identical outputs) are especially likely.
* Given a small, privileged set of inputs (e.g., reserved words for a compiler), the permutation table can be adjusted so that those inputs yield distinct hash values, producing what is called a perfect hash function.

The algorithm was originally described by the following pseudocode, which computes the hash of message "C" using the permutation table "T" and the auxiliary array "h":

h [0] := 0 for i in 1..n loop index := h [i-1] xor C [i] h [i] := T [index] end loop return h [n] In the Python programming language, the hash algorithm can be implemented as follows (assuming that permutation_table is defined externally):

def hash(input): h = 0 for ch in input: h = permutation_table [h ^ ord(ch)] return h

References