Le titre de l'article devrait être : Quelles sont les complexités temporelles des implémentations de collections Java ?
- Linda Hamiltonoriginal
- 2024-10-28 02:33:31765parcourir
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!
Articles Liés
Voir plus- Décalage de bits ou multiplication/division : devriez-vous vous soucier des performances en Java et .NET ?
- Comment activer l'accès à distance JMX pour jconsole et vous connecter à votre JVM ?
- Pourquoi class.getResource() renvoie-t-il Null dans IntelliJ IDEA ?
- Voici quelques options de titre, intégrant un format de question : * Comment Java gère-t-il la désallocation de mémoire ? (Simple et direct) * La définition des objets sur Null garantit-elle la désallocation de mémoire dans
- Voici quelques titres basés sur des questions, alignés sur le contenu de l'article : * Besoin de profiler votre code Java ? Découvrez VisualVM, l'outil gratuit et puissant ! * Vous recherchez un profilage Java Open Source ? Vi