在 Java 中删除重复项的最快最有效的方法

Question

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

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

// 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]);

If add returns true 那么你插入了一个唯一的字符串； false 如果重复。

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

您也可以尝试 TreeSet<String> 以查看最适合您的特定数据集的方法。可能会更糟，给定 JDK 8 个新的 HashSet 实现：过度拥挤的桶自动存储为迷你树集，即使在 散列函数 时也能提供有竞争力的性能行为不端。（此优化仅适用于 Comparable 类型，例如 String。）

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

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

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

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

Answer 2

在您的示例中，data[i] 值用作 HashMap uniqueItems.

HaspMap 将始终具有唯一键。现有密钥将被 put() 操作覆盖。你不需要 conatinsKey() 如果你想添加一个新元素。

为什么要移除和插入现有密钥？

在 Java 中删除重复项的最快最有效的方法

Most fastest and efficient way to remove duplicates in Java

java

optimization

hashmap

hashset

time-complexity