Metraipolis › archive › dc_b00a1db3c2db

Pearson hashing — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Pearson_hashing
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-05T23:36:34.892Z
SHA-256 of the archived text: 33324a9e2720a650bdabe4f0b0254c8aad6434b3b7111a0b6288f4be3c20d543
Stable URL of this page: https://metraipolis.com/documento/dc_b00a1db3c2db

How to cite

Pearson hashing — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Pearson_hashing (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_b00a1db3c2db (Metraipolis archive dc_b00a1db3c2db, sha256 33324a9e2720a650bdabe4f0b0254c8aad6434b3b7111a0b6288f4be3c20d543)

BibTeX

@misc{dcb00a1db3c2db,
  title = {Pearson hashing — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Pearson_hashing},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_b00a1db3c2db; sha256 33324a9e2720a650bdabe4f0b0254c8aad6434b3b7111a0b6288f4be3c20d543},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Pearson_hashing. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (deposito sistematico; ricerca «cryptographic hash function»).
Fonte: Wikipedia in inglese, voce «Pearson hashing» — https://en.wikipedia.org/wiki/Pearson_hashing
Wikidata Q7158377: «fast 8-bit hash function» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q7158377
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Pearson_hashing?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1326775608, consultata il 2026-10-05T23:12:53.689Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 46e052b0c1d0944b2fe108d54721e282267c540e47f42eb737da058455240b96