5

そこから中小規模の静的ハッシュ テーブルを作成する必要があります。通常、これらには 5 ～ 100 のエントリがあります。ハッシュ テーブルが作成されると、すべてのキー ハッシュが事前に認識されます (つまり、キーは既にハッシュです)。現在、私は HashMap を作成しています。気になるサイズの平均ルックアップ。ウィキペディア連鎖を伴う単純なハッシュテーブルは、完全なテーブルに対して平均で 3 回のルックアップをもたらすと主張しているため、これはまだ私にとって面倒なことではありません (つまり、最初のエントリとして hash%n を取得し、連鎖を実行します)。ハッシュを前もって、高速で静的な完全なハッシュを取得する簡単な方法があるように思われます-しかし、私はどのように良いポインタを見つけることができませんでした. つまり、追加のオーバーヘッドなしで (ほとんど?) 償却された O(1) アクセス。このような静的テーブルをどのように実装すればよいですか?

メモリ使用量は重要なので、保存する必要が少ないほど良いです。

編集: 衝突を 1 つほど手動で解決する必要がある場合は問題ないことに注意してください。つまり、たとえば、平均して直接アクセスし、最悪の場合 3 つの間接アクセスを持つ連鎖を行うことができれば、それで問題ありません。完全なハッシュが必要というわけではありません。

4

3 に答える 3

3

c または c++ の場合、gperfを使用できます

GNU gperf は完璧なハッシュ関数ジェネレーターです。指定された文字列のリストに対して、入力文字列に応じて値を検索するために、ハッシュ関数とハッシュ テーブルを C または C++ コードの形式で生成します。ハッシュ関数は完全です。つまり、ハッシュ テーブルには衝突がなく、ハッシュ テーブルのルックアップには単一の文字列比較のみが必要です。

GNU gperf は高度にカスタマイズ可能です。C または C++ コードを生成するためのオプション、ハッシュ テーブルの代わりに switch ステートメントまたはネストされた if を発行するためのオプション、および gperf で使用されるアルゴリズムを調整するためのオプションがあります。

于 2011-06-10T20:56:25.513 に答える
3

プリプロセッサを使用して外部ライブラリを使用せずに、C で小さなハッシュを作成することもできます。たとえば、次のようになります。

swich (hash_string(*p))
{
case HASH_S16("test"):
    ...
    break;
case HASH_S256("An example with a long text!!!!!!!!!!!!!!!!!"):
    ...
    break;
}

コード@ http://www.heeden.nl/statichashc.htmを見てください

于 2015-11-14T21:20:44.250 に答える
0

Sux4jを使用して、Java または C++ で最小限の完全なハッシュを生成できます。(Java を使用しているかどうかはわかりませんが、HashMap について言及したので、推測しています。) C の場合は、cmphライブラリを使用できます。

于 2011-06-10T20:53:44.550 に答える