__hash__の戻り値が0固定のオブジェクトを、dictのキーにしてみる

Pythonのdictのオープンアドレス法のハッシュテーブルで実装されており、GetとSetの計算量は O(1) である。
(Pythonのdictの実装はこの記事が詳しい)
しかし、O(1) なのは異なるキーから同じハッシュ値が頻繁に生成されないことが前提である。
ここでは、全てのキーから同じハッシュ値が生成する最悪ケースで実験してみる。

import time


class BadKey:
    name = 'bad'

    def __init__(self, key):
        self.key = key

    def __hash__(self):
        return 0

    def __eq__(self, o):
        return self.key == o.key

    def __repr__(self):
        return self.key


class GoodKey:
    name = 'good'

    def __init__(self, key):
        self.key = key

    def __hash__(self):
        return hash(self.key)

    def __eq__(self, o):
        return self.key == o.key

    def __repr__(self):
        return self.key


N = 10 ** 4

for Key in [BadKey, GoodKey]:
    d = {}
    start = time.time()
    ret = []
    for i in range(N):
        start = time.time()
        d[Key(str(i))] = True
        ret.append(f'{time.time() - start}\n')

    with open(f'{Key.name}_insert.txt', 'w') as f:
        f.writelines(ret)

    ret = []
    for i in range(N):
        start = time.time()
        a = d[Key(str(i))]
        ret.append(f'{time.time() - start}\n')

    with open(f'{Key.name}_get.txt', 'w') as f:
        f.writelines(ret)

Pythonは__hash__が実装されたオブジェクトであれば、dictのkeyとすることができる。
ただし、__eq__も実装しなければ、Getの時にKeyErrorとなるのでそちらも実装しておく。
BadKeyの__hash__の戻り値は、0固定なので2回以上Setしたら必ずハッシュ衝突するようにしている。

BadKeyの1回目のSetはハッシュテーブルの0番目の要素に格納されて終了だが、2回目は1回目とハッシュ衝突するため再計算が発生し、
再計算されたハッシュ値のインデックスの要素に格納される。
3回目以降のSetも流れは同じで、N回目のSetは N-1 回のハッシュ再計算が必要となる。
回数が増えるごとに1回ずつ増えるので、Setにかかる時間は線形で上昇していくと予想される。
Getも基本的には同じだ。

GoodKeyはハッシュ衝突は無視できる程度にしか起こらないはずなので、回数に関係なくほぼ一定の処理時間と予想される。
1万個の異なるキーをSetして、Setした順番にGetした場合の処理時間を全て計測する。

実際にコードの出力結果をグラフとしてプロットしたのが以下となる。
外れ値を除くとGet, Setともに、BadKeyの処理時間は、予想取り線形に上昇しており、
GoodKeyはほぼ一定に抑えられている。(グラフの見た目だけでなく実数でも確認

Pythonのdictを使っていて、実際にGetやSetが遅くなる現象はなかなか経験できないと思う。
__hash__やハッシュ関数を自前で実装していて、性能が悪いときは疑ってみるといいかもしれない。