1.集合：collection 接口
①数组：（方便查询）
特点：1） 内存地址连续，使用之前必须要指定数组长度
2） 可以通过下标的方式访问成员 ，查询效率高
3） 增删操作会给系统带来性能消耗。（需要新创建一个数组，把原来数据复制到新
的数组里面）【保证数组越界问题，需要动态扩容】。
②链表：（方便增删）
单向链表 和 双向链表
双向链表：
特点：
1）灵活的空间要求，存储空间不要求联系。
2）不支持下标访问，支持顺序遍历检索
3）针对增删效率高，只和操作节点的前后节点有关系。无需移动元素。
场景应用：
LinkedList
private static class Node{
E item; //节点元素
Node next;//下一个节点
Node prev;// 上一个节点
}
③树：（平衡二叉树）
特点：
某节点的左子树节点值仍包含小于该节点的值
某节点的右子树节点值仍包含大于该节点的值
左右子树每个也必须是二叉树找数
顺序排列
红黑树RBT：（不平衡二叉树）hashmap、 treeMap：
自平衡二叉树，【不是绝对】平衡
特点：
①每个节点要么红色要么黑色
②根节点必须是黑色
③每个叶子节点必须是黑色
④每个红色节点的两个子节点必须是黑色
⑤任意节点到每个叶子节点的路径包含相同数量的黑节点
黑平衡的二叉树
1.recolor 重新标记颜色
2.rotation 旋转 树达到平衡的关键 （左旋，右旋）
集合介绍：
collection 接口
数组[......]
List：LinkedList , ArrayList ,vector
ArrayList:
Add(): 默认长度为10的数组，动态扩容1.5倍
Get(): 检查下标，根据指针查值。
Set():
remove():
modCount: FailFast 机制，快速失败的机制，java集合类为了应对并发访问在集合迭代过程中，内部结构发生变化的一种防护措施，这种错误检查的机制为这种可能发生错误通过抛出 java.util.ConcurrentModificationException.
ModCount的修改次数 发生变化，和迭代之前的值不相等了，导致的抛出异常
//todo
避免fail-fast
了解了fail-fast机制的产生原理，接下来就看看如何解决fail-fast
方法1
在单线程的遍历过程中，如果要进行remove操作，可以调用迭代器的remove方法而不是集合类的remove方法。看看ArrayList中迭代器的remove方法的源码：
可以看到，该remove方法并不会修改modCount的值，并且不会对后面的遍历造成影响，因为该方法remove不能指定元素，只能remove当前遍历过的那个元素，所以调用该方法并不会发生fail-fast现象。该方法有局限性。
eg:
public static void main(String[] args) {
List list = new ArrayList<>();
for (int i = 0 ; i < 10 ; i++ ) {
list.add(i + "");
}
Iterator iterator = list.iterator();
int i = 0 ;
while(iterator.hasNext()) {
if (i == 3) {
iterator.remove(); //迭代器的remove()方法
}
System.out.println(iterator.next());
i ++;
}
}
方法2
使用java并发包(java.util.concurrent)中的类来代替 ArrayList 和hashMap。
比如使用CopyOnWriterArrayList代替 ArrayList， CopyOnWriterArrayList在是使用上跟 ArrayList几乎一样， CopyOnWriter是写时复制的容器(COW)，在读写时是线程安全的。该容器在对add和remove等操作时，并不是在原数组上进行修改，而是将原数组拷贝一份，在新数组上进行修改，待完成后，才将指向旧数组的引用指向新数组，所以对于 CopyOnWriterArrayList在迭代过程并不会发生fail-fast现象。但 CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。
对于HashMap，可以使用ConcurrentHashMap， ConcurrentHashMap采用了锁机制，是线程安全的。在迭代方面，ConcurrentHashMap使用了一种不同的迭代方式。在这种迭代方式中，当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException，取而代之的是在改变时new新的数据从而不影响原有的数据 ，iterator完成后再将头指针替换为新的数据 ，这样iterator线程可以使用原来老的数据，而写线程也可以并发的完成改变。即迭代不会发生fail-fast，但不保证获取的是最新的数据。
LinkedList：
LinkedList是通过双向链表去实现的，他的数据结构具有双向链表的优缺点，· 既然是双向链表，那么他的顺序访问的效率非常高，随机访问效率比较低，它包含一个非常重要的私有内部静态类：Node
push():
add():
get():
set():
Vector():不推荐使用，线程安全的
响，慢慢会被放弃
//需要实现线程安全，推荐使用该方法
collections工具类，synchronized方法
Set: 无重复有序
hashSet ：底层是hashMap，存的Kay，value是new Object().
实现set接口，有hash表支持，他不保证set的迭代顺序，特别是 他不保证该
顺序永久不变，允许为空
TreeSet：底层是TreeMap，存的Kay，value是new Object().
Map 接口
KV对:TreeMap,HashMap,WeakHashMap
Map集合的特点：
①能够存储唯一列的数据（唯一，不可重复）set
②能够存储可以重复的数据（可重复） list
③值的顺序取决于键的顺序
④键和值都能存储null
TreeMap：本质上就是红黑树的实现
①每个节点要么红色要么黑色
②根节点必须是黑色
③每个叶子节点必须是黑色
④每个红色节点的两个子节点必须是黑色
⑤任意节点到每个叶子节点的路径包含相同数量的黑节点
HashMap：底层结构
jdk1.7 及以前 是采用数组+链表
jdk1.8之后采用数组+链表 或者数组+红黑树的方式进行元素的存储
存储在hashMap 集合中的元素都将是一个map.Entry 的内部接口的实现
HashMap:
public v put(K key , V value){
return putVal(hash(K),key,value,false,true);
}
put():
hash(K):获取key的哈希值
Iterator 迭代
工具类：
Collections
Arrays
比较器：
Comparable
Comparator
