問題タブ [perfect-hash]

私はよく単射の写像を扱います。プログラミング用語では、これは、すべての値と、もちろんすべてのキーが一意である辞書として表現できます。

辞書から期待されるすべての時間の複雑さのプロパティを備えた単射マッピング用のメモリ効率の高いデータ構造はありますか?

例えば：

Two way/reverse mapのすべてのソリューションは、双方向マップで操作を実行しやすくすることに重点を置いて、2 セットのマッピングを使用または結合する必要があるようです。これは、メモリにきちんと収まる小さな辞書には適していますが、大きな辞書には適していません。

要件は、一方向マッピングのみを格納する通常のディクショナリに対して、単射双方向マップを格納する追加のメモリ オーバーヘッドがないことです。

辞書は、連想配列データ型を使用するハッシュ テーブルを使用することを理解しています。定義上、連想配列は一意のキーを使用してキー -> 値のマッピングを実装します。理論的または実際に、逆引きを可能にするスマートな単射マッピングを生成することは可能ですか?

不可能な場合は、辞書と同じ効率でそのような構成を実装することが難しい、または不可能である理由を説明していただければ幸いです。

アップデート

@rpy との議論に続いて (以下のコメントを参照)、完全な可逆ハッシュ関数を使用して Python 辞書のようなオブジェクトを設定する方法に関する情報は役に立ちます。しかし、もちろん、機能する実装が理想的です (私はすでに完全に試しました)。

まばらに入力されたキーのリストには、64 ビットから 16 ビットの完全なハッシュ関数が必要です。

長さ64ビットの48326個のキーを持つPythonの辞書があります。このキーのリストの最小完全ハッシュを作成したいと思います。（MPHを計算するのに数日待つ必要がないので、16ビットハッシュにマッピングしても問題ありません）

目的は、最終的にこのディクショナリを dict 値を含む配列として C に移植することであり、インデックスは key を input として取得する最小完全ハッシュ関数によって計算されます。構築中のアプリケーションの C ポートで外部ハッシュ ライブラリを使用できません

質問: キーを入力として受け取り、ハッシュ パラメータを提供し、(ハッシュに使用される定義済みアルゴリズムに基づいて) 出力として提供する Python ライブラリはありますか。

ライブラリの完全性 2.0.0を見つけましたが、キーが 64 ビット形式であるため、これがハングしました。（2000個のキーのサブセットでテストした場合でも）

編集 コメントで示唆されているように、私はスティーブ・ハノフのアルゴを見て、64 ビット整数を取るようにハッシュ関数を変更しました (このwiki ページに従って FNV プライムとオフセットの値を変更します)

結果を取得している間、残念ながら、マップは -ve インデックス値を返しますが、それを機能させることはできます。つまり、-ve インデックスをチェックして、ハッシュ計算にさらに 4 サイクルを追加する必要があります。

これは避けたい

私は (C++ で) パーサーを作成しており、それぞれが有効なパーサー タグを表す小さな文字列 (100 未満) のリストを持っています。このような既知の各タグを、さらに処理するために列挙値にマップする必要があります。すべての文字列はコンパイル時に認識されるため、この目的のために完全なハッシュ関数を使用することを検討しています。

完全なハッシュ関数を生成するための既存のツールとアルゴリズム sa gperf、mph、cmphを認識しています。ただし、そのようなツール/実装はすべて、いくつかの制限付きライセンス (GPL、LGPL、MPL など) の下にありますが、私の制限のために、再利用のための緩和されたライセンス (MIT ライセンスなど) の下にあり、できればC/C++ または C#。そのようなツールやコードを知っていますか?