すべてのハッシュ衝突を、生まれる前に消し去りたい。すべての宇宙、過去と未来の全てのハッシュ衝突を、この手でなくてもいいから。

ハッシュテーブル (hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の最も効率的な実装のうち1つである

ハッシュテーブルはあまりに愛用されてきたため、連想配列の愛称にすらなってしまいました。まあ Perl が悪いのですが、 Ruby も Hash の愛称をそのまま援用しちゃったのであまりに立派な共犯者といえるでしょう。

任意のデータからデータへの写像(ゆえにmap)を、O(1)で実現するというこの宝石ソウルジェムは、しかし近年のhashdosの「発見」により頭痛の種グリーフシードへとかわることが判明しています。

• 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン?

ハッシュテーブルに代わる連想配列の実装として最も有力なのが trie であり、そのよりコンパクトな表現である PATRICIA であることは、ほぼ確実視されています。

• 404 Blog Not Found:algorithm - Patricia Trie (Radix Trie) を JavaScript で

実際のところ、すでにあちこちで利用されているのはよいこのみんなはご存知のとおり。手前味噌ながらEncode.pmでも使ってますし、OSのメモリー管理やIMEでもよく用いられています。特に最近は簡潔データ構造の研究が進んだおかげで、元のキー列より少ないメモリー消費で、ハッシュテーブルに匹敵するどころか凌駕するような検索が実現していたりします。これまた魔法にしか見えなかったりするのですが(実装の名前が魔女だったりするし)、しかしハッシュテーブルを追放するには至っていません。

その一番の理由は、現時点における実装のほとんどが動的更新に対応していないこと。

つまり後から鍵(と連想配列の場合は鍵と値のペア)を追加したり削除したりすることができないんですね。

しかし、データの追加と削除を自在に行える trie の実装は難しい、いや難しかったのです。

こうして実装してみると、Trieがコンテンツを整理するコンテナーとして実に自然であることがわかると同時に、電脳上でこれをコンパクトに実現することがなかなか大変なのも実感できます。何も考えずに分岐点に256個のポインターを配列として並べたらそれだけで32bitアーキテクチャーでも1024bytes。いくらなんでもこれでは富豪すぎるというものです。

trieの実装の難しさは、ひとえに分岐をどう実装するかにかかっていたわけです。

ここまでは、理想の Key-Value Storage(KVS) を追い求めてきたよいこであれば、誰もが持っている問題意識でしょう。

Daniel J. Bernstein (djb)も、そのひとりでした。

Most people don't seem to realize how fast crit-bit trees can be; most people don't seem to realize how small crit-bit trees can be; most people don't seem to realize that crit-bit trees support all of the standard data-structure operations. PATRICIA is often dismissed as being large and complicated, but pure crit-bit trees are actually quite small and simple.

「君たちはいつもそうだね。PATRICIAはデブでも複雑でもないという事実をありのままに伝えると決まって同じ反応をする。わけがわからないよ」

Crit-Bit Tree (ひっそりと) 降臨

これでやっと本題です。

Crit-Bit Tree は、そのDJBが見つけたデータ構造です。

The revised strategy is much simpler: there should be one fundamental set-storage type, namely a crit-bit tree.

ひさびさにたまげましたよ。こんな簡単なことを、それまで誰も試みてなかったことに。

要点は、二つだけ。

1. キーはビット列とみなし、分岐は二分木として表現する
2. 分岐点(ノード)には、それぞれの枝へのポインター以外には分岐ビットの位置=クリティカルビット= crit bitのみを記録する

これだけみても何がなんやらなので、実物を見てみましょう。以下は 0000, 0001, 1001 (0,1,9)が入った crit-bit tree です。

0 +-> 3 +-> 0000
  |     +-> 0001
  +-------> 1001

これで 0001 を検索してみます。まず最初のノードの crit bit は0。つまり左から0番目で分岐があることを意味しているので、0の枝に行きます。次の crit bit は3なので、3番目のビットを見ます。1の枝に行きます。そして葉にたどりついたので、最後に値を比較してみます。同じなので確かに見つかりました。

次に 0111 を検索してみます。0 → 3 と追って行くと、 0001 な葉にたどり着きますが、値が一致しないので検索失敗。期待通りです。

それでは今度は、0111 をこの tree に追加してみましょう。検索失敗の位置にあったのは、0001 でした。0111 がこれと最初に異なるビットは、1番目。新たなノードを作った上で、3のノードを新ノードの0の枝に、0111を1の枝にそれぞれ追加した上で、3のノードの位置に新ノードを入れれば完成です。

0 +-> 1 +-> 3 +-> 0000
  |     |     +-> 0001
  |     +-------> 0111
  +-------------> 1001

ここで、動作の計算量を吟味してみます。まずは空間計算量。要素数をNとすると、必要なノード数は必ずN-1。そして各ノードにはcrit bitの位置と左右の枝で3 * sizeof(int)。ハッシュテーブルのように衝突を防ぐために配列に隙間を作ったりする必要もありません。なにしろ衝突しないのですから。

つぎに時間計算量。crit bit tree は平衡させない二分木とみなせるので、キーの長さをkビットとすると最悪でk回。そして枝にたどり着いてからキーの比較が一回でこれも最悪k。つまり2k。これは最悪の場合でもハッシュテーブルで衝突しなかった場合と同等です(ハッシュキーの計算にk、衝突検知にk)。

A hash table supports insertion, deletion, and exact searches. A crit-bit tree supports insertion, deletion, exact searches, and ordered operations such as finding the minimum. Another advantage is that a crit-bit tree guarantees good performance: it doesn't have any tricky slowdowns for unusual (or malicious) data.

djbの願いは、ハッシュテーブルや赤黒木を凌駕した!

djbが言ってたこと、本当なの?

一言で返せば「訂正するほど間違ってはいないね」ですが、他の実装の方が優れている点だって多々あるのでここに思いつくまま列挙しておきます。

• 分岐をたぐるということは、ポインターを追いかけるということですが、参照の局所性から見るとこれはマイナス点です。同じ回数でも、ぎっしり並んだデータを順繰りにアクセスする方がバラバラなデータにとびとびにアクセスするより速いということで、この点ではハッシュテーブルの方が優れています。
• 省資源といっても、簡潔データ構造ほどではありません。他の radix tree の実装と比較してという意味であり、実践的な実装においてはハッシュテーブルや平衡二分木より同等かやや少ないぐらいに落ち着くかと思われます。
• 特に、他の多くのPATRICIAの実装と違って、キーの「たたみこみ」がない点には注目。要するにf|foo|fool|foolish|foolishをf(oo(l(ish(ness)?)?)?のようにはしてくれません。

最後の点は、なぜこれほど単純な仕組みが今まで見落とされたかを説明する一番説得力のある理由だと思います。djbほど聡明な人でも、見つけたのはCDBよりずっと後の2004年で、公開したのが2006年ですから。

とはいえ、これらを克服する手段は、既存のハッシュテーブや二分木やtrieで使われているものをそのまま持ってこれます。

• ノードは都度mallocするのではなく、配列にあらかじめ確保しておく
• 枝の表現は今や64bitもあるポインターではなく、その配列の添字とする

などなど。

それにしても qmail や djbdns や daemontools の作者という著名人による発見なのに、ほとんど知られていないのです。私自身、知ったのはつい先日だったりします。

Crit-bit trees are underused and it's this author's hope that a good example will aid their adoption.

自分で思いつかなかったのが恥ずかしいと思わせるほど簡単で、しかしやはり真に難しいのは、複雑なものごとを複雑なまま理解することではなく、それを簡単にすることなのだと改めて思い知らされました。

If you're designing a programming language, imagine how much happier your programmers will be if your basic built-in data type allows not just looking up x, but also enumerating the strings after x in sorted order. You can't do this with hash tables. You could do it with an AVL tree, but your operations will be simpler and faster if you use a crit-bit tree.

シンプルさとそれによる資源量の見積もりやすさと実装しやすさ。汎用ソートの選択において Quicksort が Mergesort になっていった変化が、連想配列と集合という、今日日のプログラマーにとって空気より当然で不可欠なデータ構造の実装に起こりうるだけの力を crit-bit tree は秘めているように思われます。

Dan the Man with Too Many Keys to Look up