yono

特性简介#

ハッシュテーブルシリーズのデータ構造は、キーと値のペアの関係を構築することを主な目的としています。私はすべてのロジックをキーと値の関係に抽象化するのが非常に好きなので、ハッシュテーブルのデータ構造もとても好きです。

• ハッシュテーブルの特性：ハッシュテーブルは、ハッシュ関数を使用してキー（key）をテーブル内のある位置にマッピングし、記録にアクセスする方法であり、迅速な挿入と検索をサポートします。ハッシュテーブルはキーや値の連続性を保証しません。
• 完全ハッシュテーブルの特性：完全ハッシュテーブルは、キーを値に衝突なしにマッピングできるハッシュテーブルです。これは、各キーがユニークなハッシュ値を持ち、ハッシュ関数がキーに対応する値を直接特定できることを意味し、より効率的な検索性能を提供します。
• 最小完全ハッシュテーブルの特性：最小完全ハッシュテーブルは特別に設計された完全ハッシュテーブルであり、衝突がないことを保証しながら、キーから値へのマッピング関係を最小のスペースで保存できます。この種のハッシュテーブルは、キーの集合が静的で既知である場合に特に適しています。

私たちは、テーブルの動的度とキーと値の連続性を使用して、どのハッシュテーブル構造を選択するかを評価します。これは純粋に個人的な見解です。

ハッシュテーブルは非常にメモリスペースを浪費するため、高動的なテーブルの削除や変更のアプリケーションシーンでは、ハッシュテーブルが依然としてより良い選択です。
赤ちゃんたちはこれに疑問を持つかもしれませんが、これは何か推論関係があるのでしょうか？実際にはありますが、説明するのが面倒です。

一方、キーと値の連続性が弱いアプリケーションシーンでは、ハッシュテーブルが大量のメモリスペースを浪費することは受け入れがたいです。

テーマは「最小完全ハッシュテーブル」ではありませんか？

最小完全ハッシュテーブルのアプリケーションシーンは非常に狭く、ほぼ単一であり、テーブルの関係が完全に動的でない場合にのみ使用できます。しかし、最小完全ハッシュテーブルの利点も非常に際立っています。まず、キーと値のメモリ領域はコンパクトで、無駄がありません。次に、各キーと値のペアの検索時間の複雑さは O (1) です。

（a） 完全なハッシュ関数。（b) 最小完全ハッシュ関数。

誰のライブラリを盗んだか#

その一はgperf、これは GNU の完全ハッシュ関数生成器で、PHF（完全ハッシュ関数）と MPHF（最小完全ハッシュ関数）を生成できます。重要なのは、これは GNU のプログラムライブラリであり、長期的には最も良い展望を持っています。しかし、現時点では、このライブラリは効率が非常に低く、大きなマッピングテーブルを構築することをサポートしていません。

その二はCMPH、これはブラジルの仲間が作った完全ハッシュ関数生成器で、複数のアルゴリズムをサポートしています。大きなハッシュマッピングテーブルを構築するためのトップクラスのソリューションだと称されています（ただの称号ですが）、ネットユーザーのテストによると、効率は彼の論文で主張されているほど高くはありません（でも生成はできるのですが）。
私自身のテストによると、このライブラリは本当に使いにくいです。一方で、彼はフレームワークを作成し、機能モジュールを単独で使用できず、追加すると 4 つのアルゴリズムが必要です。さらに、提供されたソースコードにはいくつかのバグがあり、正常にテストするためにはいくつかの修正が必要です。最後に最も重要なのは、これらの仲間のソースコードにはほとんどコメントがなく、修正が非常に困難であり、このライブラリを変更するには全体を理解する必要があります。|| 私のようなライブラリ改造愛好者には非常に難しいです。おそらく彼らも小人に対する防備の考慮からそうしているのでしょう。||

その三はBobMPHで、アクセスするには VPN が必要です。これは私が付けた名前で、作者は明らかに Bob Jenkins という方で、具体的に誰かはよく知らないです。ソースコードはプロジェクトや圧縮パッケージの形式で公開されておらず、独立した URL に一つずつ置かれているようです。おそらくこの方は直接サーバーに保存しているのでしょう。Windows でダウンロードするのにはかなりの労力がかかりました。まだ詳しく見ていませんが、研究の必要があれば直接私にソースコードを求めてください。

追記#

最初はビジネスロジックのキーと値のマッピング関係を最適化する必要がありました。現在は私が自作したマクロテーブル翻訳スイッチマッピングですが、これにより ROM の消費が巨大になってしまいました。同時に、私は検索時間の不確実性が非常に嫌いで、これらの要件に基づいて最小完全ハッシュテーブルを見つけました。

私は数日間、上記の **「その二 CMPH」** の実装を研究しましたが、ようやく佳境に入った時にビジネス上のバグに中断されました。バグを修正した後、突然ハッシュテーブル系の関係が私の要件に完全に合わないことに気づきました。私はキーを int 値にしたいと思っており、より多く、値はトリガー関数であり、より少なくしたいと思っていました。ハッシュテーブル系は生まれつきそれを実現できません。当然、ライブラリを変更することもできますが、それはもはやハッシュテーブルではありません。より適切な構造を探す方が良いのではないでしょうか？

上記の Bob Jenkins の見解は私の考えに非常に似ています。

また、この方のホームページも非常に興味深いですHome page, Bob Jenkins (burtleburtle.net)、

見たところ、彼はベテランプログラマーのようです。

この文は Mix Space によって xLog に同期更新されました。元のリンクは https://www.yono233.cn/posts/shoot/24_7_20_%E7%BB%9D%E5%AF%B9%E6%98%A0%E5%B0%84%E2%80%94%E2%80%94%E6%9C%80%E5%B0%8F%E5%AE%8C%E7%BE%8E%E5%93%88%E5%B8%8C%E8%A1%A8