「实实在在面试」—List和Map集合面试合集【含讲解视频】
「实实在在面试」—List和Map集合面试合集【含讲解视频】
什么是数组
image-20200716114132581
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
特点：
- 线性表 物理内存上连续还是逻辑上连续的数据结构都称之为线性表
- 连续的内存空间和相同类型的数据
优点：
- 按照下标访问快「随机访问」（直接访问 任意访问） 假如：每个元素占据长度 为 3，第一个元素开始地址编号为 10 那么只要知道下标 就可以快速计算出来运算的地址 第三个元素位置为：10+2*3 =16
缺点：
- 数据插入 需要扩容和挪动元素
- 删除元素 也需要挪动元素
什么是链表
链表通过指针将一组零散的内存块串联在一起的线性数据结构，把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，记录下个结点地址的指针叫作后继指针 next。
如下图所示：
image-20200716143134994
特点：
- 线性表 通过“指针”将一组零散的内存块串联
优点：
- 增删快 不需要元素搬移
缺点：
- 查询慢 需要通过前结点 获取后结点的地址
其他链表：
- 循环链表
image-20200716173146870
- 双向链表 插入 删除更加高效 查询可以双向遍历
image-20200716173502165
ArrayList 和 LinkedList 的区别
数据结构实现
- ArrayList 是数组的数据结构实现
- LinkedList 是双向链表的数据结构实现。
访问效率
- ArrayList 比LinkedList 在下标访问的时候效率要高
- LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。
增加和删除效率
- 在非首尾的增加和删除操作，LinkedList 要比ArrayList效率要高，因为ArrayList增删操作要影响数组内的其他数据的下标。.
综合来说，在需要频繁读取集合中的元素时，更推荐使用ArrayList，而在插入和删除操作较多时，更推荐使用LinkedList。
ArrayList 初始化长度多少
ArrayList 底层是数组，ArrayList 初始长度为 10
- 1.8 之前 ArrayList 初始长度为 10
- 1.8 之后
- 通过无参构造方法第一次创建集合的时候不会创建底层长度为10的数组
- 在第一次添加的元素的时候 创建底层数组 长度为10
image-20200717170610239
ArrayList 如何添加元素
按照下标添加，每次添加都会判断集合的容量
- 第一次添加 会创建长度为10的底层数组
- 后续添加 如果容量不足 会扩容
ArrayList 如何扩容
什么时候发生扩容：
- 每次添加的时候 会检查要不要扩容 执行ensureCapacityInternal 确保内部容量
image-20200717171043520
- ensureCapacityInternal 会判断数组长度够不够 不够就扩容
扩容流程：
判断数组长度够不够添加新元素
image-20200717171743560
不够就触发扩容 grow方法
//真正的扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新的容量是在原有的容量基础上+50% 右移一位就是二分之一
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新容量小于最小容量，按照最小容量进行扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//这里是重点 调用工具类Arrays的copyOf扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 扩容 1.5 倍
创建集合的时候如果能够预估长度，最好指定集合大小
image-20200717155506620
ArrayList 和 Vector 的区别
ArrayList 线程不安全
Vector 线程安全 Vector几乎所有的方法都加了锁
1598926062661
除了 Vector 还有什么线程安全的List
CopyOnWriteArrayList 读不加锁写加锁
复制写：复制一个新数组 将元素添加新数组中
public boolean add(E e) {
创建锁对象
final ReentrantLock lock = this.lock;
加锁
lock.lock();
try {
获取现有数组
Object[] elements = getArray();
获取现有数组长度
int len = elements.length;
根据现有数组得到一个长度+1的新数组 【复制】
Object[] newElements = Arrays.copyOf(elements, len + 1);
将要添加的元素 写入新数组中
newElements[len] = e;
用新数组替换老数组
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
HashMap的底层结构
1.7 数组+链表
1598943151710
1.8 数组+链表+红黑树
如果链表的长度大于8 链表就会处理为树结构
1598943495683
HashMap 默认初始化大小是多少？
默认初始值 16
1598943720885
HashMap的主要参数都有哪些？
默认初始值（数组的长度）：16
1598943739052
负载因子：0.75
1598943762994
扩容的条件：当底层数组 四分之三 的位置有了元素 就扩容
HashMap是怎么处理hash碰撞的？
hash碰撞，两个key计算的结果都是同一个下标
- 链表
- 链表+树
HashMap 新的Entry节点在插入链表的时候，是怎么插入的
Entry
1598944106163
- 在JDK8之前是头插法，新的值会取代原有的值，原有的值会被推到链表上
- 在JDK8之后是尾插法
- 头插法可能出现循环链表的问题
- 使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
- Java7在多线程操作 HashMap 时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
HashMap的扩容机制？
- 什么时候扩容？（risize）
HashMap的底层是数组，数组的容量有限，到达一定的数量就会进行扩容。
影响扩容时机的因素有两个：
什么意思呢？当数组中75％的位置满了的时候，就会进行扩容。想要晚的触发扩容就只能调高负载因子。
- Capacity：HashMap当前长度
- LoadFactor：负载因子，默认值0.75f
- 怎么扩容？
扩容分为两步
- 扩容：创建一个新的Entry空数组，长度是原数组的2倍
- ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组 进行重新Hash的原因：Hash的计算和数组的长度有关（对长度位运算）HashCode（Key） & （Length - 1）。所以长度改变了，所有的元素复制到新数组中需要重新计算位置
HashMap 线程安全吗？
不是
有哪些线程安全的 Map
Hashtable
1598944691036
ConcurrentHashMap
ConcurrentHashMap 基本原理
1.7 分段锁
1598945352890
1.8 CAS 无锁算法（乐观锁）
加不加锁为条件进行分类
- 悲观锁 确实加锁了 一个线程操作的时候会持有锁对象 其他线程需要等到拿到锁对象的时候才能操作元素
- 乐观锁 算法控制 逻辑锁 原子性 Integer AtomicInteger 实现原子性的自增
HashSet
HashSet 底层是HashMap 只使用HashMap的key 不使用value
Queue
Queue ---》线程池