[Mew-dist 15159] hash
Kazu Yamamoto ( 山本和彦 )
kazu at example.com
2000年 11月 28日 (火) 09:52:02 JST
Message-ID: とハッシュに関して調べました。
RFC822 では、"<" と ">" の中に white-space を書けるようになっています。
(もちろん、お勧めじゃないのだろうけど。) DRUMS では、送信時には
white-space を入れないようにと書いてあるように読めます。
---結論 1---
(1.1) Message-ID: の値を正規化して In-Reply-To: などに入れるのは
おせっかい。
(1.2) ただし、内部的に正規化するのは OK。
(1.3) Mew で "<" と ">" を含めて保存するのかは、悩ましいところ。
(1.3.1) 正規化するなら、"<" と ">" は不要
(1.3.2) しないなら、必要
------------
さて、ハッシュ登録関数 intern の実装ですが、以下のようになっています。
hash = hash_string (ptr, size_byte);
hash %= obsize;
hash_string() で、文字列全体を 32 ビット程度の値に集約します。(そう言
えば、昔 shigeya さんに教えてもらいましたね。)
---結論 2---
(2) intern に渡すすべての文字列が "<" から始まっていても
適度にばらける。
-----------
で、obarray のサイズで割ってあまりを取る、つまり 32 ビットを obarray
のサイズに集約しています。
info を読むとサイズは、
- 素数
あるいは
- 2^n - 1
がよいと書いてあります。
#「2^n から遠い」というのは僕の勘違い。
---結論 3---
(3.1) 素数を使うと、割り算のコストは高いが、よいハッシュ値が
とれる。
(3.2) 2^n だと最悪。上位ビットを全部捨てるから。
------------
おまけ:
2^n - 1 は、素数になることがあります。たとえば、3、7、31、127。(だから、
ハッシュによいのかも。)
ぜんぜん関係ないけど、2^n - 1 が素数の場合は、2^(n-1) x (2^n - 1) は、
「完全数」となります。たとえば、6、28、496、8128。
P.S.
(問) 2^n - 1 が素数の場合、2^(n-1) x (2^n - 1) が「完全数」となること
を証明せよ。(30点)
--かず@月が28日周期なのは、28が完全数だからさ
Mew-dist メーリングリストの案内