Java:优化hashset以进行大规模重复检测

Question

我正在处理一个项目,我正在处理很多推文; 我的目标是在处理它们时删除重复项.我有推文ID,它以格式的字符串形式出现"166471306949304320"

我一直在使用HashSet<String>这个,它可以正常工作一段时间.但到了大约1000万件物品的时候,我却陷入了巨大的困境,并最终得到了一个GC错误,大概是从重新开始.我试着定义一个更好的尺寸/负载

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

这让它变得更远,但仍然非常缓慢(大约1000万,它需要花费3倍的时间来处理).我该如何优化呢？鉴于我已经大致知道在结尾集合中应该有多少项目(在这种情况下,大约20-2200万)我应该创建一个只重复两次或三次的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基本上只是一个很薄的包装器.

考虑到这一点,看看特洛伊或番石榴的替代品.此外,你的ID看起来像多头.那些是64位,比字符串表示小很多.

您可能想要考虑的另一种方法是使用bloom过滤器(番石榴有一个不错的实现).如果包含某些内容,布隆过滤器会告诉您某些内容是否肯定不在集合中并且具有合理的确定性(小于100%).结合一些基于磁盘的解决方案(例如数据库,mapdb,mecached,......)应该可以很好地工作.您可以缓冲传入的新ID,批量编写它们,并使用bloom过滤器检查是否需要查看数据库,从而避免在大多数情况下进行昂贵的查找.