为什么java.util.Set不包含取值器？它是否有替代方案？

Question

作为集合条目，只能通过其子集属性（hashCode() + equals()）来区分。有时需要操作集合中包含的原始对象，但这在java.util.Set中是不可能的。我想到的唯一替代方案是：Map<T, T> - 这不是一个非常简洁的解决方案。

在集合框架中是否有其他替代方案？要求是：获取时间为O(1)，且基于hashCode() + equals()结果没有重复项。

- Marcin

---

不，这就是为什么你需要一个HashMap。这是标准API中另一个基于哈希的集合。这是最省力的解决方案，虽然不是很美观，但你似乎对美观没有太高的要求 :| - Kayaman

@Marcin，也许我没有理解你的问题。但是使用HashSet，您可以在基本操作中实现常数时间检索，并且由于它是由集合支持的，它不会允许重复项（基于hashCode()和equals()）。这难道不能解决您的问题吗？ - Dhrubajyoti Gogoi

@DhrubajyotiGogoi 尝试从HashSet中提取原始对象。这就是我想要做的事情。 - Marcin

@Marcin 你的意思是一种池，这样当你需要一个新的对象实例时，你首先检查集合中是否已经存在一个类似的对象（equals + hashcode），如果是这种情况，就使用那个对象？ - assylias

一个 Map<T, T> 是正确的解决方案。 - Louis Wasserman

Answer 1

如果不介意多一次 O(1) 操作，可以使用 set.remove(Object) 和 set.add(Object) 方法配对模拟 get(Object) 缺席方法。否则，可以像你提到的那样使用 Map<T,T> 或者简单的包装类和基础映射。

编辑：为什么 Set 不包含 get(Object) 的原因是你不需要返回已知对象。你只需要检查你的对象是否包含在集合中。

- matoni

Answer 2

基于HashMap的HashSet代码非常简单：如果您查看JDK中实现方式，除了构造函数和序列化代码之外，实际代码行数非常少。

一种实现方法是使用额外的get()方法来实现自己版本的HashSet。

public E get(Object o) {
   return map.get(o);
}

- Guillaume

Answer 3

是的，这有点令人烦恼，无法共享相等的对象。 Set API 的问题在于缺少特定的 addAndGet：

AddOnceSet<String> set = new AddOnceSet<>();
String s = in.readLine();
s = set.addOnce(s); // The new s is equal, and identical to the first added one.

s = set.getOnce(s);

很遗憾，这不符合集合API的要求。我希望它能在Java 8及以上版本中实现。 在Java 8中，您可以添加一个带有addOnce和getOnce默认值的接口。

像您所说的那样实现：

private Map<T, T> sharedThings = new HashMap<>().

public T shareThing(T s) {
    String t = sharedThings.get(s);
    if (t == null) {
        t = s;
        sharedStrings.put(t, t);
    }
    return t;
}

...

public void setT(T t) {
    this.t = sharedThing(t);
}

- Joop Eggen

Answer 4

虽然这个函数不在 java.util.Collections 自己的库里面，但是你可以通过使用 Google Guava 来从给定的 Iterator 中检索任何元素，具体方法是使用 Iterables.get。

通常我不会倡导使用外部库，但是考虑到 Guava 的效果非常强大和有用，我认为没有任何问题。

或者你也可以自己实现一个迭代器来遍历集合。

---

此外，我在这里找到了一个非常有趣的线程，解释了这种行为。

- epoch

---

但它将不再是O(1)。 - Kayaman

Answer 5

一个 Set 不能包含两个对象 o1 和 o2，这样的对象满足 o1.equals(o2)（这个条件下不使用 hashCode）。

一个 HashSet 使用哈希映射来高效地存储其对象，所以最终你需要的是一个 HashMap，用于基于 hashCode()+equals() 的操作。

- giorashc

---

这不是他要求的：他想以常数时间从一个集合中检索与另一个对象相等的对象。 - arshajii

@arshajii 我明白，但是Set接口不提供获取对象的get方法，这可能是因为Set的意图并非如此。他需要通过使用它们的哈希码和equals有效地区分对象，这正是哈希映射的用途。 - giorashc

那么你的意思是他应该使用 Map<T, T>，就像他已经尝试过的那样？ - arshajii

这实际上取决于他所说的“原始对象”是什么意思。它是指在内存方面创建的相同实例，还是具有完全相同属性的对象。对于后者，他可以安全地使用Hashmap。如果是这种情况，我真的很想知道需要完全相同的实例是什么。 - giorashc

Answer 6

我写了这样一个类，如果你想重用它的话。Jayes 包含一个 org.eclipse.recommenders.jayes.util.sharing.CanonicalSet 类，它允许基于你可以在 hashCode() 和 equals() 实现中编码的任何等价关系进行检索。我使用它来构建数组等价类。你可以查看那些 CanonicalSet 的实现，它们在同一个包中。

噢，但是，它也只是基于一个 Map<Entry<T>,T>，所以没有什么魔法。

- kutschkem

Answer 7

你可以从 commons-collections 中使用 SetUniqueList。

它可以装饰一个 java.util.List，确保没有重复项存在，就像一个 java.util.Set 一样。

- M. Abbas