hash

前回は圧縮がらみでgaucheのコードを見てしまった。そこにはハッシュも見ておくようにって案内が出てた。

ヒープとハッシュ法

(define t (make-hash-table `string=?))
(hash-table-put! t "kk" 123)
(hash-table-get t "kk")

普通に使うと上記のようになる。内部はどうなってる？

ソースを展開してhash.cをみる。

/* For strings, we employ siphash.
   We use public domain implementation by Sam Trenholme
   http://samiam.org/blog/20131006.html.  It has a version suitable
   for 32bit architecture, too.
   See dws_adapter.h for the details.
 */

パブリックドメインのソフトにお願いしてるとな。

/* Public domain 2013 Sam Trenholme */

/* Calculate the hash for a given string */
DwSH_WORD DwSip_hash(uint8_t *str, uint32_t len, DwSH_WORD k1, DwSH_WORD k2) {
        uint32_t offset = 0;
        int a = 0;
        DwSH_WORD v0 = 0, v1 = 0, v2 = 0, v3 = 0, fx = 0, m = 0;
        DwSip_ksetup(&k1, &k2, &v0, &v1, &v2, &v3, &fx);
        while(offset <= len) {
                m = DwSip_getword(&offset, str, len);
                v3 ^= m;
                for(a = 0; a < DwSH_CROUNDS; a++) {
                        DwSip_round(&v0,&v1,&v2,&v3);
                }
                v0 ^= m;
        }
        :

なんと、世間一般で使われている、md5とかsha256みたいな奴っぽい。まあ、そうだわな。任意長の文字列を一定の長さの数値に変換。かつ、その数値がなるべく衝突しない実装って言うと、暗号系のハッシュしかない。

これってshiroさんの目の付けどころって事かな？

と言う事で、我がrubyも調べてみる。

Hash from ri

The older syntax for Hash data uses the "hash rocket," =>:

  h = {:foo => 0, :bar => 1, :baz => 2}
  h # => {:foo=>0, :bar=>1, :baz=>2}

Alternatively, but only for a Hash key that's a Symbol, you can use a
newer JSON-style syntax, where each bareword becomes a Symbol:

  h = {foo: 0, bar: 1, baz: 2}
  h # => {:foo=>0, :bar=>1, :baz=>2}

You can also use a String in place of a bareword:

  h = {'foo': 0, 'bar': 1, 'baz': 2}
  h # => {:foo=>0, :bar=>1, :baz=>2}

まずはハッシュの復習。昔はロケット記号ってのにお世話になったな、と遠くを見る目だ。

sip_hash13(const uint8_t key[16], const uint8_t *data, size_t len)
{
   :
    for (; data != end; data += sizeof(uint64_t)) {
        m = U8TO64_LE(data);
        SIP_ROUND(m, v0, v1, v2, v3);
    }

string hashぐらいでgrepすると、何とまあ、gaucheと同じパブリックドメインなソフトにお世話になってました。この分ではpythonも同じかな。

2013年より古い、老舗のやつはどうよ？ 再びscheme系に戻って、昔からのやつを調べてみる。

unsigned long strhash(str, len, n)
     unsigned char *str;
     sizet len;
     unsigned long n;
{
  if (len>5)
    {
      sizet i = 5;
      unsigned long h = 264 % n;
      while (i--) h = ((h<<8) + ((unsigned)(downcase[str[h % len]]))) % n;
      return h;
    }
  else {
    sizet i = len;
    unsigned long h = 0;
    while (i) h = ((h<<8) + ((unsigned)(downcase[str[--i]]))) % n;
    return h;
  }
}

nは、ハッシュのバケットと呼ばれていて、scmでは137に設定されてた。値を137にちらばるようにしてるんだな。

古典と言ったら、この本でしょう。ここにもハッシュの基本が解説されてた。さりげなくね。

struct hashlist {
        S_CHAR  *name;
        S_CHAR  *def;
        struct  hashlist *next;         /* next in chain     */
};

#define HASHMAX 100                     /* size of hashtable */
struct hashlist *hashtab[HASHMAX];

hash(s)
S_CHAR * s;
{
    int             hashval;

    for (hashval = 0; *s != '\0';)
        hashval += *s++;
    return (hashval % HASHMAX);
}

lookup(s)
S_CHAR * s;
{
    struct hashlist *np;

    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return (np);        /* found     */
    return (NULL);              /* not found */
}

勿論ハッシュテーブルへの登録関数も掲載されてるんだけど、長くなるので省略(てか、著作権があるからね)。

これから、hashの挙動を調べてみようと思う。特にバケット数は、素数が良いと言われているけど、本当か？ なんてのを確かめてみたい。hashに喰わせる文字列は、適当に英文から拾ってくるのもあれなんで、あれを使う事にする。

世の中で一番長い単語は call-with-current-continuation だと思っている。 名前と言うなら、寿限無でしょう。実話としては、長い名前こういうのもあるそうです。そのうちにNHKのあの番組で取あげられるかな。

それはさておき、 システムに備付のやつを確認してみる。

ob$ wc /usr/share/dict/words
  235971  235971 2493843 /usr/share/dict/words
ob$ echo '2493843 / 235971' | bc
10

23万語を収録する単語帳で、平均は10文字と出た。でも、短かいのやら長いのやらが有るはず。ちょいとawkで確認してみる。リナだとGNUに汚染されてるので、BSD系のやつを使います。

ob$ cat cnt.swk
{ cnt[ length($1) ] += 1 }
END { for( x in cnt ) print x, "\t", cnt[x] }

思わず連想配列が出て来たけど、これもハッシュだよな。

ob$ cat /usr/share/dict/words | awk -f cnt.awk | sort -n
1        52
2        160
3        1427
4        5286
5        10237
6        17712
7        23881
8        29999
9        32411
10       30882
11       26018
12       20468
13       14941
14       9767
15       5926
16       3376
17       1814
18       842
19       428
20       198
21       82
22       41
23       17
24       5
28       1

この表を眺めていると、どうもベル型カーブっぽい。

gnuplot> plot "cnt.txt" using 1:2 with line

グラフにしてみたら、正しくそうだった。人間の所業にもこういうカーブが現れるって面白いね。

perlの元となったawkにもhashが使われているはず。探してみたら、tran.cに定義されてた。

int hash(const char *s, int n)  /* form hash value for string s */
{
        unsigned hashval;

        for (hashval = 0; *s != '\0'; s++)
                hashval = (*s + 31 * hashval);
        return hashval % n;
}

これだとKR本の欠点を解消してるね。あちらは単に文字コードを加算してるだけだ。だから、文字列 "ab" も "ba" も、同一のハッシュ値を生成してしまう。対して、こちらは、重み付けをしてるから、同一になる事は無い。

とほほのAWK入門 が、良いまとめになっているので、見ておくと吉。debianにはgawkが入っていると思っていたら、軽量版のmawkってのが入っていた。んで、面白いオプションを発見。

sakae@deb:/tmp$ awk -W dump -f cnt.awk
END
000 .   pusha   x
002 .   a_pusha cnt
004 .   set_al  018
006 .   pushi   x
008 .   pushs   "\011"
010 .   pushi   x
012 .   ae_pushi        cnt
014 .   pushint 3
016 .   print
018 .   aloop   006
020 .   pop_al
021 .   exit0
MAIN
000 .   omain
001 .   f_pushi $1
004 .   pushint 1
006 .   length
008 .   ae_pusha        cnt
010 .   pushd   1
012 .   add_asg
013 .   pop
014 .   ol_gl

assembler-like listing of program だそうです。面白いので追求していってもいいんだけど、脱線しちゃうんで、又の機会に。

実際に単語帳のそれぞれのwordのハッシュを取り、その個数を積算してみる。 手始めにKR本のオリジナルな関数をkrとして組み込んでみる。

#include <stdio.h>
#include <string.h>

#define SEED "/usr/share/dict/words"
#define HASHMAX 100

int kr(const char *s, int n){
        unsigned hashval;

        for (hashval = 0; *s != '\0'; s++)
                hashval += *s;
        return hashval % n;
}

int main(){
  char buf[64], *p;
  FILE *fp;
  int  ht[HASHMAX], i;

  for (i=0; i<HASHMAX; i++) ht[i] = 0;

  fp = fopen(SEED, "r");
  while (fgets(buf, sizeof(buf), fp) != NULL) {
    p = strchr(buf, '\n');
    *p = '\0';
    ht[ kr(buf, HASHMAX) ] += 1;
  }
  fclose(fp);

  for (i=0; i<HASHMAX; i++) printf("%d\t%d\n", i, ht[i]);
}

結果の表の２列目でソートしてみた。

ob$ ./a.out | sort -n -k 2 
19      1741
23      1776
21      1793
9       1797
:
65      2874
70      2886
69      2920
68      2921

大変、隔った結果となった。バケットサイズを100から素数の101に変更してみる。

6       1527
13      1599
:
60      3092
62      3115

素数にすると良い結果って嘘かな。scmのそれに習って137にしてみる。

100     1621
65      1624
:
61      1821
46      1833

長くなりそうなので、続く。

This year's Index

Home