某度一面，有点难度

今天分享的是训练营的朋友在某度外包的面经，他在面完后跟我说：Java 集合底层的好久没问,有点忘了，所以这一块答的不太好。

我一直都会和大家强调复习的重要性，尤其是这种常见的问题。看看下面的问题你都能答得上来吗？

1. ArrayList 的添加与删除元素为什么慢？
2. ArrayList 是如何扩容的？
3. ArrayList 是线程安全的吗？
4. 什么是 HashMap？介绍一下
5. HashMap 的底层实现是怎样的？
6. 拉链法导致的链表过深问题为什么用红黑树？

ArrayList 的添加与删除元素为什么慢？

这里面的原因是主要是其内部实现基于数组的特性所导致的。
ArrayList 的添加与删除操作慢，主要是因为其内部实现基于数组，而数组在插入和删除元素时需要移动其他元素来保证连续性和顺序性，这个过程需要耗费较多的时间。
相对于基于链表的数据结构（如 LinkedList），ArrayList 的插入和删除操作的时间复杂度是 O(n)级别的，而链表的时间复杂度为 O(1)。

更加具体地说，

当在 ArrayList 的尾部添加元素时，如果当前数组的容量还未达到最大值，只需要将新元素添加到数组的末尾即可，此时时间复杂度为 O(1)。
但是，当数组容量已满时，需要进行扩容操作。扩容操作通常会将数组的容量增加到当前容量的 1.5 倍或 2 倍，并将原数组中的所有元素复制到新的更大的数组中。这一过程的时间复杂度为 O(n)，其中 n 为当前数组中的元素数量。
当在 ArrayList 的指定位置（非尾部）插入元素时，需要将目标位置之后的所有元素向后移动一个位置，然后将新元素插入到指定位置。这个过程涉及到移动元素的操作，时间复杂度为 O(n)，在最坏情况下，如头部插入，需要移动所有的元素。
当在 ArrayList 的指定位置（非尾部）删除元素时，需要将删除点之后的所有元素向前移动一个位置，以填补被删除元素的位置。这个过程同样涉及到移动元素的操作，时间复杂度为 O(n)，在最坏情况下，如头部删除，需要移动除了被删除元素之外的所有元素。

ArrayList 是如何扩容的？

ArrayList 的扩容机制是 Java 集合框架中一个重要的概念，它允许 ArrayList 在需要时自动增加其内部数组的大小以容纳更多的元素。

在 Java 中 ArrayList 的扩容过程，主要涉及到以下的几个步骤：

1. 初始容量和扩容因子：

当创建一个新的 ArrayList 对象时，它通常会分配一个初始容量，这个初始容量默认