java - 当集合大小超过 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 的大小，这样它就不会动态增长。