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!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
