Ich habe eine Anforderung, 2 bis 15 Millionen Konten (die ein String der Länge 15 sind) in einer Datenstruktur für Nachschlagezwecke und Überprüfung der Eindeutigkeit zu speichern. Anfangs plante ich, sie in HashSet zu speichern, aber ich bezweifle, dass die Geschwindigkeit der Suche aufgrund von Hash-Kollisionen langsam ist und letztendlich langsamer sein wird als eine TreeMap (mit binärer Suche).
Es ist nicht erforderlich, dass Daten sortiert werden. Ich benutze Java 7. Ich habe 64G System mit 48G für diese Anwendung gewidmet.
Diese Frage ist kein Duplikat des HashSet- und TreeSet-Leistungstests , da es sich bei dieser Frage um die Leistung von handelt Hinzufügen von Elementen zu Set und diese Frage bezieht sich auf die Leistung von Prüfen einer vorhandenen Set auf doppelte Werte.
Als wir versuchten, 50 Millionen Datensätze in HashMap mit den richtigen Initialisierungsparametern zu speichern, begann das Einfügen langsamer zu werden, besonders nach 35 Millionen Datensätzen. Das Wechseln zu TreeMap führte zu einer konstanten Einfüge- und Wiederherstellungsleistung.
Beobachtung: TreeMap bietet eine bessere Leistung als eine HashMap für große Eingabesets. Für ein kleineres Set wird HashMap natürlich eine bessere Leistung bringen.
Wenn Sie 48 GB dedizierten Speicher für Ihre 2 Millionen bis 15 Millionen Datensätze haben, ist Ihre beste Wette wahrscheinlich, ein HashMap<Key, Record> zu verwenden, wobei Ihr Schlüssel abhängig von Ihren Anforderungen ein Integer oder ein String ist.
Bei Hash-Kollisionen ist alles in Ordnung, solange Sie dem Map genügend Speicher zur Verfügung stellen und einen entsprechenden Ladefaktor haben.
Ich empfehle, den folgenden Konstruktor zu verwenden: new HashMap<>(13_000_000); (30% mehr als die erwartete Anzahl an Datensätzen - die automatisch um HashMap 's Implementierung auf 2^24 Zellen erweitert wird).
Teilen Sie Ihrer Anwendung mit, dass dieses Map von Anfang an sehr groß sein wird, sodass es nicht automatisch wachsen muss, wenn Sie es füllen.
HashMap verwendet eine O(1) Zugriffszeit für seine Mitglieder, während TreeMap O(log n) Nachschlagezeit verwendet, aber effizienter mit Speicher sein kann und keine clevere Hash-Funktion benötigt. Wenn Sie jedoch String oder Integer keys verwenden, müssen Sie sich keine Gedanken über das Entwerfen einer Hashing-Funktion machen und die konstanten Zeit-Lookups werden eine große Verbesserung darstellen. Ein weiterer Vorteil von TreeMap / TreeSet ist die sortierte Bestellung, von der Sie angegeben haben, dass Sie sich nicht darum kümmern. Verwende HashMap .
Wenn der einzige Zweck der Liste darin besteht, nach eindeutigen Kontonummern zu suchen , ist alles, was ich oben gesagt habe, immer noch wahr, aber wie Sie in Ihrer Frage angegeben haben, sollten Sie ein% co_de verwenden %, nicht HashSet<String> . Das Leistungsempfehlungen und Konstruktorargument ist weiterhin anwendbar.
Weitere Informationen: HashSet- und TreeSet-Leistungstest
Tags und Links java performance hashset treeset