val it: α → α = fun

ハッシュ表でも拡張可能なものがあったり(むかーし技術評論社から出ていた雑誌で読んだ記憶が。誌名は忘れました。SoftwareDesignとかプロセッサではないです)、全要素のハッシュ値を再計算してより大きな表に切り替える(PerlとかRubyでやってますね) という手段があるわけですけど、連想配列の、「数値以外のオブジェクト(という表現でいいのだろうか)で添え字付けする」という性質にのみ着目した場合にハッシュ以外の手段を採用した方がよい場面もあるんじゃないのかなあという考えが念頭にありました。

データ量が漸進増加するときに遅くなる可能性は確かにあるけど、平衡木だって回転させるコストも発生する。もちろん木の探索と回転は O(log n) なのに rehash は全要素を再配置するため遅くなりそうだが、新しいサイズをうまく取るとならしコストは O(1) になりそうな。検証してないけど(これと同じリクツ)。

ちなみに Haskell (GHC) では Data.Map がよく使われる気がしていて、これは AVL 木なんですが、なぜかというと関数的に書きやすいから(たぶん)。ハッシュ表も GHC には標準で存在するものの、関数的ではないので IO を伴い、書きづらい。ただし圧倒的に速いです。ちなみに GHC には IntMap なるものもあり、これはパトリシア木(Trieの一種)を使っていて速いらしいのだが IntMap はほとんど使ったことないな。

それから dbm では単純なハッシュのものもあればツリーのインデックスを使うこともあって、前者は gdbm とか ndbm とか cdb とか qdbm の Depot とか。後者は Berkeley-DB とか qdbm の Villa とか。でも BDB も qdbm も B+tree だね。 Tokyo cabinet はどうだったかと思ったけどやっぱりハッシュとB+tree と両方が用意されるらしい。

dbm がツリーのようなデータ構造を利用するのはまさに順序が重要だからで、特定のプレフィクスをもつキー集合とか、特定の範囲内のキーに対応する値を取り出すとか、 sql の where 節に書ける程度の演算はそこそこ速くやってほしいのでそのようになっているのだと思われます。一方たとえば skk の辞書みたいなやつは完全一致以外を考えなくていいので、こういうのはハッシュで充分なわけで、 cdb を使った skk サーバみたいなのが出回っていてこれがめちゃくちゃ速かったりする。