公式解説にあるようなシンプルなハッシュ関数は、Schwartz-Zippel lemma を用いずとも衝突確率を抑えることができます。

多重集合 \(S, T\) が \(S \neq T\) を満たす場合、\(S\) に含まれる個数と \(T\) に含まれる個数が異なるような要素 \(e\) が存在します。 \(e\) 以外の要素に割り当てられたハッシュ値を固定すると、\(H(S) - H(T)\) は \(e\) に割り当てられたハッシュ値 \(x\) の関数として \(h + cx\) と表されます。 ここで \(h\) は何らかの定数で、\(c\) は \(e\) が \(S\) に含まれる個数と \(T\) に含まれる個数の差です。 \(N < P\) より \(c \neq 0 \pmod P\) ですから \(h + cx = 0 \pmod P \Leftrightarrow x = -h / c \pmod P\) と変形されて、\(x\) は \(0 , 1 , \dots , P-1\) から一様ランダムに選ぶので衝突確率は \(1 / P\) です。

法を巨大な素数ではなく \(2^{64}\) にした場合も十分に安全です。 先ほどと同様に議論すると、\(c\) が偶数の場合に \({} \bmod 2^{64}\) 上で逆元を持たないため、\(h + cx = 0 \pmod {2^{64}}\) を \(x = -h/c \pmod {2^{64}}\) に変形できないことが問題となります。 そこで、\(c\) が \(2\) で割り切れる回数を \(k\) とします。 \(h\) が \(2\) で \(k\) 回以上割り切れない場合、\(h + cx = 0\) となる \(x\) は存在しないため衝突の恐れはありません。 \(k\) 回以上割り切れる場合、\(x = -h/c \pmod {2^{64-k}}\) と変形されます。 この式を満たす \(x\) を引く確率は \(1/2^{64-k}\) ですが、\(k \leq \log_2 N\) であるため \(2^{64-k}\) は十分に大きいです。 同様の議論により、\(2^{32}\) を法にした場合に \(1/30000\) 程度の確率で衝突してしまうことも分かります。