Java集合类常用方法时间复杂度

---

ArrayList常用方法时间复杂度

ArrayList底层数据结构是： 数组

增加

add(E)：尾部添加，时间复杂度 O(1)
add(index, E)： 指定位置添加，时间复杂度 O(N) ;指定位置添加后，需要将指定位置后面的全部元素向后移动一个位置

删除

remove(E) ：删除指定元素，需要先遍历找到指定元素，因此时间复杂度是 O(N)
remove(index)：删除指定位置元素，删除后需要将指定位置后面的元素全部向前移动一个位置，时间复杂度 O(N)

查询

get(index)：查询指定位置元素， O(1)

改

set(index, E)：修改指定位置元素， O(1)

contains()方法

需要遍历数据去判断是否存在指定元素，所以是 O(N)

HashMap常用方法时间复杂度

HashMap底层数据结构是： 数组+链表+红黑树
增删查改时间复杂度均为 O(1)
containsKey()方法时间复杂度是 O(1)
containsValue()方法时间复杂度是 O(N)

TreeMap常用方法时间复杂度

TreeMap底层数据结构是： 红黑树
增删查改时间复杂度均为 O(logN)
containsKey()时间复杂度 O(logN)
containsValue()时间复杂度 O(N) ，因为value是无序的，所以要依次遍历

LinkedHashMap常用方法时间复杂度

LinkedHashMap底层数据结构是： HashMap+双向链表
增删查改时间复杂度均为 O(1)
containsKey()时间复杂度是 O(1)
containsValue()时间复杂度是 O(N)

HashSet常用方法时间复杂度

HashSet底层数据结构是基于 HashMap 来实现的
因此增删查改时间复杂度均为 O(1)
contains()方法时间复杂度 O(1)

TreeSet常用方法时间复杂度

TreeSet底层数据结构是基于 TreeMap 来实现的
增删查改时间复杂度均为 O(logN)
contains()时间复杂度 O(logN)

---

原文链接：https://www.cnblogs.com/skylv/p/13528143.html

---