使用 Java 集进行重复数据删除

Question

我有一组对象，让我们称它们为 A、B、C、D...，其中一些与其他对象相同。如果 A 和 C 相等，那么我想用对 A 的引用替换对 C 的每个引用。这意味着 (a) 对象 C 可以被垃圾收集，释放内存，以及 (b) 我以后可以使用“==”比较对象而不是昂贵的equals()操作。（这些对象很大，equals()操作很慢。）我的直觉是使用java.util.Set. 当我遇到 CI 时可以很容易地看到是否有Set等于 C的条目。但如果有，似乎没有简单的方法可以找出该条目是什么，并替换我对现有条目的引用。我错了吗？遍历所有条目以找到匹配的条目显然是不可能的。目前，Set我使用的不是 a ，而是 a ，Map其中的值始终与键相同。调用map.get(C)然后找到 A。这有效，但感觉非常复杂。有没有更优雅的方式来做到这一点？

Answer 1

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

标准方法是使用 aMap而不是 a 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。

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

就其价值而言，HashSet<T>该类在底层实现为HashMap<T, T>. 因此，您不会通过HashSet直接使用...