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

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

我一直在使用HashSet<String>为此，暂时效果很好。但当我达到大约 1000 万个项目时，我彻底陷入困境，最终出现 GC 错误，大概是由于重新哈希造成的。我尝试定义更好的尺寸/负载

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

这让它走得更远，但速度仍然极其缓慢（大约 1000 万，处理时间是原来的 3 倍）。我该如何优化这个？考虑到我对最后应该有多少项有一个大致的了解（在本例中，大约 20-2200 万），我是否应该创建一个仅重新散列两次或三次的 HashSet，或者这样的开销设置会招致太多时间处罚吗？如果我不使用字符串，或者定义不同的 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>简直是巨大且不必要的，因为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; 
    }

您可能想要超越 Java 集合框架。我已经完成了一些内存密集型处理，您将面临几个问题

1. 大型哈希图和哈希集的桶数将是 造成大量开销（内存）。您可以通过使用来影响这一点 某种自定义哈希函数和模数，例如50000
2. Java 中的字符串使用 16 位字符表示。对于大多数脚本，您可以通过使用 utf-8 编码的字节数组将其减半。
3. HashMap 通常是相当浪费的数据结构，而 HashSet 基本上只是这些数据结构的薄包装。

鉴于此，看看 trove 或 guava 的替代品。另外，你的 id 看起来像 long。这些是 64 位的，比字符串表示形式小很多。

您可能需要考虑的另一种选择是使用布隆过滤器（番石榴有一个不错的实现）。布隆过滤器会告诉您某些东西是否绝对不在集合中，并且以合理的确定性（小于 100%）告诉您某些东西是否包含在集合中。与一些基于磁盘的解决方案（例如数据库、mapdb、mecached...）相结合应该可以很好地工作。您可以缓冲传入的新 ID，批量写入它们，并使用布隆过滤器检查是否需要在数据库中查找，从而在大多数情况下避免昂贵的查找。