webentwicklung-frage-antwort-db.com.de

Big-O-Zusammenfassung für Java Collections Framework-Implementierungen?

Möglicherweise unterrichte ich bald einen "Java-Crash-Kurs". Während es wahrscheinlich sicher ist anzunehmen, dass die Zuschauer die Big-O-Notation kennen, ist es wahrscheinlich nicht sicher anzunehmen, dass sie die Reihenfolge der verschiedenen Operationen auf verschiedenen Auflistungsimplementierungen kennen.

Ich könnte mir Zeit nehmen, um selbst eine Zusammenfassungsmatrix zu erstellen, aber wenn sie bereits irgendwo im öffentlichen Bereich verfügbar ist, würde ich sie gerne wiederverwenden (natürlich mit angemessener Gutschrift).

Hat jemand irgendwelche Hinweise?

149
Jared

Diese Website ist ziemlich gut, aber nicht spezifisch für Java: http://bigocheatsheet.com/Here is an image in case this link won't work

134
Ben J

Das Buch Java Generics and Collections enthält diese Informationen (Seiten: 188, 211, 222, 240).

Implementierungen auflisten:

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(n)      O(n)
LinkedList            O(n) O(1) O(n)     O(1) O(1)      O(1)
CopyOnWrite-ArrayList O(1) O(n) O(n)     O(1) O(n)      O(n)

Implementierungen festlegen:

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table capacity
LinkedHashSet         O(1)     O(1)     O(1) 
CopyOnWriteArraySet   O(n)     O(n)     O(1) 
EnumSet               O(1)     O(1)     O(1) 
TreeSet               O(log n) O(log n) O(log n)
ConcurrentSkipListSet O(log n) O(log n) O(1)

Kartenimplementierungen:

                      get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
LinkedHashMap         O(1)     O(1)        O(1) 
IdentityHashMap       O(1)     O(1)        O(h/n)   h is the table capacity 
EnumMap               O(1)     O(1)        O(1) 
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 
ConcurrentSkipListMap O(log n) O(log n)    O(1)

Warteschlangenimplementierungen:

                      offer    peek poll     size
PriorityQueue         O(log n) O(1) O(log n) O(1)
ConcurrentLinkedQueue O(1)     O(1) O(1)     O(n)
ArrayBlockingQueue    O(1)     O(1) O(1)     O(1)
LinkedBlockingQueue   O(1)     O(1) O(1)     O(1)
PriorityBlockingQueue O(log n) O(1) O(log n) O(1)
DelayQueue            O(log n) O(1) O(log n) O(1)
LinkedList            O(1)     O(1) O(1)     O(1)
ArrayDeque            O(1)     O(1) O(1)     O(1)
LinkedBlockingDeque   O(1)     O(1) O(1)     O(1)

Das Ende des Javadocs für das Paket Java.util enthält einige gute Links:

194
toolkit

Die Javadocs von Sun für jede Sammlungsklasse enthalten in der Regel genau die Informationen, die Sie benötigen. HashMap , zum Beispiel:

Diese Implementierung bietet eine zeitlich konstante Leistung für die Grundoperationen (get und put), vorausgesetzt, die Hash-Funktion verteilt die Elemente ordnungsgemäß auf die Buckets. Die Iteration über Erfassungsansichten erfordert eine Zeit, die proportional zur "Kapazität" der HashMap-Instanz (Anzahl der Buckets) plus ihrer Größe (Anzahl der Schlüsselwerte) ist Zuordnungen).

TreeMap :

Diese Implementierung bietet garantierte Protokoll (n) Zeitkosten für die enthältKey-, Get-, Put- und Remove-Vorgänge.

TreeSet :

Diese Implementierung bietet garantierte Protokoll (n) Zeitkosten für die Basisoperationen (Hinzufügen, Entfernen und Enthalten).

(Hervorhebung von mir)

12
matt b

Der Typ oben gab einen Vergleich für HashMap/HashSet vs. TreeMap/TreeSet.

Ich werde über ArrayList vs. LinkedList sprechen:

Anordnungsliste:

  • O (1) get()
  • abgeschrieben O(1) add()
  • wenn Sie ein Element in der Mitte mit ListIterator.add() oder Iterator.remove() einfügen oder löschen, werden alle folgenden Elemente durch O(n) verschoben

LinkedList:

  • O (n) get()
  • O (1) add()
  • wenn Sie ein Element in der Mitte mit ListIterator.add() oder Iterator.remove() einfügen oder löschen, ist dies O (1).
6
newacct