- ここ最近のRDBはhashに次のものを使っている
- murmurhash
- cityhash
- farmhash
- clhash
- static hashing
- linear probe hashing
- robin hood hashing
- 自分が入りたかったところからいくつ追い出されたかの値を持っておく
- コリジョンしたら上記の値を見比べて小さい値のものを追い出す
- もともと入りたかった場所からできるだけ離れないようにしている感じ
- ブランチミスとかデータコピーとかがあって linear probe hashing のほうがうまく行くらしい
- cuckoo hashing
- 複数のハッシュを使う
- 片方でコリジョンしたら別のハッシュを試す
- ぶつかりまくると無限ループになるので、テーブルサイズを増やす
- dynamic hash table
- static だと要素があふれると全部作り直しなのでできるだけさける
- extendible hashing
- あるバケットが溢れたら、そのバケットをsplitする
- どのバケットを使うかを指し示すグローバルなスロットを用意する
- このスロット数はsplitが起こるたびには先頭ビットの数が増えるので、倍々ゲームで増える
- linear hashing
- 次にsplitするバケットを指す split pointer を用意する
- 何らかの基準で split pointer のバケットをsplitする
- このときにハッシュ関数をもう一つ用意する
- もとのハッシュ関数で split pointer が指していたバケットだったら、新しいハッシュを使う
- この方式だとバケットを指すスロットが線形に増える
linear hashing の挙動の理解が怪しいがモチベーションはわかった。
