parameter r, the number of bits per block in the partition of the keys into blocks. Simple tabulation is limited to keys of a fixed length, because a different table of random values needs to be initialized for each position of a block in the keys. studies variations of tabulation hashing suitable for variable-length keys such as character strings. The general type of hashing scheme studied by Lemire uses a single table T indexed by the value of a block, regardless of its position within the key. However, the values from this table may be combined by a more complicated function than bitwise exclusive or. Lemire shows that no scheme of this type can be 3-independent. Nevertheless, he shows that it is still possible to achieve 2-independence. In particular, a tabulation scheme that interprets the values T[xi] (where xi is, as before, the ith block of the input) as the coefficients of a polynomial over a finite field and then takes the remainder of the resulting polynomial modulo another polynomial, gives a 2-independent hash function. Mixed Tabulation Mixed Tabulation hashing (and the less general Twisted Tabulation) were introduced by Dahlgaard and Thorup as a way to strengthen the properties of Tabulation hashing while keeping nearly the same performance. Mixed tabulation can be seen as a xor'ing a "Double Tabulation" hash function with a simple tabulation hash function. This turns out to have many nice properties even when parameters are chosen to make the mixed tabulation much faster than double tabulation The idea is to pick a number and hash to bits rather than just . This gives new "derived characters" which are hashed by a second hash function and the two values are xor'ed together. Formally we have and , both simple tabulation functions. If , then the mixed tabulation hash is defined to be The following example shows the algorithm with , and : int D = 2; uint128_t T1[8][256]; uint64_t T2[D][256]; // Fill tables with random values for (int j = 0; j < 256; j++) { for (int i = 0; i < 8; i++) T1[i][j] = getRandomUInt128(); for (int i = 0; i < D; i++) T2[i][j] = getRandomUInt64(); } // Compute Mixed Tabulation of x with D derived characters uint64_t hash(uint64_t x) { uint128_t v1v2 = 0; for (int i = 0; i < 8; i++) v1v2 ^= T1[i][(char)(x >> 8*i)]; uint64_t v1 = v1v2