C ++ハッシュテーブルに適したハッシュ関数がありますか？

StackOverflow https://stackoverflow.com/questions/628790

  •  07-07-2019
  •  | 
  •  

質問

コーディングするハッシュテーブルのために、パフォーマンス指向のハッシュ関数をC ++で実装する必要があります。私はすでに見て回ったが、良いハッシュ関数<！> quot;一般的な<！> quot;とは何かを尋ねる質問だけを見つけた。 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 "

私のハッシュテーブルの最優先事項は、クイック検索（検索）です。クイック挿入は重要ではありませんが、クイック検索に伴い追加されます。削除は重要ではなく、再ハッシュは私が検討するものではありません。衝突を処理するために、こちら。私はすでにこの記事を見てきましたが、そのようなことを扱った人の意見をお願いします前のタスク。

役に立ちましたか？

解決

ここで、ハッシュが必要だと仮定し、あなたのケースで動作する非常に高速が必要だと仮定します。文字列はわずか6文字なので、この魔法を使用できます：

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

CRCはslowpokes用です;）

説明： これは、文字列ポインターの内容を<！> quot; look like <！> quot;にキャストすることで機能します。 size_t（ハードウェアに最適な一致に基づいて、int32またはint64）。したがって、文字列の内容は生の数字として解釈され、文字の心配はなくなり、必要な精度にビットシフトします（この数字を最高のパフォーマンスに調整すると、2つの文字列をハッシュするのにうまくいくことがわかりました数千のセット）。

また、本当にきちんとした部分は、現代のハードウェアのきちんとしたコンパイラが1つのアセンブリ命令でこのような文字列をハッシュすることです。

他のヒント

この単純な多項式は驚くほどうまく機能します。 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を使用します。

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

Boost.Functional / Hash はあなたに使用します。試したことがないので、その性能を保証することはできません。

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

最初に Boost.Unordered を探します（すなわち、boost :: unordered_map <！> lt; <！> gt;）。コンテナにバイナリツリーではなくハッシュマップを使用します。

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

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

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

英語の単語を保存するため、ほとんどの文字は文字になり、データの最上位の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をハッシュテーブルの実装として見ましたか？これらを使用すると、おそらく独自のクラスを実装するよりも多くの作業を節約できます。

  

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

それでは、ハッシュテーブルでの検索はO（1）であるため、正しいデータ構造を使用しています。 ：）

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

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

// 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ビット整数を想定しています。文字ごとに5ビットを使用するため、ハッシュ値には30ビットしかありません。これを修正するには、おそらく最初の1文字または2文字に対して6ビットを生成します。文字セットが十分に小さい場合、30ビットを超える必要はないかもしれません。

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

これを行うには、各ノードに文字を配置して、最初にノード<！> quot; a <！> quot;を確認し、次に<！> quot; a <！> quotを確認します。 <！> quot; p <！> quot;の子、および<！> quot; p <！> quot;の子、そして<！> quot; l <！> quot;そして、<！> quot; e <！> quot;。 <！> quot; apple <！> quot;がある場合および<！> quot; apply <！> quot;最後のノードをシークする必要があります（最後の<！> quot; e <！> quot;と<！> quot; y <！> quot;のみが異なるため）

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

C ++ 11以降、C ++は std::hash< string >( string ) 。これは、ハッシュコードの適切な配布を提供する効率的なハッシュ関数である可能性が高いほとんどの文字列。

さらに、ハッシュテーブルの実装を考えている場合は、C ++ std::unordered_map 。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top