35

コーディングする予定のハッシュ テーブルのために、パフォーマンス指向のハッシュ関数を C++ で実装する必要があります。私はすでに周りを見回しましたが、「一般的に」良いハッシュ関数とは何かを尋ねる質問しか見つかりませんでした。私は CRC32 (しかし、適切な実装はどこにありますか?) といくつかの暗号化アルゴリズムを検討しました。ただし、私のテーブルには非常に具体的な要件があります。

テーブルは次のようになります。

100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
     examples: "become"    "and he"    ", not "

私のハッシュテーブルの最優先事項は、クイック検索（取得）です。クイック挿入は重要ではありませんが、クイック検索が必要になります。削除は重要ではなく、再ハッシュは私が検討しているものではありません。衝突を処理するために、ここで説明されているように、おそらく別のチェーンを使用します。この記事は既に見ましたが、以前にそのようなタスクを処理したことがある方のご意見をお聞かせください。

4

9 に答える 9

24

ハッシュが必要で、文字列の長さがわずか6文字であるため、この魔法を使用できるため、ケースで機能する非常に高速なものが必要であると仮定します。

size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
   return (*(size_t*)str)>> precision;
}

CRCはスローポーク用です;）

説明: これは、文字列ポインターの内容を size_t (ハードウェアの最適な一致に基づいて int32 または int64) に「似ている」ようにキャストすることによって機能します。したがって、文字列の内容は生の数値として解釈され、文字についてはもう心配する必要はありません。次に、これを必要な精度にビットシフトします (この数値を微調整して最高のパフォーマンスを実現します。数千のセット）。

また、本当にすてきな部分は、最新のハードウェア上の適切なコンパイラは、1 つのアセンブリ命令でこのような文字列をハッシュすることです。それを打ち負かすのは難しいです ;)

于 2009-03-10T03:37:22.740 に答える
14

この単純な多項式は驚くほどうまく機能します。さまざまなハッシュ関数とハッシュ乗数を研究した Microsoft Research の Paul Larson から入手しました。

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

saltハッシュテーブル攻撃から防御するために、ハッシュテーブルが作成される前に、ランダムに選択された値に初期化する必要があります。これが問題にならない場合は、0 を使用してください。

衝突を最小限に抑えるために、テーブルのサイズも重要です。あなたのは大丈夫のようですね。

于 2009-03-10T06:36:42.073 に答える
6

Boost.Functional/Hashが役立つかもしれません。試したことがないので、その性能を保証することはできません。

BoostにはCRCライブラリもあります。

私はBoost.Unorderedを最初に見ます（つまり、boost :: unordered_map <>）。コンテナには二分木の代わりにハッシュマップを使用します。

一部のSTL実装では、stdext名前空間にhash_map<>コンテナがあると思います。

于 2009-03-10T03:10:36.313 に答える
4

テーブルのサイズによって、使用するハッシュのサイズが決まります。もちろん、衝突を最小限に抑えたいと思います。最大アイテムと容量で何を指定しているかわかりません（私には同じように見えます）。いずれにせよ、これらの数値のいずれかは、32ビットハッシュで十分であることを示しています。CRC16（〜65,000の可能性）でうまくいくかもしれませんが、おそらく多くの衝突に対処する必要があります。一方、衝突はCRC32ハッシュよりも処理が速い場合があります。

私は、CRC32で行きます。ドキュメントとサンプルコードが不足することはありません。最大値を把握し、速度を優先するため、ポインターの配列を使用します。ハッシュを使用してインデックスを生成します。衝突時に、空のバケットに到達するまでインデックスをインクリメントします。すばやく簡単に。

于 2009-03-10T03:17:31.617 に答える
4

英単語を保存するため、ほとんどの文字は文字になり、データの最上位 2 ビットに大きな変化はありません。それに加えて、XORを使用するだけで、非常にシンプルに保ちます。結局のところ、暗号化の強度を求めているのではなく、適度に均一な分布を求めているだけです。これらの行に沿ったもの：

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

それに加えて、ハッシュ関数としての std::tr1::hash および/またはハッシュ テーブルの実装としての std::tr1::unordered_map を見ましたか? これらを使用すると、独自のクラスを実装するのとは対照的に、おそらく多くの作業を節約できます。

于 2009-03-10T03:53:25.417 に答える
2

短い文字列を検索する必要があり、挿入が問題にならない場合は、Bツリーまたは2〜3ツリーを使用できますが、この場合、ハッシュしてもあまりメリットはありません。

これを行う方法は、各ノードに文字を配置して、最初にノード「a」をチェックし、次に「a」の子で「p」をチェックし、次に「a」の子で「p」をチェックし、次に「 l」、次に「e」。「apple」と「apply」がある状況では、最後のノードを探す必要があります（唯一の違いは最後の「e」と「y」にあるため）

ただし、ほとんどの場合、ほんの数ステップ（ "xylophone" => "x"-> "ylophone"）で単語を取得できるため、このように最適化できます。これはハッシュよりも高速です

于 2009-03-10T03:12:01.117 に答える
2

私のハッシュテーブルの最優先事項は、クイック検索（取得）です。

それでは、ハッシュ テーブルでの検索は O(1) であるため、適切なデータ構造を使用しています。:)

CRC32 は正常に動作するはずです。実装はそれほど複雑ではなく、主に XOR に基づいています。適切な多項式を使用していることを確認してください。

于 2009-03-10T03:25:08.447 に答える
2

簡単なものはどうですか：

// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];

// Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

これは、32 ビット整数を想定しています。1 文字あたり 5 ビットを使用するため、ハッシュ値は 30 ビットしかありません。おそらく、最初の 1 つか 2 つの文字に対して 6 ビットを生成することで、これを修正できます。文字セットが十分に小さければ、30 ビット以上は必要ないかもしれません。

于 2009-03-10T03:27:24.603 に答える