集合

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会直接使用