JAVA集合框架
Java 集合概览
Java 集合，也叫作容器，主要是由两大接口派生而来：一个是 Collection接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。对于Collection 接口，下面又有三个主要的子接口：List、Set 、 Queue。
Java 集合框架如下图所示：
说说 List, Set, Queue, Map 四者的区别？
List(对付顺序的好帮手): 存储的元素是有序的、可重复的。Set(注重独一无二的性质): 存储的元素不可重复的。Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，”x” 代表 key，”y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值
集合框架底层数据结构总结
List
ArrayList：Object[]数组。Vector：Object[]数组。LinkedList：双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)。
Set
HashSet(无序，唯一): 基于HashMap实现的，底层采用HashMap来保存元素。LinkedHashSet:LinkedHashSet是HashSet的子类，并且其内部是通过LinkedHashMap来实现的。TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)。
Queue
PriorityQueue:Object[]数组来实现小顶堆。DelayQueue:PriorityQueue。ArrayDeque: 可扩容动态双向数组。
Map
HashMap：JDK1.8 之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。LinkedHashMap：LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。Hashtable：数组+链表组成的，数组是Hashtable的主体，链表则是主要为了解决哈希冲突而存在的。TreeMap：红黑树（自平衡的排序二叉树）。
Iterator迭代器
集合框架中Iterator迭代器 集合框架中所有的类都实现了这个接口
Java迭代器（Iterator）是 Java 集合框架中的一种机制，是一种用于遍历集合（如列表、集合和映射等）的接口。
它提供了一种统一的方式来访问集合中的元素，而不需要了解底层集合的具体实现细节。
Java Iterator（迭代器）不是一个集合，它是一种用于访问集合的方法，可用于迭代 ArrayList 和 HashSet 等集合。
Iterator 是 Java 迭代器最简单的实现，ListIterator 是 Collection API 中的接口， 它扩展了 Iterator 接口。
Collection接口
Collection派生出了三个子接口
List
List代表了有序可重复集合，可直接根据元素的索引来访问
- 集合中的元素允许重复
- 集合中的元素是有顺序的，各元素插入的顺序就是各元素的顺序
- 集合中的元素可以通过索引来访问或者设置
List接口下有三个实现类
ArrayList
ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
ArrayList 继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
扩容机制
以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。
- 当我们要
add进第 1 个元素到ArrayList时，elementData.length为 0 （因为还是一个空的 list），因为执行了ensureCapacityInternal()方法 ，所以minCapacity此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入grow(minCapacity)方法。 - 当
add第 2 个元素时，minCapacity为 2，此时elementData.length(容量)在添加第一个元素后扩容成10了。此时，minCapacity - elementData.length > 0不成立，所以不会进入 （执行）grow(minCapacity)方法。 - 添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。
直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.
LinkedList
Vector
底层由object[]数组实现,具有线程安全
ArrayList 与 LinkedList 区别?
Set
Set代表无序不可重复集合，只能根据元素本身来访问
Queue
Queue是队列集合
