java数据结构总结
一、ArrayList
Arraylist是list接口的实现类，它是支持根据需要而动态增长的数组。java中标准数组是定长的，但有时需要动态程序中获取数组长度，arraylist就是为此而生。
扩容机制
ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去
- 开始检查当前插入位置时数组容量是否足够ArrayList 是否未初始化，未初始化是则初始化 ArrayList ，容量给 10.
- 判断当前要插入的下标是否大于容量不大于，插入新增元素，新增流程完毕。
- 如果所需的容量大于当前容量，开始扩充。扩容规则是当前容量 + 当前容量右移 1 位。也就是 1.5 倍。 int newCapacity = oldCapacity + (oldCapacity >> 1);
- 如果扩充之后还是小于需要的最小容量，则把所需最小容量作为容量。
- 如果容量大于默认最大容量，则使用 最大值 Integer 作为容量。
- 拷贝老数组元素到扩充后的新数组插入新增元素，新增流程完毕。
存储区间连续、内存占用严重、空间复杂度大
优点：随机读取和修改效率高，原因是数组是连续的（随机访问性强，查找速度快）
缺点：插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中都要往后移动。
LinkedList
LinkedList 的底层就是一个链表线性结构，链表除了要有一个节点对象外，根据单向链表和双向链表的不同，还有一个或者两个指针。 LinkedList属于双向链表。
扩容机制
创建一个新的节点，新节点的 prev 设置现有的末尾节点，现有的末尾 Node 指向新节点 Node，新节点的 next 设为 null 即可
链表结构：存储区间离散、占用内存宽松、空间复杂度小
优点：插入删除速度快，内存利用率高，没有固定大小，扩展灵活
缺点：不能随机查找，每次都是从第一个开始遍历（查询效率低）
HashMap
结合数组结构和链表结构的优点，从而实现了查询和修改效率高，插入和删除效率也高的一种数据结构
底层实现
HashMap类中的元素是Node类，翻译过来就是节点，是定义在HashMap中的一个内部类，实现了Map.Entry接口。
Node类的基本属性有：
hash：key的哈希值
key：节点的key，类型和定义HashMap时的key相同
value：节点的value，类型和定义HashMap时的value相同
next：该节点的下一节点
由Node节点组成链表之后，HashMap定义了一个Node数组：
transient Node<K,V>[] table;
这个数组记录了每个链表的第一个节点，于是最终形成了HashMap下面这样的数据结构：
image.png
扩容机制：
集合的扩容机制，一般是发生在数据存入的过程中，故直接看put方法
- 通过hash(Object key)算法得到hash值；
static final int hash(Object key) {
int h;
//如果key为空，说明hashMap的key可为空
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 根据存入元素的key计算hash值，计算方法为
如果key为空，hash=0,否则对key进行hashCode运算，同时取hashCode值的高16位进行异或运算得到hash值，目的是使hash值更散列，减少hash碰撞。
- 判断table是否为null或者长度为0，如果是执行resize()进行扩容；
- 如果是首次添加数据，则Node[]数组为空，会进行第一次扩容操作，设置默认初始容量为1 << 4=16，初始阈值为16*0.75=12，并创建一个新的长度为16的Node数组
- 通过hash值以及table数组长度得到插入的数组索引i，判断数组table[i]是否为空或为null；
- 计算数组下标=(15&hash)是否存在元素，如果不存在，则将hash,key,value,null组成的Node对象存入该下标位置，
- 如果table[i] == null，直接新建节点添加，转向 8），如果table[i]不为空，转向 5）；
- 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，这里的相同指的是hashCode以及equals，否则转向 6）；
- 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转7）；
- 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
- 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
- 当该数组中存入的元素长度达到阈值时，也即12位时，又会发生扩容，
- 先判断原数组长度是否大于等于能够分配的长度上限-2的30次方，如果达到，则不再扩容，并将阈值设置为Integer.MAX_VALUE，2的31次方-1，否则将原数组扩容至新容量为原数组额两倍，阈值也扩大至原来阈值的两倍
- 元素转移到新数组的下标计算方式为 通过元素的hash值与新数组容量-1,目的也是为了使数据更加的散列，与运算的逻辑是必须同时为1才等于1，这样就减少了hash碰撞的概率
举个例子，如果新容量为32，则其二进制为100000，如果用该二进制去进行与运算时，基本上都为0，hash碰撞的概率很大，但是一旦减1后变为31，其二进制变为11111，进行与运算时变为0或1的概率都比较均匀，发生hash碰撞的概率就会小很多，这也同时解释了为什么扩容的容量要是2的倍数，就是为了这一步减1做准备的，否则就没有必要减1了。如果原数组元素的next指针不为空，则会判断是否为红黑树结构或者为链表结构
get方法
- 通过传入的key通过hash()算法得到hash值
- 在通过(n - 1) & hash找到数组下标，如果数组下标所对应的node值正好key一样就返回，否则找到node.next找到下一个节点，看是否是treenNode，如果是，遍历红黑树找到对应node，如果不是遍历链表找到node
https://zhuanlan.zhihu.com/p/113332649
https://blog.csdn.net/qq_40871196/article/details/101855801
https://blog.csdn.net/hefenglian/article/details/79763634
LinkedHashMap
HashMap和双向链表合二为一即是LinkedHashMap。
HashMap是无序的，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。
LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap 和 保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。
HashMap和双向链表的密切配合和分工合作造就了LinkedHashMap。
image.png
next用于维护HashMap各个桶中的Entry链，before、after用于维护LinkedHashMap的双向链表，虽然它们的作用对象都是Entry，但是各自分离，是两码事儿。
LinkedHashMap 与 LRU(Least recently used，最近最少使用)算法
LinkedHashMap区别于HashMap最大的一个不同点是，前者是有序的，而后者是无序的。为此，LinkedHashMap增加了两个属性用于保证顺序，分别是双向链表头结点header和标志位accessOrder。我们知道，header是LinkedHashMap所维护的双向链表的头结点，而accessOrder用于决定具体的迭代顺序
参考链接：https://blog.csdn.net/justloveyou_/article/details/71713781
