一、HashMap集合

1.HashMap的头插法和尾插法

image.png
只有元素添加的时候，才会出现链表元素的插入，
首先JDK1.7的HashMap当出现Hash碰撞的时候，最后插入的元素会放在前面，这个称为 “头插法”

JDK 1.7 采用头插法来添加链表元素，存在链表成环的问题，
1.8 中做了优化，采用尾插法来添加链表元素
在扩容时，头插法会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题，而尾插法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题


2.HashMap的底层结构（1.7和1.8）

JDK1.7中HashMap的底层是由数组+单向链表这两种数据结构组合而成的
JDK1.8中HashMap是由数组+单向链表+红黑树三种数据结构组合而成的。


3.HashMap的扩容原理

数组初始16，

数组可以增大，16>32>64，2的幂次方进行扩容，
每个节点对应的hash都会先对数组数量进行取余，
首先当数组长度大于64，链表长度大于8，链表转为红黑树，不大于64，对数组进行扩容。
链表和红黑树转换，低于6转化为链表，高于8转换红黑树，


4.Concurrent(啃踹儿)HashMap实现安全的原理（1.7和1.8）

通过ReentrantLock(为俺锤特 唠嗑)+CAS+分段思想来保证的并发安全的，
ConcurrentHashMap的put方法会通过CAS的方式，把一个Segment(塞哥门特)对象存到Segment数组中，一个Segment内部存在一个HashEntry数组，相当于分段的HashMap，Segment继承了ReentrantLock，每段put开始会加锁。
image.png

5.Hash碰撞是什么，Hash碰撞严重会有什么问题

在HashMap的查询和添加过程中，绕不过去的是计算元素在数组的位置index，key的HashCode作为这个计算的基础。计算后的Hash值存在相同的情况，hash与长度取余的结果也有相同的情况，这个时候运算结果相同的两个对象就需要存储到同一个链表中，这就是HashMap中的Hash碰撞。

这样会引起什么问题呢，碰撞严重的话，大量的元素都存储在一个链表中，检索过程中的第三步，遍历链表会耗费大量的时间，严重极端情况下会遍历所有元素，检索效率会很低。和HashMap快速检索的设计严重不符。

5.1 hash碰撞严重回来带查询效率问题，那么HashMap做了什么优化，来避免Hash碰撞呢

HashMap减轻Hash碰撞主要做了两个方面的优化，

1）提高hash的复杂度，减少相同hash的出现

很简单，将key的HashCode右移16位将高16位和 低16位做异或运算，目的是让hash值得低16位也 包含高16位的特性。
这样做有什么好处呢，元素在数组的下标index =hash%数组长度n，当数组长度很短的时候，如初始状态下是16，如果两个key的HashCode低16位相同，不处理的话index计算结果相同。只要HashCode不同的话，计算后的hash低16位保证不会相同。增强了hash结果的复杂度。

2）让元素尽量均匀的分部到数组中

保证&运算中二进制数每一位都是1，也就是数组的长度保证是2的整数次幂，就不会出现分不到元素的情况了

二、ArrayList集合


5.ArrayList的扩容原理

ArrayList是采取延迟分配对象数组大小空间的，当第一次添加元素时才会分配10个对象空间，当添加第11个元素的时候，会扩容1.5倍，当添加到16个元素的时候扩容为15*1.5=22，以此类推。 ArrayList每次扩容都是通过Arrays.copyof (elementData, newCapacity)来实现的。