ArrayList

image.png
image.png
本质还是数组，默认容量是10

主要的核心在于扩容
image.png
image.png
数组的扩容无非就是新建一个数组，然后进行拷贝。如果考虑性能的话平时尽量不要让这个容器进行频繁拷贝，提前分配好容量。

Vector

image.png
官方已经不推荐使用了，没使用过

实现原理跟ArrayList差不多，差别主要是不是线程安全的
image.png

Queue和Deque


队列的几个接口区别**
image.png

LinkedList

image.png
image.png
不需要扩容，就是正常的链表操作

image.png
这里继承了队列的功能
image.png
image.png
队列的功能主要通过联调的头结点和尾结点来实现

image.png
image.png
这里可以看下遍历remove可能会遇到的问题，所以都是用Iteator来遍历操作链表

HashMap

image.png

image.png
节点结构

image.png
image.png
这个的原理没看懂

hash函数
image.png
这个hash的选择更多是数学经验，只要足够离散就好，可以参考《hash的原理》

数据结构
image.png
hash冲突使用链表法，链表长度超过8则会转换成红黑树
image.png
虽然红黑树的引入自然在查询上有性能上的提升，那为什么是8呢？经验值？
image.png
hash冲突是会发生，但链表超过8的概率这么低，这种优化如果不是真的有洁癖或者闲的发慌我是不做的….

同样loadFactor为什么是0.75更多也是数学统计上的经验值（泊松分布？）
image.png

put的流程
image.png

image.png

扩容过程
image.png

数组位置的扩容举例
image.png

HashTable

没有用过，不推荐使用
image.png
image.png
这里还继承了字典类
总体和JDK 7的HashMap实现方式差距不大
image.png
这里用了sychronized进行同步，如果追求性能使用_ConcurrentHashMap会更好，锁粒度上有所差距，但是在并发竞争不激烈的情况下应该差距应该不大，毕竟_sychronized在JDK 8中已经经过了优化。

TreeMap

用的比较少，暂时不管
解读1 解读2

LinkedHashMap

image.png
LinkedHashMap 在 HashMap 的基础上增加了顺序：分别为「插入顺序」和「访问顺序」。即遍历 LinkedHashMap 时，可以保持与插入顺序一致的顺序；或者与访问顺序一致的顺序。则意味着可以使用它来做类似缓存的工作。

image.png

节点结构上继承了HashMap的Node,增加了before和after来形成链表

image.png

put流程

image.png
直接使用父类HashMap的put方法，然后重写了newNode、afterNodeAccess、afterNodeInsertion等方法
image.pngimage.png
有序就是在这里实现的
image.png

image.png
image.png
这里就是很明显的淘汰策略了，但方法是空的，这样我们可以使用这个方法来自定义淘汰策略

image.png
这个在get的时候进行了顺序调整？有点奇葩啊

实现一个LRU
image.png

PriorityQueue

image.png

image.png

image.png
image.png
image.png
image.png
image.png
image.png就是两个反向操作
image.png
堆化是有集合初始化进行的，可以看到是从中间位置开始