Multiply-shift hashing

The multiply-shift family of Dietzfelbinger, Hagerup, Katajainen and Penttonen [DHKP97] hashes a w-bit word x to M bits with a random odd w-bit multiplier a: it keeps the top M bits of the low w bits of a x, that is (a x mod 2 ^ w) / 2 ^ (w - M). On a machine this is one multiplication and one shift. It is 2 / 2 ^ M-universal: twice the optimal bound.

The proof counts multipliers. Write the difference of two distinct inputs as 2 ^ s z' with z' odd. If the inputs collide, the top M bits of a x and a y agree, so a (x - y) mod 2 ^ w lies within 2 ^ (w - M) of 0 modulo 2 ^ w. As a ranges over the odd multipliers, a (x - y) mod 2 ^ w is 2 ^ s times an odd residue modulo 2 ^ (w - s), each attained by 2 ^ s multipliers, and at most 2 ^ (w - M - s) of those residues lie near 0.

Main definitions

• Cslib.Probability.multiplyShift: multiply-shift hashing with the multiplier 2 b + 1.

Main results

• Cslib.Probability.card_filter_multiplyShift_eq_le: at most 2 ^ (w - M) of the 2 ^ (w - 1) multipliers make two distinct inputs collide.
• Cslib.Probability.isUniversalHash_multiplyShift: multiply-shift is 2 / 2 ^ M-universal.

References

• M. Dietzfelbinger, T. Hagerup, J. Katajainen, M. Penttonen, A Reliable Randomized Algorithm for the Closest-Pair Problem, Lemma 2.4.

def Cslib.Probability.multiplyShift (w M : ℕ) (b : Fin (2 ^ (w - 1))) (x : Fin (2 ^ w)) : ℕ

Multiply-shift hashing of a w-bit word to M bits, with the odd multiplier 2 b + 1: the top M of the low w bits of the product.

theorem Cslib.Probability.card_filter_multiplyShift_eq_le {w M : ℕ} (hw : 0 < w) (hM : M ≤ w) {x y : Fin (2 ^ w)} (hxy : x ≠ y) : {b : Fin (2 ^ (w - 1)) | multiplyShift w M b x = multiplyShift w M b y}.card ≤ 2 ^ (w - M)

Multiply-shift collisions: at most 2 ^ (w - M) of the 2 ^ (w - 1) odd multipliers make two distinct w-bit inputs collide.

theorem Cslib.Probability.isUniversalHash_multiplyShift {w M : ℕ} (hw : 0 < w) (hM : M ≤ w) : IsUniversalHash (PMF.uniformOfFintype (Fin (2 ^ (w - 1)))) (multiplyShift w M) (2 / 2 ^ M)

Multiply-shift is 2 / 2 ^ M-universal ([DHKP97], Lemma 2.4): for a uniform odd w-bit multiplier, two distinct w-bit inputs have the same top M bits of product with probability at most 2 / 2 ^ M.