共计 3186 个字符，预计需要花费 8 分钟才能阅读完成。
前言
Tip：该笔记为 B 站面试解说视频 的配套文档， B 站搜寻”编程鹿“能够看到面试题解说视频
视频地址如下：奥利给 编程人—2020 年 Java 大厂面试题集锦（面试必备 继续更新）
https://www.bilibili.com/video/BV15i4y1L7Bt
什么是数组
数组（Array）是一种线性表数据结构。它用一组间断的内存空间，来存储一组具备雷同类型的数据。
特点：
- 线性表 物理内存上间断还是逻辑上间断的数据结构都称之为线性表
- 间断的内存空间和雷同类型的数据
长处：
- 依照下标拜访快「随机拜访」（间接拜访 任意拜访）
如果：每个元素占据长度 为 3，第一个元素开始地址编号为 10
那么只有晓得下标 就能够疾速计算出来运算的地址
第三个元素地位为：10+2*3 =16
毛病：
- 数据插入 须要扩容和移动元素
- 删除元素 也须要移动元素
什么是链表
链表通过指针将一组零散的内存块串联在一起的线性数据结构，把内存块称为链表的“结点 ”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还须要记录链上的下一个结点的地址，记录下个结点地址的指针叫作 后继指针 next。
如下图所示：
特点：
- 线性表 通过“指针”将一组 零散的内存块 串联
长处：
- 增删快 不须要元素搬移
毛病：
- 查问慢 须要通过前结点 获取后结点的地址
其余链表：
- 循环链表
- 双向链表 插入 删除更加高效 查问能够双向遍历
ArrayList 和 LinkedList 的区别
数据结构实现
- ArrayList 是数组的数据结构实现
- LinkedList 是双向链表的数据结构实现。
拜访效率
- ArrayList 比 LinkedList 在下标拜访的时候效率要高
- LinkedList 是线性的数据存储形式, 所以须要挪动指针从前往后顺次查找。
减少和删除效率
- 在非首尾的减少和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其余数据的下标。.
综合来说，在须要频繁读取汇合中的元素时，更举荐应用 ArrayList，而在插入和删除操作较多时，更举荐应用 LinkedList。
ArrayList 初始化长度多少
ArrayList 底层是数组，ArrayList 初始长度为 10
- 1.8 之前 ArrayList 初始长度为 10
-
1.8 之后
- 通过无参构造方法第一次创立汇合的时候不会创立底层长度为 10 的数组
- 在第一次增加的元素的时候 创立底层数组 长度为 10
ArrayList 如何增加元素
依照下标增加，每次增加都会判断汇合的容量
- 第一次增加 会创立长度为 10 的底层数组
- 后续增加 如果容量有余 会扩容
ArrayList 如何扩容
什么时候产生扩容：
- 每次增加的时候 会查看要不要扩容 执行 ensureCapacityInternal 确保外部容量
- ensureCapacityInternal 会判断数组长度够不够 不够就扩容
扩容流程：
- 判断数组长度够不够增加新元素
-
不够就触发扩容 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 倍
- 扩容须要赋值数据
创立汇合的时候如果可能预估长度，最好指定汇合大小
ArrayList 和 Vector 的区别
ArrayList 线程不平安
Vector 线程平安 Vector 简直所有的办法都加了锁
除了 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 数组 + 链表
1.8 数组 + 链表 + 红黑树
如果链表的长度大于 8 链表就会解决为树结构
HashMap 默认初始化大小是多少？
默认初始值 16
HashMap 的主要参数都有哪些？
默认初始值（数组的长度）：16
负载因子：0.75
扩容的条件：当底层数组 四分之三 的地位有了元素 就扩容
HashMap 是怎么解决 hash 碰撞的？
hash 碰撞，两个 key 计算的后果都是同一个下标
- 链表
- 链表 + 树
HashMap 新的 Entry 节点在插入链表的时候，是怎么插入的
Entry
- 在 JDK8 之前是头插法，新的值会取代原有的值，原有的值会被推到链表上
-
在 JDK8 之后是尾插法
- 头插法可能呈现循环链表的问题
- 应用头插 会扭转链表的上的程序，然而如果 应用尾插，在扩容时会放弃链表元素本来的程序，就不会呈现链表成环的问题了。
- Java7 在多线程操作 HashMap 时可能引起死循环，起因是扩容转移后前后链表程序倒置，在转移过程中批改了原来链表中节点的援用关系。
HashMap 的扩容机制？
-
什么时候扩容？（risize）
HashMap 的底层是数组，数组的容量无限，达到肯定的数量就会进行扩容。
影响扩容机会的因素有两个：
- Capacity：HashMap 以后长度
- LoadFactor：负载因子，默认值 0.75f
什么意思呢？当数组中 75%的地位满了的时候，就会进行扩容。想要晚的触发扩容就只能调高负载因子。
-
怎么扩容？
扩容分为两步
- 扩容：创立一个新的 Entry 空数组，长度是原数组的 2 倍
- ReHash：遍历原 Entry 数组，把所有的 Entry 从新 Hash 到新数组
进行从新 Hash 的起因：Hash 的计算和数组的长度无关（对长度位运算）HashCode（Key）&（Length – 1）。所以长度扭转了，所有的元素复制到新数组中须要从新计算地位
HashMap 线程平安吗？
不是
有哪些线程平安的 Map
Hashtable
ConcurrentHashMap
ConcurrentHashMap 基本原理
1.7 分段锁
1.8 CAS 无锁算法（乐观锁）
加不加锁为条件进行分类
- 乐观锁 的确加锁了 一个线程操作的时候会持有锁对象 其余线程须要等到拿到锁对象的时候能力操作元素
- 乐观锁 算法管制 逻辑锁
原子性 Integer AtomicInteger 实现原子性的自增
HashSet
HashSet 底层是 HashMap 只应用 HashMap 的 key 不应用 value
Queue
Queue —》线程池
「❤️ 帅气的你又来看了我」
如果你感觉这篇内容对你挺有有帮忙的话：
- 点赞反对下吧，让更多的人也能看到这篇内容（珍藏不点赞，都是耍流氓 -_-）
- 欢送在留言区与我分享你的想法，也欢送你在留言区记录你的思考过程。
