2007-02-28 [長年日記]
■100万までの素数表
テキスト検索で(Firefoxなら数字を普通に入力するだけで*1)判定ができるのがよい。
http://www.h7.dion.ne.jp/~konton/sosuu.html
http://web.archive.org/web/20080617184309/http://www.h7.dion.ne.jp/~konton/sosuu.html
■Boolean型のhashCode()はなぜ1231と1237か?
- Boolean : このオブジェクトが true を表す場合は整数 1231、false を表す場合は整数 1237
1231と1237ってなんだろ？
lethevert is a programmer - Java : hashCodeの値
考えてみた。
まず、どちらも、わりと大きな*2素数だなぁ。
あとは、これが HashMap や HashSet で使われることを考えると……。
HashMap や HasSet ではハッシュ表の個数で剰余をとって、どこに入れるかを決めるので、ハッシュ表の数がどのように決められるか? と、その数で剰余をとった時にちゃんと散らばるか? を見ればいいのかな*3。
ソースを見るとコンストラクタで initialCapacity を指定しなかった時の値は11。private メソッド rehash で capasity が伸長されると *2+1 となる。
11 から始めて 1231 までの範囲で *2+1 させていって、1231,1237 に対して剰余をとると……、
1231 % 11 = 10 1237 % 11 = 5 1231 % 23 = 12 1237 % 23 = 18 1231 % 47 = 9 1237 % 47 = 15 1231 % 95 = 91 1237 % 95 = 2 1231 % 191 = 85 1237 % 191 = 91 1231 % 383 = 82 1237 % 383 = 88 1231 % 767 = 464 1237 % 767 = 470
ちゃんと、違う値を出す。
……あれ? Java SE 5.0 で仕様が変わっているのか。
initialCapacity を指定しなかった時の値は16。指定したときはその数以上の2のべき乗を内部で計算する。
で、剰余を計算するんじゃなくて、ハッシュ表の数-1 とハッシュコードの論理積をとるんだ。実質は剰余だけど、計算は単純で高速。
これは確かめてみるまでもなくビットパターンで判断できる。
4以上の2のべき乗数に対して違う剰余を出すので、OK。
追記:かなりいいかげんなこと(悪い意味の方)を書いた。詳細な内容をトラックバックでいただいた(多謝)ので、そちらを見ていただいた方がいいかと。
- 2つともそれなりに大きな素数であること*4
- そうすると必然として最下位のビットは共通して1になるから、第2ビットが異なることが望ましいだろう
という条件を満たす数ならまぁ、大体なんでも良かったのでは?
と思った。
(追記)2008/03/25
素数と剰余が作る「衝突のない世界」が気になる人は以下のエントリも読むといいかも。
■子が親に見せたくないテレビ番組
2005年7月1日朝日新聞に記事があったらしい。
1位 伊東家の食卓
2位 クイズ＄ミリオネア
3位 発掘！あるある大辞典II
4位 トリビアの泉
5位 ＮＨＫニュース７
6位 いきなり！黄金伝説。
7位 ロンドンハーツ
8位 水戸黄門
9位 プロ野球中継
10位 銭形金太郎
単に「見たい番組の裏番組」が混じっている気もすごくするけど……。
これ、もっと継続してやって欲しいなぁ。