:-(: 午前, 午後, 夜, Knuth 先生の hash, 艦これ

2013-10-04 :-(

_ 午前

0530 起床

0550 筋トレ

0830 出勤 && 自習

_ 午後

1300 自習

_ 夜

1700 退勤 && 移動

1800 自社 && 業績評価面談

1850 退勤

2100 飯。豚肉の生姜焼き

_ [Knuth][hash][クヌース][ハッシュ][namazu]Knuth 先生の hash

はるか昔に namazu のコードを読んでいたときに knuth 先生の hash というものを見かけた。( 私が読んだときは namazu 1.x だったと思う。1.x は Perl で実装されているが、namazu は 2.x で全面的に書きなおされており、2.x では C で実装されなおされている。1.x はこちらにある Index of /stable )

namazu

1.x のコード

namazu-1.3.0.11/src/mknmz.pl

# Knuth先生の ``hash'' (UNIX MAGAZINE 1998 5月号) 用の乱数表
# 0-65535までの数を使った要素数256の乱数表を 4つ使います。
sub init_seed () {
    (
     [
      3852, 26205, 51350, 2876, 47217, 47194, 55549, 43312, 
      63689, 40984, 62703, 10954, 13108, 60460, 41680, 32277, 
      51887, 28590, 17502, 57168, 37798, 27466, 13800, 12816, 
      53745, 8833, 55089, 15481, 18993, 15262, 8490, 22846, 
        :

# Dr. Knuth's  ``hash'' from (UNIX MAGAZINE May 1998)
sub hash ($) {
    my ($word) = @_;
    my ($i, $hash);

    $hash = 0;
    $word =~ tr/\xa1-\xfea-z0-9//cd; # 記号を捨てる
    for ($i = 0; $word ne ""; $i++) {
    $hash ^= $Seed[$i % 4][ord($word)];
        $word = substr($word, 1);
    # $word =~ s/^.//;  is slower
    }
    $hash & 65535;
}

2.x のコード

namazu-2.0.21/nmz/seed.c

/*
 *
 * Reference: Dr. Knuth's ``hash'' (from UNIX MAGAZINE May, 1998)
 *
 */

int nmz_seed[4][256] = 
{
    {
    3852, 26205, 51350, 2876, 47217, 47194, 55549, 43312, 
    63689, 40984, 62703, 10954, 13108, 60460, 41680, 32277, 
    51887, 28590, 17502, 57168, 37798, 27466, 13800, 12816, 
     :

namazu-2.0.21/nmz/search.c

/*
 * Calculate the hash value of the string str.
 */
static int 
hash(const char *str)
{
    int hash = 0, i, j;
    uchar *ustr = (uchar *)str;  /* for 8 bit chars handling */

    for (i = j = 0; *ustr; i++) {
        if (!issymbol(*ustr)) { /* except symbol */
            hash ^= nmz_seed[j & 0x3][*ustr];
            j++;
        }
        ustr++;
    }
    return (hash & 65535);
}

knuth 先生の hash

肝心の UNIX MAGAZINE 1998 年 5 月号 p.108 のコード。

#include <stdlib.h>

#define TBLSIZ 1024 /* hash bucket のサイズ。 2 の冪乗でなければならない */
#define NSEED  4    /* 乱数表の種類。2 の冪乗でなければならない */

unsigned int seed[NSEED][256];

void
init_seed()
{
    int i, j;
    srand(time(NULL));
    for ( i = 0; i < NSEED; ++i ) {
        for ( j = 0; j < 256; ++j ) {
            seed[i][j] = rand();
        }
    }
}

int
hash(unsigned char *key, int keylen)
{
    int i, j, hash;

    hash = 0;
    i = j = 0;
    while ( i < keylen ) {
        hash ^= seed[j++][key[i++]];
        j &= NSEED - 1;
    }
    return (hash & (TBLSIZ - 1));
}