Le titre de l'article devrait être : Quelles sont les complexités temporelles des implémentations de collections Java ?

Implémentations du framework Java Collections : un résumé Big-O

Lorsque vous enseignez un « cours intensif Java », il est crucial d'être conscient de la complexité temporelle Big-O associée à diverses implémentations de collections. Bien que les membres du public soient familiers avec la notation Big-O, il est peu probable qu'ils connaissent les complexités spécifiques de différentes opérations sur des collections spécifiques.

Heureusement, le livre "Java Generics and Collections" fournit des informations précieuses sur ces complexités. . Cet article résume les informations du livre, fournissant un tableau détaillé pour chaque type de collection : listes, ensembles, cartes et files d'attente.

Implémentations de listes :

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)

Définir les implémentations :

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

Implémentations de cartes :

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

Implémentations de files d'attente :

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)

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!