、
这一节先快速回顾所学集合知识（抓要点，不深追底层代码），下一节复习集合的八股文
狠狠学java，猛猛赚他一笔！
一集合体系图
集合分为单列集合和双列集合，先来看集合体系图
二单列集合
2.1List之三种遍历方式
iterator迭代器遍历（idea快捷键itit）
List list = new ArrayList();
Iterator iterator = r.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
}增强for循环（idea快捷键I）
ArrayList r = new ArrayList();
for (Object o :r) {
System.out.println(o);
}注意：增强for循环的底层就是通过迭代器实现
普通for循环
ArrayList r = new ArrayList();
for(int i=0;i<r.size();i++){
System.out.println(r.get(i));
}2.2ArrayList（基本等同Vector）
ArrayList的特点：底层是数组（连续的内存空间），元素有序，可重复（可以放多个null值），支持索引，线程不安全(无synchronized），不适用多线程
ArrayList的扩容机制：
有参构造器eg：ArrayList List = new ArrayList（100），按照参数的1.5倍扩容
无参构造器：第一次初始化时，容量=10，之后按照1.5倍扩容
源码：
初始化默认容量
private static final int DEFAULT_CAPACITY = 10;扩容机制：1+0.5 >>向右位移 除以2
int newCapacity = oldCapacity + (oldCapacity >> 1);使用ArrayList.copyOf()扩容
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));2.3Vector（对象数组）
Vector特点：元素有序，可重复，支持索引，可以放多个null值，线程安全(synchronized），适用多线程
Vector扩容机制：两倍扩容
(capacityIncrement > 0) false
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);无参构造器默认初始化容量为10
//无参构造器
public Vector() {
this(10);
}2.4LinkedList（双向链表+双端队列）
LinkedList特点：底层是双向链表（不连续的内存空间），元素有序，可重复，支持索引，可以放多个null值，线程不安全(无synchronized），不适用多线程
public LinkedList() {
}
有first指针指向头结点，last直接指向尾结点，每个节点有pre前驱和next后继结点
2.5List集合选择
基本逻辑：首先考虑线程安全性
数组是连续内存空间，便于查询，
链表中包含指针操作，便于增删
2.6HashSet（底层HashMap）
这里先说说Set接口统一特点：
1）无序，添加与取出的顺序不一致，没有索引，不能保证元素一致性
2）不允许重复元素，最多一个null值
3）遍历方式:迭代器，增强for，不能根据索引遍历（无get（index）方法）
4）取出顺序的相对位置固定
//HashSet中数据占据hashMap的键位置，其值位置全部用PRESENT替代，注意：static final ，只会初始化一次，所用的值均是同一个PRESENT
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}HashSet(HashMap)扩容机制：
table表中每增加一个元素到table中，就算是增加1个（无论是加到表的空位置还是挂到链表上）当达到临界值：容量*加载因子，进行双倍扩容：容量*2
//默认初始化容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//扩容加载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;2.7LinkedHashSet（数组加双向链表）
1）LinkedHashSet是HashSet的子类
2）底层是LinkedHashMap，底层维护了一个数组＋双向链表
3）LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，使得元素看起来是有序的
2.8TreeSet（底层TreeMap）
public TreeSet() {
this(new TreeMap<>());
}
1)使用无参构造器，创建TreeSet时，仍是无序的
2）可排序，可以在构造器中自己定义一个Comparator
TreeSet treeSet = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((String)o1).compareTo(((String)o2);
}
});三双列集合
先说说map的特点：
key-value，键值对，key和value可以是任何引用类型的数据
map中的key不能重复（原因同hashSet，与添加规则有关），value可重复
如果添加相同的key，而值不同，则会覆盖原来的key-val（覆盖）
3.1HashMap（HashSet的底层）
hashMap三种（六大）遍历方式：
1）键找值（keySet）
2）值集合（values）
3）键值对（EntrySet）
HashMap hashMap = new HashMap();
hashMap.put("1","1");
hashMap.put("2","2");
hashMap.put("3","3");
hashMap.put("4","4");
Set set = hashMap.keySet();//键找值
for (Object o :set) {
System.out.println(hashMap.get(o));
}
// Iterator iterator = set.iterator();也可以迭代器，略
Collection values = hashMap.values();//值集合
for (Object o :values) {
System.out.println(o);
}
// Iterator iterator = values.iterator();
Set entries = hashMap.entrySet();//键值对
for (Object o :entries) {
Map.Entry entry = (Map.Entry) o;
System.out.println(entry.getKey()+" "+entry.getValue());
}HashMap底层：数组+链表+红黑树
hashMap添加元素机制：先通过hash算法求得该元素的哈希值，进行转换得到该元素在数组的索引值，
判断该索引位置有无元素，无则直接添加
有：则进行equals（程序员可重写，定义比较规则）比较，若equals也相同，就放弃添加，不相同则添加到最后（若是链表则会循环对每一个数据进行equals比较）
树化：
在java8中，如果一条链表的元素 >= TREEIFY_THRESHOLD=8 &&
table表的大小 >= MIN_TREEIFY-CAPACITY(64)就会进行树化（红黑树）
3.2Hashtable
hashTable的特点：
1）键和值都不能为空，否则会空指针异常
2）使用方法同hashMap
3）hashtable线程安全，synchronized
public Hashtable() {
this((initialCapacity)11, (loaderFactor)0.75f);
}int newCapacity = (oldCapacity << 1) + 1;
扩容机制：达到临界值时，乘2＋1
3.3TreeMap
public TreeMap() {
comparator = null;
}四集合选型规则（一张表）
先判断存储类型，再看是否可重复，或要求有序
