Java：大規模な重複検出のためにハッシュセットを最適化する

Question

私は多くのツイートを処理しているプロジェクトに取り組んでいます。目標は重複を削除することです。私はtweet IDを持っています。これは、フォーマットの文字列として入っています。"166471306949304320"

これはしばらくの間うまく動作するHashSet<String>です。しかし、私が約1000万アイテムに達する頃には、私は激減し、最終的には再ハッシュからGCエラーが発生するでしょう。私は

tweetids = new HashSet<String>(220000,0.80F);

とのより良いサイズ/ロードを定義しようと、それはそれは遠く少しを取得することができますが、それでも（約10百万処理する限り3Xを取っている）耐え難いほど遅いです。これをどのように最適化できますか？私は、最終的にどれくらいの数のアイテムがセットに収まるべきかを概観しているので（この場合、2億2000万-200万）、2〜3回しか再ハッシュしないハッシュセットを作成するか、セットはあまりにも多くの時間ペナルティを被るでしょうか？文字列を使用していない場合や、別のHashCode関数（文字列の特定のインスタンスの場合は、どうすればよいかわかりません）を定義すると、よりうまくいくのでしょうか？実装コードのこの部分は以下のとおりです。あなたの勧告に

tweetids = new HashSet<String>(220000,0.80F); // in constructor 
duplicates = 0; 
... 
// In loop: For(each tweet) 
String twid = (String) tweet_twitter_data.get("id"); 
// Check that we have not processed this tweet already 
if (!(tweetids.add(twid))){ 
    duplicates++; 
    continue; 
} 

SOLUTION

おかげで、私はそれを解決しました。問題は、ハッシュ表現に必要なメモリ量でした。まず、HashSet<String>は、この規模のために大量のものであるため、単純に莫大で無防備でした。次に、私はトライを試しましたが、ちょうど100万を超えるエントリーで墜落しました。配列を再割り当てするのは問題がありました。私はHashSet<Long>を使用して効果を上げ、ほぼ完成させましたが、スピードが落ち込み、最終的に処理の最後の頃にクラッシュしました（約1900万）。この解決策は、標準ライブラリを去り、Troveを使用して行われました。重複を何もチェックしないよりも、2200万レコードが数分早く終了しました。最終的な実装がシンプルであり、このように見えた：

import gnu.trove.set.hash.TLongHashSet; 
... 
    TLongHashSet tweetids; // class variable 
... 
    tweetids = new TLongHashSet(23000000,0.80F); // in constructor 
... 
    // inside for(each record) 
    String twid = (String) tweet_twitter_data.get("id"); 
    if (!(tweetids.add(Long.parseLong(twid)))) { 
     duplicates++; 
     continue; 
    } 

Answer 1

Javaコレクションフレームワークを超えて見たい場合があります。私はいくつかのメモリを大量に処理を行ってきた、あなたは大規模なハッシュマップとハッシュセットのバケットの数は オーバーヘッド（メモリ）の多くを引き起こすことが起こっているいくつかの問題

1. に直面するだろう。 何らかの種類のカスタムハッシュ関数とモジュロを使用することで、これに影響を与えることができます。 50000
2. 文字列は、Javaでは16ビット文字で表されます。ほとんどのスクリプトでutf-8でエンコードされたバイト配列を使用することで、それを半分にすることができます。
3. 一般に、HashMapsは非常に無駄なデータ構造であり、HashSetは基本的にそれらを囲む単なるラッパーです。

これを考えると、代わりにtroveやguavaを見てください。また、あなたのIDはロングのように見えます。これらは64ビットで、文字列表現よりかなり小さいです。

花粉フィルターを使用することをお勧めします（グアバにはまともな実装があります）。ブルームフィルタは、何かが含まれている場合、何かが確実にセットに含まれておらず、合理的な確実性（100％未満）であるかどうかを示します。ディスクベースのソリューション（データベース、mapdb、mecachedなど）と組み合わせると合理的にうまくいくはずです。入ってくる新しいIDをバッファリングし、バッチで書き込み、Bloomフィルタを使用してデータベースを調べる必要があるかどうかを確認し、ほとんどの場合高価なルックアップを避けることができます。

Answer 2

、シンプル未試行とおそらく愚かな提案：

Map<String, Set<String>> sets = new HashMap<String, Set<String>>(); 
String tweetId = "166471306949304320"; 
sets.put(tweetId.substr(0, 5), new HashSet<String>()); 
sets.get(tweetId.substr(0, 5)).add(tweetId); 
assert(sets.containsKey(tweetId.substr(0, 5)) && sets.get(tweetId.substr(0, 5)).contains(tweetId)); 

：つぶやきのIDの最初/最後のN文字でインデックス化セットの地図を作成します。

これにより、ハッシュスペースの最大サイズを簡単に適切な値以下に保つことができます。

Answer 3

文字列の存在を探している場合は、Trie（プレフィックスツリーとも呼ばれます）を試してみることをおすすめします。 Trieで使用されるスペースの合計は、HashSetより小さくなければなりません。また、文字列の検索にも時間がかかります。

主な欠点は、ハッシュのような格納された線形構造ではなく、ツリーをロードしているときにハードディスクから使用すると遅くなることです。だから、それがRAMの中に保持できることを確認してください。

私が与えたリンクは、このアプローチの賛否両論の良いリストです。

*を除いて、Jilles Van Gurpによって提案されたブルームフィルターは素晴らしい高速プレフィルターです。