Entry

プログラミング・メモ - ハッシュ関数性能評価選手権

2007年09月27日

えー……,やってまいりました。第255回ハッシュ関数性能評価選手権(ウソ)。決められたテーブルサイズに対して,いかに効率の良いハッシュ値を算出することができるのかを競うこの大会。今回もあちこちのソースコードから,選りすぐりのハッシュ関数を取り揃えてまいりました。今回は選手のご紹介をば。なお,ソースコードは一部インデントを編集している場合があります。

まずは,Gnome 代表,libxml2 さんのハッシュから。

/*
 * xmlHashComputeKey:
 * Calculate the hash key
 */
static unsigned long
xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
	          const xmlChar *name2, const xmlChar *name3) {
    unsigned long value = 0L;
    char ch;
    
    if (name != NULL) {
	value += 30 * (*name);
	while ((ch = *name++) != 0) {
	    value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
	}
    }
    if (name2 != NULL) {
	while ((ch = *name2++) != 0) {
	    value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
	}
    }
    if (name3 != NULL) {
	while ((ch = *name3++) != 0) {
	    value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
	}
    }
    return (value % table->size);
}
ftp://xmlsoft.org/libxml2/
libxml2-2.6.27.tar.gz/hash.c

3つの文字列についてハッシュを取る関数です。やり方はどの文字列に対しても同じで,計算値を左に5bit右に3bitシフトさせて文字列値を足し,元の値との XOR を取っています。value が溢れそうになっているときに,計算値の上位2bitを捨てて,(全体として)左に2bitシフトさせているわけですが。あたしにはなぜそうするのか分かりません(無知ゆえに)。

ともあれ,この効果が吉と出るのか凶と出るのか,乞御期待。

つづきまして,C++ 代表,STL さん(SGI 所属)のハッシュです。今回は C++ からの参戦ということで,公平な評価プログラムを書けるのか,ちょっと不安になってまいります。

inline size_t __stl_hash_string(const char* __s)
{
  unsigned long __h = 0;
  for ( ; *__s; ++__s)
    __h = 5*__h + *__s;

  return size_t(__h);
}
http://www.sgi.com/tech/stl/
stdlib_19991014.zip/stl_hash_fun.h

実装は,単純に計算値に5を掛けて文字の値を足しているだけのようです。大丈夫か!こんなんで?結果の程は後日。ご期待ください。

さてさて続きまして,Solaris 代表,MDMA さんの登場です。MDMA というのはヤバゲなアレではなくて,マルチメディア向けの HTTP サーバとのことです。あたしゃ使ったことがないのでよく分かりません。

extern unsigned long seed_table[];

static inline unsigned long hash(char* str) {
    unsigned  long t = 0;
    int n=0;
    while(*str) {
        t += seed_table[n] * *str;
        n++;
        str++;
    }
    return t;
}
http://www.ibiblio.org/mdma-release/
mdma.tar.gz/mdma/include/hash.h

こちらは,前回このサイトでご紹介したような,seed_table を利用した方法のようです。seed_table に何が入っているのかで性能が決まりそうですけれど,それは次回のお楽しみ!

まだまだ参ります。今度は大物,Linux 代表 Linux カーネルさんの登場です。

/*
 * Knuth recommends primes in approximately golden ratio to the maximum
 * integer representable by a machine word for multiplicative hashing.
 * Chuck Lever verified the effectiveness of this technique:
 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
 *
 * These primes are chosen to be bit-sparse, that is operations on
 * them can use shifts and additions instead of multiplications for
 * machines where multiplications are slow.
 */
#if BITS_PER_LONG == 32
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME 0x9e370001UL
#elif BITS_PER_LONG == 64
/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
#else
#error Define GOLDEN_RATIO_PRIME for your wordsize.
#endif

static inline unsigned long hash_long(unsigned long val, unsigned int bits)
{
	unsigned long hash = val;

#if BITS_PER_LONG == 64
	/*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
	unsigned long n = hash;
	n <<= 18;
	hash -= n;
	n <<= 33;
	hash -= n;
	n <<= 3;
	hash += n;
	n <<= 3;
	hash -= n;
	n <<= 4;
	hash += n;
	n <<= 2;
	hash += n;
#else
	/* On some cpus multiply is faster, on others gcc will do shifts */
	hash *= GOLDEN_RATIO_PRIME;
#endif

	/* High bits are more random, so use them. */
	return hash >> (BITS_PER_LONG - bits);
}

static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
{
	return hash_long((unsigned long)ptr, bits);
}
#endif /* _LINUX_HASH_H */
http://www.kernel.org/pub/linux/kernel/v2.6
linux-2.6.1.tar.bz2/linux-2.6.1/include/linux/hash.h

こちらも,シフトと加算を繰り替したものになっています。コメントを読むと……どれどれ,「こっちの方が速いから」みたい(ほとんどウソ)。Knuth 先生のお墨付きというアルゴリズム,どこまで健闘するでしょうか。楽しみです。

さて,エントリもこれで最後になりました。最後は,Apache project 代表 Apache さんに登場してもらいましょう。

APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key,
                                                      apr_ssize_t *klen)
{
    unsigned int hash = 0;
    const unsigned char *key = (const unsigned char *)char_key;
    const unsigned char *p;
    apr_ssize_t i;

    /*
     * This is the popular `times 33' hash algorithm which is used by
     * perl and also appears in Berkeley DB. This is one of the best
     * known hash functions for strings because it is both computed
     * very fast and distributes very well.
     *
     * The originator may be Dan Bernstein but the code in Berkeley DB
     * cites Chris Torek as the source. The best citation I have found
     * is "Chris Torek, Hash function for text in C, Usenet message
     * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich
     * Salz's USENIX 1992 paper about INN which can be found at
     * <http://citeseer.nj.nec.com/salz92internetnews.html>.
     *
     * The magic of number 33, i.e. why it works better than many other
     * constants, prime or not, has never been adequately explained by
     * anyone. So I try an explanation: if one experimentally tests all
     * multipliers between 1 and 256 (as I did while writing a low-level
     * data structure library some time ago) one detects that even
     * numbers are not useable at all. The remaining 128 odd numbers
     * (except for the number 1) work more or less all equally well.
     * They all distribute in an acceptable way and this way fill a hash
     * table with an average percent of approx. 86%.
     *
     * If one compares the chi^2 values of the variants (see
     * Bob Jenkins ``Hashing Frequently Asked Questions'' at
     * http://burtleburtle.net/bob/hash/hashfaq.html for a description
     * of chi^2), the number 33 not even has the best value. But the
     * number 33 and a few other equally good numbers like 17, 31, 63,
     * 127 and 129 have nevertheless a great advantage to the remaining
     * numbers in the large set of possible multipliers: their multiply
     * operation can be replaced by a faster operation based on just one
     * shift plus either a single addition or subtraction operation. And
     * because a hash function has to both distribute good _and_ has to
     * be very fast to compute, those few numbers should be preferred.
     *
     *                  -- Ralf S. Engelschall <rse@engelschall.com>
     */

    if (*klen == APR_HASH_KEY_STRING) {
        for (p = key; *p; p++) {
            hash = hash * 33 + *p;
        }
        *klen = p - key;
    }
    else {
        for (p = key, i = *klen; i; i--, p++) {
            hash = hash * 33 + *p;
        }
    }

    return hash;
}
ftp://apache.mirrors.pair.com/httpd
httpd-2.2.4.tar.bz2/httpd-2.2.4/srclib/apr/tables/apr_hash.c

コメント長っ。ついでだから読んでみましょう。

なんでも,この方法は「33倍法」(勝手訳)なる方法だそうで,とても有名なハッシュアルゴリズムなんだそうです。速い・上手い・安い(?)の3拍子(?)が揃っていて,Perl や Berkeley DB(BDB)にも使われてるんだとか……。これは期待が持てそうです。

で,そもそもなんで33なのかというと,これがまた誰も満足に説明できていない。以下,「なぜ33なのか問題」ついて,ラルフさんの考えがとうとうと示されています。興味のある方はご一読をば。

と……選手権とはいったものの,どうやって評価したらいいものやら。アタマのいい人達のエントリを受けてしまって,主催者としては苦労しそうです。ハッシュ関数性能評価選手権企画,立ち消えの危機!

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN