Editing Pearson hashing

{{short description|Fast 8-bit hash function}}
'''Pearson hashing''' is a [[non-cryptographic hash function]] designed for fast execution on processors with 8-bit [[processor register|register]]s. 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.<ref name=acmref>{{Citation
 |title= Fast Hashing of Variable-Length Text Strings
 |first= Peter K.
 |last= Pearson
 |journal= [[Communications of the ACM]]
 |volume= 33
 |issue= 6
 |pages= 677–680
 |date= June 1990
 |url= http://cs.mwsu.edu/~griffin/courses/2133/downloads/Spring11/p677-pearson.pdf
 |issn= 
 |doi= 10.1145/78973.78978
 |access-date= 2013-07-13
 |archive-url= https://web.archive.org/web/20120704025921/http://cs.mwsu.edu/~griffin/courses/2133/downloads/Spring11/p677-pearson.pdf
 |archive-date= 2012-07-04
 |url-status= dead
 }}</ref>

This hash function is a [[CBC-MAC]] that uses an 8-bit [[substitution cipher]] implemented via the [[S-box|substitution table]]. An 8-bit [[cipher]] has negligible cryptographic security, so the Pearson hash function is not [[cryptographically strong]], but it is useful for implementing [[hash table]]s or as a [[Checksum|data integrity check code]], for which purposes it offers these benefits:

* It is extremely simple.
* It executes quickly on resource-limited processors.
* There is no simple class of inputs for which [[hash collision|collision]]s (identical outputs) are especially likely.
* Given a small, privileged set of inputs (e.g., [[reserved word]]s 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]].
*  Two input strings differing by exactly one character never collide.<ref name=univ>{{Citation
 |title= The universality of iterated hashing over variable-length strings
 |first= Daniel
 |last= Lemire
 |journal= [[Discrete Applied Mathematics]]
 |volume= 160
 |issue= 4–5
 |pages= 604–617 
 |date= 2012
 |arxiv= 1008.1715|doi= 10.1016/j.dam.2011.11.009}}</ref> E.g., applying the algorithm on the strings ABC and AEC will never produce the same value.

One of its drawbacks when compared with other hashing algorithms designed for [[8-bit processor]]s is the suggested 256 byte lookup table, which can be prohibitively large for a small [[microcontroller]] with a program memory size on the order of hundreds of bytes. A workaround to this is to use a simple permutation function instead of a table stored in program memory. However, using a too simple function, such as <code>T[i] = 255-i</code>, partly defeats the usability as a hash function as [[anagram]]s will result in the same hash value; using a too complex function, on the other hand, will affect speed negatively. Using a function rather than a table also allows extending the block size. Such functions naturally have to be [[bijective]], like their table variants.

The algorithm can be described by the following [[pseudocode]], which computes the hash of message&nbsp;''C'' using the permutation table&nbsp;''T'':

 '''algorithm''' pearson hashing '''is'''
     h := 0
 
     '''for each''' c '''in''' C '''loop'''
         h := T[ h '''xor''' c ]
     '''end loop'''
 
     '''return''' h

The hash variable ({{code|h}}) may be initialized differently, e.g. to the length of the data ({{code|C}}) modulo 256.

== Example implementations ==

===[[C Sharp (programming language)|C#]], 8-bit ===
<syntaxhighlight lang="csharp" line>
public class PearsonHashing
{
    public static byte Hash(string input)
    {
        byte[] T = { /* Permutation of 0-255 */ };
        
        byte hash = 0;
        byte[] bytes = Encoding.UTF8.GetBytes(input);

        foreach (byte b in bytes)
        {
            hash = T[hash ^ b];
        }

        return hash;
    }
}
</syntaxhighlight>

==See also==
* [[Non-cryptographic hash functions]]

==References ==
<references/>

[[Category:Error detection and correction]]
[[Category:Hash function (non-cryptographic)]]
[[Category:Articles with example pseudocode]]