Sammlung mit Index- und Hash-Zugriff

Question

Ich brauche eine Sammelklasse, die beides hat: schnellen Index- und Hash-Zugriff. Jetzt habe ich ArrayList. Es hat gute Indexzugriffe, aber seine contains Methode ist nicht performant. HashSet hat eine gute contains Implementierung, aber keinen indizierten Zugriff. Welche Sammlung hat beides? Wahrscheinlich etwas von Apache? Oder sollte ich meine eigene Sammlungsklasse erstellen, die beide hat: ArrayList für indizierte Zugriffe und HashSet für contains überprüfen?

Nur zur Klarstellung: Ich brauche beide get(int index) und contains(Object o)

Answer 1

Wenn Sie den Index von Anfang bis Ende durchqueren, ich denke, das Ihre Bedürfnisse befriedigen könnte: LinkedHashSet

Wenn Sie zufällig über die zugreifen müssen Index, sowie Hash-Zugriff, wenn niemand sonst einen besseren Vorschlag hat, denke ich, dass Sie Ihre eigene Sammlung machen können, die beides tut.

Answer 2

indizierte Zugriffsleistung kein Problem ist, ist die nächste Übereinstimmung LinkedHashSet API ist, das sagt, dass es

Hash-Tabelle und verknüpfte Liste Implementierung der Set-Schnittstelle, mit vorhersagbaren Iterationsreihenfolge.

zumindest denke ich nicht, dass die Leistung schlechter sein wird als die von LinkedListPerformance. Sonst kann ich keine Alternative sehen, aber Ihre ArrayList + HashTable-Lösung

Answer 3

Tun Sie dies; verwenden Kombination von Hash Technik sowie Liste Beste aus beiden Welten zu bekommen :)

class DataStructure<Integer>{ 
    Hash<Integer,Integer> hash = new HashMap<Integer, Integer>(); 
    List<Integer> list = new ArrayList<Integer>(); 

    public void add(Integer i){ 
     hash.add(i,i); 
     list.add(i); 
    } 
    public Integer get(int index){ 
     return list.get(index); 
    } 
    ... 
} //used Integers to make it simpler 

So Objekt; Sie halten in HashMap/HashSet sowie ArrayList.

Also, wenn Sie wollen

contains method : call hashed contains method. 

get an object with index: use array to return the value 

So stellen Sie sicher bedienen, dass Sie diese beiden Sammlungen synchron sind. Und kümmern sich um Aktualisierung/Löschung in beiden Datenstrukturen.

Answer 4

Ich weiß nicht die genaue Nachschlagen Zeiten, aber vielleicht könnten Sie einige Implementierung der Map interface verwenden. Sie können Ihre Objekte mit map.put(objectHash, obj) speichern.

Dann könnten Sie überprüfen, ob Sie mit einem bestimmten Objekt haben:

boolean contained = map.containsValue(obj); 

Und Sie den Hash verwenden können, um ein Objekt in der Karte zum Nachschlagen:

MyObject object = map.get(objectHash); 

Obwohl, ist der einzige Nachteil dass Sie Ihre Hashes für diesen Suchaufruf kennen müssen, der möglicherweise nicht in Ihrer Implementierung enthalten ist.