Java 集合时间复杂度
2023-04-18 16:58:02 时间
List
ArrayList
get() 直接读取下标,复杂度 O(1) add(E) 直接在队尾添加,复杂度 O(1) add(index, E) 在第n个元素后插入,n后面的元素需要向后移动,复杂度 O(n) remove() 删除元素后面的元素需要逐个前移,复杂度 O(n)
LinkedList
addFirst() 添加队列头部,复杂度 O(1) removeFirst() 删除队列头部,复杂度 O(1) addLast() 添加队列尾部,复杂度 O(1) removeLast() 删除队列尾部,复杂度 O(1) getFirst() 获取队列头部,复杂度 O(1) getLast() 获取队列尾部,复杂度 O(1) get() 获取第n个元素,依次遍历,复杂度O(n) add(E) 添加到队列尾部,复杂度O(1) add(index, E) 添加到第n个元素后,需要先查找到第n个元素,复杂度O(n) remove() 删除元素,修改前后元素节点指针,复杂度O(1)
Set
HashSet
add() 复杂度为 O(1) remove() 复杂度为 O(1) contains() 复杂度为 O(1)
TreeSet(基于红黑树)
add() 复杂度为 O(log (n)) remove() 复杂度为 O(log (n)) contains() 复杂度为 O(log (n))
map
TreeMap(基于红黑树)
平均时间复杂度 O(log n)
HashMap
正常时间复杂度 O(1)~O(n) 红黑树后 O(log n)
LinkedHashMap
能以时间复杂度 O(1) 查找元素,又能够保证key的有序性
相关文章
- Jease 2.6发布 Java开源内容框架
- JVM调优总结:反思
- JVM调优总结:调优方法
- JVM调优总结:新一代的垃圾回收算法
- JVM调优总结:典型配置举例
- JVM调优总结:分代垃圾回收详述
- JVM调优总结:垃圾回收面临的问题
- JVM调优总结:基本垃圾回收算法
- JVM调优总结:一些概念
- 用Java GUI编写的画板程序
- Java的动态绑定机制
- jOOQ 2.0.2发布 Java的ORM框架
- Java中带复选框的树的实现和应用
- Java网络编程菜鸟进阶:TCP和套接字入门
- 甲骨文与谷歌专利权之争定于今年三月开审
- Java调用C/C++编写的第三方dll动态链接库
- 集成开发环境 NetBeans IDE 7.1正式版发布
- kangle 2.7.5紧急发布 防hash碰撞攻击
- 东方通技术引领模式为国产软件“争权”
- UML中关联,组合与聚合等关系的辨析