Tabulation hashing

In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It is simple and fast enough to be usable in practice, and has theoretical properties that (in contrast to some other universal hashing methods) make it usable with linear probing, cuckoo hashing, and the MinHash technique for estimating the size of set intersections.

Method

Let p denote the number of bits in a key to be hashed, and q denote the number of bits desired in an output hash function. Choose another number r, less than or equal to p; this choice is arbitrary, and controls the tradeoff between time and memory usage of the hashing method: smaller values of r use less memory but cause the hash function to be slower. Compute t by rounding p/r up to the next larger integer; this gives the number of r-bit blocks needed to represent a key. For instance, if r = 8, then an r-bit number is a byte, and t is the number of bytes per key. The key idea of tabulation hashing is to view a key as a vector of t r-bit numbers, use a lookup table filled with random values to compute a hash value for each of the r-bit numbers representing a given key, and combine these values with the bitwise binary exclusive or operation. The choice of r should be made in such a way that this table is not too large; e.g., so that it fits into the computer's cache memory.

The initialization phase of the algorithm creates a two-dimensional array T of dimensions 2^r by t, and fills the array with random q-bit numbers. Once the array T is initialized, it 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 x₀ consists of the low order r bits of x, x₁ consists of the next r bits, etc. For example, with the choice r = 8, x_i is just the ith byte of x. Then, use these values as indices into T and combine them with the exclusive or operation: Nevertheless, despite only being 3-independent, tabulation hashing provides the same constant-time guarantee for linear probing.

Cuckoo hashing, another technique for implementing hash tables, guarantees constant time per lookup (regardless of the hash function). Insertions into a cuckoo hash table may fail, causing the entire table to be rebuilt, but such failures are sufficiently unlikely that the expected time per insertion (using either a truly random hash function or a hash function with logarithmic independence) is constant. With tabulation hashing, on the other hand, the best bound known on the failure probability is higher, high enough that insertions cannot be guaranteed to take constant expected time. Nevertheless, tabulation hashing is adequate to ensure the linear-expected-time construction of a cuckoo hash table for a static set of keys that does not change as the table is used.

Extensions

Although tabulation hashing as described above ("simple tabulation hashing") is only 3-independent, variations of this method can be used to obtain hash functions with much higher degrees of independence. Siegel (2004) uses the same idea of using exclusive or operations to combine random values from a table, with a more complicated algorithm based on expander graphs for transforming the key bits into table indices, to define hashing schemes that are k-independent for any constant or even logarithmic value of k. However, the number of table lookups needed to compute each hash value using Siegel's variation of tabulation hashing, while constant, is still too large to be practical, and the use of expanders in Siegel's technique also makes it not fully constructive. Thorup (2013) provides a scheme based on tabulation hashing that reaches high degrees of independence more quickly, in a more constructive way. He observes that using one round of simple tabulation hashing to expand the input keys to six times their original length, and then a second round of simple tabulation hashing on the expanded keys, results in a hashing scheme whose independence number is exponential in the 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. Lemire (2012) 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[x_i] (where x_i 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.

References

• Carter, J. Lawrence; Wegman, Mark N. (1979), "Universal classes of hash functions", Journal of Computer and System Sciences, 18 (2): 143–154, doi:10.1016/0022-0000(79)90044-8, MR 0532173.
• Lemire, Daniel (2012), "The universality of iterated hashing over variable-length strings", Discrete Applied Mathematics, 160: 604–617, arXiv:1008.1715, doi:10.1016/j.dam.2011.11.009, MR 2876344.
• Pagh, Anna; Pagh, Rasmus; Ružić, Milan (2009), "Linear probing with constant independence", SIAM Journal on Computing, 39 (3): 1107–1120, doi:10.1137/070702278, MR 2538852.
• Pătraşcu, Mihai; Thorup, Mikkel (2010), "On the k-independence required by linear probing and minwise independence" (PDF), Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), Bordeaux, France, July 6-10, 2010, Part I, Lecture Notes in Computer Science, vol. 6198, Springer, pp. 715–726, doi:10.1007/978-3-642-14165-2_60, MR 2734626.
• Pătraşcu, Mihai; Thorup, Mikkel (2012), "The power of simple tabulation hashing", Journal of the ACM, 59 (3): Art. 14, arXiv:1011.5200, doi:10.1145/2220357.2220361, MR 2946218.
• Siegel, Alan (2004), "On universal classes of extremely random constant-time hash functions", SIAM Journal on Computing, 33 (3): 505–543, doi:10.1137/S0097539701386216, MR 2066640.
• Thorup, M. (2013), "Simple tabulation, fast expanders, double tabulation, and high independence", Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pp. 90–99, doi:10.1109/FOCS.2013.18, MR 3246210.
• Wegman, Mark N.; Carter, J. Lawrence (1981), "New hash functions and their use in authentication and set equality", Journal of Computer and System Sciences, 22 (3): 265–279, doi:10.1016/0022-0000(81)90033-7, MR 0633535.
• Zobrist, Albert L. (April 1970), A New Hashing Method with Application for Game Playing (PDF), Tech. Rep. 88, Madison, Wisconsin: Computer Sciences Department, University of Wisconsin.