Welche Java-Datenstruktur ist eine geordnete Sammlung, bietet die Funktionalität Konstante Zeit contains Methode von HashSet, und bietet konstante Zeit Nachschlagen von Index sehr ähnlich der get Methode von ArrayList? Enthält die Java-API so etwas? Ich überlegte, TreeSet zu verwenden, aber laut den Java-Dokumenten sind diese Operationen O (log n).Java Ordered Hashable Collection
Verwenden Sie LinkedHashSet. Es ist Hash-Tabelle und verkettete Listenimplementierung der Set-Schnittstelle mit vorhersagbarer Iterationsreihenfolge.
Sie sehen bis zu O (n) -Komplexität zum Einfügen oder Überprüfen der Existenz eines Elements im Hash-Set. In den meisten Fällen werden jedoch keine Kollisionen angezeigt. In den meisten Fällen ist dies O (1).
Unterstützt LinkedHashSet Indizierung? – Aroto
Set-Schnittstelle hat keine direkten Methoden wie indexOf() oder get(). Sie müssen die gesamte Sammlung analysieren, um nach einem Element zu suchen. indexOf() und get() tun intern nur das selbe. – FallAndLearn
Das OP fordert den Abruf von Konstantenzeitelementen * nach Index * an. Obwohl 'LinkedHashSet' das Abrufen in konstanter Zeit bietet, ist es nur nach Schlüssel, nicht nach Index. –
Die Java-Standardbibliothek bietet keine solche Klasse, aber Sie könnten Ihre eigenen implementieren, ohne zu viele Probleme. Es wäre mehr oder weniger das Dual von LinkedHashSet: ein List (vielleicht Einwickeln ArrayList), das eine interne HashSet für konstante Zeit Verarbeitung beibehält.
Die Collections API verfügt über Klassen, die die Implementierung von Auflistungsklassen erleichtern sollen. In diesem Fall würde ich eine konkrete Unterklasse von AbstractList implementieren.
Update: Auf der anderen Seite, wenn Ihre Idee ist, dass die Instanzen automatisch ihre Elemente in Ordnung halten und/oder dass sie doppelte Elemente nicht zulassen, dann, was du redest ist keine List überhaupt . In diesem Fall sollten Sie in Betracht ziehen, eine konkrete Unterklasse von AbstractSet zu implementieren, die indizierte Abrufmethoden hinzufügt. Sie könnten immer noch eine HashSet und eine ArrayList umbrechen, aber Sie müßten etwas Mühe aufwenden, um die Liste beim Einfügen von Elementen geordnet zu halten.
A ['LinekdHashSet'] (https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashSet.html) vielleicht? – Mureinik
Benötigen Sie eine konstante Zeiteinfügung? Wenn dies der Fall ist, wird dies nicht funktionieren, da eine Datenstruktur wie diese eine Vergleichssortierung in O (n) Zeit ermöglichen würde. – user2357112
Wenn Sie "geordnet" sagen, meinen Sie eine sortierte Bestellung, oder meinen Sie eine andere Bestellung, wie z. – user2357112