ハッシュ検索の中身の複雑さによる計算速度の違いについて

やりたいこと

ハッシュ検索は計算オーダーがO(1)と言われているが，
hash検索が中身の複雑さ（例えば，単語やハッシュ値など）に応じて，計算速度が変化するのかを確認したい

hashの中身がintの場合

number.py

import time

if __name__ == '__main__':
    N = 100000
    dict = {i: None for i in range(N)}

    start = time.time()
    for i in range(N):
        if i in dict:
            pass

    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
# elapsed_time:0.010960102081298828[sec]

hashの中身が複雑な場合

今回は中身を複雑にするために，hashで作成することする

hash.py

import hashlib
import time

if __name__ == '__main__':
    N = 100000
    dict = {hashlib.md5(i.to_bytes(4, 'little')).hexdigest(): None for i in range(N)}

    list = [hashlib.md5(i.to_bytes(4, 'little')).hexdigest() for i in range(N)]
    start = time.time()
    for item in list:
        if item in dict:
            pass

    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

# elapsed_time:0.023391008377075195[sec]

こうして比べてみると,同じhash検索でも，辞書の中身のデータタイプによって，大きく計算速度が変わることはないのではないかと思う．

###　もしhas検索でなかったら

もしhash検索でなかったらどうなるのだろうか？
ということで試してみた．

list.py

import time

if __name__ == '__main__':
    N = 100000
    list = [hashlib.md5(i.to_bytes(4, 'little')).hexdigest() for i in range(N)]

    start = time.time()
    for i in range(N):
        if hashlib.md5(i.to_bytes(4, 'little')).hexdigest() in list:
            pass

    elapsed_time = time.time() - start
    print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

# elapsed_time:85.36278200149536[sec]

listの中に特定の要素が存在するかを検索すると，かなりの時間がかかることがわかる．

なので，要素の検索をする際には，hash検索をするべきであることがわかる．