java - 使用 Java Set 进行重复数据删除

Question

我有一个对象集合，我们称它们为 A、B、C、D...，其中一些对象与其他对象相等。如果 A 和 C 相等，那么我想用对 A 的引用替换对 C 的每个引用。这意味着 (a) 可以对对象 C 进行垃圾回收，释放内存，以及 (b) 我稍后可以使用“==”比较对象代替昂贵的 equals() 操作。 (这些对象很大，equals() 操作很慢。)

我的直觉是使用 java.util.Set。当我遇到 C 时，我可以很容易地看到 Set 中是否有等于 C 的条目。但如果有，似乎没有简单的方法来找出该条目是什么，并替换我的引用到现有条目。我错了吗？遍历所有条目以找到匹配的条目显然是行不通的。

目前，我使用的不是 Set，而是 Map，其中值始终与键相同。调用 map.get(C) 然后找到 A。这行得通，但感觉非常复杂。有更优雅的方式吗？

Answer 1

这个问题不是简单的重复数据删除:它是规范化的一种形式。

标准方法是使用 Map而不是 Set .这是如何操作的草图:

public <T> List<T> canonicalizeList(List<T> input) {
    HashMap<T, T> map = new HashMap<>();
    List<T> output = new ArrayList<>();
    for (T element: input) {
        T canonical = map.get(element);
        if (canonical == null) {
            element = canonical;
            map.put(canonical, canonical);
        }
        output.add(canonical);
    }
    return output;
}

注意这是O(N) .如果您可以安全地假设 input 中的重复百分比可能很小，那么可以设置map的容量和 output大小为 input .

---

现在你似乎在说你已经在这样做了(最后一段)，你在问是否有更好的方法。据我所知，没有一个。 (HashSet API 让您可以测试一个集合是否包含等于 element 的值，但它不会让您找出它在 O(1) 中的内容。)

就其值(value)而言，在引擎盖下 HashSet<T>类实现为 HashMap<T, T> .因此，使用 HashSet 不会节省时间或空间。直接...