この関数によって生成されるハッシュコードが一意ではないのはなぜですか?

https://stackoverflow.com/questions/63897

09-06-2019
|

質問

Google 検索から取得した以下の VB 関数をテストしています。これを使用して、文字列を簡単に比較するためのハッシュコードを生成する予定です。ただし、2 つの異なる文字列が同じハッシュコードを持つ場合があります。たとえば、これらの文字列は

「122Gen 1 ヒープサイズ (.NET CLR メモリ w3wp):mccsmtpteweb025.20833333333333E-02」

「122Gen 2 ヒープサイズ (.NET CLR メモリ w3wp):mccsmtpteweb015.20833333333333E-02」

ハッシュコードは237117279と同じです。

教えてください：- 機能の何が間違っているのでしょうか?- どうすれば修正できますか?

ありがとう

マーティン

Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)

Private Function HashCode(Key As String) As Long
  On Error GoTo ErrorGoTo

  Dim lastEl As Long, i As Long
  ' copy ansi codes into an array of long'
  lastEl = (Len(Key) - 1) \ 4
  ReDim codes(lastEl) As Long
  ' this also converts from Unicode to ANSI'
  CopyMemory codes(0), ByVal Key, Len(Key)
  ' XOR the ANSI codes of all characters'

  For i = 0 To lastEl - 1
    HashCode = HashCode Xor codes(i) 'Xor'
  Next

ErrorGoTo:
  Exit Function
End Function

解決

関数を使用して 2 つの文字列が同じハッシュを生成する場合は、単に「場合」だけではないはずです。実際、それはおそらくあなたが思っているよりも頻繁に起こります。

注意すべき点がいくつかあります:

まず、ハッシュの衝突が発生します。それは起こります。MD5 (128 ビット) のような非常に大きなスペースであっても、同じ結果のハッシュを生成できる文字列が 2 つあります。バケットを作成して、これらの衝突に対処する必要があります。

第二に、long 整数は実際には大きなハッシュ空間ではありません。より多くのビットを使用した場合よりも多くの衝突が発生することになります。

第三に、Visual Basic で利用できるライブラリ (.NET のライブラリなど) があります。 System.Security.Cryptography 名前空間) は、ほとんどの単なる人間よりもはるかに優れたハッシュ処理を実行します。

他のヒント

2 つの文字列は同じ文字を持ちます。(「2」と「1」が反転していることに注意してください)

そのため、ハッシュ値は同じになります。

ハッシュ関数が文字の順序を考慮していることを確認してください。

ハッシュ関数はハッシュ値の一意性を保証しません。入力値の範囲 (サンプル文字列から判断) が出力値の範囲 (例: 32 ビット整数) より大きい場合、一意性は物理的に不可能です。

最大の問題がバイトの位置を考慮していないことである場合は、次のように修正できます。

Private Function HashCode(Key As String) As Long
  On Error GoTo ErrorGoTo

  Dim lastEl As Long, i As Long
  ' copy ansi codes into an array of long'
  lastEl = (Len(Key) - 1) \ 4
  ReDim codes(lastEl) As Long
  ' this also converts from Unicode to ANSI'
  CopyMemory codes(0), ByVal Key, Len(Key)
  ' XOR the ANSI codes of all characters'

  For i = 0 To lastEl - 1
    HashCode = HashCode Xor (codes(i) + i) 'Xor'
  Next

ErrorGoTo:
  Exit Function
End Function

唯一の違いは、XOR の前に文字の位置をバイト値に追加することです。

一意性を保証できるハッシュ関数はありません。32 ビット整数は約 40 億個あるため、最良のハッシュ関数であっても、約 40 億個と 1 個の文字列が与えられると重複が生成されます (ほとんどの場合、ずっと前から)。

64 ビットハッシュや 128 ビットハッシュへの移行は、衝突の可能性を減らすことにはなりますが、実際の解決策ではありません。

より良いハッシュ関数が必要な場合は、暗号化ハッシュを検討することもできますが、アルゴリズムを再検討し、他の方法で衝突に対処できるかどうかを判断する方がよいでしょう。

のシステム.セキュリティ.暗号化名前空間には、ハッシュを実行できる複数のクラスが含まれています (例: MD5）これにより、おそらく自分で行うよりもうまくハッシュ化され、はるかに少ない労力で済みます。

常に車輪を再発明する必要はありません。

単純な XOR は悪いハッシュです。衝突する文字列がたくさん見つかります。まず、ハッシュは文字列内の文字の順序には依存しません。

FNV ハッシュを使用してみる http://isthe.com/chongo/tech/comp/fnv/

これは実装が非常に簡単です。各 XOR の後でハッシュコードをシフトするため、同じ文字を異なる順序で使用すると、異なるハッシュが生成されます。

ハッシュ関数は、個別の文字列に対して個別の値を返すことを意図したものではありません。ただし、優れたハッシュ関数は、似ている文字列に対して異なる値を返す必要があります。ハッシュ関数は、大規模なコレクションの検索など、さまざまな目的で検索に使用されます。ハッシュ関数が良好で、[0,N-1] の範囲の値を返す場合、M 個のオブジェクトの大規模なコレクションは N 個のコレクションに分割され、それぞれのコレクションには約 M/N 個の要素が含まれます。この方法では、M 要素の配列を検索するのではなく、M/N 要素の配列のみを検索する必要があります。

ただし、弦が 2 本しかない場合は、ないそれらのハッシュ値を計算する方が速くなります。それは より良い 2 つの文字列を比較するだけです。

重要なハッシュ関数は次のとおりです。



    unsigned int hash(const char* name) {
      unsigned mul=1;
      unsigned val=0;
      while(name[0]!=0) {
        val+=mul*((unsigned)name[0]);
        mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
        name++;
      }
      return val;
    }

彼の構文強調表示を修正しました。

また、環境についてよくわからない人、またはより安全なハッシュを提案している人のために:.Net では CopyMemory の呼び出しに括弧が必要になるため、これはクラシック (.Net 以前) VB です。

IIRC、Classic VB には安全なハッシュが組み込まれていません。ウェブ上にもあまり情報がないので、これが彼の最善の策かもしれません。

あなたが働いている環境がよくわかりません。これは .Net コードですか?本当に優れたハッシュコードが必要な場合は、独自のハッシュコードを作成しようとするのではなく、暗号化ハッシュ (実績のあるアルゴリズム) を検討することをお勧めします。

ところで、投稿を編集してコードをコードサンプル (ツールバーを参照) として貼り付けていただけますか?そうすれば読みやすくなるでしょう。

「そんなことはしないでください。」

独自のハッシュ関数を作成するのは大きな間違いです。なぜなら、あなたの言語には完全に優れたハッシュ関数である SHA-1 が確実に実装されているからです。(SHA-1 が提供する 160 ビットではなく) 32 ビットのみが必要な場合は、SHA-1 の最後の 32 ビットを使用してください。

この特定のハッシュ関数は、文字列内のすべての文字の XOR を計算します。残念ながら、XOR は結合的です。

(a XOR b) XOR c = a XOR (b XOR c)

したがって、同じ入力文字を含む文字列は同じハッシュコードになります。提供される 2 つの文字列は、2 つの文字の位置を除いて同じであるため、同じハッシュコードを持つ必要があります。

より良いアルゴリズムを見つける必要があるかもしれません。MD5 が良い選択でしょう。

XOR 演算は可換です。つまり、文字列内のすべての文字の XOR 演算を行う場合、文字の順序は関係ありません。文字列のすべてのアナグラムは、同じ XOR ハッシュを生成します。

あなたの例では、「...Gen 」の後の「1」をその後に続く最初の「2」と交換することで、2 番目の文字列を最初の文字列から生成できます。

あなたの機能には何も問題はありません。便利なハッシュ関数はすべて衝突を発生させることがあるため、プログラムで衝突を解決できるように準備する必要があります。

衝突は、入力が以前の入力ですでに識別されている値にハッシュされるときに発生します。ハッシュアルゴリズムが衝突を生成できない場合、ハッシュ値は入力値と同じくらい大きくなければなりません。このようなハッシュアルゴリズムは、入力値を保存するだけの場合と比べて、用途が限られています。

-アル。

ここには MD5 ハッシュのビジュアルな基本的な実装があります。

http://www.bullzip.com/md5/vb/md5-visual-basic.htm

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

この関数によって生成されるハッシュ コードが一意ではないのはなぜですか?

この関数によって生成されるハッシュコードが一意ではないのはなぜですか?