集合

Collection

​ Collection一般存储的是列表数据

List

​ List存储的数据是有序可重复的

ArrayList

​ ArrayList数组存储，可以动态扩容，适合大量查找，线程不安全

// 使用ArrayList进行插入和删除操作时，因为采用数组存储，所以如果执行插入操作时，会默认将元素插入到数组的末尾，这时候时间复杂度为O(1),如果插入到中间位置，时间复杂度就为O(n-1),因为要插入到中间，需要将当前位置和后续的元素向后移一位。
// 支持高效的元素随机访问，可以通过元素的序号快速获取元素对象
// 内存空间浪费主要体现在list列表的结尾会预留一定的容量空间

ArrayList扩容机制：

JDK8之前直接创建长度为10的数组elementData，EMPTY_ELEMENTDATA=10是默认值；

JDK8之后只有当add时才初始容量值

ArrayList底层有三种构造器

​ 当创建ArrayList数组时，没有定义初始值，这时候系统给ArrayList赋初始值为10

​ 定义初始值，会进行判断，如果大于0，直接使用定义的初始值，如果等于0，系统赋值默认初始值10，如果小于0，报错

​ 当定义了一个集合对象时，这时候构造器会先将集合转为数组，然后判断数组长度，如果为0，则赋初始值10，如果不为0，判断集合类型是否和ArrayList相同，如果相同直接将该集合赋值给ArrayList，如果不相同，将该集合的长度和元素赋值给ArrayList

ArrayList扩容

​ 当进行新增操作时，判断数组是否需要扩容，就是判断数组需要的容量和当前的容量进行判断，如果大于当前容量，则需要扩容进入grow()方法，首先将数组扩容1.5倍，然后判断数组所需的容量是否小于新扩容的容量，如果大于新扩容的容量，则将新容量赋为数组所需的容量。然后进行判断新长度是否大于最大容量（MAX_ARRAY_SIZE）（Integer.MAX_VALUE-8），如果大于最大容量，则新容量为Integer.MAX_VALUE

LinkedList

​ LinkedList链表存储（双向链表，jdk7之前循环，之后取消了循环链表），适合增、删、改，线程不安全

// 使用LinkedList进行插入和删除操作时，因为采用链表存储，所以头插尾插都不受元素位置影响，时间复杂度为O(1),如果要在指定位置插入元素的话，时间复杂度为O(n),因为需要先将元素移动到指定位置再进行插入。
// 不支持高效的元素随机访问
// 内存空间的花费主要体现在创建存放每一个节点的元素的空间都比ArrayList消耗的空间更多

我们再项目中一般都不会去使用LinkedList，需要用到LinkedList的场景都可以用ArrayList来代替。

Vector

​ Vector数组存储，是List的古老实现类，线程安全

Set

​ Set存储的数据是无序的，也就是存储数据的底层数组并非按照数组索引的位置进行添加，而是根据数据的哈希值决定的；不可重复的，就是说添加元素时，需要同时重写equals()和hashCode()方法

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

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

HashSet

​ 底层数据结构是哈希表，基于HashMap实现的，底层采用HashMap来保存元素

TreeSet

​ 底层是红黑树（自我平衡排序的二叉树），元素是有序的，排序的方式有自然排序和定制排序

LinkedHashSet

​ 底层数据结构是链表+哈希表，内部也是基于HashMap实现的，但是有一点不一样，有链表将Set变得有序，元素插入和取出满足FIFO

Queue// 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。`PriorityQueue`: `Object[]` 数组来实现二叉堆`ArrayQueue`: `Object[]` 数组 + 双指针

Map

​ 底层是键值对存储，key是无序不可重复的，value是无序可以重复的，

HashMap

​ JDK8之前是由数组+链表组成，数组是主体，链表主要是解决哈希冲突而存在的（”拉链法“解决冲突）

​ JDK8之后在解决哈希冲突有了较大的变化，当链表长度大于阈值（默认8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间，Hashtable没有这样的机制

// HashMap是非线程安全的，但是效率高
// 可以存储null的key和value，但是null作为键只能有一个
// 默认初始值大小为16，之后每次扩容容量都会变为原来的两倍
// 如果给定了初始值大小，HashMap会将其扩容为2的的幂次方大小（HashMap 中的tableSizeFor()方法保证）

HashMap底层创建原理：

JDK8之前底层是数组+链表，HashMap通过key的hashcode经过扰动函数处理过后得到hash值，然后通过(n-1)&hash判断当前元素存放的位置(n指数组长度)，如果当前位置存在元素，则判断该元素与要存入的元素 hash值以及key是否相同，如果相同的话直接覆盖，如果不相同就通过“拉链法”解决冲突。

JDK 8 的 hash 方法 相比于 JDK 7 hash 方法更加简化，但是原理不变。

拉链法：将数组和链表结合，创建一个链表数组，数组中每一个就是一个链表，若遇到哈希冲突，则将冲突的值加到链表中即可，JDK8之后在解决哈希冲突有了较大的变化，当链表长度大于阈值（默认8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

ConcurrentHashMap

Hashtable

​ 数组+链表组成，数组是Hashtable的主体，链表是主要解决哈希冲突存在的

// Hashtable是线程安全的，因为Hashtable内部的方法都经过synchrnized修饰，基本已经不使用了
// 不可以存储null的key和value，否则会抛空指针异常
// 创建时如果不指定初始值，默认初始大小为11，之后每次扩容，容量都会变为原来的2n+1
// 如果给定了初始值大小，Hashtable会直接使用

LinkedHashMap

​ 继承自HashMap，底层仍然是数组和链表或红黑树组成。

TreeMap

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

相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。