Pearson hashing

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 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 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 that permutation_table is defined externally):

def hash(input): h = 0 for ch in input: h = permutation_table [h ^ ord(ch)] return h

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • Хеширование — Хеш функция, отображающая множество имён в множество натуральныых чисел Хеширование (иногда «хэширование», англ. hashing)  преобразование по детерменированному алгоритму входного массива данных прои …   Википедия

  • Perfect hash function — A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. A perfect hash function has many of the same applications as other hash functions, but with the advantage that no… …   Wikipedia

  • List of algebraic coding theory topics — This is a list of algebraic coding theory topics. ARQ[disambiguation needed  ] Adler 32 BCH code BCJR algorithm Berger code Berlekamp Massey algo …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia

  • Collaborative filtering — (CF) is the process of filtering for information or patterns using techniques involving collaboration among multiple agents, viewpoints, data sources, etc. Applications of collaborative filtering typically involve very large data sets.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”