Abrufen eines Elements aus einer Menge

Question

Warum ist die Set eine Operation anbieten, um ein Element zu erhalten, das gleich einem anderen Element ist?

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

Ich kann fragen, ob die Set ein Element enthält, das gleich ist mit bar Warum kann ich dieses Element nicht bekommen? :(

Zur Klarstellung: Die equals wird überschrieben, aber es wird nur eines der Felder überprüft, nicht alle. Also zwei Foo Objekte, die als gleich angesehen werden, können tatsächlich unterschiedliche Werte haben, deshalb kann ich nicht einfach foo .

Answer 1

Um die genaue Frage zu beantworten " Warum nicht Set eine Operation bereitstellen, um ein Element zu erhalten, das einem anderen Element entspricht?", so lautet die Antwort: weil die Designer des Sammlungsrahmens nicht sehr vorausschauend waren. Sie haben Ihren sehr legitimen Anwendungsfall nicht vorhergesehen, haben naiv versucht, "die mathematische Mengenabstraktion zu modellieren" (aus dem Javadoc) und einfach vergessen, die nützliche get() Methode.

Nun zu der impliziten Frage " wie erhalten Sie dann das Element": Ich denke, die beste Lösung ist die Verwendung eines Map<E,E> anstelle einer Set<E> , um die Elemente auf sich selbst abzubilden. Auf diese Weise können Sie effizient ein Element aus der "Menge" abrufen, da die Methode get() der Datei Map findet das Element mit Hilfe einer effizienten Hashtabelle oder eines Baumalgorithmus. Wenn Sie wollen, können Sie Ihre eigene Implementierung von Set die zusätzlich die Möglichkeit bietet get() Methode, die die Map .

Die folgenden Antworten sind meiner Meinung nach schlecht oder falsch:

"Du brauchst das Element nicht zu holen, weil du bereits ein gleiches Objekt hast": Die Behauptung ist falsch, wie du bereits in der Frage gezeigt hast. Zwei gleiche Objekte können immer noch unterschiedliche Zustände haben, die für die Objektgleichheit nicht relevant sind. Das Ziel ist es, Zugriff auf diesen Zustand des Elements zu erhalten, das in der Set und nicht den Zustand des Objekts, das als "Abfrage" verwendet wird.

"Sie haben keine andere Möglichkeit, als den Iterator zu verwenden": Das ist eine lineare Suche über eine Sammlung, die für große Mengen völlig ineffizient ist (ironischerweise ist intern die Set als Hash-Map oder Baum organisiert ist, der effizient abgefragt werden kann). Tun Sie es nicht! Ich habe in realen Systemen schwerwiegende Leistungsprobleme bei der Verwendung dieses Ansatzes gesehen. Meiner Meinung nach ist das Schlimmste an den fehlenden get() Methode ist nicht so sehr, dass es etwas umständlich ist, sie zu umgehen, sondern dass die meisten Programmierer den linearen Suchansatz verwenden, ohne an die Folgen zu denken.

Answer 2

Es würde keinen Sinn machen, das Element zu bekommen, wenn es gleich ist. A Map ist für diesen Anwendungsfall besser geeignet.

---

Wenn Sie das Element dennoch finden wollen, haben Sie keine andere Möglichkeit als den Iterator zu verwenden:

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

Answer 3

Wenn Sie ein gleiches Objekt haben, wozu brauchen Sie dann das Objekt aus der Menge? Wenn es nur durch einen Schlüssel "gleich" ist, kann ein Map wäre eine bessere Wahl.

Wie auch immer, das Folgende wird es tun:

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

Mit Java 8 kann dies zu einem Einzeiler werden:

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

Answer 4

Default Set in Java ist leider nicht dafür ausgelegt, eine "get"-Operation zu ermöglichen, da jschreiner genau erklärt.

Die Lösungen zur Verwendung eines Iterators, um das gewünschte Element zu finden (vorgeschlagen von dacwe ) oder das Element zu entfernen und es mit aktualisierten Werten wieder hinzuzufügen (vorgeschlagen von KyleM ), könnte funktionieren, kann aber sehr ineffizient sein.

Überschreiben der Implementierung von "equals", so dass nicht-gleiche Objekte "gleich" sind, wie es korrekt in David Ogren kann leicht zu Wartungsproblemen führen.

Und die Verwendung einer Map als expliziter Ersatz (wie von vielen vorgeschlagen) macht den Code imho weniger elegant.

Wenn das Ziel darin besteht, Zugriff auf die ursprüngliche Instanz des in der Menge enthaltenen Elements zu erhalten (ich hoffe, ich habe Ihren Anwendungsfall richtig verstanden), gibt es eine weitere mögliche Lösung.

---

Ich persönlich hatte das gleiche Bedürfnis bei der Entwicklung eines Client-Server-Videospiels mit Java. In meinem Fall hatte jeder Client Kopien der auf dem Server gespeicherten Komponenten, und das Problem bestand darin, dass ein Client ein Objekt des Servers ändern musste.

Die Weitergabe eines Objekts über das Internet bedeutete, dass der Client ohnehin verschiedene Instanzen dieses Objekts hatte. Um diese "kopierte" Instanz mit der ursprünglichen Instanz abzugleichen, beschloss ich, Java UUIDs zu verwenden.

Also habe ich eine abstrakte Klasse UniqueItem erstellt, die automatisch jeder Instanz ihrer Unterklassen eine zufällige eindeutige ID zuweist.

Diese UUID wird von der Client- und der Serverinstanz gemeinsam genutzt, so dass es auf diese Weise einfach sein könnte, sie mit Hilfe einer Map abzugleichen.

Die direkte Verwendung einer Karte in einem ähnlichen Anwendungsfall war jedoch nach wie vor unelegant. Jemand könnte argumentieren, dass die Verwendung einer Map komplizierter zu verwalten und zu handhaben ist.

Aus diesen Gründen habe ich eine Bibliothek namens MagicSet implementiert, die die Verwendung einer Map für den Entwickler "transparent" macht.

https://github.com/ricpacca/magicset

---

Wie das ursprüngliche Java HashSet verwendet ein MagicHashSet (eine der Implementierungen von MagicSet, die in der Bibliothek enthalten sind) eine unterstützende HashMap, aber anstatt Elemente als Schlüssel und einen Dummy-Wert als Wert zu haben, verwendet es die UUID des Elements als Schlüssel und das Element selbst als Wert. Dies verursacht keinen Overhead bei der Speichernutzung im Vergleich zu einem normalen HashSet.

Außerdem kann ein MagicSet genau wie ein Set verwendet werden, jedoch mit einigen weiteren Methoden, die zusätzliche Funktionen bieten, wie getFromId(), popFromId(), removeFromId() usw.

Die einzige Voraussetzung für die Verwendung ist, dass jedes Element, das Sie in einem MagicSet speichern möchten, die abstrakte Klasse UniqueItem erweitern muss.

---

Hier ein Code-Beispiel, in dem die ursprüngliche Instanz einer Stadt aus einem MagicSet abgerufen werden soll, wenn eine andere Instanz dieser Stadt mit derselben UUID (oder auch nur ihrer UUID) vorliegt.

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
}

Answer 5

Mit Java 8 können Sie das tun:

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

Aber Vorsicht, .get() löst eine NoSuchElementException aus, oder Sie können ein optionales Element manipulieren.