c# - 文字列のハッシュ衝突とパフォーマンスの点で最高のハッシュアルゴリズム

Question

次の優先順位 (この順序で) がある場合、最適なハッシュアルゴリズムは何でしょうか。

最小のハッシュ衝突
パフォーマンス

安全である必要はありません。基本的に、いくつかのオブジェクトのプロパティの組み合わせに基づいてインデックスを作成しようとしています。すべてのプロパティは文字列です。

C# 実装への参照を歓迎します。

score 33 · Accepted Answer

「最高」という言葉を忘れてください。ハッシュ化する必要がある非常に限られたデータセットを持っていない限り、誰がどのハッシュアルゴリズムを思いつくかに関係なく、平均的に非常にうまく機能するすべてのアルゴリズムは、適切な方法で (またはあなたの観点から) 与えられた場合、完全に役に立たなくなる可能性があります。「間違った」) データ。

CPU時間を使いすぎずにハッシュをより衝突の少ないものにする方法を考えて時間を浪費する代わりに、「衝突の問題を軽減する方法」について考え始めたいと思います。たとえば、すべてのハッシュバケットが実際にはテーブルであり、このテーブル内のすべての文字列 (衝突があった) がアルファベット順に並べ替えられている場合、バイナリ検索 (O(log n) のみ) を使用してバケットテーブル内を検索できます。つまり、毎秒ハッシュバケットに 4 つの衝突がある場合でも、コードは適切なパフォーマンスを維持します (衝突のないテーブルに比べて少し遅くなりますが、それほどではありません)。ここでの大きな利点の 1 つは、テーブルが十分に大きく、ハッシュが単純すぎない場合、

実際、バイナリ検索を使用してソートされたテーブル内を直接検索すると、ハッシュよりも高速であることが判明する前に、私自身状況がありました。私のハッシュアルゴリズムは単純でしたが、値をハッシュするのにかなりの時間がかかりました。パフォーマンステストでは、約 700 ～ 800 を超えるエントリを取得した場合にのみ、ハッシングが実際に二分探索よりも高速であることが示されました。ただし、いずれにしてもテーブルが 256 エントリを超えることはなく、平均テーブルが 10 エントリ未満であるため、ベンチマークはすべてのシステム、すべての CPU で二分探索がより高速であることを明確に示しました。ここでは、通常、データの最初のバイトを比較するだけで、次の bsearch 反復につながるという事実が大きな利点であることが判明しました (最初の 1 ～ 2 バイトでデータが大きく異なっていたため)。

要約すると、平均してあまり多くの衝突を引き起こさず、かなり高速なまともなハッシュアルゴリズムを採用し（非常に高速であれば、さらに衝突を受け入れることさえできます！）、むしろコードをどのように最適化しますか衝突が発生した場合のパフォーマンスの低下を最小限に抑えるためです (衝突は起こります! ハッシュ空間が少なくともデータ空間と同じかそれ以上であり、一意のハッシュ値をすべての可能なデータセットにマップできる場合を除きます)。

score 17 · Accepted Answer

ナイジェルキャンベルが指摘したように、「最適な」ハッシュ関数などというものはありません。これは、ハッシュするもののデータ特性と、暗号化品質のハッシュが必要かどうかに依存するためです。

とはいえ、ここにいくつかの指針があります：

ハッシュへの入力として使用しているアイテムは単なる文字列のセットであるため、これらの個々の文字列ごとにハッシュコードを単純に組み合わせることができます。これを行うために提案された次の疑似コードを見たことがありますが、特定の分析については知りません。
```
int hashCode = 0;

foreach (string s in propertiesToHash) {
    hashCode = 31*hashCode + s.GetHashCode();
}
```
この記事によると、System.Web には、ハッシュコードを組み合わせて使用する内部メソッドがあります。
```
combinedHash = ((combinedHash << 5) + combinedHash) ^ nextObj.GetHashCode();
```
ハッシュコードを単純に xor するコードも見たことがありますが、それは悪い考えのように思えます (ただし、これを裏付ける分析はありません)。同じ文字列が別の順序でハッシュされると、衝突が発生します。
私は FNV を効果的に使用しました: http://www.isthe.com/chongo/tech/comp/fnv/
Paul Hsieh のまともな記事があります: http://www.azillionmonkeys.com/qed/hash.html
1997 年に Doctor Dobb's Journal に最初に掲載された Bob Jenkins による別の素晴らしい記事 (リンクされた記事には更新があります): http://burtleburtle.net/bob/hash/doobs.html

score 8 · Accepted Answer

私はここで足が不自由になり、ピンポイントの答えではなく、より理論的な応答をしますが、その価値を理解してください。

まず、2つの明確な問題があります。

a。衝突確率b。ハッシュのパフォーマンス（つまり、時間、CPUサイクルなど）

2つの問題は穏やかに相互に関連しています。それらは完全には相関していません。

問題aは、ハシェイと結果のハッシュスペースの違いを扱います。1KBファイル（1024バイト）ファイルをハッシュし、ハッシュが32バイトの場合、次のようになります。

1,0907481356194159294629842447338e + 2466（つまり、2466個のゼロを持つ数値）入力ファイルの可能な組み合わせ

ハッシュスペースには

1,1579208923731619542357098500869e + 77（つまり、77個のゼロを持つ数値）

違いは巨大です。それらの間には2389個のゼロの違いがあります。10^2466ケースを10^77ケースに減らしているため、衝突が発生します（2つの異なる入力ファイルがまったく同じハッシュを持つ場合の衝突は特殊なケースです）。

衝突のリスクを最小限に抑える唯一の方法は、ハッシュスペースを拡大して、ハァッを長くすることです。理想的にはハッシュはファイルの長さを持ちますが、これはどういうわけかモロニックです。

2番目の問題はパフォーマンスです。これはハッシュのアルゴリズムのみを扱います。もちろん、より長いハッシュはおそらくより多くのCPUサイクルを必要としますが、よりスマートなアルゴリズムはそうではないかもしれません。この質問に対する明確なケースの答えはありません。大変です。

ただし、さまざまなハッシュ実装のベンチマーク/測定を行い、これから事前の結論を引き出すことができます。

幸運を ;）

score 8 · Accepted Answer

単一の最適なハッシュアルゴリズムはありません。既知の入力ドメインがある場合は、gperfなどの完全ハッシュジェネレーターを使用して、その特定の入力セットで 100% のレートを得るハッシュアルゴリズムを生成できます。そうでなければ、この質問に対する「正しい」答えはありません。

score 3 · Accepted Answer

Java の String クラスで使用される単純な hashCode は、適切なアルゴリズムを示している可能性があります。

以下は「GNU Classpath」の実装です。(ライセンス: GPL)

  /**
   * Computes the hashcode for this String. This is done with int arithmetic,
   * where ** represents exponentiation, by this formula:<br>
   * <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>.
   *
   * @return hashcode value of this String
   */
  public int hashCode()
  {
    if (cachedHashCode != 0)
      return cachedHashCode;

    // Compute the hash code using a local variable to be reentrant.
    int hashCode = 0;
    int limit = count + offset;
    for (int i = offset; i < limit; i++)
      hashCode = hashCode * 31 + value[i];
    return cachedHashCode = hashCode;
  }

score 2 · Accepted Answer

こちらで説明されている Knuth ハッシュ関数を使用して両方を取得できます。

2 の累乗のハッシュテーブルサイズ (1 回の乗算、1 回のシフト、および 1 回のビットアンド) を想定すると、非常に高速です。さらに重要なのは、(あなたにとって) 衝突を最小限に抑えるのに優れていることです (この分析を参照してください)。

その他の優れたアルゴリズムについては、こちらで説明しています。

score 1 · Accepted Answer

これを自分で実装する簡単な方法を次に示します: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

投稿からのスニペットは次のとおりです。

大文字の英字の文字セットがあるとすると、文字セットの長さは 26 で、A は数字 0、B は数字 1、C は数字 2 など、Z は数字で表すことができます。 25. ここで、この文字セットの文字列を一意の数値にマップするときはいつでも、バイナリ形式の場合と同じ変換を実行します

score 1 · Accepted Answer

これがカッコウハッシュです。

ルックアップでは、ハッシュテーブル内の 2 つの場所のみを検査する必要があり、最悪の場合でも一定の時間がかかります (Big O 表記を参照)。これは、他の多くのハッシュテーブルアルゴリズムとは対照的です。これらのアルゴリズムでは、ルックアップを実行する時間に一定の最悪のケースの制限がない場合があります。

衝突とパフォーマンスの基準に適合すると思います。このタイプのハッシュテーブルは 49% しか使用できないというトレードオフがあるようです。

c# - 文字列のハッシュ衝突とパフォーマンスの点で最高のハッシュ アルゴリズム

9 に答える 9

Related

Reference

c# - 文字列のハッシュ衝突とパフォーマンスの点で最高のハッシュアルゴリズム