• 1、讲一下ArrayList 的底层原理
• 2、数组和集合之间如何转换
• 3、ArrayList 和 LinkedList 之间的区别
• 4、说一下 HashMap 的底层实现原理
• 5、讲述一下 HashMap 的 put 方法的具体流程
• 6、讲一讲 HashMap 的扩容机制
• 7、HashMap 的寻址算法和数组长度为什么是2 的 n 次幂
• 8、HashMap 在 1.7 情况下的多线程死循环问题如何解决（了解）

基础概念

集合引⼊

• 概念前提
  • ArrayList的数组默认⻓度10，1.5倍数组扩容，扩容通过开辟新数 组进⾏转移⽼数组元素
  • HashMap、ConcurrentHashMap的数组默认⻓度16，2倍数组扩 容，扩容通过开辟新数组进⾏转移⽼数组元素
• 核⼼思想
  • 读写分离
    • CopyOnWriteArrayList底层实现、处理快速失败
  • 分散热点
    • ConcurrentHashMap底层addCount计算
  • 索引优化
    • HashMap/ConcurrentHashMap 从数组->链表->红⿊树
• 考察重点
  • 集合底层实现以及设计思想
• 注意点
  • 对于存放⼤量元素到ArrayList 或 HashMap中时，建议提前初始化 好容量避免扩容导致性能损耗

快速失败(fast fail)

• 快速失败是Java基于多线程操作同⼀集合的保护机制
• 解决办法
  • 可以使⽤ Colletions.synchronizedList ⽅法处理集合 或 在修改集合 的地⽅⽤ synchronized 进⾏修饰，但是性能较低
  • 使⽤ CopyOnWriteArrayList 代替 List，采⽤读写分离的⽅式，写时 会新拷⻉⼀份数组，对新数组进⾏操作，操作完之后，再将引⽤ 指向新数组

List

ArrayList 和 Array 数组 的的区别。

ArrayList 的底层实现是动态数组，支持自动扩容，支持泛型确保类型安全。

而 Array 数组是固定的容量大小，需要在声明的时候就指定固定数据类型和指定大小，支持基本类型和对象。

ArrayList 和 Vector 的区别。

ArrayList 和 Vector 都是 List 接口下的实现类，但是 ArrayList 是线程不安全的，性能较高；

Vector 是线程安全的，是 List 接口的古老实现，但不建议目前使用（同步操作导致性能问题），如果是并发情况下，建议使用 CopyOnWriteArrayList 等.

另外两者的扩容机制不一样，ArrayList 扩容增长为原来的 1.5 倍，Vector 默认增长为原来的 2 倍。

Vector 和 Stack 的区别。

Vector 是 List 接口的古老实现类，是线程安全的有序集合。

Stack 继承于 Vector ，是一个栈结构（后进先出 LIFO）。它提供了栈结构的一些标准操作方法，实现了栈的基本功能。

但是由于同步操作导致性能问题，不推荐目前使用；栈目前一般是使用 Deque 接口的实现类 ArrayDequeu 替代 Stack 。

ArrayList 是否可以添加 null 值。

ArrayList 是可以添加 null 值的，但是不建议；

尽管 ArryayList 支持添加 null ，并且允许 重复添加，但是在使用的过程中代码可能会抛出空指针异常。

见下👇：

在使用包含null值的ArrayList时要特别小心，因为对null的操作可能会导致NullPointerException。

例如，如果你尝试调用null对象的方法或访问其属性，就会遇到这种异常。因此，在处理可能包含null值的ArrayList时，总是好的做法是进行null检查。

ArrayList 插入和删除的时间复杂度。

ArrayList的插入和删除操作的时间复杂度取决于操作的位置：

插入操作：

在 ArrayList 中，末尾添加或者移除元素的时间复杂度都是 O(1)操作，因为不需要移动已有的元素

但是考虑一个情况，就是当插入元素的时候，此时如果数组需要扩容（即当前元素数量已达到数组的容量），则插入的时间复杂度会上升到O(n)，因为需要复制现有的数组到一个更大的数组。

在ArrayList的特定位置插入元素的时间复杂度是O(n)，因为需要将插入点之后的所有元素向后移动一位以腾出空间。这里的n是从插入点到数组末尾的元素数量。

删除操作：

从ArrayList的末尾移除元素通常是O(1)操作，直接删除最后一个元素不需要移动其他元素。

从ArrayList的特定位置删除元素的时间复杂度是O(n)，

ArrayList 的实现原理是什么？

• ArrayList 底层是用动态的数组实现的
• ArrayList 初始容量为 0，当第一次添加数据的时候才会初始化容量为 10
• ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组
• ArrayList在添加数据的时候
  • 确保数组已使用长度(size) 加1 之后足够存下下一个数据
  • 计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用 grow 方法扩容（原来的1.5倍）
  • 确保新增的数据有地方存储之后，则将新元素添加到位于 size 的位置上。
  • 返回添加成功布尔值。

ArrayList list = new ArrayList(10) 中的 list 扩容几次？

未扩容

如何实现 数组和List 之间的转换

参考回答：

• 数组转 List， 使用 JDK 中 java.util.Arrays 工具类的 asList 方法
• List 转数组，使用 List 的 toArray 方法，
  • 无参 toArray 方法返回 Object 数组，
  • 传入初始化 长度的数组对象，返回该对象数组

再问：

• 用 Arrays.asList 转 List 后，如果修改了数组内容， list 受影响吗
• List 用 toArray 转数组后，如果修改了 List 内容，数组受影响吗

asList 方法的元素指向地址并没有改，如果修改了数组内容， list 内容也会 受影响

toArray 方法是将数据赋值到了一个新的数组中, 如果修改了 List 内容，数组不受影响

ArrayList 和 LinkedList 之间的区别 🚩

• 1、底层数据结构
  • ArrayList是动态数组的数据结构实现
  • LinkedList是双向链表的数据结构实现
• 2、效率
  • ArrayList按照下标查询的时间复杂度O(1)【内存是连续的，根据寻址公式】，LinkedList不支持下标查询
  • 查找（未知索引）：ArrayList需要遍历，链表也需要链表，时间复杂度都是O(n)
  • 新增和删除
    • ArrayList)尾部插入和删除，时间复杂度是O(1):其他部分增需要哪动数组，时间复杂度是O(n】
    • LinkedList头尾节点增删时间复杂度是O(I),其他都需要遍历链表，时间复杂度是O(n)
• 3、空间
  • ArrayList 底层是数组，内存连续，节省内存
  • LinkedList是双向链表需要存储数据，和两个指针，更占用内存
• 4、线程是否安全
  • ArrayListi 和 LinkedList都不是线程安全的
  • 如果需要保证线程安全，有两种方案：
    • 在方法内使用，局部变量则是线程安全的
    • 使用线程安全的ArrayList 和 LinkedList
      • 比如使用 Collections.synchronizedList 方法
• ArrayList 和 LinkedList 都是基于 List 接⼝ 实现的，LinkedList 还实现了 Deque 接⼝，可以当做队列使⽤

讲一下 ArrayList 的添加元素操作

第一次添加数据

• 第一次添加数据的时候会先计算容量，返回 minCapacity
• 判断是否需要扩容，第一次的时候会进行一下扩容
• 10 > 0 ，进行扩容操作
• 然后会获取到第一次初始化数组长度 10 (newCapacity - minCapacity < 0)

第二次至十次添加元素

第十一次添加元素

此时会进行一次扩容，扩容容量为默认容量的 1.5 倍，数据进行数组拷贝到一个新的数组中。

CopyOnWriteArrayList底层实现原理

• CopyOnWriteArrayList是基于数组实现的，采⽤多写分离的⽅式来应 对多线程的读写操作，当对内部数组进⾏操作时，会拷⻉⼀份出来⽤ 于写，写操作时会进⾏加锁避免并发写⼊导致数据丢失，⽽读依旧在 旧数组进⾏，当操作完之后，再将引⽤重新指向新数组完成整个操作
• CopyOnWriteArrayList适合读多写少的场景，但是⽐较吃内存，并且 对于实时性要求很⾼场景不太适⽤因为可能读到旧数据

Map

讲一下 HashMap 🚩

HashMapl的put方法的具体流程

• 1.判断键值对数组table是否为空或为null,否则执行resize0进行扩容（初始化）
• 2.根据键值key计算hash值得到数组索引
• 3.判断table[i]== null,条件成立，直接新建节点添加
• 4.如果table[0]== null,不成立
  • 4.1 判断table[i] 的首个元素是否和 key一样，如果相同直接覆盖value
  • 4.2 判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
  • 4.3 遍历 table[i] ，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现 key 已经存在直接覆盖value
• 5.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold(数组长度 * 0.75)，如果超过，进行扩容。

讲一讲 HashMap 的扩容机制

• 1、在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 * 0.75）
• 2、每次扩容的时候，都是扩容之前容量的2倍
• 3、扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
  • 没有hash冲突的节点，则直接使用e.hash&(newCap-1)计算新数组的索引位置
  • 如果是红黑树，走红黑树的添加
  • 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash&oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

说一下HashMap的实现原理？

• 1、底层使用hash表数据结构，即数组+（链表|红黑树）
• 2、添加数据时，计算 key 的值确定元素在数组中的下标
  • key相同则替换
  • 不同则存入链表或红黑树中
• 获取数据通过key的hash计算数组下标获取元素

HashMap的 jdk1.7和 jdk1.8有什么区别

• JDK1.8之前采用的拉链法，数组+链表
  • HashMap在JDK 7采⽤的是 数组 + 链表 的⽅式，
  • 由于HashMap的key 是基于hash值计算后放到对应的数组槽位的，可能会出现hash碰 撞，所以在每个槽位采⽤链表头插法进⾏存放元素，如果容量不⾜会 先扩容
• JDK1.8之后采用数组+链表+红黑树，链表长度大于8且数组长度大于64则会从链表转化为红黑树
  • HashMap在JDK 8采⽤的是 数组 + 链表/红⿊树 的⽅式，基于JDK 7的 基础上为了解决链表过⻓导致查询效率降低以及头插法导致循环链表 从⽽死循环造成CPU满载的问题，所以JDK 8采⽤了尾插法

头插法和尾插法

• 1.7 头插法
  • 在 Java 1.7 及之前的版本中，当一个新的元素被加入到 HashMap 中，且发生哈希冲突时，HashMap 会采用头插法将这个新元素插入到链表的头部。头插法的主要特点是新加入的元素总是被放在链表的最前面。
  • 优点：
    • 简单快速：在链表的头部插入元素是一个时间复杂度为 O(1) 的操作。
  • 缺点：
    • 在多线程环境下，头插法可能会引起循环链表，导致 get 方法形成死循环。
    • 由于每次插入都会改变链表的顺序，这可能会导致长时间的性能下降
• 1.8 尾插法
  • Java 1.8 对 HashMap 进行了优化，改用了尾插法来处理哈希冲突下的链表插入。尾插法意味着新元素总是被添加到链表的尾部。
  • 优点：
    • 在多线程环境下更安全：尽管 HashMap 本身不是线程安全的，但尾插法相比于头插法，在并发修改时减少了循环链表出现的风险。
    • 维持了元素的插入顺序，这对于一些特定的场景可能是有益的。
  • 缺点：
    • 插入操作可能会稍微慢一些，因为需要遍历到链表的末尾。

讲一下 HashMap 中的寻址算法

• 1、计算对象的hashCode()
• 2、再进行调用 hash()方法 进行二次哈希，hashcode值右移16位再异或运算，让哈希分布更为均匀
• 3、最后(capacity-1)&hash得到索引

HashMap 的寻址算法和数组长度为什么是2 的 n 次幂

ConcurrentHashMap

ConcurrentHashMap是一种线程安全的高效Map集合

• ConcurrentHashMap
  • 底层数据结构
    • 1.7：底层采用分段的数组 + 链表实现
    • 1.8：采用的数据结构跟 HashMap 1.8 的结构一样，数组 + 链表/红黑二叉树
  • 加锁的方式
    • 1.7：采用 Segment 分段锁，底层使用的是 ReentrantLock
    • 1.8：采用 CAS 添加新节点，采用 synchronized 锁定链表或红黑二叉树的首节点，相对 Segment 分段锁粒度更细，性能更好
  • 新增元素（1.8）
    • hash(key) → 在该数组节点下通过 CAS 操作新增元素操作
    • 采用 synchronized 锁定链表或红黑二叉树的首节点

JDK 1.7

组成：一个 Segment 数组（不可扩容，默认值 16），每一个数组节点对应一个 HashEntry 数组（数组 + 链表）

添加元素：计算 key 的 hash 值 定位到 Segment 数组的下标，此时通过 ReentrantLock 获取到锁进行该下标下 HashEntry 数组新增操作

JDK1.8 ConcurrentHashMap

在JDK1.8中，放弃了Segment 臃肿的设计，数据结构跟HashMapl的数据结构是一样的：数组（动态扩容）+ 链表 +红黑树

采用 CAS+Synchronized 来保证并发安全进行实现

• CAS 控制数组节点的添加
• synchronized 只锁定当前链表或红黑二叉树的首节点，只要 hash 不冲突，就不会产生并发的问题，效率得到提升。

新增元素的操作：

Set