集合底层

说一下List Set Queue Map的异同

List 有序的 可重复的

Set 不可重复的

Queue 队列 先进先出 有序可重复

Map key value key是无序 不可重复的 value 无序 可重复

ArrayList与LinkedList异同

ArrayList底层是Object数组 LinkedList是一个双向链表

前者支持随机访问 后者不支持

ArrayList是否线程安全? 如何确保

第一个采用vector几何

第二个采用CopyOnWriteArrayList

第三个就是Collections.synchronizedList

CopyOnWriteArrayList 了解多少？

CopyOnWriteArrayList是Java并发包里提供的并发类，简单来说它就是一个线程安全且读操作无锁的ArrayList。正如其名字一样，在写操作时会复制一份新的List，在新的List上完成写操作，然后再将原引用指向新的List。这样就保证了写操作的线程安全。

CopyOnWriteArrayList允许线程并发访问读操作，这个时候是没有加锁限制的，性能较高。而写操作的时候，则首先将容器复制一份，然后在新的副本上执行写操作，这个时候写操作是上锁的。结束之后再将原容器的引用指向新容器。注意，在上锁执行写操作的过程中，如果有需要读操作，会作用在原容器上。因此上锁的写操作不会影响到并发访问的读操作。

• 优点：读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。在遍历传统的List时，若中途有别的线程对其进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的List容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了。

• 缺点：一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC。二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

ArrayList的扩容机制

ArrayList 是懒加载 第一次new 如果不指定长度 默认为0

当我们第一次添加的时候 他会扩容为10

然后第 二次 第三次 不会扩容 等到第11次 他会扩容1.5 如果扩完容比我们需要的容量还是小 我们就把需要的容量作为我们新的容量

List如何进行安全删除

1. 倒叙删除

2. Stream filter collect

3. iterator

List

ArrayList

ArrayList扩容

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

Map

HashMap

HashMap的实现原理

HashMap底层有了数组加链表或者红黑树

当链表大于8而且数组大于64转化为红黑树

红黑树节点<6退回链表

变化

jdk1.8 的 HashMap 主要有五点优化：

1. 数据结构：数组 + 链表改成了数组 + 链表或红黑树原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)

2. 链表插入方式：链表的插入方式从头插法改成了尾插法简单说就是插入时，如果数组位置上已经有元素，1.7 将新元素放到数组中，原始节点作为新节点的后继节点，1.8 遍历链表，将元素放置到链表的最后。原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。

3. 扩容 rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。原因：提高扩容的效率，更快地扩容。

4. 扩容时机：在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

5. 散列函数：1.7 做了四次移位和四次异或，jdk1.8 只做一次。原因：做 4 次的话，边际效用也不大，改为一次，提升效率。

Hashmap put流程

1. 判断数组是否为空，为空进行初始化;

2. 不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;

3. 查看 table[index] 是否存在数据，没有数据就构造一个 Node 节点存放在 table[index] 中；

4. 存在数据，说明发生了 hash 冲突(存在二个节点 key 的 hash 值一样), 继续判断 key 是否相等，相等，用新的 value 替换原数据(onlyIfAbsent 为 false)；

5. 如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；

6. 如果不是树型节点，创建普通 Node 加入链表中；判断链表长度是否大于 8， 大于的话链表转换为红黑树；

7. 插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍

HashMap hash冲突的解决方案

1. 链地址法

2. 再哈希法

3. 建立公共溢出区

4. 开放定址法

为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。

不用红黑树，用二叉查找树可以么?

可以。但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的 O(n)时间复杂度。

HashMap 中 key 的存储索引是怎么计算的？

取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标

1.7 和1.8的区别

1. 数组 + 链表 -> 数组+链表+红黑树

2. 头插法->尾插法

3. 在插入时，1.7 先判断是否需要扩容，再插入，1.8 先进行插入，插入完成再判断是否需要扩容；

ConcurrentHashMap

1.7

ConcurrentHashmap 线程安全在 jdk1.7 版本是基于分段锁实现，在 jdk1.8 是基于CAS+synchronized实现

从结构上说，1.7 版本的 ConcurrentHashMap 采用分段锁机制，里面包含一个 Segment 数组，Segment 继承于 ReentrantLock，Segment 则包含 HashEntry 的数组，HashEntry 本身就是一个链表的结构，具有保存 key、value 的能力能指向下一个节点的指针。

实际上就是相当于每个 Segment 都是一个 HashMap，默认的 Segment 长度是 16，也就是支持 16 个线程的并发写，Segment 之间相互不会受到影响。

put流程

整个流程和 HashMap 非常类似，只不过是先定位到具体的 Segment，然后通过 ReentrantLock 去操作而已，后面的流程，就和 HashMap 基本上是一样的。

1. 计算 hash，定位到 segment，segment 如果是空就先初始化

2. 使用 ReentrantLock 加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功

3. 遍历 HashEntry，就是和 HashMap 一样，数组中 key 和 hash 一样就直接替换，不存在就再插入链表，链表同样操作

get 流程

get 也很简单，key 通过 hash 定位到 segment，再遍历链表定位到具体的元素

上，需要注意的是 value 是 volatile 的，所以 get 是不需要加锁的。

1.8 CAS+synchronized

1. 首先计算 hash，遍历 node 数组，如果 node 是空的话，就通过 CAS+自旋的方式初始化

2. 如果当前数组位置是空则直接通过 CAS 自旋写入数据

3. 如果 hash==MOVED，说明需要扩容，执行扩容

4. 如果都不满足，就使用 synchronized 写入数据，写入数据同样判断链表、红黑树，链表写入和 HashMap 的方式一样，key hash 一样就覆盖，反之就尾插法，链表长度超过 8 就转换成红黑树

Set