Java集合对比

ArrayListLinkedListVectorStackHashMapLinkedHashMapHashTableTreeMap实现接口 List List Deque List List Map Map Map NavigableMap 父类 AbstractList AbstractList AbstractList Vector AbstractMap HashMap Dictionary AbstractMap 底层数据结构动态数组双向链表动态数组动态数组动态数组+链表+红黑树动态数组+链表+红黑树+双向链表动态数组+链表红黑树元素是否可重复可重复可重复可重复可重复

key不能重复

value可重复

key不能重复

value可重复

key不能重复

value可重复

key不能重复

value可重复

是否允许存null允许允许允许允许key value都可以key value都可以

key不能为null

value不能为null

key不能为null

value可以为null

是否有序有序(插入顺序)有序(插入顺序)有序(插入顺序)有序(插入顺序)无序

有序(按照插入顺序或者访问顺序)

访问顺序：访问某个元素，就将元素移到双向链表尾端

无序有序(key的自然排序或者自定义比较器排序)扩容机制

默认初始容量10

原数组容量的1.5倍

不需要预先分配空间

默认初始容量10

默认扩容为原来的两倍

指定增长容量，则是原长度+增长容量

和Vector一样

默认初始容量是16

默认比例因子是0.75

扩容为原来的2倍

数组扩容和HashMap一样

默认容量是11

默认比例因子是0.75

扩容为原来的2倍+1

不需要预先分配空间

扩容时机

原数组满了没有原数组满了原数组满了

元素个数达到阈值(容量*比例因子)，扩容为原来的2倍

链表长度到达8：数组长度没到64，扩容数组

数组长度大于64，转红黑树

红黑树个数<6，转成链表

和HashMap一样，扩容不影响双向链表(元素顺序)元素个数达到阈值，扩容到原来的2倍+1没有查询

索引位查找：O(1)

指定元素查找：

O(n)

索引位查找：

头尾O(1)

其他O(n)

元素查找：

头部O(1)

其他O(n)

索引位查找：O(1)

指定元素查找：

O(n)

与Vector一样

根据key计算索引位定位:

索引位只有一个元素：O(1)

是链表O(1)+O(n)

是红黑树O(1)+O(logn)

和HashMap一样

根据key计算索引位定位:

索引位只有一个元素：O(1)

是链表O(1)+O(n)

O(logn)添加

尾部O(1)

其他部位O(n)：添加后要后移索引位之后的元素

头尾添加：O(1)

中间位置：O(n)

尾部O(1)

其他部位O(n)

与Vector一样

根据key计算索引位定位:

索引位没有值 O(1)

是链表:O(1)+O(n)

红黑树：按照其逻辑添加O(1)+O(logn)

和HashMap一样

双向链表添加：O(1)    (可以获取到节点的前后节点)

根据key计算索引位定位:

索引位没有值 O(1)

是链表O(1)+O(n)

O(logn)删除

尾部O(1)

其他部位O(n)：删除后要前移index索引位之后的元素

头尾添加：O(1)

中间位置：

1.根据元素删除：O(n)

2.根据节点删除：O(1) (节点中有前后指针，获取到对应节点修改其指针)

尾部O(1)

其他部位O(n

与Vector一样

根据key计算索引位定位:

索引位只有一个元素(不用移位)：O(1)

是链表：遍历链表找到元素删除O(1)+O(n)

是红黑树：根据逻辑查找到元素删除O(1)+O(logn)

和HashMap一样

双向链表删除：O(1)    (可以获取到节点的前后节点)

根据key计算索引位定位:

索引位只有一个元素(不用移位)：O(1)

是链表：遍历链表找到元素删除O(1)+O(n)

O(logn)是否线程安全否否是是否否是否