Java的容器
Java容器类类库的用途是“保存对象”，并将其划分为两个不同的概念。
1、Collection：一个独立元素的序列，这些元素都服从一条或多条规则，List必须按照插入的顺序保存元素，Set不能有重复元素，Queue按照排队规则来确定对象的产生顺序。
2、Map：一组成对的“键值对”对象，允许使用键值来查找值。
- - - - - - - 出自《java变成思想》- - - - - - - -
在java类库中，集合类的基本接口是Collection接口，这个接口有两个基本的方法：add(E element)与Iterator iterator()；通过Collection的源码中，可以看到Collection接口扩展了Iterable接口，所以，对于标准的类库中的任何集合都可以使用foreach循环。
因此在讲到常用的集合时，有必要提一下Iterator(迭代器)：
Iterator：迭代器（也是一种设计模式）是一个对象，它的工作是遍历并选择序列中的对象，而程序员不必要或关心该序列底层的结构·，此外迭代器通常被称为轻量级对象，因为创建它的代价很小。在java中Iterator只能单向移动，这也是for与foreach，因为foreach的底层的实现其实就是使用的迭代器，因此对于for与foreac的区别来讲，其中一个区别就是for循环是可逆的，而foreach循环是不可逆的。Iterator只能用来：
1、使用方法iterator()要求容器返回一个Iterator。Iterator将准备好返回序列的第一个元素。
2、使用next()获得序列中的下一个元素。
3、使用hasNext()检查序列中是否还有元素。
4、使用remove()将迭代器新返回的元素删除。
到这了Iterator就可以结束了，补充一点就是Iterator有一个更加强大的子类ListIterator，它能用于各种List类的访问，尽管Interator只能单向移动，但是ListIterator却是可以双向移动的，这里就不累述了，有兴趣可以去看看ListIterator的源码，自己测试一下。
List：是一个有序、可重复、可为NULL的集合，常用的实现类有ArrayList，LinkedList和Vector，当频繁进行随机访问元素的时候，使用ArrayList更快，如果频繁进行插入和删除的时候LinkedList则更快，而Vector底层通过synchronized修饰，从而实现线程安全的效果，当并发量增多，锁竞争的问题严重，会导致性能下降。这里对三种实现类的方法不在一一介绍。
ArrayList : ArrayList 是基于动态数组实现的非线程安全的集合。当底层数组满的情况下还在继续添加的元素时，ArrayList则会执行扩容机制扩大其数组长度。ArrayList查询速度非常快，因此在实际开发中被广泛使用。唯一不足的是插入和删除元素较慢，同时它并不是线程安全的。我们可以从源码对它常用的方法进行分析：
添加元素：add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}首先通过扩容机制判断原数组是否还有空间，如果没有，则重新实例化一个更大的新数组，把旧数组的数据拷贝到新数组中，然后再新数组的最后添加值。
查询元素：get(int index)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}首先判断下标是否越界，然后通过数组下标返回元素。
中间插入元素：add(int index, E element)
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}首先判断数组下标是否越界，然后根据扩容机制进行扩容，若插入下标为i，则通过复制数组方式将i以后的数组复制，并往后移一位，再将新元素替换下标为i的旧元素。
移除元素：remove(int index)
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}删除数组跟添加数组差不多一样的，只是将数组往前移一位，然后最后一个元素设置为null，等待JVM垃圾回收。
通过上述的方法可以总结：ArrayList快在下标定位，慢在数组复制。
LinkedList：基于双向链表实现的非线程安全的集合，它是一个链表结构，不能像数组一样随机访问，必须是每个元素依次遍历直到找到元素为止。其结构的特殊性导致它查询数据慢。从源码对它常用的方法进行分析：
查询：get(int index)
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}从源码中可以看出，在执行查询操作时，先判断下标是否越界，然后再判断下标是靠近头部还是尾部，如果靠近头部，则从头部查起，如果靠近尾部，则从尾部查起。
中间插入元素：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) //在链表末尾插入
linkLast(element);
else //在链表中间插入
linkBefore(element, node(index));
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}首先判断插入的位置，如果在链表尾部插入，则直接将尾节点的下一个指针指向新节点。如果在中间插入，先判断插入的位置是否为首节点，是则将首节点的上一个指针指向新增节点。否则先获取当前节点的上一个节点（简称A），并将A节点的下一个指针指向新增节点，然后新增节点的下一个指针指向当前节点。
Vector ：数据结构和使用方法与ArrayList差不多。最大的不同就是Vector是线程安全的。在源码可以看出，几乎所有的对数据操作的方法都被synchronized关键字修饰。synchronized是线程同步的，当一个线程已经获得Vector对象的锁时，其他线程必须等待直到该锁被释放。从这里就可以得知Vector的性能要比ArrayList低。如果有多余的时间建议了解一下CopyOnWriteArrayList。
List的总结：ArrayList查询快是因为底层是由数组实现，通过下标定位数据快。写数据慢是因为复制数组耗时。LinkedList底层是双向链表，查询数据依次遍历慢。写数据只需修改指针引用。ArrayList和LinkedList都不是线程安全的，小并发量的情况下可以使用Vector，若并发量很多，且读多写少可以考虑使用CopyOnWriteArrayList。因为CopyOnWriteArrayList底层使用ReentrantLock锁，比使用synchronized关键字的Vector能更好的处理锁竞争的问题。
Set：说完了List接下来撩一下Set，在java中，Set具有与Collection完全一样的接口，实际上Set就是Conllection，只是行为不同，Set和List不同的是，Set内部实现是基于Map的，所以Set取值时不保证数据和存入的时候顺序一致，并且不允许空值，不允许重复值。Set有三个较为常用的实现类，HashSet、TreeSet、LinkedHashSet如果你需要的是一个快速的集合，建议你使用HashSet，如果你需要的是一个排序集合，请选择TreeSet，如果你需要一套能够存储插入顺序的集合,请使用LinkedHashSet。
HashSet：首先看看HashSet，HashSet 底层是数组 + 单链表 + 红黑树的数据结构，HashSet底层实现依赖于HashMap，然后看看HashSet的一些源码：
// HashSet 真实的存储元素结构
private transient HashMap<E,Object> map;
// 作为各个存储在 HashMap 元素的键值对中的 Value
private static final Object PRESENT = new Object();
//空参数构造方法 调用 HashMap 的空构造参数，还有一些带参构造方法，也都实例化HashMap
public HashSet() {
map = new HashMap<>();
}
//添加元素
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//HashMap中的方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
//如果哈希表为空，调用resize()创建一个哈希表，并用变量n记录哈希表长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 如果指定参数hash在表中没有对应的桶，即为没有碰撞
* Hash函数，(n - 1) & hash 计算key将被放置的槽位
* (n - 1) & hash 本质上是hash % n，位运算更快
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//直接将键值对插入到map中即可
tab[i] = newNode(hash, key, value, null);
else {// 桶中已经存在元素
Node<K, V> e;
K k;
// 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 将第一个元素赋值给e，用e来记录
e = p;
// 当前桶中无该键值对，且桶是红黑树结构，按照红黑树结构插入
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
// 当前桶中无该键值对，且桶是链表结构，按照链表结构插入到尾部
else {
for (int binCount = 0; ; ++binCount) {
// 遍历到链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 检查链表长度是否达到阈值，达到将该槽位节点组织形式转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 链表节点的<key, value>与put操作<key, value>相同时，不做重复操作，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 找到或新建一个key和hashCode与插入元素相等的键值对，进行put操作
if (e != null) { // existing mapping for key
// 记录e的value
V oldValue = e.value;
/**
* onlyIfAbsent为false或旧值为null时，允许替换旧值
* 否则无需替换
*/
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 访问后回调
afterNodeAccess(e);
// 返回旧值
return oldValue;
}
}
// 更新结构化修改信息
++modCount;
// 键值对数目超过阈值时，进行rehash
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}从源码中，我们可以看出将一个key-value对放入HashMap中时，首先根据key的hashCode()返回值决定该Entry的存储位置，如果两个key的hash值相同，那么它们的存储位置相同。如果这个两个key的equals比较返回true。那么新添加的Entry的value会覆盖原来的Entry的value，key不会覆盖。且HashSet中add()中 map.put(e, PRESENT)==null 为false，HashSet添加元素失败。因此,如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖原来已有的集合元素。
TreeSet：TreeSet实际上是TreeMap实现的。当我们构造TreeSet时；若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。而且TreeSet是非线程安全的。TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回，TreeSet不支持快速随机遍历，只能通过迭代器进行遍历。
LinkedHashSet：LinkedHashSet是介于HashSet 和 TreeSet之间，内部是一个双向链表结构，LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。
看完了Set和List，是时候了解Map了，先说说Map的特点：1、包含键值对；2、键唯一；3、键对应的值唯一；Map最常用的实现类有HashMap和TreeMap。这里只能推荐一篇写的很好的博文，自问达不到这个高度，所以直接推荐进去参考高手的源码分析：https://blog.csdn.net/wz249863091/article/details/77483948