- 574 名前：564 mailto:sage [2008/05/05(月) 22:10:03 ]
- >>570
なんで似たようなハッシュ値が近いbucketに入る必要があると思うの？
そういう必要は無いですよ、と588で
> このとき、隣接領域で bucket 番号が隣接している必要はない。
と明記したつもりなんだけどなあ。
具体例で説明すると、たとえば 1000×1000 のメッシュに切って、
(x/1000)×(y/1000) % 100 をハッシュ関数として設定したとしよう。
ここに (10000,10000) の点 p が与えられたとしよう。
この点を含む領域に対応するハッシュ関数値は (10×10) % 100 = 0 だから、
ハッシュ関数値 0 に対応する bucket を持ってくればいい。
(点 p に対して bucket(p) を実行することが、この操作に対応する）
次に、この点を含む領域の左側の領域を調べることにしよう。
左側の領域の座標に対応するハッシュ関数値は (9×10) % 100 = 90
だから、ハッシュ関数値 90 に対応する bucket を持ってくればいい。
（p を左に 1000 だけ平行移動した点 q に対して
bucket(q) を実行することがこの操作に対応する）
|
 |
