Der Titel des Artikels sollte lauten: Was sind die großen zeitlichen Komplexitäten von Java Collection-Implementierungen?
- Linda HamiltonOriginal
- 2024-10-28 02:33:31765Durchsuche
Java Collections Framework-Implementierungen: Eine große Zusammenfassung
Beim Unterrichten eines „Java-Crashkurses“ ist es wichtig, sich dessen bewusst zu sein die Big-O-Zeitkomplexität, die mit verschiedenen Sammlungsimplementierungen verbunden ist. Auch wenn die Zuhörer möglicherweise mit der Big-O-Notation vertraut sind, ist es unwahrscheinlich, dass sie die spezifischen Komplexitäten für verschiedene Operationen an bestimmten Sammlungen kennen.
Glücklicherweise bietet das Buch „Java Generics and Collections“ wertvolle Einblicke in diese Komplexitäten . Dieser Artikel fasst die Informationen aus dem Buch zusammen und bietet eine detaillierte Tabelle für jeden Sammlungstyp: Listen, Sets, Karten und Warteschlangen.
Listenimplementierungen:
| Operation | ArrayList | LinkedList | CopyOnWriteArrayList |
|---|---|---|---|
| get | O(1) | O(n) | O(1) |
| add | O(1) | O(1) | O(n) |
| contains | O(n) | O(n) | O(n) |
| next | O(1) | O(1) | O(1) |
| remove(0) | O(n) | O(1) | O(n) |
| iterator.remove | O(n) | O(1) | O(n) |
Set-Implementierungen:
| Operation | HashSet | LinkedHashSet | CopyOnWriteArraySet | EnumSet | TreeSet | ConcurrentSkipListSet |
|---|---|---|---|---|---|---|
| add | O(1) | O(1) | O(n) | O(1) | O(log n) | O(log n) |
| contains | O(1) | O(1) | O(n) | O(1) | O(log n) | O(log n) |
| next | O(h/n) | O(1) | O(1) | O(1) | O(log n) | O(1) |
| Notes | h is the table capacity |
Kartenimplementierungen:
| Operation | HashMap | LinkedHashMap | IdentityHashMap | EnumMap | TreeMap | ConcurrentHashMap | ConcurrentSkipListMap |
|---|---|---|---|---|---|---|---|
| get | O(1) | O(1) | O(1) | O(1) | O(log n) | O(1) | O(log n) |
| containsKey | O(1) | O(1) | O(1) | O(1) | O(log n) | O(1) | O(log n) |
| next | O(h/n) | O(1) | O(h/n) | O(1) | O(log n) | O(h/n) | O(1) |
| Notes | h is the table capacity |
Warteschlangenimplementierungen:
| Operation | PriorityQueue | ConcurrentLinkedQueue | ArrayBlockingQueue | LinkedBlockingQueue | PriorityBlockingQueue | DelayQueue | LinkedList | ArrayDeque | LinkedBlockingDeque |
|---|---|---|---|---|---|---|---|---|---|
| offer | O(log n) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) |
| peek | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
| poll | O(log n) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) |
| size | O(1) | O(n) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) | O(1) |
Das obige ist der detaillierte Inhalt vonDer Titel des Artikels sollte lauten: Was sind die großen zeitlichen Komplexitäten von Java Collection-Implementierungen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
In Verbindung stehende Artikel
Mehr sehen- Bitverschiebung vs. Multiplikation/Division: Sollten Sie sich über die Leistung in Java und .NET Sorgen machen?
- Wie aktiviere ich den JMX-Remotezugriff für jconsole und verbinde mich mit meiner JVM?
- Warum gibt class.getResource() in IntelliJ IDEA Null zurück?
- Hier sind einige Titeloptionen, die ein Frageformat beinhalten: * Wie verwaltet Java die Speicherfreigabe? (Unkompliziert und direkt) * Garantiert das Festlegen von Objekten auf Null, dass die Speicherfreigabe aufgehoben wird
- Hier sind einige fragenbasierte Titel, die zum Inhalt des Artikels passen: * Müssen Sie Ihren Java-Code profilieren? Lernen Sie VisualVM kennen, das kostenlose und leistungsstarke Tool! * Suchen Sie nach Open-Source-Java-Profiling? Vi