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