r-bit and position values as indices into T, and combine the results using the exclusive or operation: h(x) = T[0][x0] ⊕ T[1][x1] ⊕ T[2][x2] ⊕ ... ⊕ T[t-1][xt-1]. Note that it is not valid to use the same table (e.g. T[0]) for each xi, since then the hash function would not be able to distinguish between strings with the same xis, but permuted differently. Code for a typical example with r = t = 8 and q = p = 64 is given below. // Secret table of random numbers uint64_t T[8][256]; for (int i = 0; i < 8; i++) for (int j = 0; j < 256; j++) T[i][j] = getRandomUInt64(); // Simple Tabulation Hash function uint64_t hash(uint64_t x) { uint64_t res = 0; for (int i = 0; i < 8; i++) res ^= T[i][(char)(x >> 8*i)]; return res; } History The first instance of tabulation hashing is Zobrist hashing, a method for hashing positions in abstract board games such as chess named after Albert Lindsey Zobrist, who published it in 1970. In this method, a random bitstring is generated for each game feature such as a combination of a chess piece and a square of the chessboard. Then, to hash any game position, the bitstrings for the features of that position are combined by a bitwise exclusive or. The resulting hash value can then be used as an index into a transposition table. Because each move typically changes only a small number of game features, the Zobrist value of the position after a move can be updated quickly from the value of the position before the move, without needing to loop over all of the features of the position. Tabulation hashing in greater generality, for arbitrary binary values, was later rediscovered by and studied in more detail by . Universality define a randomized scheme for generating hash functions to be universal if, for any two keys, the probability that they collide (that is, they are mapped to the same value as each other) is 1/m, where m is the number of values that the keys can take on. They defined a stronger property in the subsequent paper : a randomized scheme for generating hash functions is [[K-independent hashing|k-independent]] if, for every k-tuple of keys, and each possible k-tuple of values, the probability that those keys are mapped to those values is 1/mk. 2-independent hashing schemes are