Big-O-Notation für Java Collections Framework-Implementierungen
Im Vorfeld eines bevorstehenden Java-Crashkurses ist es wichtig, einen prägnanten Kurs bereitzustellen Zusammenfassung der zeitlichen Komplexität verschiedener Vorgänge für verschiedene Sammlungsimplementierungen.
Implementierungen auflisten
| Implementation | 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
| Implementation | 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
| Implementation | 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
| Implementation | 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) |
Zusätzliche Ressourcen
Zur weiteren Erkundung ziehen Sie diese wertvollen Ressourcen in Betracht:
Das obige ist der detaillierte Inhalt vonWas sind die großen Zeitkomplexitäten verschiedener Java Collections Framework-Operationen?. 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)
