java - Java 中删除重复项的最快、最有效的方法

Question

我想删除数据中的重复值。我知道这是 stackoverflow 中经常出现的问题，但我的问题有点不同，因为现在我正在处理非常大的数据。因此我必须在代码中首先考虑执行时间。

如下面的代码片段所示，我编写了一个简单的代码来删除重复的值。

// Suppose that the dataset is very huge so that
// multi-node resources should be necessary.    
String[] data = new String[10_000_000];

HashMap<String, String> uniqueItems = new HashMap<>();

for (int i = 0; i < data.length; i++) {
    if (uniqueItems.containsKey(data[i])) {
        uniqueItems.remove(data[i]);
        uniqueItems.put(data[i], "inserted");
    } else {
        uniqueItems.put(data[i], "inserted");
    }
}

但是，我不喜欢它，因为我认为其他更好的数据结构或不同的算法可以比我的代码更有效地删除重复项。

所以我想寻找更好的方法，在数据较大时快速去除重复值。
如果您能让我知道删除重复值的最快方法，我将不胜感激。

而且，我想知道重复值的数量是否会影响性能。我的意思是，如果重复值是原始数据的 50%，那么最佳算法和数据结构的选择将会改变？如果是这样，我想找到一种在一般情况下能够获得良好性能的方法。

Answer 1

转换您的uniqueItems到 HashSet<String> 和你的for循环来简单地:

uniqueItems.add(data[i]);

如果add返回true然后你插入了一个唯一的字符串； false如果重复。

在最好的情况下，两种算法都应该在 O(n) 时间内运行，但使用 HashMap当您不关心值(对于给定键)时，这是愚蠢的并且浪费资源。一个HashSet更适合这种情况。

您也可以尝试 TreeSet<String> 查看最适合您的特定数据集的方法。考虑到 JDK 8 新的 HashSet，情况可能会更糟。实现:过度拥挤的存储桶会自动存储为迷你树集，即使在哈希函数表现不佳时也能提供有竞争力的性能。 (此优化仅适用于 Comparable 类型，例如 String 。)

<小时/>

暴力搜索数组。在一个简单的基于数组的算法中，在插入每个元素之前搜索整个数组，您将获得非常糟糕的 O(n²) 性能。

因此，您可能会想先对数据进行排序，将重复的元素靠近放置。这将为您带来更快的 O(n log n) 性能，但仍落后于 HashMap/HashSet一般情况下的版本。

<小时/>

理论上线性是最好的。如果不至少访问每个元素一次，就无法检测所有重复项。因此，我们当前的 O(n) 时间复杂度确实是您可以做到的最好的时间复杂度。

当然，您始终可以尝试减少 Big O notation 中的一些隐藏常量 ，但你不会得到渐近更好的算法。