ハッシュ表のサイズ

• ref:http://d.hatena.ne.jp/zariganitosh/20090716

• キーから値を取得するには、ハッシュ%テーブルサイズで余りを取得する。その余りが、求めるキーのインデックスになっている。
• ハッシュテーブルを効率良く利用するには、インデックスの重複を無くし、キーと値が1対1となる関係を目指す必要がある。
• それを実現するために、素数で割ることで、その余りが一様にばらけた値になるようだ。
  • 以下のページで、面白い実験結果を見ることができる。（大変参考になりました。感謝です！）
  • データ構造とアルゴリズム >> 表検索アルゴリズム >> ハッシュ検索 >> ハッシュ関数の選び方

その実験結果は単にもとのハッシュ関数が悪いという話が。

• ref:http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
• ref:http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth-2
• via:http://www.kt.rim.or.jp/~kbk/zakkicho/09/zakkicho0906b.html#D20090612-2

実際に頻度の標準偏差でも計算してみる。numpy を使って手抜き。

from __future__ import with_statement
import sys
import numpy

def usage():
    print 'Usage: python %s filename n' % sys.argv[0]

def main(args):
    if len(args) != 2:
        usage()
        sys.exit(1)

    filename = args[0]
    n = int(args[1])

    counts = [0 for _ in xrange(n)]
    with file(filename) as fp:
        for line in fp:
            word = line.rstrip()
            index = hash(word) % n
            counts[index] += 1

    print n, numpy.std(counts)

if __name__ == '__main__':
    main(sys.argv[1:])

% echo 11 12 13 | xargs -n 1 python test_hash.py /usr/share/dict/words 
11 165.917185357
12 76.0602831093
13 111.986262894

11, 12, 13 だと合成数の 12 のほうが分散が大きいとかなにそれ。