全网最好的Java集合总结

1.List （有序、可重复）

1.1 ArrayList

底层是一个Object[]，在不指定容量的时候，会进行懒加载，创建一个{}对象，然后在add的时候创建一个容量为10的Object[],当数组容量不够的时候会扩容，每次扩容为原来的1.5倍。

1.2 Vector

相当于一个 sync版本的ArrayList

1.3 LinkedList

LinkedList内部就是一个双向链表，非常适合数据动态的插入和删除，但是随机访问和遍历速度很慢。

为什么内部类node是静态的？如果普通内部类会持有外部类的引用，可能会造成内存泄漏（也就是说外部类不用了但是回收不了）
LinkedList不但能够做一个普通list，同时还能做队列，栈。队列的入队出队方法为 **offer、poll方法，**栈的入栈和出栈方法为 push、pop方法

## 2. Set （唯一） Set注重独一无二的性质，该体系集合用于存储无序，**值不相同的元素。**对象相等性本质就是hashcode值。

2.1 HashSet

HashSet底层就是一个HashMap，就是在HashMap的基础上利用key不能相等，然后分hash桶，然后链化，只是entry中的value就是写死的一个Object 常量对象

1个对象来了，首先判断hashcode值是不是一样的，如果一样，再判断equals是不是一样，如果都一样，HashSet就认为这是一个对象
如果hashcode值一样，但是equal返回false，那就链化，把它放到链表上去

2.3 TreeSet

TreeSet使用二叉树的原理完成排序过程。

Integer和String对象都可以进行默认的TreeSet排序，但是自定义类对象是不可以的，自定义的类必须实现Comparable接口，并重写compareTo函数。

2.4 LinkedHashSet

搞懂LinkedHashMap就行

3. Map

3.1 HashMap

1.7 的HashMap
- 数组+链表
- 链表插入为头插法（为什么使用头插法？考虑到热点数据的原因，最近插入的元素可能最近会被使用到）
- 先扩容然后再添加元素，（先判断是否需要扩容->数量达到阈值并且发生hash冲突，如果需要扩容就扩容，再添加元素）size >= threshold && null != table[bucketIndex]

1.7 put方法的流程
1. 通过key计算一个hashCode，然后定位到哪个桶（hash算法：位运算，寻址算法：取模）
2. 把put进来key、value封装成一个entry对象，判断下标位置是否为空，如果为空，直接插入，如果不为空，把entry插入到链表中
3. 在插入链表的时候，判断链表是否存在相同的key（equals），如果存在，则更新，如果不存在，就插入
4. 使用头插法，也就是说每次插入到头节点上
1.7 扩容
- 扩容条件：达到阈值并且发生hash冲突（比如说大小为16，负载为0.75，阈值就是12，map中已经有12个元素，然后再加入一个元素的时候发生冲突了，就需要扩容了）
- 扩容过程：根据每个元素的hashCode值结合新数组的长度，重新计算下表来达到分散的作用
1.7 多线程出现的问题
- jdk7存在多线程做put操作的时候导致rehash动作，可能导致循环链表的产生，然后再来一个线程get，就死循环了
- jdk8存在put到相同槽位但是没有追加到链表尾部，而是直接覆盖的问题
1.8 的HashMap
- 新增了红黑树，使用数组+链表+红黑树
- 链表插入为尾插法
- 先添加元素然后扩容（先添加元素进去，然后判断是否需要扩容-> 数量超过了阈值）

1.8 put方法的流程
1. 通过key计算一个hashCode，然后定位到哪个桶（jdk8对于hash算法和寻址算法是如何优化？hash算法优化：hashcode32位，右移16位，然后高16位和低16位做异或运算，寻址优化：原来是取模，现在改成hash&(n-1), 效果和取模是一样的，但是性能更高）
2. 把put进来key、value封装成一个entry对象，判断下标位置是否为空，如果为空，直接插入，如果不为空，把entry插入到链表中
3. 在插入链表的时候，判断链表是否存在相同的key（equals），如果存在，则更新，如果不存在，就插入
4. jdk7的时候，使用的是头插法，jdk8的时候，使用的尾插法
5. 如果是jdk8，会遍历链表，如果链表的个数大于8个，则会把链表转为红黑树，并且把元素插入到红黑树中
链表转红黑树条件
- 链表的个数 >8个
- 同时也会去判断数组长度是不是 > 64，为什么？ 因为在解决hash冲突的时候，既可以使用链化，也可以使用扩容，如果长度还不是很长的时候，优先扩容。
1.8 扩容流程
1. 新申请2倍的一个数组长度，然后开始把链表或者红黑树开始转移
2. jdk7简单的遍历链表上的每一个元素，**然后根据每个元素的hashcode值然后结合新数组的长度 **重新计算一个新的下标来达到分散的作用
3. jdk8因为红黑树的存在，在转移的时候，会考虑到红黑树元素由于分散之后，是不是要回到链表的状态，所以会用一个双向链表来记录红黑树上面的元素，遍历双向链表，得到2个子链，一个是在原位置，一个在新位置（原位置+ 扩容长度，比如原来位置是2，从16->32，那新位置就是18），长度>8转成红黑树放到对应位置，<8把链表放到对应位置
1.8 多线程安全