Java集合

集合

Collection

List

ArrayList

（数组）

LinkedList

（链表）

Vector

（数组实现、线程同步）

Set

HashSet

（Hash 表）(底层由HashMap实现)

TreeSet

（二叉树）

底层红黑树，支持自定义排序规则

LinkedHashSet

（HashSet+LinkedHashMap）

Queue

（单端队列，满足FIFO）

Deque

LinkedList

(基于链表)

基于链表，支持存储Null，1.2存在，每次申请堆空间

ArrayDeque

(基于数组)

基于可变长数组和双指针，不支持存储NULL，1.6引入，可能扩容，实现队列更好好

PriorityQueue

（基于堆）

优先级最高的元素先出队，利用了二叉堆，时间复杂度logn，不支持存储 NULL 和 non-comparable 的对象，默认是小顶堆，可接收 Comparator 定义元素优先级的先后

Map

HashMap

（数组+链表+红黑树)

（可以存储 null 的 k和 v，容量初始16，2n，指定大小将其扩充为 2 的幂次方大小）使用 Collections.synchronizedMap() 方法来包装我们的 HashMap，底层数据结构是数组+链表/红黑树，负载因子0.75，超过size*0.75就扩容，只有大小为2次幂时，才能合理用位运算替代取模（高效），数组>64&&链表>8,链表变红黑树，红黑树<6，红黑树变链表，取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，

TreeMap

（可排序）

红黑树，可排序，通过Comparator排序，对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力

LinkedHashMap

（记录插入顺序）

底层数据结构是数组+链表/红黑树+双向链表，插入有序

HashTable

（安全）

方法基本都经过synchronized 修饰，被淘汰，不允许有 null 键和 null 值，容量初始11，2n+1，使用 synchronized 来保证线程安全，效率非常低下

Collections

排序

reverse(List list)//反转

sort(List list)//按自然排序的升序排序

sort(List list, Comparator c)//定制排序

查找替换

fill(List list, Object obj)//用指定的元素代替指定list中的所有元素

replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

同步控制

synchronizedXxx()