1

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
4

14 に答える 14

10

関数を使用して 2 つの文字列が同じハッシュを生成するときは、単なる「機会」以上のものがあるに違いありません。実際、それはおそらくあなたが思っているよりも頻繁に発生します。

いくつかの注意事項:

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

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

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

于 2008-09-15T15:30:38.560 に答える
8

2 つの String は同じ文字を持っています。(フリップフロップされた「2」と「1」に注意してください)

そのため、ハッシュ値は同じです。

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

于 2008-09-15T15:27:16.463 に答える
4

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

于 2008-09-15T15:26:35.670 に答える
2

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

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 の前にバイト値に文字位置を追加することです。

于 2008-09-15T15:55:34.053 に答える
1

ハッシュ関数は、個別の文字列に対して個別の値を返すことを意図したものではありません。ただし、優れたハッシュ関数は、似ている文字列に対して異なる値を返す必要があります。ハッシュ関数は、大規模なコレクションの検索など、さまざまな理由で検索に使用されます。ハッシュ関数が適切で、範囲[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;
    }
于 2008-09-15T17:03:37.930 に答える
1

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

64 ビット ハッシュや 128 ビット ハッシュへの移行は、衝突の可能性を減らしますが、本当の解決策ではありません。

より良いハッシュ関数が必要な場合は、暗号化ハッシュを調べることができますが、アルゴリズムを再検討して、衝突を別の方法で処理できるかどうかを判断することをお勧めします。

于 2008-09-15T15:31:14.237 に答える
1

System.Security.Cryptography名前空間には、ハッシュを行うことができる複数のクラス ( MD5など) が含まれています。これらのクラスは、おそらく自分で行うよりも適切にハッシュし、手間がかかりません。

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

于 2008-09-15T15:32:49.147 に答える
1

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

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

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

于 2008-09-15T15:33:43.250 に答える
1

彼のためにシンタックスハイライトを修正しました。

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

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

于 2008-09-15T15:36:49.623 に答える
0

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

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

于 2008-09-15T15:27:54.870 に答える
0

「それをしないでください。」

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

于 2008-09-15T15:29:50.107 に答える
0

ここに MD5 ハッシュの視覚的な基本的な実装があります

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

于 2008-09-15T15:34:46.147 に答える
0

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

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

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

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

于 2008-09-15T15:41:27.660 に答える
0

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

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

あなたの機能に問題はありません。すべての有用なハッシュ関数は衝突を生成することがあり、プログラムはそれらを解決する準備ができている必要があります。

入力が以前の入力ですでに識別されている値にハッシュされると、衝突が発生します。ハッシュ アルゴリズムが衝突を生成できない場合、ハッシュ値は入力値と同じ大きさにする必要があります。このようなハッシュ アルゴリズムは、入力値を格納するだけの場合と比較して、用途が限定されます。

-アル。

于 2008-09-15T15:53:58.443 に答える