Java：优化hashset以进行大规模重复检测
我正在处理一个项目，我正在处理很多推文; 我的目标是在处理它们时删除重复项。 我有推文ID，其格式为"166471306949304320"
我一直在使用HashSet ，它可以正常工作一段时间。 但到了大约1000万件物品的时候，我已经陷入困境并最终得到GC错误，大概是从重新开始。 我试着定义一个更好的尺寸/负载
tweetids = new HashSet(220000,0.80F);
这让它变得更远，但仍然非常缓慢（大约1000万，它需要花费3倍的时间来处理）。 我该如何优化呢？ 鉴于我已经大致知道在结尾集合中应该有多少项目（在这种情况下，大约20-2200万）我应该创建一个只重复两次或三次的HashSet，或者这样的开销是多少？设置了太多的时间罚款？ 如果我没有使用String，或者我定义了一个不同的HashCode函数（在这种情况下是String的特定实例，我不知道该怎么做），事情会更好吗？ 这部分实现代码如下。
tweetids = new HashSet(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.hashCode()对于这个比例来说过高。 接下来，我尝试了一个Trie，但它在100多万个条目中崩溃了; 重新分配arrays是有问题的。 我使用HashSet来更好地实现并且几乎成功，但是速度已经衰减并且它最终在处理的最后一段（大约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; }
您可能希望超越Java集合框架。 我做了一些内存密集型处理，你将面临几个问题
- 大型哈希映射和散列集的桶数将导致大量开销（内存）。 您可以通过使用某种自定义散列函数和例如50000的模数来影响这一点
- 字符串在Java中使用16位字符表示。 您可以通过对大多数脚本使用utf-8编码的字节数组来减半。
- HashMaps通常是相当浪费的数据结构，HashSets基本上只是一个很薄的包装器。
考虑到这一点，看看特洛伊或番石榴的替代品。 此外，你的ID看起来像多头。 那些是64位，比字符串表示小很多。
您可能想要考虑的替代方法是使用bloomfilter（番石榴有一个不错的实现）。 如果包含某些内容，布隆filter会告诉您某些内容是否肯定不在集合中并且具有合理的确定性（小于100％）。 结合一些基于磁盘的解决方案（例如数据库，mapdb，mecached，…）应该可以很好地工作。 您可以缓冲传入的新ID，批量编写它们，并使用bloomfilter检查是否需要查看数据库，从而避免在大多数情况下进行昂贵的查找。
如果您只是在寻找字符串的存在，那么我建议您尝试使用Trie （也称为前缀树）。 Trie使用的总空间应小于HashSet，并且字符串查找更快。
主要的缺点是，当它从硬盘中使用时它可能会更慢，因为它正在加载树，而不是像Hash那样存储的线性结构。 因此，请确保它可以保存在RAM内部。
我给出的链接是这种方法的优点/缺点。
*另外，Jilles Van Gurp建议的布隆filter是很好的快速预滤器。
简单，未经validation且可能是愚蠢的建议：创建集合映射，由推文ID的前N个字符或后N个字符索引：
Map> sets = new HashMap>(); String tweetId = "166471306949304320"; sets.put(tweetId.substr(0, 5), new HashSet ()); sets.get(tweetId.substr(0, 5)).add(tweetId); assert(sets.containsKey(tweetId.substr(0, 5)) && sets.get(tweetId.substr(0, 5)).contains(tweetId));
这很容易让您将散列空间的最大大小保持在合理的值以下。