Java:优化哈希集以进行大规模重复检测

Question

我正在处理一个处理大量推文的项目；目标是在我处理它们时删除重复项。我有推文 ID，它们以 "166471306949304320" 格式的字符串形式出现

我一直在使用 HashSet<String>为此，它可以正常工作一段时间。但是当我处理到大约 1000 万个项目时，我彻底陷入困境并最终得到一个 GC 错误，大概是由于重新散列。我尝试用

定义更好的尺寸/负载

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

这让它走得更远，但仍然非常慢(处理大约 1000 万时需要 3 倍的时间)。我该如何优化呢？鉴于我大致知道到最后集合中应该有多少项目(在这种情况下，大约 20-22 百万)，我应该创建一个只重新散列两次或三次的 HashSet，还是这样的开销设置招致太多的时间惩罚？如果我不使用 String，或者如果我定义一个不同的 HashCode 函数(在这种情况下，对于 String 的特定实例，我不确定该怎么做)，事情会更好吗？这部分实现代码如下。

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; 
}

解决方案

感谢您的建议，我解决了它。问题是散列表示所需的内存量；首先，HashSet<String>简直是巨大而不必要的，因为String.hashCode()对于这个规模来说太贵了。接下来我尝试了一个 Trie，但它在刚刚超过 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 通常是非常浪费的数据结构，而 HashSets 基本上只是它们的一个薄包装。

鉴于此，请查看 trove 或 Guava 以寻找替代品。此外，您的 ID 看起来像多头。它们是 64 位的，比字符串表示形式小很多。

您可能要考虑的替代方法是使用布隆过滤器(guava 有一个不错的实现)。布隆过滤器会告诉您某物是否绝对不在集合中，并且可以合理确定(小于 100%)是否包含某物。结合一些基于磁盘的解决方案(例如数据库、mapdb、mecached 等)应该可以很好地工作。您可以缓冲传入的新 ID，分批写入它们，并使用布隆过滤器检查您是否需要在数据库中查找，从而在大多数情况下避免昂贵的查找。