hash関数

出掛けにセジウィックのアルゴリズムCを見たら、「ハッシュ表のサイズは素数にして、文字列を超多倍長数としてみる」ような恐ろしげな方法が載っている。いやなのでその辺のソースに頼ってみよう。

perl-5.8.8/

hv.c : l.381

STATIC HE *
S_hv_fetch_common(pTHX_ HV *hv, SV *keysv, const char *key, STRLEN klen,
                  int flags, int action, SV *val, register U32 hash)
{
    XPVHV* xhv;
    HE *entry;
    HE **oentry;
    SV *sv;
    bool is_utf8;
    int masked_flags;

    if (!hv)
        return 0;

    if (keysv) {
        if (flags & HVhek_FREEKEY)
            Safefree(key);
        key = SvPV_const(keysv, klen);
        flags = 0;
        is_utf8 = (SvUTF8(keysv) != 0);
    } else {
        is_utf8 = ((flags & HVhek_UTF8) ? TRUE : FALSE);
    }

    xhv = (XPVHV*)SvANY(hv);
    if (SvMAGICAL(hv)) {
        if (SvRMAGICAL(hv) && !(action & (HV_FETCH_ISSTORE|HV_FETCH_ISEXISTS)))
          { 
            if (mg_find((SV*)hv, PERL_MAGIC_tied) || SvGMAGICAL((SV*)hv)) {
                sv = sv_newmortal();
            :
            :

このあたりなんだろうけども恐ろしすぎる。ちょっと腰を据えてマクロを調べないと。。。ソースの迷宮に迷い込んでしまったようだ。『デーモン君のソース探検』のデンくんになった気分。パパーヽ(´Д`；)ﾉ

ruby-1.8.6-p114

st.cの l.242あたり 、st_lookup()。ああ、読みやすさが段違い。流石Matzさん。

st_lookup(table, key, value)
    st_table *table;
    register st_data_t key;
    st_data_t *value;
{
    unsigned int hash_val, bin_pos;
    register st_table_entry *ptr;

    hash_val = do_hash(key, table);
    FIND_ENTRY(table, ptr, hash_val, bin_pos);

    if (ptr == 0) {
        return 0;
    }
    else {
        if (value != 0)  *value = ptr->record;
        return 1;
    }
}

ここのdo_hash()だ。

#define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))
#define do_hash_bin(key,table) (do_hash(key, table)%(table)->num_bins)

たどっていくと、こんなのに当たった。

static int
strhash(string)
    register const char *string;
{
    register int c;

#ifdef HASH_ELFHASH
    register unsigned int h = 0, g;

    while ((c = *string++) != '\0') {
        h = ( h << 4 ) + c;
        if ( g = h & 0xF0000000 )
            h ^= g >> 24;
        h &= ~g;
    }
    return h;
#elif defined(HASH_PERL)
    register int val = 0;

    while ((c = *string++) != '\0') {
        val += c;
        val += (val << 10);
        val ^= (val >> 6);
    }
    val += (val << 3);
    val ^= (val >> 11);

    return val + (val << 15);
#else
    register int val = 0;

    while ((c = *string++) != '\0') {
        val = val*997 + c;
    }

    return val + (val>>5);
#endif
}

おお、Elf?, やPerlのまで書いてあるっぽい。ありがたい*1しかし、やっぱり恐ろしげな方法らしい。st_lookup()の FIND_ENTRYでhash_valを mod するんだけどその値（というかテーブルサイズ＝ num_bins）は

/*
Table of prime numbers 2^n+a, 2<=n<=30.
*/
static long primes[] = {
        8 + 3,
        16 + 3,
        32 + 5,
        64 + 3,
        128 + 3,
        256 + 27,
        512 + 9,
　　　　：

となっていてセジウィックの本のとおり、素数のサイズになってる。

しかし、恐ろしげだけどやはりシンプルで考えやすい。かなり勉強になりました。これらの情報を公開してくださってる全ての方に感謝。

のあー昼休みが終わるー

追記：
脊髄反射でMatzさんだと思い込んでしまったけど、一番上に

/* This is a public domain general purpose hash table package written by Peter Moore @ UCB. */

ってかいてあった＞＜
穴が無くても入りたい。

アルゴリズムC・新版―基礎・データ構造・整列・探索

デーモン君のソース探検―BSDのソースコードを探る冒険者たちのための手引き書 (BSD magazine Books)

*1:というか本当、こんな頭のいい人と仕事できたら幸せだろうな,,,