1,000 万を超える文字列をファイルに読み書きする必要があります。また、ファイル内での重複は望ましくありません。文字列は読み取られるとすぐにファイルにフラッシュされるため、メモリに保持していません。
ハッシュコードの衝突により、重複として文字列を見逃す可能性があるため、ハッシュコードを使用できません。グーグルで見つけた他の2つのアプローチ：
1. MD5 のようなメッセージ ダイジェスト アルゴリズムを使用しますが、計算と保存にコストがかかりすぎる可能性があります。
2. チェックサム アルゴリズムを使用します。[これが文字列の一意のキーを生成するかどうかはわかりません-誰か確認してください]
利用可能な他のアプローチはありますか？ありがとう。
TreeSet<String>1000万個の文字列をメモリに保存するのは確かに多いので、たとえば最初に保存するのではなく、すぐにファイルに書き込む理由は理解できますが、比較したい1000万個の一意の数値キーをどこに保存しますか? 一意の数値(文字よりも基数/基数がはるかに小さい)を維持したい場合は、キーを文字列自体よりも短くすることはできないため、メモリを節約できません。または、最高でも GZIP のようなデータ圧縮を使用することもできますが、これは多くのオーバーヘッドを追加するだけです。2 つの異なる文字列が同じハッシュを生成する可能性があるため、 MD5 も不適切です。
UNIQUEこれについては、適切な RDBMS (SQL データベース) を使用して、列を設定し、それに応じて制約違反を処理するよりも良い解決策はありません。RDBMS は、この種のタスクに対して高度に最適化されています。
データベースを本当に考慮できない場合は、書き込み/フラッシュの前に既存のエントリのファイルを再度読み取る必要があります。それほど高速ではないかもしれませんが、確かにメモリ効率が良いです。
その文字列よりも短い文字列の一意のキーを生成する関数を作成する方法はありません。
タスクを解決できるデータ構造があります。データが十分に大きい場合は、B ツリーが適合する可能性があります。入力の性質によっては、より効果的な方法があるかもしれません。
重複を確実に削除することは、ファイルを並べ替えるのと同じくらい困難です。別の回答が示すように、各文字列の完全なコピーをメモリに保持せずに重複を正確に検出する保証された方法はありません。これは、まさに回避しようとしているようです。
ハッシュコードのメモリ内またはディスク上のインデックスを保持し、これらを使用してファイル ストレージから実際の文字列を取得して比較することもできますが、これは基本的に、データベースが実行できることを複製することになります。
別の方法は、ファイルが完成したら後処理することです。UNIX の sort コマンドは大きなファイルの処理に非常に適しているため ( UNIX の sort コマンドで非常に大きなファイルをソートするにはどうすればよいでしょうか? )、標準の UNIX コマンドライン アプローチが適切に機能することを期待しています。
sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt
(重複を削除するために uniq に渡す前に、ファイルを最初にソートする必要があることに注意してください)。
これらのツール (または同等のもの) を利用できない場合は、いつでも外部マージ ソートのバリアントを自分で実装してみることができます。
文字列が可能な文字列 (N) の固定プールからのものである場合、最小限の完全ハッシュを使用して配列 0...N-1 を作成できます。完全ハッシュ関数によって決定されたスロットのゼロは、文字列がこれまでに見られていないことを意味します。
それ以外の場合、大量のメモリとこれまでに提案された解決策以外の唯一の効果的な正しい手段は、文字列をファイルに書き込むことを決定する前にファイルを再読み取りすることです。
ファイルの一部をメモリ マッピングすることで、これを可能な限り効率的に行うことができます。
他の誰かがすでに提案したように、データベースを使用することが最善の解決策だと本当に思います。
何らかの理由でデータベースを使用できない場合でも、ハッシュコードを使用できます。確かに衝突はあります。ハッシュコードの重複を検出したときに、プログラムがファイルをチェックして、それが本物の重複か衝突かを判断するように、いくつかのコードを追加するだけです。