提高处理1亿个元素的ArrayList时的速度和内存消耗

首先，不要执行Files.readAllLines(Paths.get("filename"))，然后将所有内容传递给Set，这会保存不必要的大量数据。在任何时候都尽量少留行。

逐行读取文件并处理。这将立即大大减少您的内存使用。

Set<String> oldData = new HashSet<>();
try (BufferedReader reader = Files.newBufferedReader(Paths.get("oldData"))) {
    for (String line = reader.readLine(); line != null; line = reader.readLine()) {
        // process your line, maybe add to the Set for the old data?
        oldData.add(line);
    }
}
Set<String> newData = new HashSet<>();
try (BufferedReader reader = Files.newBufferedReader(Paths.get("newData"))) {
    for (String line = reader.readLine(); line != null; line = reader.readLine()) {
        // Is it enough just to remove from old data so that you'll end up with only the difference between old and new?
        boolean oldRemoved = oldData.remove(line);
        if (!oldRemoved) {
            newData.add(line);
        }
    }
}

最终将得到两个集，分别只包含旧数据集或新数据集中的数据。

其次，如果可能的话，尽量调整容器的大小。当它们达到其容量时，它们的大小(通常)会翻倍，这可能会在处理大型集合时产生大量开销。

另外，如果您的数据是数字，您可以使用long并保持它，而不是试图保持String的实例?有很多集合库可以让你做到这一点，例如Koloboke, HPPC, HPPC- rt, GS Collections, fastutil, Trove。即使它们的Objects集合也可以很好地为您服务，因为标准的HashSet有很多不必要的对象分配。

谢谢你的建议!

最终解为:使用fastutil库(LongOpenHashSet)将行转换为Long +

内存消耗变成3.6Gb，处理时间只有40秒!

有趣的观察。虽然使用默认设置启动java会没完没了地将1亿个字符串加载到JDK的本机HashSet(我在1小时后中断)，但使用-Xmx16G将该过程加快到1分钟。但是内存消耗是荒谬的(大约20Gb)，处理速度相当不错——2分钟。

如果不受RAM的限制，本地JDK HashSet在速度方面并不差。

注。也许任务没有清楚地解释，但我不认为有任何机会不完全加载至少一个文件。因此，我怀疑内存消耗能否进一步降低很多。

请将字符串分成两部分，重复的部分(str1或str2)大多数使用intern()，以便在堆中再次保存相同字符串的重复。这里我在两个部分都使用了intern()，只是为了显示样本，但除非它们重复得最多，否则不要使用它。

Set<MyObj> lineData = new HashSet<MyObj>();
String line = null;
BufferedReader bufferedReader = new BufferedReader(new FileReader(file.getAbsoluteFile()));
while((line = bufferedReader.readLine()) != null){
    String[] data = line.split(",");
    MyObj myObj = new MyObj();
    myObj.setStr1(data[0].intern());
    myObj.setStr1(data[1].intern());
    lineData.add(myObj);
}
public class MyObj {
    private String str1;
    private String str2;
    public String getStr1() {
        return str1;
    }
    public void setStr1(String str1) {
        this.str1 = str1;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((str1 == null) ? 0 : str1.hashCode());
        result = prime * result + ((str2 == null) ? 0 : str2.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Test1 other = (Test1) obj;
        if (str1 == null) {
            if (other.str1 != null)
                return false;
        } else if (!str1.equals(other.str1))
            return false;
        if (str2 == null) {
            if (other.str2 != null)
                return false;
        } else if (!str2.equals(other.str2))
            return false;
        return true;
    }
    public String getStr2() {
        return str2;
    }
    public void setStr2(String str2) {
        this.str2 = str2;
    }
}

我做了一个非常简单的拼写检查器，只是检查字典中是否有一个单词对于整个文档来说太慢了。我创建了一个地图结构，效果很好。

Map<String, List<String>> dictionary;

对于键，我使用单词的前两个字母。这个列表包含了所有以关键字开头的单词。为了加快速度，您可以对列表进行排序，然后使用二分搜索来检查是否存在。我不确定键的最佳长度，如果键太长，可以嵌套映射。最后它变成了一棵树。实际上，三阶结构可能是最好的。

对于这种情况，可以使用trie数据结构:http://www.toptal.com/java/the-trie-a-neglected-data-structure算法如下:

1. 逐行读取旧文件，并将每行存储在tree中。
2. 逐行读取新文件，并测试每一行是否正确

进一步的内存优化可以利用只有10位数字的优势，因此4位足以存储一个数字(而不是Java中的每个字符2字节)。您可能需要从以下链接之一调整trie数据结构:

1. Trie数据结构- Java
2. http://algs4.cs.princeton.edu/52trie/TrieST.java.html

包含11个字符(实际上最多12个)的String对象将具有64字节的大小(在64位Java压缩ops上)。唯一能够容纳这么多元素且具有合理大小的结构体是数组:

100,000,000 * (64b per String object + 4b per reference) = 6,800,000,000b ~ 6.3Gb

所以你可以立即忘记map, set等，因为它们引入了太多的内存开销。但你只需要一个数组。我的方法是:

1. 加载"旧"数据到一个数组，排序它(这应该足够快)
2. 创建一个与加载数组大小相同的原始布尔值的备份数组(您也可以在这里使用BitSet)
3. 从新的数据文件逐行读取。使用二进制搜索检查密码数据是否存在于旧数据数组中。如果条目存在，则将其在布尔数组/bitset中的索引标记为true(您从二进制搜索中获得索引)。如果项目不存在，只需将其保存在某个地方(数组列表可以服务)。
4. 当所有行被处理时，从旧数组中删除所有在布尔数组/bitset中具有false的项(当然通过索引检查)。最后，将保存在某处的所有新数据添加到数组中。
5. 可以选择对数组再次排序并保存到磁盘，所以下次加载它时，你可以跳过初始排序。

这应该足够快了。初始排序是O(n log(n))，而二进制搜索是O(log(n))，因此你应该结束(不包括最终删除+添加，最多可以是2n):

n log(n) (sort) + n log(n) (binary check for n elements) = 2 n log(n)

如果您能够更多地解释您所拥有的String的结构(如果存在某种模式或不存在模式)，则可能会有其他优化。

当readAllLines()发生时，大量调整ArrayList大小的主要问题。更好的选择是LinkedList插入数据

try (BufferedReader reader = Files.newBufferedReader(path, StandardCharsets.UTF_8)) {
        List<String> result = new LinkedList<>();
        for (;;) {
            String line = reader.readLine();
            if (line == null)
                break;
            result.add(line);
        }
        return result;
    }