Schnellste Datenstruktur für enthält () in Java?

68

Was ist die Datenstruktur in Java, die die schnellste Operation für enthält () hat?

zB habe ich eine Reihe von Zahlen {1, 7, 12, 14, 20 ...}

Was ist bei einer anderen willkürlichen Zahl x (im Durchschnitt) der schnellste Weg, um den booleschen Wert zu generieren, ob x in der Menge enthalten ist oder nicht? Die Wahrscheinlichkeit für! Enthält () ist ungefähr 5x höher.

Bieten alle Kartenstrukturen eine o (1) -Operation? Ist HashSet der schnellste Weg?

java data-structures set Codechobo
quelle

Antworten:

127

Schauen Sie sich Set- (Hashset, Enumset) und Hash- (HashMap, Linkedhash ..., Idnetityhash ..) basierte Implementierungen an. sie haben O (1) für enthält ()

Dieses Cheatsheet ist eine große Hilfe.

Aravind Yarram
quelle
7
Für das, was es wert ist, sind Hash-Maps im Allgemeinen nicht O (1) in der Suche, wenn Hash-Kollisionen auftreten (und sie können ziemlich oft auftreten, wenn auch nur sehr wenige gleichzeitig). Der schlimmste Fall ist O (n) bei der Suche.
Blindy
Ich stimme Blindy zu. Die Leistung der Hash-basierten Sammlung wird durch die Leistung der Hash-Funktion begrenzt.
Sbidwai
Als ich vor kurzem ging, war die Seite nicht erreichbar. Wenn Ihnen dies passiert, können Sie diesen Link verwenden
EasilyBaffled
Seite kann wegen robots.txt nicht gecrawlt oder angezeigt werden (korrigieren Sie den Link plz)
iluvatar_GR
9

Für Ihren speziellen Fall von Zahlen mit einer relativ hohen Dichte würde ich ein BitSet verwenden, es ist schneller und viel kleiner als ein Hash-Set.

Sternenblau
quelle
5

Die einzige Datenstruktur, die schneller als HashSet ist, ist wahrscheinlich TIntHashSet von Trove4J. Hierbei werden Grundelemente verwendet, ohne dass ganzzahlige Objekte verwendet werden müssen.

Wenn die Anzahl der Ganzzahlen gering ist, können Sie einen Booleschen Wert [] erstellen, bei dem jeder vorhandene Wert in "true" umgewandelt wird. Dies wird O (1) sein. Hinweis: Es wird nicht garantiert, dass HashSet O (1) ist, und es ist wahrscheinlicher, dass es O ist (log (log (N))).

Sie erhalten nur O (1) für eine ideale Hash-Verteilung. Es ist jedoch wahrscheinlicher, dass Kollisionen von gehashten Buckets auftreten und einige Suchvorgänge mehr als einen Wert überprüfen müssen.

Peter Lawrey
quelle
-2

Hashing (Hash-Set) ist das beste mit O (1)

Satish
quelle
7
Zwischen Ihrer Antwort und der von Pangaea liegen 8 Minuten. Ihre fügt keinen zusätzlichen Wert hinzu, warum also posten?
Bart Kiers
1
@bart echte langsame Internetverbindung
@ Will vielleicht. Wenn ja, dann hatte @Satish inzwischen genug Zeit, um seine überflüssige Antwort zu entfernen. Dennoch lässt er es baumeln. Vielleicht in der Hoffnung, einige Punkte zu sammeln? Vielleicht war das zunächst die Absicht, wer weiß?
Bart Kiers
8
@Bart: Ihr Up / Down-Stimmenverhältnis deutet darauf hin, dass Sie den Menschen gegenüber ein wenig hart sind. Entspannen Sie sich ^ _ ^
Phil
1
@Po, zu Ihrer Information, ich bin nicht schwer für Leute, sondern für die Antworten, die Leute geben, von denen ich denke, dass sie falsch sind oder keine neuen Informationen hinzufügen. Bevor ich solche Antworten ablehne, gebe ich normalerweise zuerst einen Kommentar ab, warum ich die Antwort für falsch / unangemessen halte. Wenn das OP keine Maßnahmen ergreift oder sich selbst erklärt, gebe ich meine Stimme ab. Darum geht es bei SO doch! Wenn das OP seiner Antwort einige zusätzliche Informationen hinzugefügt oder diese einfach entfernt hätte, hätte ich in diesem Fall nicht abgestimmt. Wieder stimme ich nicht die Leute ab (oder auf), sondern die Antworten, die sie geben. Ein großer Unterschied.
Bart Kiers