# Splitting the output of a wide hash in lieu of multiple independent hashes

Certain algorithms require two independent hash functions. An optimization I've seen is to split the output of a wide hash function and use the parts instead of the two independent hash functions of shorter output.

For instance, double hashing is often used as a technique to compute the k independent indexes required by a Bloom filter rather than using k independent hashes, but this is often optimized to use a single wide hash and splitting its output. E.g., Google's Guava Bloom filter operates in this way using 128-bit Murmur3.

Alas, I've not been able to find any literature that addresses when it may be safe to do this. I.e., what properties should the wide hash function have for this to be acceptable? Is meeting the bit independence criterion sufficient?

• Splitting one hash to two outputs is called "two-for-one hashing" in T D Ahle et al. The Power of Hashing with Mersenne Primes, though it seems like the term is only used in the paper so far. Feb 22, 2022 at 3:28
• @pcpthm thank you. I'll have to spend some time digesting the paper. Feb 23, 2022 at 22:27

Here is a justification why it is a reasonable/plausible thing to do. Suppose our hash function is a uniform random function $$h:\{0,1\}^m \to \{0,1\}^{2b}$$. Define $$h_0(x)$$ to be the first half of $$h(x)$$ and $$h_1(x)$$ to be the second half of $$h(x)$$. Then $$h_0,h_1$$ are independent uniform random functions with signature $$\{0,1\}^m \to \{0,1\}^b$$. It follows that if our hash function is indistinguishable from a uniform random function, then using its output in this way will be indistinguishable from using two independent smaller hash functions.