3

多くの文字列データ (csv ファイル) の比較に問題があります。これらのファイルには uniqueID がありますが、ソートされておらず、非常に大きいです。

そこで、キーがファイルの uniqueID で、値が int で、変更に関心のある文字列の GetHashCode() を返す 2 つの辞書を作成しようとしました。

しかし、短い例:

if ("30000100153:135933:Wuchterlova:335:2:Praha:16000".GetHashCode() == 
    "30000263338:158364:Radošovická:1323:10:Praha:10000".GetHashCode())
{
    Console.WriteLine("Hmm that's strange");
}

それを行う方法は他にありますか？

フットプリントをできるだけ小さくする必要があります (約 3M 行を含む 2 つの csv ファイルの 2 つの辞書のメモリ割り当てのため) ありがとうございます

4

2 に答える 2

18

まず第一に、string.GetHashCode のドキュメントでは、時間の経過とともに安定する必要があるアプリケーションでは文字列ハッシュ コードを使用しないように具体的に述べています。文字列ハッシュ コードは、文字列を辞書に入れるという 1 つの目的にのみ使用する必要があります。

第 2 に、ハッシュ コードは一意ではありません。考えられるハッシュ コードは 40 億しかありませんが (ハッシュ コードは 32 ビット整数であるため)、明らかに 40 億を超える文字列があるため、同じハッシュ コードを持つ文字列は多数あるはずです。わずか数千の文字列のコレクションには、同じハッシュ コードを持つ 2 つの文字列が含まれる可能性が非常に高くなります。確率のグラフは次のとおりです。

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

そのため、辞書が GetHashCode を使用していても衝突が発生する可能性がある場合、辞書がどのように機能するのか不思議に思うかもしれません。答えは、同じハッシュ コードを持つ X と Y の 2 つのものを辞書に入れると、同じ「バケット」に入るということです。X を検索すると、辞書はハッシュ コードを使用して適切なバケットに移動し、適切なバケットが見つかるまで、バケット内の各要素に対してコストのかかる等価性チェックを実行します。各バケットは小さいため、ほとんどの場合、このチェックは十分に高速です。

問題の解決方法がわかりませんが、32 ビット ハッシュを使用するのは明らかに正しい方法ではないため、別の方法を試してください。管理するデータが多い場合は、CSV ファイルではなくデータベースの使用を開始することをお勧めします。そのためのデータベースです。

私は文字列ハッシュについて、あなたが興味を持つかもしれない多くの記事を書きました:

http://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/

http://blogs.msdn.com/b/ericlippert/archive/2011/07/12/what-c​​urious-property-does-this-string-have.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/10/24/do-not-use-string-hashes-for-security-purposes.aspx

http://blogs.msdn.com/b/ericlippert/archive/tags/hashing/

于 2014-01-21T17:31:04.957 に答える
0

You don't actually want to use GetHashCode. You should just compare the strings directly. However, comparing each of 3M strings against each of another 3M strings is going to be difficult in any reasonable time without sorting the lists first.

My approach would be to sort each list first (how to do that depends on a number of things), read the first sorted from each - lets call then A and B and:

  1. if A = B then do whatever and read next A and next B and repeat
  2. if A < B do whatever and read next A and repeat
  3. if A > B do whatever and read next B and repeat

.. where 'do whatever' means do whatever is required in that situation and repeat means go back to step 1.

(This process is how mainframe computers used to merge stacks of cards and has a particular name, but I can't for the life of me remember it!)

Cheers -

于 2014-01-21T17:36:06.277 に答える