- 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 ahash 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-bytelookup table containing apermutation of the values 0 through 255.This hash function is a
CBC-MAC that uses an 8-bitrandom block cipher implemented via the permutation table. An 8-bitblock cipher has negligible cryptographic security, so the Pearson hash function is notcryptographically 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 word s for acompiler ), the permutation table can be adjusted so that those inputs yield distinct hash values, producing what is called aperfect 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 thatpermutation_table
is defined externally):References
Wikimedia Foundation. 2010.