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 :
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!