[Mew-dist 15159] hash

[Kazu Yamamoto ( 山本和彦 )]

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が完全数だからさ