Der Titel des Artikels sollte lauten: Was sind die großen zeitlichen Komplexitäten von Java Collection-Implementierungen?

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!