実験・実装 · 基礎から応用へ

衝突率を変えてハッシュ表を試す

同じ答えを返す二つのキー集合で、衝突が等価比較の回数へ与える影響を観察します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 処理時間より先に比較回数を見る
  2. ハッシュと等価性の契約を守る
  3. 登録を終えてから観測を始める
  4. 同じハッシュ値でも誤答にはしない
  5. 件数とキーの費用を変える
  6. 観測を記録するときの限界
  7. この記事をロゲイアに質問する理解を確かめる

処理時間より先に比較回数を見る

ハッシュ表の平均的な高速さは、キーの分布やハッシュ値の性質を前提にしています。この実験ではPythonの辞書へ300個のキーを登録し、同じキーを別のオブジェクトとして探します。一方は整数値のハッシュを使い、もう一方は全て同じハッシュ値0を返します。答えはどちらも整数の二乗です。実行時間だけを比べると装置や負荷の影響が混じるため、まずキーの等価比較が何回呼ばれたかを数えます。比較回数は実装固有ですが、強制した衝突の影響を調べる観測値になります。

ハッシュと等価性の契約を守る

Keyのvalueが同じなら等しいと判定し、同じ実験内で等しいキーは同じハッシュ値を返します。衝突させる場合も、この契約は破っていません。異なるキーが同じハッシュ値を持てることと、同じキーが毎回違う値を返してよいことは別です。登録後にvalueを変更すると、辞書内でキーを正しく探せなくなる危険があるため、この例では変更しません。collideの設定が異なるキーを一つの辞書で混ぜることも避けます。実験条件の切替と、同じ辞書内のキーの整合性を分けて扱います。

登録を終えてから観測を始める

コードでは辞書の構築後に比較回数を0へ戻します。これにより、登録時の衝突処理と検索時の衝突処理を混ぜず、読み取りの観測へ対象を絞ります。検索には同じオブジェクトを使い回さず、同じvalueを持つ新しいKeyを渡します。答えの配列を既知の二乗列と照合し、存在しない999の検索も行います。見つからない場合には候補をさらに調べることもあるため、成功する検索だけを対象にした計測と区別します。結果の件数と内容が一致しない試行は、比較回数が少なくても改善とは扱いません。

Python 3
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は実験を小さく保つための条件で、性能の境界や推奨容量ではありません。等価比較カウンタの更新自体も実行時間を増やすため、計数付きの試行と本来の高速なキーを同じ速度として扱わないようにします。正しさ、観測のための負担、実装固有の結果を分けて報告します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ