Die Durchführung der Schnellste Suche - welche Kollektion soll ich verwenden?
Weiß ich:
- Wenn Sie benötigen schnellen Zugriff auf Elemente über index, ArrayList sollte Wahl.
- Wenn Sie benötigen schnellen Zugriff auf Elemente mit einem Schlüssel, verwenden HashMap.
- Wenn Sie schnelle hinzufügen und entfernen von Elementen verwenden LinkedList (aber es hat eine sehr schlechte Suche nach performance).
Zur Durchführung der Schnellste Suche, die auf der Grundlage von gespeicherten Daten in einem collection-Objekt, das die Sammlung sollte ich verwenden?
Unten ist mein code:
public void fillAndSearch(Collection<Student> collection) {
if(collection!=null){
for (int i=0; i<=10; i++) {
Student student = new Student("name" + i, "id" + i);
collection.add(student);
}
}
//here We have to perform searching for "name7" or "id5",
//then which implementation of collection will be fastest?
}
class Student {
String name;
String id;
Student(String name, String id) {
this.name = name;
this.id = id;
}
}
verwenden ArrayList, weil es die Suche auf der Grundlage der Indizierung
Sind Ihre Daten IMMER in der form von
Beim suchen der schnelle Zugriff ist ur -, so
Verwenden
Sammlung.man(ich) immer ein Objekt von student, die Sammlung ist alles über,ich bin nicht in der Lage zu erreichen U richtig was U Fragen?
Sind Ihre Daten IMMER in der form von
collection.get(i) = [name_i, id_i]
? (mit dem gleichen Wert der i
für den index, den Namen und die id)?Beim suchen der schnelle Zugriff ist ur -, so
HashMap
oder ArrayList
(denken Sie über die sortierte Liste und Zwiespalt). Aber in deinem Fall würde ich ein Exemplar einer HashMap<String, Student>
, und anzeigen der id und dem Namen der Schüler, so finden sich Ihre Schüler in O(1) (wenn es keine hash-Kollision) !Verwenden
java.util.HashMap
zum speichern der Objekte und die Verwendung der Schlüssel, d.h. der name oder die id, zwei Karten eigentlich mit Schlüssel als Namen andere mit Schlüssel als idSammlung.man(ich) immer ein Objekt von student, die Sammlung ist alles über,ich bin nicht in der Lage zu erreichen U richtig was U Fragen?
InformationsquelleAutor | 2015-05-19
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wird, was oft übersprungen, wenn der Vergleich
ArrayList
undLinkedList
den cache-und Speicher-management-Optimierungen.ArrayList
ist effektiv nur ein array-was bedeutet, dass es gespeichert ist, in einem kontinuierlichen Raum in der Erinnerung. Dies ermöglicht es, das Betriebssystem zu verwenden Optimierungen wie "wenn ein byte in den Speicher zugegriffen wurde, wird wahrscheinlich das nächste byte zugegriffen wird bald". DeshalbArrayList
ist schneller alsLinkedList
außer in einem Fall: beim einfügen/löschen das element am Anfang der Liste (da alle Elemente im array haben, werden verschoben). Hinzufügen/löschen am Ende oder in der Mitte iteriert, Zugriff auf das element sind alle schneller im Falle vonArrayList
.Wenn Sie brauchen, um die Suche für die Schüler mit bestimmten Namen und id, es klingt für mich wie eine Karte mit composite-Schlüssel -
Map<Student, StudentData>
. Ich würde empfehlen die VerwendungHashMap
Umsetzung, es sei denn, Sie müssen in der Lage sein, sowohl die Suche der Sammlung und abrufen alle Elemente, sortiert nach dem Schlüssel (in dem FallTreeMap
möglicherweise eine bessere Idee. Obwohl daran erinnern, dassHashMap
hatO(1)
Zugriffszeit, währendTreeMap
hatO(logn)
Zugriffszeit.Ich bin nicht ganz sicher, was Sie versuchen zu erreichen - warum suchen diese Sammlung überhaupt? Was wollen Sie finden?
InformationsquelleAutor Jaroslaw Pawlak
Mit bestimmten Einschränkungen, die Sie verwenden sollten HashMap.
Es wird Ihnen eine schnelle Suche, wie Sie wollten.
Wenn Sie sich sorgen über die Traversierung der Elemente in der bestimmten Reihenfolge, die Sie wählen sollten TreeMap (Natürliche Ordnung) oder LinkedHashMap (insertion order).
Wenn Sie Ihre Sammlung ist garantiert unveränderlich, die Sie verwenden können, sortiert der ArrayList mit binären Suche, wird es sparen Sie etwas Speicherplatz. In diesem Fall können Sie suchen, nur durch einen bestimmten Schlüssel, was unerwünscht ist in vielen realen Anwendungen.
Trotzdem, Sie sollte wirklich riesige Anzahl der Elemente (Millionen/Milliarden), den Unterschied zu fühlen zwischen O(logN) - Lösungen und-O(1) - Lösungen.
Wenn Sie mehr darüber erfahren möchten, Datenstrukturen, empfehle ich Ihnen zu überprüfen, Algorythms natürlich von der Princeton university auf coursera.com
InformationsquelleAutor AdamSkywalker
Es ist nichts falsch halten mehrere Sammlungen auf Ihre Daten zugreifen schneller.
In dieser situation würde ich 2
HashMap<String, Student>
's. Eine für jeden search-Taste.(PS: Oder wenn Sie nicht wissen, welche Art von keyword-Suche verwendet wird, dann speichern Sie beide in der gleichen Karte).
InformationsquelleAutor bvdb