基本情報技術者試験 ハッシュ法

10進数で5桁の数を、その各桁の数の合計を13で割った余りをハッシュ値として配列に格納するという問題をみて、すべての5桁の数についてハッシュ値を調べるとそれぞれのハッシュ値が何回使われるのかを調べてみた。

Pythonのプログラム

def sum_of_digits(n):
    s = 0
    while n != 0:
        q, r = divmod(n, 10)
        s += r
        n = q
    return s

dict = {}
for i in range(13):
    dict[i] = 0

for i in range(10000, 100000):
    dict[sum_of_digits(i) % 13] += 1

print(dict)

実行結果

{0: 6933, 1: 6917, 2: 6899, 3: 6887, 4: 6887, 5: 6899, 6: 6917, 7: 6933, 8: 6943, 9: 6947, 10: 6948, 11: 6947, 12: 6943}