ハッシュ関数については、原田さんから elfhash というのを教えていただきました。

<PRE>
MIME-Version: 1.0 (generated by vin3.4.3)
Content-Type: text/plain; charset=ISO-2022-JP
X-Mailer: Vin 3.4.3/040419 on Linux/2.4.2-2
To: harada@ingrid.org
Cc: ysato@delegate.org
Subject: Re: Copyright of Freya
From: ysato@delegate.org (Yutaka Sato)
Organization: The DeleGate Project
Message-Id: <10psgr.ysato@delegate.org>
Date: Wed, 16 Jun 2004 07:17:55 +0900 (JST)

原田さま

In message <20040616051509M.harada@ingrid.org> on 06/16/04(05:15:09)
you Masanori Harada <harada@ingrid.org> wrote:
 |At Tue, 15 Jun 2004 19:54:24 +0900 (JST), ysato@delegate.org (Yutaka Sato) -san wrote:
 |
 |> 教科書なんかをあたれば、より適切な関数がありそうですが。昔から
 |> 教科書を読まないもので。。。）
 |
 |有名どころの elfhash も試してみてはいかがでしょう?
 |
 |unsigned long elfhash(const unsigned char *name) {
 |  unsigned long h = 0, g;
 |  while (*name) {
 |      h = (h << 4) + *name++;
 |      g = h & 0xF0000000L;
 |      if (g) h ^= g >> 24;
 |      h &= ~g;
 |  }
 |  return h;
 |}

ありがとうございます。やってみました。(H5)

 |   表1) 平均ハッシュ衝突回数
 |   ----------------------------------------------------
 |   対象データ: DeleGate-ML の最初の 1400 件(*a)の記事
 |   単語数: 31605
 |   ハッシュ表サイズ: 32768*4 (デフォルト)
 |
 |       平均衝突回数   所要処理時間(*b) 所要処理時間(*c)
 |   (H1)       239.4     23.2 + 4.9      12.9 + 0.9
 |   (H2)        83.5     19.9 + 4.6      10.5 + 0.9
 |   (H3)        20.3     18.3 + 4.5       9.0 + 0.8
 |   (H4)         1.1     17.8 + 4.4       8.8 + 0.7
     (H5)         4.7     17.7 + 4.3       8.6 + 0.7

単語バッファサイズを64Kにしてみると、

     対象データ: DeleGate-ML の最初の 1400 件(*a)の記事
     単語数: 31605
     ハッシュ表サイズ: 64*1024*4
     (H1)       125.6                     10.9 + 0.7
     (H2)        81.1                     10.2 + 0.6
     (H3)        15.4                      8.8 + 0.6
     (H4)         0.4                      8.8 + 0.6
     (H5)         2.7                      8.6 + 0.7

同じバッファサイズで英語版MLについてやってみると、

     対象データ: 英語版DeleGate-ML の 2600 件(*a)の記事
     単語数: 42027
     ハッシュ表サイズ: 64*1024*4
     (H1)       219.4                     10.1 + 1.0
     (H2)        30.0                      6.3 + 0.7
     (H3)         2.2                      5.7 + 0.7
     (H4)         0.7                      5.9 + 0.8
     (H5)         2.5                      5.7 + 0.7

H5はこの２つの例に対しては、いずれも良い結果を出していますので、自作の
ハッシュ関数(H3)よりはこれを使うべきかと思いますが、より多くのパタ
ーンのデータに適応できると思われる CRC32 (H4) も捨て難いと思います。
なんせ衝突率の低さはピカイチですし、話として面白いですし(^^)

　　　　　　　 　　　        D G　　
┌─┐┬┌──┬┐ ／／\^^ ( - ); {Do the more with the less -- B. Fuller}
├─┤│└─┐│ ／　877m\_<   >_ <URL:http://www.delegate.org/delegate/>
┴　└┴──┘┴──────────────────────────────
佐藤豊＠情報処理研究部門.産業技術総合研究所(独立行政法人)
</PRE>