ユニバーサルハッシュの実装で整数オーバーフローが発生する

Question

私のペットプロジェクトの1つとして、任意の数の異なる整数ハッシュを作成したいと考えています。少しの研究の後、私は普遍的なハッシュが行く方法だと思った。しかし、私は（numpy）の実装に苦しんでいます。私はハッシュファミリh(a,b)(x) = ((a * x + b) mod p) mod mを使用しようとしており、私のxはuint32の範囲内であればどこでもかまいません。 p >= max(x)とa, b < pを選択すると、最悪の場合、a * x + bはuint32だけでなくuint64もオーバーフローします。私はこの問題を解決する実装を見つけようとしましたが、モジュロ演算をスピードアップする巧妙な方法しか見つからず、オーバーフローについては何も見つかりませんでした。

これを実装する方法についてのご意見をいただければ幸いです。ありがとう:-)

Answer 1

(x + y) % z == ((x % z) + (y % z)) % zだから、合計を行う前に係数を取ることができる：

1. はuint64型にaとxをキャスト。 （2つのuint32を乗算すると、uint64は決してオーバーフローしません）。
2. 計算h = (a * x) % p + b
3. 返信(h - p) if h > p else h。 （代替：返信h % p）