検索と挿入がともにO(1)であるようなHashを作るにはコツがいる
このところ立て続けに表記の事実を理解していない俺実装のHash(しかもCで!)を見かけたので、おそらく知られていないんだと思う。以降、同じ轍を踏む人が少なくなればと思い、啓蒙のために公開しておく。
おまえらはHashを再発明するんじゃねよボケが。おとなしくありもののライブラリ使えよ。つうかHashのある言語使えよ。Cとかマゾかよ。
とりあえずHashが何であるかとか、どういう作りになっているかとか、そういうことは既知とする。リストの配列ってことね。←これで何言ってるか分からないおまえらにはこの文章はちょっとはやい。先にデータ構造の教科書を読むことをおすすめ。以下ではHashに登録されるキーとデータのペアのことをentryと呼び、リストの配列と言ったときのリストのほうをbin、配列のほうをbucketと呼ぶ。つまり、
class Hash { typedef list<entry> bin; vector<bin> bucket; int entry_count; };
こうね。このコードは説明のために出してるだけで、繰り返すけどおまえらはHashを再発明(略)。
あと、話を簡単にするためにcompare関数とhash関数はオラクルによって一様に分布するものがO(1)で御神託されるものとしておく。
さて、極端な場合としてhash.bucket.size() == 1の場合を考えてみよう。つまりどんなhash値だったとしても、すべてのentryが必ずhash.bucket[0]のbinに格納されるという状態。これは、まあ極端だから明らかだけど、検索する場合を考えれば常に同じbinをたどって検索するしかないわけで、それってようするにただの線形リストだ。つまりO(n)。
じゃあ、一個増えてhash.bucket.size() == 2の場合はどうなるかというと、実はこれもO(n)なのである。線形リストが二本になってそれぞれの長さが半分になったところで、それはいわゆる定数項というやつだ。巨視的に見て検索にO(n)かかるのは変わらない。もちろん、二本が百本や千本になったところで結論は同じである。
そういうわけで帰納的に明らかなんだが、Hashってのは実はどんな定数を持ってきても、bucketのサイズが定数である場合は検索のオーダーはO(n)なんだよ。意外にも。もちろんオーダーってのは常に巨視的なわけで、entryの数が少ないうちは定数サイズでもそこそこ定数時間っぽく振る舞うことはできる。できるんだが、たくさんentryを詰めていけばやがて破綻するし、どのくらい挿入するとヤバいかとかはbucketのサイズの他に使うhash関数にも大きく依存する話なので見積りが難しい。
したがって検索でO(1)を実現したければ、その時々でbucketをリサイズするっきゃないのである。
なーんも考えない場合のHashへの挿入はたしかにO(1)である。hash関数を呼んで、その戻り値をbucketのサイズを法にmodして、その位置のbinに突っ込む(先頭でよい)。どこにもhashのサイズに絡む要素がないわけで、何個突っ込んでも一定の時間だ。めでたしめでたし。
めでたくねーのは、上に書いたとおり検索でO(1)を実現したければbucketのリサイズが不可欠って点を考慮する場合である。bucketのリサイズっていつやるかといえば、裏のスレッドでやるとかは現実的じゃないわけで、大抵が挿入/削除、つまりentryの数が変わるときにやるという話になる。
まず、ここでも極端なほうの場合で、常にhash.bucket.size() == hash.entry_countを満たすようにするということを考えよう。この場合は(いま、hashが一様に分布している仮定だから)、検索の方はようするにただの配列である。O(1)だね。でも挿入削除はどうなるかというと、挿入削除はそのたびにbucketをリサイズする必要がある。bucketのリサイズはたんにbucketのメモリ領域をreallocすればいいだけじゃなくて、きちんと全部のentryを(ちゃんと新しいサイズでhash値をmodしながら)再配置しなきゃいかん。明らかなように、それって要するに一旦まっさらにして一個一個入れ直すのと一緒だから、計算量としてはO(n)である。
では、もう少しbinの長さのばらつきを許容してみるとどうなるだろうか。たとえばJavaのjava.util.HashMapだとloadFactorという概念がある。挿入が行われるときにhash.bucket.size() * loadFactor >= hash.entry_countを満たすと、bucketのサイズが2倍くらい(注:偶数は避けているようだ)に増える。削除のときは得にリサイズはしないようだ。このようになっていると、あるエントリ数近辺で挿入したり削除したりを繰り替えしても、エントリ数が大きく変わらない限りは挿入のコストはO(1)であるから、ありがちなケースでは大変優秀と言える。O(1)でなくなるのはエントリ数が増え続ける場合で、おおむねentry数が2倍になる度にrehash一回と考えると、x個挿入するにあたってrehash回数はlog(x)回くらいで、それぞれのrehashはO(n)なので、えーと、x回めでのrehash手数は積算でxに比例して、ようするに1回あたりだとO(1)である。
しつこく繰り返すがおおまえらは素直にJavaとかC#とかを使うべきなのである。上ではJavaの場合として説明したが、.NET Frameworkでもまったく同じロジックが実装されている。もちろんRubyのHashだって同じである。ソースは読んでないがPerlやPythonがそうなってないとも思えん。きちんと設計されたライブラリをきちんと使うことがおまえらにとってはもっとも重用である。
そういうものが使えなくてどうしてもどうしても自作するばあいは、上記の事実、つまり、rehashしないhashはhashじゃねえという事実を知っておかないと、予想外の振る舞いに戸惑うことになる。どうもhashの振る舞いが定数時間じゃなくてソース読んでみた俺がびっくり仰天とかいう話になる。おまえらもわざわざできそこないを作りたくはないだろうから、自作するならこの点はぜひ知っておくべきだ。