Quelles sont les complexités Big-O Time des différentes opérations du framework Java Collections ?

Notation Big-O pour les implémentations du framework Java Collections

En prévision d'un prochain cours intensif Java, il est essentiel de fournir un résumé concis résumé de la complexité temporelle de diverses opérations sur différentes implémentations de collection.

Liste des implémentations

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)

Définir les implémentations

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)	-

Implémentations de cartes

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)	-

Implémentations de files d'attente

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)

Ressources supplémentaires

Pour une exploration plus approfondie, considérez ces précieuses ressources :

• Aperçu des collections : propose un tableau récapitulatif utile
• Aperçu annoté : contient une liste complète des implémentations sur une seule page

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!