特徴

ハッシュテーブル系のデータ構造は、キーと値のペア関係の構築が主役だ。私はあらゆるロジックをキーと値の関係に抽象化するのがとても好きなので、ハッシュテーブルというデータ構造も大好きだ。

-

ハッシュテーブルの特性：ハッシュテーブルとは、ハッシュ関数を使ってキー（key）をテーブル内の位置にマッピングし、レコードへアクセスする方法だ。高速な挿入と検索を実現する。ハッシュテーブルは、キーや値の連続性を保証しない。

• 完全ハッシュテーブルの特性：完全ハッシュテーブルは、一切の衝突なしにキーを値へマッピングできるハッシュテーブルだ。つまり、各キーが一意なハッシュ値を持ち、ハッシュ関数がキーに対応する値を直接特定できるため、より効率的な検索性能が得られる。
• 最小完全ハッシュテーブルの特性：最小完全ハッシュテーブルは、特別に設計された完全ハッシュテーブルで、一切の衝突がないことを保証しつつ、最小の空間でキーから値へのマッピングを格納する。キーの集合が静的かつ既知である場合に特に適している。

どのハッシュテーブル構造を選ぶかを、テーブルの動的度とキーと値の連続性で評価してみよう。あくまで私見だ。

ハッシュテーブルはメモリを大量に浪費するが、テーブルの削除・変更が多い高動的なアプリケーションでは、それでもハッシュテーブルの方が良い選択だ。 「それってどういう理屈なの？」と疑問に思う読者もいるかもしれないが、実は理由はある。ただ説明するのが面倒なだけだ。

一方、キーと値の連続性が弱い応用シーンでは、ハッシュテーブルによるメモリの大量浪費は許容しにくくなる。

テーマは「最小完全ハッシュテーブル」じゃなかったのか？

最小完全ハッシュテーブルの適用シーンは非常に狭く、ほとんど単一的だ。使えるのは、テーブルの関係性がまったく動的でない場合に限られる。ただし、最小完全ハッシュテーブルの利点もかなり際立っている。まず、キーと値のメモリ領域がコンパクトで、無駄が生じないこと。次に、どのキーと値のペアも検索の時間計算量が O(1) であることだ。

誰のライブラリをパクるか

その1は gperfだ。これは GNU の完全ハッシュ関数ジェネレータで、PHF（完全ハッシュ関数）と MPHF（最小完全ハッシュ関数）を生成できる。何せ GNU 製のプログラムだから、長期的に見れば将来性が一番ある。ただし、今のところ効率が極めて低く、大きなマッピングテーブルを作ることもできない。

その2は CMPHだ。ブラジルの兄貴が作った完全ハッシュ関数ジェネレータで、複数のアルゴリズムに対応している。大きなハッシュマッピングテーブルを構築するための最高級ソリューションと自称している（あくまで自称）。ネットの検証では、論文で主張するほど効率的ではないらしい（それでも生成はできるが）。 自分で試した限り、このライブラリは本当に使いにくい。まず、フレームワーク化されていて機能モジュールを単体で使えない。追加するとアルゴリズムが四つまとめて付いてくる。さらに、公開されているソースコードには少しバグがあって、数か所直さないと正常にテストできない。そして何より、あの連中のソースコードにはコメントがほとんどない。改造するのは非常に難しく、ライブラリ全体を理解する必要がある。||私のようなライブラリ改造好きには難しすぎる。もしかすると、あの兄貴たちも悪人を警戒しているのかもしれない。||

その3は BobMPHで、アクセスには VPN が要る。この名前は私が勝手に付けた。作者の兄貴はどうやら Bob Jenkins という名前だが、詳しく調べたわけではない。ソースコードもプロジェクトや圧縮ファイルとして公開されているわけではなく、個別の URL にバラバラに置かれている。たぶん、この兄貴がサーバーにアーカイブとして直接置いているだけなんだろう。Windows でダウンロードするのにも一苦労した。まだ詳しく見ていないが、研究が必要なら直接私にソースコードを頼んでくれ。

追記

もともとは、とある業務ロジックのキーと値のマッピングを最適化する必要があった。今は自作のマクロテーブル変換 switch マッピングを使っているが、これだと ROM の消費が莫大になる。同時に、検索時間が不確定なのが大嫌いだった。そうした要件から最小完全ハッシュテーブルに行き着いた。

数日かけて上記の「その2 CMPH」の実装を調べていたのだが、ようやく調子が出てきたところで業務のバグを処理することになって中断した。バグを直して戻ってきたとき、ふとハッシュテーブル系の関係性は自分の要件にまったく合っていないと気づいた。キーは int 値でもっともっと多く、値はトリガー関数でもっともっと少ない、というのが理想だった。だが、ハッシュテーブル系ではそもそも実現不可能だ。もちろん、ライブラリを改造すれば実現できるが、それはもはやハッシュテーブルではない。だったら、もっと適した構造を探せばいいじゃないか。

先ほどの Bob Jenkins は、私とかなり似た考えを持っている。

この兄貴のホームページもかなり面白い。彼はお金持ちになれる「裏ワザ」を紹介している。年利10％を実現すれば、25年で10倍になるとか。Bob Jenkins のホームページ (burtleburtle.net)

どうやらベテランのプログラマーらしい。