処理時間より先に比較回数を見る
ハッシュ表の平均的な高速さは、キーの分布やハッシュ値の性質を前提にしています。この実験ではPythonの辞書へ300個のキーを登録し、同じキーを別のオブジェクトとして探します。一方は整数値のハッシュを使い、もう一方は全て同じハッシュ値0を返します。答えはどちらも整数の二乗です。実行時間だけを比べると装置や負荷の影響が混じるため、まずキーの等価比較が何回呼ばれたかを数えます。比較回数は実装固有ですが、強制した衝突の影響を調べる観測値になります。
ハッシュと等価性の契約を守る
Keyのvalueが同じなら等しいと判定し、同じ実験内で等しいキーは同じハッシュ値を返します。衝突させる場合も、この契約は破っていません。異なるキーが同じハッシュ値を持てることと、同じキーが毎回違う値を返してよいことは別です。登録後にvalueを変更すると、辞書内でキーを正しく探せなくなる危険があるため、この例では変更しません。collideの設定が異なるキーを一つの辞書で混ぜることも避けます。実験条件の切替と、同じ辞書内のキーの整合性を分けて扱います。
登録を終えてから観測を始める
コードでは辞書の構築後に比較回数を0へ戻します。これにより、登録時の衝突処理と検索時の衝突処理を混ぜず、読み取りの観測へ対象を絞ります。検索には同じオブジェクトを使い回さず、同じvalueを持つ新しいKeyを渡します。答えの配列を既知の二乗列と照合し、存在しない999の検索も行います。見つからない場合には候補をさらに調べることもあるため、成功する検索だけを対象にした計測と区別します。結果の件数と内容が一致しない試行は、比較回数が少なくても改善とは扱いません。
class Key:
comparisons = 0
def __init__(self, value, collide):
self.value, self.collide = value, collide
def __hash__(self):
return 0 if self.collide else hash(self.value)
def __eq__(self, other):
Key.comparisons += 1
return isinstance(other, Key) and self.value == other.value
def trial(collide):
mapping = {Key(i, collide): i * i for i in range(300)}
Key.comparisons = 0
answers = [mapping[Key(i, collide)] for i in range(300)]
assert answers == [i * i for i in range(300)]
assert Key(999, collide) not in mapping
return Key.comparisons
normal, collision = trial(False), trial(True)
assert collision > normal
print({"normal_equality_calls": normal, "colliding_equality_calls": collision})
同じハッシュ値でも誤答にはしない
衝突があっても、辞書はキーの等価性を確かめて区別するので、この例では同じ正しい値を返します。ハッシュ値だけで一致とみなし、本来異なるキーを一件へまとめる実装なら、速度以前に誤答です。ハッシュ表が内部でどのように候補を探すか、拡張のタイミングや細かい比較回数は、言語処理系と版によって変わります。ここでは特定の回数を正解として固定せず、衝突試行の比較回数が通常試行を上回ることだけをassertします。内部アルゴリズムの全てを推定する材料とはしません。
件数とキーの費用を変える
件数を30、300、1000へ変える場合には、同じ二試行で結果の一致を確かめ直します。比較関数自身が長い文字列を走査するなら、一回の比較も一定の費用とは限りません。ハッシュ計算、等価比較、メモリ確保、表の拡張を分けて考えると、平均O(1)という説明で省略された条件が見えます。外部から入力されるキーを大量に処理するサービスでは、悪い分布が入力で作られ得るかも重要です。ただし、この人工的なKeyクラスの結果を、文字列辞書の耐攻撃性の測定結果として一般化してはいけません。
観測を記録するときの限界
Pythonの版、件数、成功検索と失敗検索の内訳、実際の比較回数を記録します。性能を追加で測るなら、辞書の構築を含めるかどうかをそろえ、複数回の実行でばらつきを確認します。この教材の数値設定300は実験を小さく保つための条件で、性能の境界や推奨容量ではありません。等価比較カウンタの更新自体も実行時間を増やすため、計数付きの試行と本来の高速なキーを同じ速度として扱わないようにします。正しさ、観測のための負担、実装固有の結果を分けて報告します。