In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It was first studied in the form of Zobrist hashing for computer games; later work by Carter and Wegman extended this method to arbitrary fixed-length keys. Generalizations of tabulation hashing have also been developed that can handle variable-length keys such as text strings. Despite its simplicity, tabulation hashing has strong theoretical properties that distinguish it from some other hash functions. In particular, it is 3-independent: every 3-tuple of keys is equally likely to be mapped to any 3-tuple of hash values. However, it is not 4-independent. More sophisticated but slower variants of tabulation hashing extend the method to higher degrees of independence. Because of its high degree of independence, tabulation hashing is usable with hashing methods that require a high-quality hash function, including hopscotch hashing, cuckoo hashing, and the MinHash technique for estimating the size of set intersections. Method The basic idea is as follows: First, divide the key to be hashed into smaller "blocks" of a chosen length. Then, create a set of lookup tables, one for each block, and fill them with random values. Finally, use the tables to compute a hash value for each block, and combine all of these hashes into a final hash value using the bitwise exclusive or operation. More formally: Let p be the number of bits in a key to be hashed, and q be the number of bits desired in an output hash function. Choose a block size r ≤ p; the choice of block size controls the tradeoff between time and memory usage, so it should be made so that the tables are not too large, e.g., so that the tables fit into the computer's cache memory. Smaller blocks use less memory but slow down the hash function. Compute t = ceil(p/r), the number of r-bit blocks needed to represent a key. Create a two-dimensional 2r × t array, T, and fill it with random q-bit numbers. Now T can be used to compute the hash value h(x) of any given key x. To do so, partition x into r-bit values, where x0 consists of the lowest r bits of x, x1 consists of the next r bits, etc. For example, if r = 8, then xi is just the ith byte of x. Then, use these