当集合大小超过500.000时，java的处理速度会显著降低

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篇文章，因此单词数量非常庞大

从我对集合的理解来看，或者具体地说，hashset，可以说，这应该是适合这项工作的人。一开始一切都很顺利，但在写了50万篇文章之后，速度开始放缓。当它达到700.000时，它开始变得足够慢，基本上会停止两秒钟，然后再继续。这里的某个地方有个瓶颈，我看不出是什么

有什么想法吗

Answer 1

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

这个扩展包括创建一个包含2 * previousSize个条目的新表，然后复制旧条目。所以，如果你不断扩张，你可能最终会碰到一个区域，比如 524288，它将不得不增长，但它将创建一个能够处理1048576个条目的新表，但它必须复制整个上一个表

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