■ハッシュ関数を調べる

セキュリティ目的ではない。ハッシュテーブルで使うような奴でキャッシュで使いたい。

手軽なほうが良い。軽いほうが良い。推測可能でよい。数十バイトくらいの文字列にしたい。

md5が一番汎用っぽいけど、無駄に重い気がする。crc32は軽そうだしそれなりに汎用っぽいけど、ハッシュ長が短いのがめんどい。

ベターはなんだろう。セオリーはなんだろう。

調べた→ http://anond.hatelabo.jp/20090327015620

ベンチ用スクリプト

#!/usr/local/bin/python
from sys import argv, stderr
from time import time
from string import ascii_letters, join
from random import choice
from hashlib import md5
from binascii import crc32
from itertools import izip

time_fmt = '%10s: %5d ms'
shift = int(argv[1]) if len(argv)>1 and argv[1].isdigit() else 2
length = 0x100 << shift
cycle = 0x10000 &gt;&gt; shift
print &gt;&gt; stderr, 'string length: 0x%x, cycle: 0x%x' % (length, cycle)
data = tuple(''.join(choice(ascii_letters) for i in xrange(length)) for j in xrange(cycle))

start = time()
md5hex = tuple(md5(s).hexdigest() for s in data)
print &gt;&gt; stderr, time_fmt % ('md5hex', (time() - start) * 1000)

start = time()
crc32x4 = tuple(''.join('%08x' % abs(crc32(s[i::4])) for i in (0, 1, 2, 3)) for s in data)
print &gt;&gt; stderr, time_fmt % ('crc32x4', (time() - start) * 1000)

start = time()
startend = tuple(s[:16]+s[-16:] for s in data)
print &gt;&gt; stderr, time_fmt % ('headtail', (time() - start) * 1000)

start = time()
skip = tuple(s[::(len(s)/32+1)] for s in data)
print &gt;&gt; stderr, time_fmt % ('skipover', (time() - start) * 1000)

for s in izip(data, md5hex, crc32x4, startend, skip):
    print join(s)

実行結果

% python hashbench.py 0 > hash0.txt
string length: 0x100, cycle: 0x10000
    md5hex:   199 ms
   crc32x4:  1081 ms
  headtail:    30 ms
  skipover:    41 ms
% python hashbench.py 2 > hash1.txt
string length: 0x400, cycle: 0x4000
    md5hex:    83 ms
   crc32x4:   363 ms
  headtail:    10 ms
  skipover:    20 ms
% python hashbench.py 4 > hash2.txt
string length: 0x1000, cycle: 0x1000
    md5hex:    52 ms
   crc32x4:   170 ms
  headtail:     2 ms
  skipover:     5 ms

Permalink | 記事への反応(3) | 12:39

ツイートシェア