Editing Hash function (section)

=== Zobrist hashing ===
{{main | Tabulation hashing|Zobrist hashing}}
Tabulation hashing, more generally known as ''Zobrist hashing'' after [[Albert Lindsey Zobrist|Albert Zobrist]], is a method for constructing universal families of hash functions by combining table lookup with XOR operations. This algorithm has proven to be very fast and of high quality for hashing purposes (especially hashing of integer-number keys).<ref>{{citation|first=Albert L.|last=Zobrist|author-link= Albert Lindsey Zobrist|url=https://www.cs.wisc.edu/techreports/1970/TR88.pdf|title=A New Hashing Method with Application for Game Playing|series=Tech. Rep. 88|publisher=Computer Sciences Department, University of Wisconsin|location=Madison, Wisconsin|date=April 1970}}.</ref>

Zobrist hashing was originally introduced as a means of compactly representing chess positions in computer game-playing programs.  A unique random number was assigned to represent each type of piece (six each for black and white) on each space of the board.  Thus a table of 64×12 such numbers is initialized at the start of the program.  The random numbers could be any length, but 64 bits was natural due to the 64 squares on the board.  A position was transcribed by cycling through the pieces in a position, indexing the corresponding random numbers (vacant spaces were not included in the calculation) and XORing them together (the starting value could be 0 (the identity value for XOR) or a random seed).  The resulting value was reduced by modulo, folding, or some other operation to produce a hash table index.  The original Zobrist hash was stored in the table as the representation of the position.

Later, the method was extended to hashing integers by representing each byte in each of 4 possible positions in the word by a unique 32-bit random number.  Thus, a table of 2<sup>8</sup>×4 random numbers is constructed. A 32-bit hashed integer is transcribed by successively indexing the table with the value of each byte of the plain text integer and XORing the loaded values together (again, the starting value can be the identity value or a random seed). The natural extension to 64-bit integers is by use of a table of 2<sup>8</sup>×8 64-bit random numbers.

This kind of function has some nice theoretical properties, one of which is called ''3-tuple independence'', meaning that every 3-tuple of keys is equally likely to be mapped to any 3-tuple of hash values.