后端常问面经之Java集合

HashMap底层原理

HashMap的数据结构： 底层使用hash表数据结构，即数组和链表或红黑树

1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标

2. 存储时，如果出现hash值相同的key，此时有两种情况。

a. 如果key相同，则覆盖原始值；

b. 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中

1. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

面试官追问：HashMap的jdk1.7和jdk1.8有什么区别

• JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

• jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8） 时并且数组长度达到64时，将链表转化为红黑树，以减少搜索时间。扩容 resize( ) 时，红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表

面试官追问：红黑树的优点是什么

他是自平衡的二叉搜索树，将链表转换成红黑树可以有效提高查询效率

为什么要引入红黑树，而不用其他树？

• 为什么不使用二叉排序树？问题主要出现在二叉排序树在添加元素的时候极端情况下会出现线性结构。比如由于二叉排序树左子树所有节点的值均小于根节点的特点，如果我们添加的元素都比根节点小，会导致左子树线性增长，这样就失去了用树型结构替换链表的初衷，导致查询时间增长。所以这是不用二叉查找树的原因。

• 为什么不使用平衡二叉树呢？红黑树不追求"完全平衡"，而而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。红黑树读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。

基本上主要的几种平衡树看来，红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在诸如STL的场景中需要稳定表现。

HashMap的put方法的具体流程

HashMap的put()方法用于向HashMap中添加键值对。当调用HashMap的put()方法时，会按照以下详细流程执行：

第一步：根据要添加的键的哈希码计算在数组中的位置（索引）。

第二步：检查该位置是否为空（即没有键值对存在）

• 如果为空，则直接在该位置创建一个新的Entry对象来存储键值对。将要添加的键值对作为该Entry的键和值，并保存在数组的对应位置。将HashMap的修改次数（modCount）加1，以便在进行迭代时发现并发修改。

第三步：如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同？

• 如果相同，则表示找到了相同的键，直接将新的值替换旧的值，完成更新操作。

第四步：如果第一个键值对的哈希码和键不相同，则需要遍历链表或红黑树来查找是否有相同的键：

如果键值对集合是链表结构：

• 从链表的头部开始逐个比较键的哈希码和equals()方法，直到找到相同的键或达到链表末尾。

• 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。

• 如果没有找到相同的键，则将新的键值对添加到链表的头部。

如果键值对集合是红黑树结构：

• 在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。

• 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。

• 如果没有找到相同的键，则将新的键值对添加到红黑树中。

第五步：检查链表长度是否达到阈值（默认为8）：

• 如果链表长度超过阈值，且HashMap的数组长度大于等于64，则会将链表转换为红黑树，以提高查询效率。

第六步：检查负载因子是否超过阈值（默认为0.75）：

• 如果键值对的数量（size）与数组的长度的比值大于阈值，则需要进行扩容操作。

第七步：扩容操作：

• 创建一个新的两倍大小的数组。

• 将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。

• 更新HashMap的数组引用和阈值参数。

第八步：完成添加操作。

需要注意的是，HashMap中的键和值都可以为null。

此外，HashMap是非线程安全的，如果在多线程环境下使用，需要采取额外的同步措施或使用线程安全的ConcurrentHashMap。

了解的哈希冲突解决方法有哪些？

• 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。

• 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。

• 再哈希法：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。

• 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。“hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

HashMap多线程操作导致死循环的问题

JDK1.7及之前会出现这个问题。因为当一个桶位有多个元素需要扩容时，多个线程同时对链表进行操作，头插法有可能导致链表中的元素指向错误的位置，形成环形链表，从而导致死循环问题。

JDK1.8后，HashMap使用尾插法进行扩容，使得插入的节点永远在链表末尾，避免形成环形链表。不过多线程环境下还是建议使用ConcurrentHashMap。

HashMap多线程操作导致数据丢失风险

在HashMap中，当多个键值对被分到同一个桶当中时，多个线程对HashMap的put操作可能会导致数据丢失风险。原因是先判断是否hash冲突，再写入数据，这个过程并不是原子性的。

举个例子：

1. 有两个待写入的键值对a和b，要写入同一个桶当中，并且这个桶先前就存在元素c。

2. 键值对a在线程1中，线程1进行hash冲突的判断，a应该写在c元素的后面，判断完成后，线程1的时间片用完。

3. 键值对b在线程2中，线程2进行hash冲突的判断，并将b元素写在c元素的后面。

4. 线程1重新获得时间片，元素a写在元素c后面，这就导致了线程2的数据丢失。

ConcurrentHashMap的底层实现

ConcurrentHashMap 是一种线程安全的高效Map集合，jdk1.7和1.8也做了很多调整。

• JDK1.7的底层采用是分段的数组+链表 实现

• JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。

在jdk1.7中 ConcurrentHashMap 里包含一个 Segment 数组，这个数组不能扩容，默认是长度16。一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构 的元素，当对 HashEntry 数组的数据进行修 改时，必须首先获得对应的 Segment的锁。

Segment 是一种可重入的锁 ReentrantLock，每个Segment 守护一个HashEntry 数组里得元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁

在jdk1.8中的ConcurrentHashMap 做了较大的优化，性能提升了不少。首先是它的数据结构与jdk1.8的hashMap数据结构完全一致。其次是放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保 证并发安全进行实现，CAS控制数组节点的添加，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲 突，就不会产生并发 , 效率得到提升

ArrayList

底层结构

动态数组，可动态扩容，但删除元素时不能自动缩容。

ArrayList与Array区别

ArrayList底层是基于动态数组，Array底层是基于静态数组。

1. ArrayList可以自动扩容，但不能自动缩容，需要手动调用trimToSize()方法进行缩容操作。Array一旦创建就不能更改容量。

2. ArrayList只可以存储对象，Array既可以存储基本类型也可以存储对象。

3. ArrayList提供了add()，remove()，get()等方法，Array只能根据下标访问元素。

ArrayList的扩容过程

在调用add()方法添加元素时，会先检查容量，如果容量不足，会创建一个新数组，新数组的容量说原数组的1.5倍，然后将原数组的元素复制到新数组上去，并添加新的元素。

数组的初始容量为10个元素，如果需要频繁添加元素，应当在初始化是，设置一个合理的容量，这样可以避免频繁的扩容操作。初始化示例：List<String> list = new ArrayList<>(20);

线程安全

ArrayList是线程不安全的，两种解决方法：

1. 现有的ArrayList转换为线程安全，方法是Collections.synchronizedList()

2. 使用CopyOnWriteArrayList集合。CopyOnWriteArrayList获取元素的时候使用的是当前数组Array的一个快照， 而修改元素的时候，会复制一份Array再进行修改，修改不会对原本的Array产生影响，修改完后会覆盖原本的Array

ArrayList可以添加null值吗？

可以但不建议，因为在后续处理时，如果没有做判空处理就有可能导致空指针异常。

LinkedList

底层原理

双向链表

LinkedList为什么不实现RandomAccess接口

实现RandomAccess接口的类表明支持随机访问，由于LinkedList底层的数据结构是链表，链表的内存地址是不连续的，因此不支持随机访问。

LinkedList和ArrayList 时间复杂度的对比

1. 查询操作：ArrayList支持随机访问，时间复杂度为O(1)，LinkedList的查询时间复杂度为O(n)

2. 增删操作：如果只在尾部进行增删操作，ArrayList的时间复杂度为O(1)，反之为O(n)。

   如果只在首尾增删，LinkedList的时间复杂度为O(1)，反之LinkedList的增删操作时间复杂度为O(n)