Java 集合框架实现的 Big-O 表示法
在即将到来的 Java 速成课程中，有必要提供一个简洁的不同集合实现上的各种操作的时间复杂度的总结。
列表实现
| 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) |
集合实现
| 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) | - |
地图实现
| 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) | - |
队列实现
| 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) |
其他资源
要进一步探索，请考虑以下宝贵的资源：
以上是不同 Java 集合框架操作的 Big-O 时间复杂度是多少？的详细内容。更多信息请关注PHP中文网其他相关文章！
