In TreeSet gibt es eine Methode namens contains, die true zurückgibt, wenn ein Element in der Menge ist. Ich nehme an, dass diese Methode die binäre Suche verwendet und nicht alle Elemente in aufsteigender Reihenfolge durchläuft. Habe ich recht?
Ich habe ein TreeSet, das Objekte einer Klasse enthält, die zwei String-Instanzvariablen verwendet, um sie von anderen Objekten derselben Klasse zu unterscheiden. Ich möchte in der Lage sein, eine Methode zu erstellen, die das TreeSet durch den Vergleich der Objekte zwei Instanzvariablen (mit Get-Methoden natürlich) mit zwei anderen String-Variablen und wenn sie gleich sind, das Element zurückgeben. Wenn die Instanzvariablen kleiner sind, gehe zum ersten Element im rechten Teilbaum oder wenn sie größer sind, suche im linken Teilbaum usw. Gibt es eine Möglichkeit, dies zu tun?
Ich weiß, ich könnte die Objekte einfach in einer ArrayList speichern und die binäre Suche verwenden, um das Objekt zu finden, aber das wäre nicht so schnell, als nur das TreeSet zu durchsuchen.
Anstatt ein TreeSet zu verwenden, könnten Sie Ihre Objekte in einem TreeMap<Foo, Foo> oder TreeMap<FooKey, Foo> speichern (wenn Sie nicht jedes Mal, wenn Sie suchen wollen, einfach ein neues aktuelles Foo erstellen können). Set s sind nicht wirklich zum Nachschlagen gedacht.
Für das Beispiel FooKey wäre FooKey eine einfache unveränderliche Klasse, die nur die zwei String s und Comparable enthält. Den Wert von Foo für zwei String s zu finden wäre dann eine einfache Angelegenheit von treeMap.get(new FooKey(firstString, secondString)) . Dies benutzt natürlich die Baum-Traversierung, um den Wert zu finden.
Sie sollten entweder Comparable für Ihr Objekt implementieren oder eine separate Comparator-Klasse erstellen, die Sie zum Zeitpunkt der Konstruktion von TreeSet übergeben. Dadurch können Sie Ihre benutzerdefinierte Vergleichslogik einwerfen und das TreeSet seine optimierte Speicher- / Suchfunktion ausführen lassen.
Eine Sache, die ich mich gefragt habe, ist, warum Sie in einem sortierten Set suchen wollen? Wenn Sie in der Lage sein möchten, in der richtigen Reihenfolge zu iterieren und schnell nachzuschlagen, können Sie davon profitieren, Ihre Objekte in zwei separaten Datenstrukturen zu speichern. Einer wie dein SortedSet<Foo> und dann auch ein HashMap<FooKey,Foo> ähnlich dem, was ColinD erwähnt hat. Dann erhalten Sie konstante Zeitabfragen anstelle von log (n) auf der TreeMap. Sie haben eine Schreibstrafe dafür, dass Sie in beide Strukturen schreiben müssen, und eine Speicherresource, die die beiden Datenstrukturen einschränkt, aber Sie haben Ihren Zugriff auf die Daten vollständig optimiert.
Auch wenn Speicherressourcen eingeschränkt sind und Ihre Strings wirklich die Objekte unterscheiden, können Sie einfach hashcode() und equals() für Ihr Objekt Foo implementieren und sie dann sowohl als Schlüssel als auch als Wert verwenden ( like HashMap<Foo,Foo> Der Nachteil ist, dass Sie einen Foo erstellen müssen, um den Getter aufzurufen.
Sie haben die Antwort über die Verwendung vergleichbarer / Komparatoren erhalten, aber ich dachte, ich würde hinzufügen, dass Sie Recht haben, dass contains () eine binäre Suche durchführt, obwohl Sie diese Details nicht kennen sollten
Tags und Links java arraylist binary-search treeset