The title of the article should be: What are the Big-O Time Complexities of Java Collection Implementations?
- Linda HamiltonOriginal
- 2024-10-28 02:33:31765browse
Java Collections Framework Implementations: A Big-O Summary
When teaching a "Java crash-course," it's crucial to be aware of the Big-O time complexity associated with various collection implementations. While audience members may be familiar with Big-O notation, it's unlikely they'll know the specific complexities for different operations on specific collections.
Fortunately, the book "Java Generics and Collections" provides valuable insights into these complexities. This article summarizes the information from the book, providing a detailed table for each type of collection: lists, sets, maps, and queues.
List Implementations:
| 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) |
Set Implementations:
| 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 |
Map Implementations:
| 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 |
Queue Implementations:
| 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) |
The above is the detailed content of The title of the article should be: What are the Big-O Time Complexities of Java Collection Implementations?. For more information, please follow other related articles on the PHP Chinese website!
Related articles
See more- How do I efficiently switch between different panels in a Java GUI using a CardLayout?
- How can I control the content type of the response with @ResponseBody in Spring MVC?
- Why Can\'t You Define a Static Method in a Non-Static Inner Class in Java Prior to Version 16?
- How Can the Command Pattern Improve Code Maintainability and Simplify Command Handling in Java?
- Here are a few title options, keeping in mind the question format and content of your article: Option 1 (Focus on the problem): * Why is Catching All Exceptions a Bad Idea? Option 2 (Focus on best p