集合在我们日常开发和学习中十分常见,最近整理了一下集合,包括常见的map,list,set,queue

集合分为两种类型,一种是collection接口下的包含 List（有序可重复）、Set（无序不可重复）、Queue（队列操作）,一种是Map这种键值对类型的,键唯一、值可重复

目录

 一、Map

1.HashMap

2.LinkedHashMap

3.TreeMap

4.WeakHashMap,EnumMap,IdentityHashMap

二、List

1.ArrayList

2.LinkedList

3.CopyOnWriteArrayList

三、Set

1.HashSet,LinkedHashSet,TreeSet

四、Queue

1.双端队列（Deque）

2.优先级队列（PriorityQueue）

五、总结

 一、Map

Map 的特点是根据键快速查找值

1.HashMap

首先由常见的HashMap切入,直接实现的Map接口

底层结构:HashMap是基于一种类似数组加链表(红黑树)的哈希桶的结构,key允许存 1 个 null,value可以为null,初始化容量16,必须是2的幂次,为了扩容时计算下标更高效,用hash & (容量-1) 比 hash % 容量操作效率更高,当元素个数到容量*负载因子(默认0.75)时,翻倍扩容,写值通过哈希映射key插入对应的哈希桶内,插入时是没有顺序的,如果有哈希冲突的话,会用一个链表连接后续的数据,链表长度小于等于8时用链表,当容量>=64且链表长度大于8就优化成红黑树

时间复杂度:读写效率都是O(1)的(不过如果哈希冲突的话就需要一个个遍历链表导致需要O(n)的时间,如果优化成红黑树则是O(logn))

线程安全:不是线程安全的,如果需要线程安全可以使用ConcurrentHashMap(cas+synchronized细粒度锁)或HashTable(不推荐,锁整个方法,锁粒度太大导致效率太低)

2.LinkedHashMap

由于HashMap没有顺序,所以有一个LinkedHashMap继承于HashMap,就是在HashMap基础上加一个双向链表,用于记录插入或者访问的顺序(accessOrder=false（默认）是插入顺序，accessOrder=true访问顺序),用该数据结构可以实现LRU最近最少使用算法

3.TreeMap

TreeMap底层是红黑树,也就是读写时间复杂度都是O(logn)的

实现SortedMap接口和NavigableMap接口

Integer、String类型的键通过Comparable接口进行排序

实现自定义排序：创建 TreeMap 时传入Comparator比较器，按自定义规则排序；

4.WeakHashMap,EnumMap,IdentityHashMap

WeakHashMap键为弱引用，GC 自动清理无强引用的键,使用轻量级缓存,EnumMap键为枚举类型，底层数组实现,IdentityHashMap用==判断键相等,只要引用地址一样就行

二、List

List 的特点是有序（按插入顺序 / 索引排序）和 可重复

1.ArrayList

底层是动态数组,读效率O (1),写除数组尾部数据O (n)（需移动元素）

初始化默认无长度,第一次加元素默认10,扩容到1.5倍,扩容是new一个扩容后大小的新数组,然后把旧数组拷贝过去

2.LinkedList

底层双向链表,读效率O (n),写操作本身O (1)但是由于需要遍历找到元素还是O(n),除非在队首尾写元素

3.CopyOnWriteArrayList

底层动态数组,读效率O(1),写O (n)（复制数组）,适合高并发读、低并发写

三、Set

Set 的特点是不可重复，底层都依赖 Map 实现,用元素做 key，value 为虚拟占位符 PRESENT(PRESENT 是个空对象,底层 HashMap 的 Value 若为 null，会在元素不存在时也返回null,就分不清是不是真的存在了）

1.HashSet,LinkedHashSet,TreeSet

HashSet底层套壳HashMap,键允许一个为 null,LinkedHashSet底层LinkedHashMap去重,TreeSet底层TreeMap加个去重,键不允许为 null，依赖 Comparable/Comparator 实现排序

四、Queue

Queue  分为普通队列（FIFO）、双端队列（Deque）、优先级队列（PriorityQueue）

1.双端队列（Deque）

Deque继承Queue接口，兼容Queue的核心方法：offer(队尾添加)、add(队尾添加，满则抛异常)、poll(队首删除)、remove(队首删除，空则抛异常)、peek(查询队首)

不过他因为是双端队列所以有addFirst,addLast这样的方法

两种实现类一种ArrayDeque基于数组,一种LinkedList基于双向链表

2.优先级队列（PriorityQueue）

底层结构：基于堆（完全二叉树）实现，非 FIFO，队首永远是优先级最高的元素；

排序规则:跟TreeMap相同

五、总结

一类是 Collection 接口下的：专门存 “单个元素”，包括 3 种：

        List：有序、可重复；

        Set：无序、不可重复；

        Queue：按规则排队；

另一类是 Map 接口下的：专门存 “键值对”（key-value），比如存用户 ID 和用户名，key 不能重复，value 可以重复，核心就是通过 key 快速找到 value（像查字典，通过拼音找汉字）。