java - 当 Set size 超过 500.000 时处理速度明显变慢

Question

我不习惯处理非常大的数据集，我有点被难住了。

我有以下代码:

private static Set<String> extractWords(BufferedReader br) throws IOException {
    String strLine;
    String tempWord;
    Set<String> words = new HashSet<String>();
    Utils utils = new Utils();
    int articleCounter = 0;
    while(((strLine = br.readLine()) != null)){
        if(utils.lineIsNotCommentOrLineChange(strLine)){
            articleCounter++;
            System.out.println("Working article : " + utils.getArticleName(strLine) + " *** Article #" + articleCounter + " of 3.769.926");
            strLine = utils.removeURLs(strLine);
            strLine = utils.convertUnicode(strLine);
            String[] temp = strLine.split("\\W+");
            for(int i = 0; i < temp.length; i++){
                tempWord = temp[i].trim().toLowerCase();
                if(utils.validateWord(tempWord)){
                    words.add(tempWord);
                    System.out.println("Added word " + tempWord + " to list");
                }
            }
        }
    }
    return words;
}

这基本上是从 BufferedReader 获取一个巨大的文本文件，其中每一行文本都是一篇文章中的文本。我想在这个文本文件中制作一个独特的单词列表，但那里有 3.769.926 篇文章，所以字数非常大。

根据我对 Sets 或特别是 HashSets 的了解，可以说这应该是这份工作的合适人选。一开始一切都运行得很顺利，但是在 500.000 篇文章之后它开始变慢了一点。当它达到 700.000 时，它开始变得足够慢，以至于它基本上停止两秒钟，然后再继续。这里某处有瓶颈，我看不出是什么..

有什么想法吗？

Answer 1

我相信您可能面临的问题是哈希表(集合或映射)必须由它可以容纳的固定数量的条目支持。所以你的第一个声明可能有一个能够容纳 16 个条目的表。撇开负载因子之类的因素不谈，一旦您尝试将 17 个条目放入表中，它就必须增长以容纳更多条目以防止冲突，因此 Java 会为您扩展它。

此扩展包括创建一个包含 2 * previousSize 条目的新表，然后复制旧条目。所以如果你不断地扩张，你最终可能会触及一个区域，比如524,288 它必须增长，但它会创建一个能够处理 1,048,576 个条目的新表，但它必须复制整个以前的表。

如果您不介意额外的查找时间，您可能会考虑使用 TreeSet 而不是 HashSet。您的查找现在将是对数时间，但是 Tree 没有预先分配的表并且可以轻松地动态增长。要么使用它，要么声明您的 HashSet 的大小，这样它就不会动态增长。