从Set中获取元素

Question

为什么 Set 没有提供一种获取与另一个元素相等的元素的操作？

Set<Foo> set = ...;
...
Foo foo = new Foo(1, 2, 3);
Foo bar = set.get(foo);   // get the Foo element from the Set that equals foo

我可以询问Set是否包含与bar相等的元素，那么为什么我不能获取该元素呢？ :(

为了澄清， equals方法已被重写，但它只检查一个字段而不是所有字段。 因此，被认为相等的两个Foo对象实际上可以具有不同的值，这就是为什么我不能只使用foo的原因。

- foobar

---

这篇帖子已经被广泛讨论，也提出了很好的答案。但是，如果你只是想要一个有序集合，只需使用 SortedSet 及其实现，它们是基于映射的（例如，TreeSet 允许访问 first()）。 - Eliran Malka

我也很想用那种方法，就像你上面描述的那样。Objective-C（NSSet）有这样一个方法，称为member，它返回集合中与member方法参数“相等”的对象（可能是不同的对象，也可能具有不同的属性，但相等性检查不会考虑这些差异）。 - Mecki

Answer 1

为了回答精确的问题“为什么Set不提供一个获取与另一个元素相等的元素的操作？”，答案是：因为集合框架的设计者没有很好地展望未来。他们没有预料到您非常合法的用例，天真地试图“模拟数学集合抽象”（来自javadoc），并简单地忘记添加有用的get()方法。

现在回答隐含的问题“那么你怎么获得这个元素呢？”：我认为最好的解决方案是使用Map而不是Set，将元素映射到它们自己。通过这种方式，您可以有效地从“集合”中检索元素，因为Map的get()方法将使用高效的哈希表或树算法查找元素。如果您愿意，还可以编写自己的Set实现，提供附加的get()方法，封装Map。

以下答案我认为是错误的：

“你不需要获取元素，因为你已经有一个相等的对象”：断言是错误的，正如您在问题中所示。两个相等的对象仍然可以具有与对象等价无关的不同状态。目标是访问包含在Set中的元素的状态，而不是作为“查询”的对象的状态。

“你别无选择，只能使用迭代器”：这是对大型集合完全无效的线性搜索（具有讽刺意味的是，内部Set组织为可以高效查询的哈希映射或树）。不要这么做！我在现实生活中看到了严重的性能问题，使用这种方法。我认为缺少get()方法的可怕之处不是它有点麻烦，而是大多数程序员将使用线性搜索方法而不考虑其影响。

- jschreiner

---

重写equals方法，使得不相等的对象变成“相等”是问题所在。要求一个方法来获取与该对象相同的对象，然后期望返回一个非相同的对象似乎很荒谬，并且容易引起维护问题。正如其他人建议的那样，使用映射可以解决所有这些问题，并且使你所做的事情自我说明。很容易理解两个不相等的对象可能在映射中具有相同的键，并且具有相同的键将显示它们之间的关系。 - David Ogren

@David Ogren，你的话语有力。"Meh?" 意思是什么？在你的评论中，你使用“identical”和“equal”这两个词好像它们的意思相同。但事实上它们并不相同。特别是在Java中，“==”运算符表示引用的身份(identity)，而equals()方法则表示值的相等性(equality)。如果它们的意思相同，那就没有必要再有equals()方法了。当然，在其他编程语言中，情况可能不同。例如，在Groovy中，identity是is()方法，而equality则是“==”。很有意思，是不是？ - jschreiner

你对我使用单词“identical”而不是“equivalent”的批评非常有道理。但是，如果定义对象的相等关系，使得Foo和Bar在“相等”方面是“不够相等”的，这将会在功能性和可读性/可维护性方面带来各种问题。Set中遇到的这个问题只是潜在问题的冰山一角。例如，相等的对象必须具有相等的哈希码。因此，他可能会遇到哈希碰撞的问题。如果调用.get(foo)时返回的不是foo本身，这是否令人困惑？ - David Ogren

值得注意的是，例如 HashSet 是作为 HashMap 的包装器实现的（将键映射到虚拟值）。因此，明确使用 HashMap 而不是 HashSet 不会导致内存使用方面的额外开销。 - Alexey B.

@user686249 我感觉这已经沦为了一场纯粹的学术辩论。我承认在反对重写equals方法方面我可能有些过头，尤其是像你这样使用的情况下。但是，我仍然反对将此方法称为“get()”。在你的例子中，customerSet.get(thisCustomer)会让我非常困惑。（相比之下，像许多回答建议的Map一样）使用canonicalCustomerMap.get(this customer)就可以了。我也可以接受一个更清晰命名的方法（例如Objective-C的NSSet上的成员方法）。 - David Ogren

Answer 2

如果元素相等，则获取该元素没有任何意义。在这种情况下，Map 更适合。

---

如果你仍想找到该元素，除了使用迭代器之外别无选择:

public static void main(String[] args) {

    Set<Foo> set = new HashSet<Foo>();
    set.add(new Foo("Hello"));

    for (Iterator<Foo> it = set.iterator(); it.hasNext(); ) {
        Foo f = it.next();
        if (f.equals(new Foo("Hello")))
            System.out.println("foo found");
    }
}

static class Foo {
    String string;
    Foo(String string) {
        this.string = string;
    }
    @Override
    public int hashCode() { 
        return string.hashCode(); 
    }
    @Override
    public boolean equals(Object obj) {
        return string.equals(((Foo) obj).string);
    }
}

- dacwe

---

获取该元素的确有其必要。例如，当.equals()方法没有使用所有字段时，就需要更新该元素已添加到Set中后的一些值。更少效率的解决方案是删除该元素并重新添加已更新的值。 - KyleM

我认为使用Map（在这种情况下是Map<Foo, Foo>）更合适。 - dacwe

@dacwe，我来到这里是因为我开始寻找一种避免这种情况的方法！一个同时充当键和对应值的对象正是集合应该拥有的特性。在我的情况下，我希望通过键（字符串）从集合中获取一些复杂的对象。这个字符串被封装（并且唯一地）映射到对象上。实际上，整个对象都围绕着这个键“旋转”。此外，调用者知道这个字符串，但不知道对象本身；这正是它想要通过键检索它的原因。我现在当然在使用Map，但它的行为仍然很奇怪。 - pauluss86

我了解使用情况，但我想强调不要触碰hashCode/equals属性的重要性。从Set Javadoc中可以看到："注意：如果可变对象用作集合元素，则必须非常小心。如果在对象作为集合元素时以影响equals比较的方式更改对象的值，则集合的行为未指定。" -- 我建议这些对象是不可变的，或者至少具有不可变的键属性。 - stivlo

我同意您可以使用 Map<Foo, Foo> 作为替代方法，缺点是 map 必须始终存储至少一个键和一个值（为了性能，还应该存储哈希值），而 set 可以只存储值（也许为了性能可以存储哈希值）。因此，一个良好的 set 实现可以与 Map<Foo, Foo> 一样快，但使用的内存少多达50%。在 Java 中，这并不重要，因为 HashSet 在内部基于 HashMap 实现。 - Mecki

Answer 3

如果你已经有了一个相等的对象，为什么还需要从集合中获取一个？如果它只是通过键值“相等”，那么使用 Map 会更好。

无论如何，以下内容可以实现：

Foo getEqual(Foo sample, Set<Foo> all) {
  for (Foo one : all) {
    if (one.equals(sample)) {
      return one;
    }
  } 
  return null;
}

使用Java 8，这可以变成一行代码：

return all.stream().filter(sample::equals).findAny().orElse(null);

- Arne Burmeister

---

我更喜欢这个答案，我只是会避免使用两个返回语句，因为这违反了面向对象编程的原则，并且会使圈复杂度值变高。 - Leo

@Leo，谢谢你的回复。单一出口范式并不与面向对象编程相矛盾，并且在比Fortran或COBOL更现代的语言中大多无效。参见http://softwareengineering.stackexchange.com/questions/118703/where-did-the-notion-of-one-return-only-come-from#。 - Arne Burmeister

使用 Map 而不是 Set 似乎是更好的选择：遍历 Set 的元素比从 Map 中获取单个值更费力。（O(N) vs O(1)） - Jamie Flournoy

@JamieFlournoy 如果你需要多次检查相同的集合以查找不同的元素，那么使用哈希表会更好。但如果只需使用一次，则需要更多的努力来先构建哈希表。 - Arne Burmeister

Answer 4

很不幸，Java中的默认设置并没有设计提供“获取”操作，正如jschreiner所准确解释的。

使用迭代器查找感兴趣的元素（由dacwe建议）或删除元素并重新添加其更新后的值（由KyleM建议）的解决方案可能有效，但可能非常低效。

重写equals的实现使得不相等的对象“相等”，正如David Ogren正确指出的那样，可能会轻易引起维护问题。

而使用Map作为明确的替代方案（正如许多人建议的那样），在我看来，会使代码变得不够优雅。

如果目标是获取包含在集合中的元素的原始实例（希望我正确理解了您的用例），这里有另一种可能的解决方案。

---

在使用Java开发客户端服务器视频游戏时，我个人遇到了与您相同的需求。在我的情况下，每个客户端都存储了服务器上组件的副本，问题是当客户端需要修改服务器上的对象时。

通过互联网传递对象意味着客户端无论如何都有不同的该对象实例。为了将此“复制”的实例与原始实例匹配，我决定使用Java UUIDs。

因此，我创建了一个抽象类UniqueItem，自动为其子类的每个实例提供随机唯一ID。

此UUID在客户端和服务器实例之间共享，因此可以通过简单地使用Map进行匹配。

但是，在类似用例中直接使用Map仍然不够优雅。有人可能会认为使用Map可能更加复杂，难以维护和处理。

出于这些原因，我实现了一个名为MagicSet的库，使开发人员可以“透明”地使用Map。

https://github.com/ricpacca/magicset

---

像原始的Java HashSet一样，MagicHashSet（是库中提供的MagicSet实现之一）使用支持HashMap，但不同于将元素作为键和虚拟值作为值，而是使用元素的UUID作为键和元素本身作为值。与普通HashSet相比，这不会导致内存使用方面的开销。

此外，可以像Set一样完全使用MagicSet，但还提供了一些额外的方法，如getFromId()，popFromId()，removeFromId()等，提供了其他功能。

唯一要求使用它的是，您想要存储在MagicSet中的任何元素都需要扩展抽象类UniqueItem。

---

这里有一个代码示例，假设从一个MagicSet中检索具有相同UUID（甚至只有UUID）的另一个城市实例，以获取该城市的原始实例。

class City extends UniqueItem {

    // Somewhere in this class

    public void doSomething() {
        // Whatever
    }
}

public class GameMap {
    private MagicSet<City> cities;

    public GameMap(Collection<City> cities) {
        cities = new MagicHashSet<>(cities);
    }

    /*
     * cityId is the UUID of the city you want to retrieve.
     * If you have a copied instance of that city, you can simply 
     * call copiedCity.getId() and pass the return value to this method.
     */
    public void doSomethingInCity(UUID cityId) {
        City city = cities.getFromId(cityId);
        city.doSomething();
    }

    // Other methods can be called on a MagicSet too
}

- ricpacca

Answer 5

使用Java 8，你可以做到：

Foo foo = set.stream().filter(item->item.equals(theItemYouAreLookingFor)).findFirst().get();

但是要小心，.get()会抛出NoSuchElementException异常，或者你可以操作一个Optional项。

- cloudy_weather

---

item->item.equals(theItemYouAreLookingFor) can be shortened to theItemYouAreLookingFor::equals - Henno Vermeulen

需要API级别24以上的“stream”！！ - C.F.G

Answer 6

如果您的集合确实是一个NavigableSet<Foo>（例如TreeSet），并且Foo实现Comparable<Foo>，则可以使用以下代码：

Foo bar = set.floor(foo); // or .ceiling
if (foo.equals(bar)) {
    // use bar…
}

（感谢 @eliran-malka 的提示。）

- Jesse Glick

---

如果我不介意任何人在查看我的代码后觉得我完全疯了，那么这将是一个很好的解决方案。 - Adam

很遗憾，使用TreeSets（底层为TreeMaps）时，所有基本操作的时间复杂度都为log(N) :c - nllsdfx

Answer 7

为什么：

Set在提供比较手段方面发挥了有用的作用。它被设计成不存储重复元素。

由于这种意图/设计，如果获取对存储对象的引用，然后改变它，可能会破坏Set的设计意图，并导致意外行为。

来自JavaDocs

如果可变对象用作集合元素，则必须非常小心。如果对象的值在其作为集合元素时以影响equals比较的方式更改，则不会指定集合的行为。

如何：

现在引入了Streams，可以执行以下操作

mySet.stream()
.filter(object -> object.property.equals(myProperty))
.findFirst().get();

- Jason M

---

因为Stream API而点赞。然而，不建议使用get()，而应该使用orElse()或ifPresent()。 - alistairv

Answer 8

将set转换为list，然后使用列表的get方法。

Set<Foo> set = ...;
List<Foo> list = new ArrayList<Foo>(set);
Foo obj = list.get(0);

- To Kra

---

我不理解这个。它将检索集合中的一个“任意”对象，而不是“特定”的对象。 - aioobe

为什么这个回答会有这么多赞？在这个回答中，您将集合转换为列表并检索第一个对象，而不是“foo”。 - Uri Loya

过度复杂化会使其潜在地非常低效（消耗大量内存，速度慢）。正确的方法是使用Map。 - zakmck

Answer 9

Object objectToGet = ...
Map<Object, Object> map = new HashMap<Object, Object>(set.size());
for (Object o : set) {
    map.put(o, o);
}
Object objectFromSet = map.get(objectToGet);

如果你只执行一次获取操作，这并不会非常高效，因为你需要遍历所有的元素。但是，在对大量数据进行多次检索时，你将会注意到它们之间的差异。

- Xymon

Answer 10

如果您查看java.util.HashSet的实现的前几行，您会看到：

public class HashSet<E>
    ....
    private transient HashMap<E,Object> map;

因此，HashSet 内部实际上使用的是 HashMap，这意味着如果您直接使用 HashMap 并将相同的值用作键和值，则可以获得所需的效果并节省一些内存。

- rghome