Java集合概述（上）

Java集合框架：

List、Map、Queue、Set的区别：

• List（对付顺序的好帮手）：存储的元素是有序的，可重复的
• Map（key-value，适用于用key来搜索）：使用键值对（key-value存储），key是无序的、不可重复的，value是无序的、可重复的，每个键最多映射到一个值
• Queue（实现了排队的效果）：按照不确定的方式来确定先后顺序，存储的数据是有序的、可重复的
• Set（有独一无二的性质）：存储的元素是无序的、不可重复的

Collection接口下的集合：

List：

1. ArrayList：Object[]数组，是List的主要实现类，适用于频繁的查找工作，线程不安全
2. Vector：Object[]数组，是List的古老实现类，线程安全
3. LinkedList：双向链表（JDK1.7以后取消了循环）

ArrayList和LinkedList都是不同步的，也就是不保证线程安全
ArrayList:采用数组存储，所以插入和删除元素的时间会受数据的位置影响
LinkedList:采用链表存储，所以插入元素或者删除元素不会受数据的位置影响
LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象的方法
内存空间占用:ArrayList的空间浪费主要体现在在list列表的结尾会预留一部分空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）

Map：

HashMap：在JDK1.8以前是由数组+链表组成的，数组是HashMap的主体，链表是主要为了解决哈希冲突而存在的（拉链发解决哈希冲突）JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间

LinkedHashMap：它继承自HashMap，所以它的底层仍然是基于链式散列结构（由数组和链表或红黑树组成）。另外，在HashMap的基础上增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时对链表进行相应的操作，实现了访问顺序相关逻辑

HashTable：数组+链表组成，数组是HashTable的主体，链表是为了解决哈希冲突

TreeMap：红黑树（自平衡的排序二叉树）

Set：

HashSet（无序、唯一）：基于HashMap实现的，底层是采用HashMap来保存元素

LinkedHashSet：是HashSet的子类，并且其内部是通过LinkedHashMap来实现的

TreeSet（有序、唯一）：红黑树

comparable和Comparator的区别：

comparable接口实际上是出自java.lang包，他有一个compareTo(Object obj)方法用来排序

Comparator接口实际上是出自java.util包，他有一个compare(Object obj1 , Object obj2)方法用来排序

无序性和不可重复性：

无序性并不是指随机的，而是指存储的数据在底层数组中并非是按照数组索引的顺序添加，而是根据数据的哈希值决定的

不可重复性是指添加的元素按照equals()判断时，返回false，需要同时重写equals()方法和hashCode()方法

HashSet、LinkedHashSet和TreeSet三者的异同：

三者都是Set接口的实现类，都能保证元素唯一，但是都不是线程安全的

三者主要区别在于底层的数据结构不同，HashSet底层数据结构是哈希表（基于HashMap），LinkedHashSet底层数据结构是基于链表和哈希表的，元素的插入和取出顺序满足FIFO，TreeSet底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序

底层的数据结构不同决定了应用场景不同：HashSet用于不需要保证元素插入和取出顺序的场景，LinkedHashSet适用于保证元素插入和取出顺序是FIFO的场景，TreeSet适用于支持对元素自定义排序规则的场景

Queue：

Queue是单端队列，只能从一端插入数据，另一端删除元素，实现上一般遵循先进先出原则（FIFO）；

Queue扩展了Collection接口，根据因为容量问题而导致操作失败后处理方式不同分为两类方法：一种在失败时候会抛出异常，另一种则是返回特殊值

Queue接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

Deque是双端队列，在队列的两端均可以插入和删除元素

Deque扩展了Queue的接口，增加了在队首和队尾进行插入和删除方法，同样根据失败后处理方式不同分为两类：

Deque接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询队首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

另外，Deque还有pop和push等其它方法，可用于模拟栈

ArrayDeque 与 LinkedList 的区别：

都实现了Deque接口，都具有队列的功能

ArrayDeque是基于可变长的数组和双指针来实现的，而LinkedList是基于链表实现的

ArrayDeque不支持存储null数据，而LinkedList支持

ArrayDeque插入时可能存在扩容过程，不过均摊后的插入操作仍然为O(1)。虽然LinkedList不需要扩容，但是每次插入新数据都要申请新的堆空间，均摊性能较慢

从性能的角度来看ArrayDeque要更好，当然它还可以用来实现栈

PriorityQueue：

在JDK1.5时被引入的，它和Queue的区别在于元素出队顺序是有优先级决定的，即总是优先级最高的先出队

PriorityQueue利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据

PriorityQueue通过堆元素的上浮和下沉，实现了在O(logn)的时间复杂度内插入元素和删除堆顶元素

PriorityQueue是非线程安全的，不支持null和non-comparable的对象

PriorityQueue默认是小顶堆，但可以接收一个Comparator作为构造参数，用来自定义元素优先级的先后