Pearson hashing 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 can be described by the following pseudocode, which computes the hash of message C using the permutation table T:
h := 0
for each c in C loop index := h xor c h := T
end loop
return h
Famous quotes containing the word pearson:
“...we shall never be the people we should and might be until we have learned that it is the first and most important business of a nation to protect its women, not by any puling sentimentality of queenship, chivalry or angelhood, but by making it possible for them to earn an honest living.”
—Katharine Pearson Woods (1853–1923)