ハッシュについて - komiyamの日記

衝突の問題さえ回避すれば非常に優秀なデータ構造である。
弱点はメモリを大量に消費すること。メモリの局所化とは対極であること。for_eachみたいなことができない。STLにない(tr1とかextとか__gnu_cxxとかはさておき)等。
そもそもsetやmapと計算量がlog程度しか変わらないので定数倍最適化程度の効果しかない。なのでSRMとかで使う機会はほぼ無い。とはいえsetやmapの定数が重いことは周知の事実だが。
上述の通り、ハッシュテーブルを使うのは計算時間が厳しいときが多い。なので、modとかはあまり使いたくない。
ではそれをどう解消するかというと、ハッシュ値の計算をunsignedでやればよい。それだと値が大きすぎる場合は、下nビットをマスクして取り出せばよい。
ハッシュの衝突について少し真面目に考えよう
- 誕生日のパラドックスは知っておくべき。ハッシュテーブルのサイズがNのとき、sqrt(N)個のデータを突っ込めばたいてい衝突が起こる。
- でも、特定のひとつが他のデータと衝突する確率は割と低い。
  - もう少し真面目に考えると、1-(1-1/MAX_HASH)^N ≒　N/MAX_HASH
  - この値が大きくなると普通に実装するか(Open Addressingとかchained hashとか)ハッシュテーブル使わずに他の所で速度を稼ぐかしなきゃならない。
- 同じ理由で、3つのハッシュ値が衝突する可能性は十分低い。
- 例えば、大量のデータが与えられたとき同じものが存在するかどうか判定しろ、みたいな問題があるとしよう。
- このとき、ヒューリスティック解法ではあるけどハッシュ値の一致だけで判定する方法を考えてみよう。
- ハッシュテーブルのサイズをHASH_SIZEとする。配列はint(32bit)で用意することにしよう。
- このとき、あるデータに関してハッシュ値を2つ用意する(hash1(in [0,HASH_SIZE) ), hash2(in [1,MAX_INT] ))。
- 各データに対して、indexがhash1となるところにhash2の値を突っ込んでいく。2つのデータが同じかどうかは、もちろんhash1とhash2の値が一致するかどうかで判定する。
- hash1の値が衝突したとき、hash2の値が一致しなければ、そのデータは捨てる。
- もちろん、同一のデータを捨ててしまうこともあり、このアルゴリズムはそれを検知できない。ただし、それが唯一の答えだったとき、そもそもそのhash1の値が衝突する可能性は前述の通り十分低いと考えられる(太字参照)。
- 同一のデータが複数組あるときもやはり十分な確率で検出することが期待できる。
- このアルゴリズムは、ビット演算使ってHASH_SIZEを32倍するより効果があると思う。前述の通り、HASH_SIZEを32倍してもそれは√でしか効いてこない。
- ちなみに異なるデータでhash1とhash2が同時に一致する確率は、さすがに十分低いと期待できる。なんだったらhash2のサイズを64bitにしてもよい。
- WAをもらったら、ハッシュ関数で使う素数をちょっといじれば大抵通るようになる。
ハッシュ関数についても考えてみよう
- どうせハッシュテーブルに突っ込むのは文字列とかvectorとか。要するに配列。
- なので重み付きの和を計算する(位取り記法のあれ)。
- 基数のi乗をあらかじめ計算して配列に突っ込んでおくと気持ち速くなるかもしれない。
- 基数はそれなりに大きい素数とする。配列が長ければ実は大きい必要はない。おまけに、ハッシュ値の上限+1と互いに素でありさえすれば素数である必要すら無い。
- ローリングハッシュで部分列に対して計算するときは前の方により重みをつける。
- 上で書いたけどC++でハッシュ値の範囲を[0,2^64)とすればunsigned long longで普通に計算するだけでよい(modいらず)。ハッシュ値の上限をもっと小さくしたい場合でも[0,2^64)で計算した後計算結果のmodをとればよい。
- Javaにはunsignedが無いので別の方法をとる。というかJavaって定数倍最適化でどうこうするようなものでもないし。そもそもHashSetとかHashMapとか用意されてるし。