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

Ich werde bald einen “Java Crash-Kurs” unterrichten. Es ist zwar sicher anzunehmen, dass die Zuschauer die Big-O-Notation kennen, es ist jedoch wahrscheinlich nicht sicher anzunehmen, dass sie die Reihenfolge der verschiedenen Operationen bei verschiedenen Auflistungsimplementierungen kennen.

Ich könnte mir Zeit nehmen, um eine Zusammenfassungsmatrix selbst zu erstellen, aber wenn sie irgendwo im öffentlichen Bereich bereits existiert, würde ich sie gerne wiederverwenden (natürlich mit richtiger Bonität).

Jeder hat irgendwelche Hinweise?

   

Diese Website ist ziemlich gut, aber nicht spezifisch für Java: http://bigocheatsheet.com/ Hier ist ein Bild für den Fall, dass dieser Link nicht funktioniert

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) 

Der untere Teil des Javadoc für das Paket java.util enthält einige gute Links:

  • Collections Overview hat eine nette Übersichtstabelle.
  • Annotierte Gliederung listet alle Implementierungen auf einer Seite auf.

Die Javadocs von Sun für jede Sammelklasse werden Ihnen im Allgemeinen genau sagen, was Sie wollen. HashMap , zum Beispiel:

Diese Implementierung bietet konstante performance für die grundlegenden Operationen (get und put), vorausgesetzt, die Hash-function verteilt die Elemente ordnungsgemäß zwischen den Buckets. Die Iteration über Sammlungsansichten erfordert Zeit, die proportional zur “Kapazität” der HashMap-Instanz (Anzahl der Buckets) und ihrer Größe (Anzahl der Schlüssel / Wert-Zuordnungen) ist.

Baumkarte :

Diese Implementierung bietet garantierte log (n) -Zeitkosten für die Vorgänge containsKey, get, put und remove.

Baumsatz :

Diese Implementierung bietet garantierte Log (n) -Zeitkosten für die grundlegenden Operationen (hinzufügen, entfernen und enthalten).

(Hervorhebung von mir)

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

Ich werde über ArrayList vs. LinkedList sprechen:

Anordnungsliste:

  • O (1) get()
  • Amortized O (1) add()
  • Wenn Sie ein Element in der Mitte einfügen oder löschen, indem Sie ListIterator.add() oder Iterator.remove() , wird O (n) verwendet, um alle folgenden Elemente zu verschieben

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, wird es O (1)