Pythonの弱いhashがたくさん衝突する例

三か月ぐらいブログをサボっていました。お久しぶりです。

以前Pythonを使う必要があったのですが、組込みのハッシュ関数が弱すぎ、大変悲惨な目にあったので、その記録です。

Pythonの組込みのハッシュ関数では、hash(-2)hash(-1)がどちらも-2となります*1

-1-2という、よく使う数のハッシュ値が衝突するのは残念な感じですが、問題はこれだけではありません。 (仕様なのか実装依存なのか知りませんが、)タプルのハッシュ値は、要素のハッシュ値をハッシュ化した値になるようです。 これを使うと、ハッシュ値が衝突する組み合わせをいくらでも作り出すことができます。

具体的には、(-1,-1)(-1,-2)(-2,-1)(-2,-2)ハッシュ値はすべて3713082714462658231になります(python 3.6.9にて確認)*2。 タプルの要素数が10であれば、1024個もの全く同じハッシュ値を持つタプルが簡単に作れることになります。 これはハッシュを用いた辞書の性能を著しく低下させます。

以下の非常に単純なベンチマークを動かす時間を測ってみます。 計測はWSL上で行い、timeコマンドで出力されるuser時間を使用しました([1, 2]の場合はsys時間がuser時間の半分くらいありましたが……)。 計測は各パラメータにつき6回行いました。

import sys,itertools

size = int(sys.argv[1])
print(size)

dic = { t: t[0] for t in itertools.product([1, 2], repeat=size) }

f:id:lpha_z:20210801063404p:plain
図1: ベンチマークの実行時間の測定結果

図1に測定結果を示します。各点は6回計測の平均値であり、エラーバーの長さは不偏分散の平方根です。 縦軸は対数軸です。横軸はsizeをそのままとっているため、処理量に対して対数軸です。

[1, 2]の場合は傾きが1の直線に乗っていることから、Θ(N)の実行時間となっていることが分かります。 つまり、辞書への追加一回当たりの平均時間計算量がΘ(1)であることを意味しています。

一方、[-1, -2]の場合は傾きが2の直線に乗っていることから、Θ(N2)の実行時間になっていることが分かります。 つまり、辞書への追加一回当たりの平均時間計算量がΘ(N)であることを意味しています。

このように、要素の違いが-1-2の違いのみであるtupleのペアはハッシュが衝突するため、こういったものを辞書のキーに使用すると性能が大きく低下することがあり注意が必要です。

*1:CPythonがC言語の慣習に従い返り値-1をエラー用に使用していることに由来する?

*2:python 3.8.0以降では960947337673586213になるようですが、いずれも同じという点では同じです。