使用Java Set进行去重

Question

我有一组对象，我们称之为A、B、C、D...，其中一些相等。如果A和C相等，则我想用A替换所有对C的引用。这意味着(a)对象C可以被垃圾回收，释放内存，(b)我以后可以使用“==”来比较对象，而不是昂贵的equals()操作。(这些对象很大，equals()操作很慢。)

我的直觉是使用java.util.Set。当我遇到C时，我可以轻松地查看是否存在与C相等的条目。但是，如果有一个这样的条目，似乎没有简单的方法找出那个条目，并将我的引用替换为现有的条目。我错了吗？显然，遍历所有条目以找到匹配项是不可行的。

目前，我使用的是Map，其中值始终与键相同。然后调用map.get(C)找到A。这有效，但感觉非常费解。有更优雅的方法吗？

- Michael Kay

---

这篇帖子（https://dev59.com/SGw05IYBdhLWcg3wXQsg）尤其是它的第一个回答对这篇帖子非常相关，尽管我不认为它是一个重复的帖子。从我的理解来看，Map<T,T>在这里并不是一个罕见的做法。 - Kevin W.

看一下HashSet源代码，public boolean add(E e) { return map.put(e, PRESENT)==null; }。如果我没有弄错，这恰好是你想要的行为？ - Neil

@NeilEdelman 这不会返回对象，而是返回 true 或 false。如果没有映射，则返回 true；如果对象已经存在，则返回 false。 - mavriksc

你还可以使用SortedSet进行二进制查找。但我不认为Map是一个坏主意。如果你不需要顺序，我会选择Map。 - Juan

这里讨论了你可能在寻找的内容：https://www.baeldung.com/java-flyweight。 - Pawel Zieminski

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）的时间找出它是什么。）

值得一提的是，在底层，HashSet<T>类被实现为一个HashMap<T，T>。因此，直接使用HashSet不会节省时间或空间...

- Stephen C

---

你可能可以将其缩短为 input.stream().distinct().collect(Collectors.toList())。 - Pawel Zieminski

是的...但是那样做可能会让原帖作者不理解 :-) - Stephen C

谢谢。这似乎证实了我当前的做法已经没有更好的方法了。也许我应该在一个实现类中封装我的Map<T,T>结构，以隐藏其笨拙性，而不是将它暴露在各个地方。 - Michael Kay