はじめてのにき(2009-10-21)_ 対関数 sin-x さんに教えてもらう。 http://ja.wikipedia.org/wiki/対関数 よく整数2つの点とかの hash 値をどう計算するか悩むわけなんだけど、 本質的にこの関数はちょっと遅そうだけど、悪くないかも、ね。 ちょっとやってみた。 適当な値域の乱数のペアを大量に作って適当に突っ込む。 http://github.com/shinh/test/blob/da1e28b9fd201ca2d203d3e187cc280e9a8b9f9a/bijection_hash.cc ハッシュ関数としては単なるかけ算、 よくある x + y * prime みたいなヤツ、 それとこの対関数、をそれぞれ使ってみた。 最初の立ち上がり部分は値域がほぼ埋まってるのであんまり関係ない。 単なるかけ算は明らかに悪い。 対関数は密度がある程度あるうちは衝突が少ないおかげかちょっと早そ
