mathematics

Pearson hashing

Pearson hashing is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Pearson hashing rather than just read about it. In short: Pearson hashing is a non-cryptographic 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.

Key takeaways

Pearson hashing belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Pearson hashing to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Pearson hashing from memory before moving on to harder problems.

Reference excerpt

Pearson hashing is a non-cryptographic 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 substitution cipher implemented via the 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 tables or as a 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 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. Two input strings differing by exactly one character never collide. 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 processors 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 T[i] = 255-i, partly defeats the usability as a hash function as anagrams 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 C using the permutation table 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 (h) may be initialized differently, e.g. to the length of the data (C) modulo 256.

Example implementations

C#, 8-bit

See also Non-cryptographic hash functions

References

Worked examples

Example 1 — a first encounter with Pearson hashing

Start with the simplest possible case. Write down what Pearson hashing claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Pearson hashing before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Pearson hashing ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Pearson hashing

In research: Pearson hashing appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Pearson hashing in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Pearson hashing is common in secondary-school and first-year university syllabi. It links to neighbouring topics Error detection and correction, Hash function (non-cryptographic), so understanding it makes those chapters shorter.
In everyday life: Look for Pearson hashing outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Pearson hashing in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Pearson hashing means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Pearson hashing out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Pearson hashing in simple terms?

Why does Pearson hashing matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Pearson hashing?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Pearson hashing.