Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence

摘要

Simple tabulation dates back to Zobrist in 1970 who used it for game playing programs. Keys are viewed as consisting of c characters from some alphabet A. We initialize c tables h_0, ..., h_c-1 mapping characters to random hash values. A key x=(x_0, ..., x_c-1) is hashed to h_0[x_0] xor h_1[x_1] xor ... xor h_c-1[x_c-1]. The scheme is extremely fast when the character hash tables h_i are in cache. Simple tabulation hashing is not even 4-independent, but we show here that if we apply it twice, then we do get high independence. First we hash to some intermediate keys that are 6 times longer than the original keys, and then we hash the intermediate keys to the final hash values. The intermediate keys have d=6c characters from A. We can then view the hash function as a highly unbalanced bipartite graph with keys on one side, each with edges to d output characters on the other side. We show that this graph has nice expansion properties, and from that it follows that if we perform another level of simple tabulation on the intermediate keys, then the composition is a highly independent hash function. More precisely, the independence we get is |A|Omega(1/c). In our O-notation, we view both A and c is going to infinity, but with c much smaller than |A|. Our space is O(c|A|) and the hash function is evaluated in O(c) time. Siegel [FOCS'89, SICOMP'04] has proved that with this space, if the hash function is evaluated in o(c) time, then the independence can only be o(c), so our evaluation time is best possible for Omega(c) independence-our independence is much higher if c=|A|o(1/c). Siegel used O(c)c evaluation time to get the same independence with similar space. Siegel's main focus was c=O(1), but we are exponentially faster when c=omega(1). Applying our scheme recursively, we can increase our independence to |A|Ω(1) with o(clog c) evaluation time. Compared with Siegel's scheme this is both faster and higher independence. Siegel states about his scheme tha- it is "far too slow for any practical application". Our scheme is trivial to implement, and it does provide realistic implementations of 100-independent hashing for, say, 32-bit and 64-bit keys.