Getting an element from a Set

Question

Why doesn't Set provide an operation to get an element that equals another element?

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

I can ask whether the Set contains an element equal to bar, so why can't I get that element? :(

To clarify, the equals method is overridden, but it only checks one of the fields, not all. So two Foo objects that are considered equal can actually have different values, that's why I can't just use foo.

Solution 1

There would be no point of getting the element if it is equal. A Map is better suited for this usecase.

---

If you still want to find the element you have no other option but to use the iterator:

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);
    }
}

Solution 2

To answer the precise question "Why doesn't Set provide an operation to get an element that equals another element?", the answer would be: because the designers of the collection framework were not very forward looking. They didn't anticipate your very legitimate use case, naively tried to "model the mathematical set abstraction" (from the javadoc) and simply forgot to add the useful get() method.

Now to the implied question "how do you get the element then": I think the best solution is to use a Map<E,E> instead of a Set<E>, to map the elements to themselves. In that way, you can efficiently retrieve an element from the "set", because the get() method of the Map will find the element using an efficient hash table or tree algorithm. If you wanted, you could write your own implementation of Set that offers the additional get() method, encapsulating the Map.

The following answers are in my opinion bad or wrong:

"You don't need to get the element, because you already have an equal object": the assertion is wrong, as you already showed in the question. Two objects that are equal still can have different state that is not relevant to the object equality. The goal is to get access to this state of the element contained in the Set, not the state of the object used as a "query".

"You have no other option but to use the iterator": that is a linear search over a collection which is totally inefficient for large sets (ironically, internally the Set is organized as hash map or tree that could be queried efficiently). Don't do it! I have seen severe performance problems in real-life systems by using that approach. In my opinion what is terrible about the missing get() method is not so much that it is a bit cumbersome to work around it, but that most programmers will use the linear search approach without thinking of the implications.

Solution 3

If you have an equal object, why do you need the one from the set? If it is "equal" only by a key, an Map would be a better choice.

Anyway, the following will do it:

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

With Java 8 this can become a one liner:

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

Solution 4

Default Set in Java is, unfortunately, not designed to provide a "get" operation, as jschreiner accurately explained.

The solutions of using an iterator to find the element of interest (suggested by dacwe) or to remove the element and re-add it with its values updated (suggested by KyleM), could work, but can be very inefficient.

Overriding the implementation of equals so that non-equal objects are "equal", as stated correctly by David Ogren, can easily cause maintenance problems.

And using a Map as an explicit replacement (as suggested by many), imho, makes the code less elegant.

If the goal is to get access to the original instance of the element contained in the set (hope I understood correctly your use case), here is another possible solution.

---

I personally had your same need while developing a client-server videogame with Java. In my case, each client had copies of the components stored in the server and the problem was whenever a client needed to modify an object of the server.

Passing an object through the internet meant that the client had different instances of that object anyway. In order to match this "copied" instance with the original one, I decided to use Java UUIDs.

So I created an abstract class UniqueItem, which automatically gives a random unique id to each instance of its subclasses.

This UUID is shared between the client and the server instance, so this way it could be easy to match them by simply using a Map.

However directly using a Map in a similar usecase was still inelegant. Someone might argue that using an Map might be more complicated to mantain and handle.

For these reasons I implemented a library called MagicSet, that makes the usage of an Map "transparent" to the developer.

https://github.com/ricpacca/magicset

---

Like the original Java HashSet, a MagicHashSet (which is one of the implementations of MagicSet provided in the library) uses a backing HashMap, but instead of having elements as keys and a dummy value as values, it uses the UUID of the element as key and the element itself as value. This does not cause overhead in the memory use compared to a normal HashSet.

Moreover, a MagicSet can be used exactly as a Set, but with some more methods providing additional functionalities, like getFromId(), popFromId(), removeFromId(), etc.

The only requirement to use it is that any element that you want to store in a MagicSet needs to extend the abstract class UniqueItem.

---

Here is a code example, imagining to retrieve the original instance of a city from a MagicSet, given another instance of that city with the same UUID (or even just its 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
}

Solution 5

If your set is in fact a NavigableSet<Foo> (such as a TreeSet), and Foo implements Comparable<Foo>, you can use

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

(Thanks to @eliran-malka’s comment for the hint.)

View more solutions