Maison >Java >javaDidacticiel >Le titre de l'article devrait être : Quelles sont les complexités temporelles des implémentations de collections Java ?
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:31840parcourir
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!