集合基础知识

Java中的容器

Java集合也叫做容器，由两个接口组成，一个是Collection，主要存放单一元素，另一个是Map，主要存放的是键值对。

collection接口

主要由三个接口组成，分别为 List,Set,Queue
1.List
特点 ： 储存的元素是有序的，可重复的
2.Set
特点： 储存元素是无序的，不可重复的
3.Queue
特点： 元素先进先出，储存是有序的，可重复的

List

List主要由ArrayList，LinkdeList，Vector构成
1）ArrayList
ArrayList的底层数据结构是数组，默认初始大小是10，每次扩容为原来的1.5倍，ArrayList的查询速率高，增删操作效率低，因为涉及增删操作时要移动或者复制数组。线程不安全。
2）LinkedList
LinkedList底层是双向链表，1.6之前是循环链表，LinkedList的增删操作效率高，因为只需要改变指针的指向即可。线程不安全。
3）Vector
底层与ArrayList一样是数组，其他的基本也一致，不同的是Vector是线程安全的，且扩容时Vector会按传入的扩容值进行扩容或者按照默认的原数组2倍进行扩容。

Set

set主要由HashSet,LinkedHashSet,TreeSet构成
1）HashSet底层是由HashMap实现的，所以特点什么的基本和HashMap一致。
2）LinkedHashMap底层是由LinkedHashMap实现的，所以特点什么的基本和LinkedHashMap一致。
3）TreeSet底层是由TreeMap实现的，所以特点什么的基本和TreeMap一致。

Queue

Queue主要由PriorityQueue和ArrayDeque构成
先说一下Queue和deque的区别，Queue是单端队列只能从一端进，另一端出，而Deque是双端队列，两端都可以进出。
Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

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

1）PriorityQueue
PriorityQueue是由数组实现的二叉堆，默认数组大小为11，扩容是如果数组长度小于64会扩容为原来的2倍+1，否则扩容为原来的1.5倍，通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素，是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象， 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。
2）ArrayDeque
ArrayDeque是由数组 + 双指针构成的，默认的初始容量为16，当传入参数小于数组长度直接为8，扩容是会扩容为原来的2倍，ArrayDeque插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)，不支持存储 NULL 数据，但 LinkedList 支持。

Map接口

主要由四个部分组成，分别为HashMap，HashTable，TreeMap，LinkedHashMap

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

HashTable特点： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。

TreeMap特点： 红黑树。

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

HashMap

HashMap底层数据结构时数据加链表或者红黑树，1.8之前是数组加链表。默认的初始容量是16，负载因子是0.75，扩容时会扩容为原来的原来的2倍。1.8的HashMap采用的时尾插法进行插入数据的，但是再1.8之前采用的时头插法，头插法在多线程对数组进行扩容时会出现死循环的问题。HashMap的key值可以是null，但是只能有一个,HashMap线程是不安全的。

HashTable

HashTable 是由数组+链表组成的，默认的初始大小是11，负载因子也是0.75，扩容时会扩容为原来数组大小的2倍+1。

TreeMap

TreeMap底层数据结构是红黑树，与HashMap不同的是TreeMap中元素是有序的，会按照元素的大小进行排序。

LinkedHashMap

LinkedHashMap与HashMap一致，只是加了一个前后指针来维护插入或者查找的顺序。