Was sind die großen Zeitkomplexitäten verschiedener Java Collections Framework-Operationen?

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:

• Sammlungsübersicht: Bietet eine hilfreiche Übersichtstabelle
• Annotierte Gliederung: Enthält eine umfassende Liste der Implementierungen auf einer einzigen Seite

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!