1

操作しなければならない長い文字列がたくさんあります。それらは何度も発生する可能性があり、2 回発生した場合は無視したいと思います。これを行う最善の方法は、文字列をハッシュし、ハッシュのリストをある種の順序付けられたリストに格納し、ルックアップ時間を高速にして、データセットから新しい文字列が渡されたときにいつでも比較できるようにすることだと考えました。

要件：

  • コレクションにアイテム (ハッシュ) を追加できるようにする
  • 特定のハッシュが既にコレクションにあるかどうかを (すばやく) チェックできるようにします。
  • あまりにもメモリ集約的ではありません。これらのハッシュが最大 100,000 個になる可能性があります。

違いがある場合は、逆方向に移動する必要はありません (キー -> 値)。

どの .NET データ型が最も効率的かについて何か提案はありますか?

4

2 に答える 2

8

これを行う最善の方法は、文字列をハッシュし、ハッシュのリストをある種の順序付けられたリストに格納し、ルックアップ時間を高速にして、データセットから新しい文字列が渡されたときにいつでも比較できるようにすることだと考えました。

いいえ、そうしないでください。2 つの理由:

  • ハッシュは、2 つの値が同じかどうかのみを示します。それらが同じかどうかはわかりません。
  • あなたはすでにあなたのために行われている多くの仕事をしているでしょう.

基本的には、HashSet<String>. それは問題ないはずです。簡単なルックアップが必要です。自分で実装する必要はありません。

欠点は、すべての文字列をメモリに保持することになることです。それが問題である場合は、別の戦略を立てる必要があります...実際には、ハッシュだけをメモリに保持することになる可能性があります。正確な詳細は、おそらく文字列がどこから来ているか、および誤検知が発生した場合にどのような問題が発生するかによって異なります。たとえば、各文字列の MD5 ハッシュを「単なるhashCode」ハッシュよりも優れたものとして保持できますが、それでも攻撃者は同じハッシュを持つ別の文字列を提示することができます。問題ありますか？その場合は、より安全なハッシュ アルゴリズム (SHA-256 など) が役立つ可能性があります。ただし、文字列ごとに異なるハッシュになることは保証されません。

本当に確実にしたい場合は、ハッシュをメモリに保持する必要がありますが、実際の文字列データを (ディスクまたはデータベースに) 保持する必要があります。前) 保存された文字列を新しい文字列と比較する必要があります。

ハッシュをメモリに格納している場合、最適なアプローチは、使用しているハッシュのサイズによって異なります。たとえば、64 ビット ハッシュだけの場合は、Longハッシュごとを使用して、HashSet<Long>. より長いハッシュの場合、簡単に比較できるオブジェクトなどが必要になります。その時点で、 (Guava v16 以降非推奨)のファクトリ メソッドと共に、Guavaとそのクラスを確認することをお勧めします。HashCodeHashCodes

于 2013-05-29T11:35:17.073 に答える
2

セットでご利用ください。

ISet<T>インターフェースは、例えばによって実装されていますHashSet<T>

AddそしてContains、O(1) が期待されます。ハッシュ関数が非常に貧弱でない限り、最悪のケースは O(n) です。

于 2013-05-29T11:34:35.180 に答える