java ständig sortierte Liste mit schnellem Abruf

Question

Ich bin auf der Suche nach einer ständig sortierten Liste in Java, die auch verwendet werden kann, um ein Objekt sehr schnell abzurufen. PriorityQueue funktioniert großartig für die "ständig sortiert" Anforderung, und HashMap funktioniert großartig für die schnelle Abfrage nach Schlüssel, aber ich brauche beide in der gleichen Liste. An einem Punkt hatte ich meine eigene geschrieben, aber es implementiert nicht die Sammlungen Schnittstellen (so kann nicht als Drop-in-Ersatz für eine java.util.List usw. verwendet werden), und ich würde lieber zu Standard-Java-Klassen bleiben, wenn möglich.

Gibt es eine solche Liste? Im Moment verwende ich 2 Listen, eine Prioritäts-Warteschlange und eine Hashmap, beide enthalten die gleichen Objekte. Ich verwende die Prioritäts-Warteschlange, um den ersten Teil der Liste in sortierter Reihenfolge zu durchlaufen, die Hashmap für die schnelle Abfrage nach Schlüssel (ich muss beide Operationen austauschbar tun), aber ich hoffe auf eine elegantere Lösung...

Bearbeiten: Ich sollte hinzufügen, dass ich die Liste durch einen anderen Komparator als das, was für die Abfrage nach Schlüssel verwendet wird, sortiert haben müssen; die Liste wird durch einen langen Wert sortiert, die Schlüsselabfrage ist ein String.

Answer 1

Da Sie bereits mit HashMap das bedeutet, dass Sie eindeutige Schlüssel haben. Angenommen, Sie möchten nach diesen Schlüsseln ordnen, TreeMap ist Ihre Antwort.

Answer 2

Es klingt, als ob Sie eine Sammlung mit einem automatisch gepflegten Index meinen.

Versuchen Sie zu schauen GlasierteListen die "Listen-Pipelines" verwenden, um Änderungen effizient zu verbreiten - ihre SortierteListe Klasse sollte diese Aufgabe erfüllen.

edit: Ich habe Ihre Anforderung "Abruf nach Schlüssel" übersehen. Das kann erreicht werden mit GlazedLists.syncEventListToMap y GlazedLists.syncEventListToMultimap -- syncEventListToMap funktioniert, wenn es keine doppelten Schlüssel gibt, und syncEventListToMultimap funktioniert, wenn es doppelte Schlüssel gibt. Das Schöne an diesem Ansatz ist, dass Sie mehrere Maps basierend auf verschiedenen Indizes erstellen können.

---

Wenn Sie TreeMaps für Indizes verwenden möchten - was Ihnen eine bessere Leistung bieten kann - müssen Sie Ihre TreeMaps privat in einer benutzerdefinierten Klasse Ihrer Wahl kapseln, die die gewünschten Schnittstellen/Methoden bereitstellt, und Accessoren/Mutatoren für diese Klasse erstellen, um die Indizes mit der Sammlung synchron zu halten. Stellen Sie sicher, dass Sie Gleichzeitigkeitsprobleme behandeln (über synchronized Methoden oder Sperren oder was auch immer), wenn Sie von mehreren Threads aus auf die Sammlung zugreifen.

---

edit: schließlich, wenn schnelles Durchlaufen der Elemente in sortierter Reihenfolge wichtig ist, erwägen Sie die Verwendung von ConcurrentSkipListMap anstelle von TreeMap - nicht wegen der Gleichzeitigkeit, sondern wegen des schnellen Traversals. Listen überspringen sind verknüpfte Listen mit mehreren Verknüpfungsebenen: eine, die alle Elemente durchläuft, die nächste, die im Durchschnitt alle K Elemente durchläuft (für eine gegebene Konstante K), die nächste, die alle K durchläuft 2 Artikel im Durchschnitt, usw.

Answer 3

TreeMap

http://download.oracle.com/javase/6/docs/api/java/util/TreeMap.html

Answer 4

Gehen Sie mit einem TreeSet .

Eine NavigableSet-Implementierung auf der Grundlage einer TreeMap. Die Elemente werden anhand ihrer natürlichen Reihenfolge oder durch einen Comparator geordnet, der bei der Erstellung des Sets bereitgestellt wird, je nachdem, welcher Konstruktor verwendet wird.

Diese Implementierung bietet garantierte log(n)-Zeitkosten für die Grundoperationen (add, remove und contains).

Answer 5

Ich habe das nicht getestet, also könnte ich mich irren, also betrachten Sie dies nur als einen Versuch. Verwenden Sie TreeMap, verpacken Sie den Schlüssel dieser Map als ein Objekt, das zwei Attribute hat (den String, den Sie als Schlüssel in hashmap verwenden und den Long, den Sie verwenden, um die Sortierreihenfolge in PriorityQueue zu erhalten). Überschreiben Sie nun für dieses Objekt die Methoden equals und hashcode unter Verwendung von string. Implementieren Sie die vergleichbare Schnittstelle unter Verwendung des long.