面试题分享之Java集合篇（三）

注意：文章若有错误的地方，欢迎评论区里面指正 🍭 

系列文章目录

• 面试题分享之Java基础篇（二）
• 面试题分享之Java基础篇（三）

• 面试题分享之Java集合篇（一）、

• 面试题分享之Java集合篇（二）

---

前言

哈喽，小伙伴们，昨天我们见识了HaspMap常见的面试题，如：HaspMap的get、put、resize方法的原理等等，废话不多说，今天继续来给大家分享几道Java集合的高频面试题。🌈

---

一、HashMap怎么计算 key 的 hash 值的？

先贴上源码（jdk1.8为例）：

    /**这是官方注释计算 key.hashCode（） 并将 （XOR） 更高的哈希位传播到更低的哈希位。由于该表使用二次幂掩码，因此仅比当前掩码高位变化的哈希集将始终发生冲突。（在已知的例子中，有一组浮点键在小表中保存连续的整数。因此，我们应用了一个变换，将更高位的影响向下传播。在速度、实用性和比特扩展质量之间需要权衡。由于许多常见的哈希集已经合理分布（因此不会从扩展中受益），并且由于我们使用树来处理 bin 中的大量冲突，因此我们只是以最便宜的方式对一些移位进行异或运算，以减少系统损失，并合并最高位的影响，否则由于表边界，这些比特永远不会用于索引计算。*/static final int hash(Object key) {int h;/*如果key是null，则直接返回0作为哈希值如果不为null，返回原hashCode值和原hashCode值无符号右移16位的值按位异或的结果按位异或：将两个十进制数先转化为二进制数，相同的就取0，不同的就取1例如：15 跟 16 按位异或16    1 0 0 0 0  842115  ^ 0 1 1 1 1------------1 1 1 1 1  ---> 31*/return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

🧑‍💼面试官追问：右移16位有什么好处?

1. 右移16位，正好是32位的一半，高半区和低半区做异或操作，就是为了混合原始哈希码的高位与地位，以此来加大低位的随机性。
2. 设计者考虑到现在hashCode分布的已经不错了，而且当发生较大碰撞时也用树形存储降低了冲突，仅仅异或一下，少了系统的开销，也不会造成因为高位没有参与下标的计算，从而引起碰撞。

二、HashMap如何解决hash冲突

不清楚什么是hash冲突小伙伴可以参考：

面试题分享之Java基础篇（二）-CSDN博客

1、链地址法（也称为拉链法）：

• 当两个或多个键的哈希值相同时，它们不会被存储在同一个桶（bucket）中，而是会被链接到同一个桶内的链表中。
• HashMap在内部使用Node<K,V>[]数组来存储桶，每个桶可以是一个链表或红黑树（在Java 8及更高版本中，当链表长度超过某个阈值时，会转换为红黑树以提高性能）。
• 当发生哈希冲突时，新的键值对将被添加到相应桶的链表或红黑树的末尾。

2、开放地址法：

• 这种方法并不是HashMap直接使用的，但在其他哈希表实现中可能会看到。
• 当发生哈希冲突时，会按照一定的规则（如线性探测、平方探测等）在哈希表中寻找下一个空闲位置来存储键值对。

3、再哈希法：

• 这不是HashMap的标准做法，但在某些哈希表实现中可能会使用。
• 当通过第一个哈希函数计算得到的哈希值发生冲突时，使用第二个哈希函数再次计算哈希值，并尝试将键值对存储在新的位置。如果仍然冲突，可以继续使用更多的哈希函数。

​4、建立公共溢出区：

• 这种方法也不是HashMap的标准做法。
• 当哈希表的主区域无法容纳更多的键值对时，可以将它们存储在一个单独的溢出区域中。然而，在HashMap中，当容量不足时，它会通过重新分配更大的数组并进行重新哈希来扩展其容量。

对于HashMap来说，它主要依赖链地址法（拉链法）来解决哈希冲突。当向HashMap中插入新的键值对时，它会首先计算键的哈希值，并使用该哈希值来确定应该将其存储在哪个桶中。如果该桶已经存在其他键值对（即发生了哈希冲突），则将新的键值对添加到该桶的链表或红黑树的末尾。

此外，为了优化性能并减少哈希冲突的可能性，HashMap还使用了以下技术：

• 哈希函数：HashMap使用了一个精心设计的哈希函数来计算键的哈希值。这个函数试图将键均匀地分布到不同的桶中，以减少哈希冲突的可能性。
• 动态扩容：当HashMap中的键值对数量超过其容量的一定比例（称为加载因子，默认为0.75）时，它会自动扩容其内部数组的大小，并重新哈希所有键值对以确保它们仍然被正确地分配到新的桶中。这有助于减少哈希冲突并提高性能。

三、HashMap多线程操作导致死循环问题知道吗?

        这个问题主要源于 HashMap 的扩容机制和链表或红黑树的节点转移过程。在扩容时，HashMap 会创建一个新的数组，并重新计算每个键的哈希值以确定它们在新数组中的位置。这个过程需要遍历原数组中的所有桶（bucket），并将桶中的链表或红黑树节点转移到新数组对应的桶中。

        如果在这个过程中发生并发修改（例如，另一个线程插入或删除了键值对），就可能导致节点在新旧数组之间形成循环引用，进而引发死循环。具体来说，如果两个线程同时对一个桶进行扩容操作，并且其中一个线程在遍历链表或红黑树的过程中修改了链表或红黑树的结构（例如，删除了某个节点），那么另一个线程在继续遍历时就可能会遇到已经遍历过的节点，从而形成循环引用。

四、说说HashMap 和 HashSet 区别？

HashSet 底层就是基于 HashMap 实现的。两者主要区别：

	HashSet	HshMap
数据结构和存储方式	实现Set接口，HashSet内部使用哈希表来存储元素，并通过元素的哈希码来判断是否重复	实现Map接口，HashMap存储的是键值对，键（key）是唯一的，值（value）可以重复
元素类型和唯一性	存储的是单一的元素类型（如整数、字符串等），并且元素必须是唯一的，不会存在重复的元素	存储的是键值对，键和值可以是不同类型的对象。键必须是唯一的，而值可以重复
查找速度	速度相对较慢	速度相对较快

五、ConcurrentHashMap在Jdk1.7和Jdk1.8的实现原理

1、ConcurrentHashMap跟HashMap的区别

• HashMap的底层数据结构主要是数组+链表（确切的说是由链表为元素的数组），ConcurrentHashMap的底层数据结构在JDK 1.7中是基于Segment数组+HashEntry数组+链表，而在JDK 1.8中则改为了Node+红黑树。
• HashMap是非线程安全的，它不能在多线程环境下正确工作。当多个线程同时对HashMap进行修改时，可能会导致数据不一致或者抛出异常。而ConcurrentHashMap是线程安全的，它使用了锁分段技术（lock striping）来实现并发安全性，允许多个线程在不同的段上并发地进行修改操作。

2、在JDK1.7实现原理 

在JDK1.7中ConcurrentHashMap采用数组+Segment+分段锁的方式实现。

什么是Segment呢？

        ConcurrentHashMap中的分段锁称为Segment.它类似HashMap的结构，内部拥有一个Entry数组，数组中的每个元素又是一个链表，同时又是一个ReentrantLock(Segment继承了ReentrantLock)

Concurrent使用分段锁机制，将数据一段一段的存储，然后给每一段数据加锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据可以被其他线程访问，能够实现真正的并发访问。

Concurrent的扩容机制：当某个 Segment 中的元素数量超过其容量阈值时，会触发扩容操作。扩容操作会创建一个新的 Segment 数组，并将原有的 Segment 中的元素重新分配到新的 Segment 中。这个过程中会涉及到大量的数据迁移和重哈希操作，因此是一个耗时的过程。但由于采用了分段锁机制，扩容操作可以并行进行，从而提高了性能。

ConcurrentHashMap定位一个元素需要经过两次hash过程：第一次定位到Segmnent,第二次定位到元素所在的链表的头部。

该结构的优缺点：

缺点：Hash的过程要比普通的HashMap要长
优点：写操作时只对元素所在的Segment进行加锁即可，不会影响到其他Segment,在最理想的情况下,ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（写操作非常平均的分布在所有Segment上）。所以，通过这种结构，ConcurrentHashMap并发能力大大提高。

3、在JDK1.8实现原理

在 JDK 1.8 中，ConcurrentHashMap 的实现发生了较大的变化，主要采用了CAS（Compare-And-Swap）操作、Synchronized关键字以及Node+红黑树的存储结构。

1. CAS 操作：CAS 是一种无锁算法，它通过比较并交换操作来实现对共享变量的原子操作。在 ConcurrentHashMap 中，CAS 操作被用于实现节点的插入、更新和删除等操作。由于 CAS 操作具有原子性，因此可以保证多线程环境下的数据一致性。
2. Synchronized：虽然 JDK 1.8 中的 ConcurrentHashMap 摒弃了分段锁机制，但它仍然使用了 Synchronized 关键字来保证对共享变量的同步访问。具体来说，ConcurrentHashMap 的每个节点（Node）在更新数据时都会使用 Synchronized 来保证操作的原子性。
3. Node+红黑树：在 JDK 1.8 中，ConcurrentHashMap 的内部存储结构由 Segment+HashEntry 改为了 Node+红黑树。具体来说，当某个桶（bucket）中的链表长度超过一定的阈值（默认为 8）时，会将该链表转换为红黑树，以提高查询效率。红黑树是一种自平衡的二叉搜索树，它的查询、插入和删除操作的时间复杂度都是 O(logN)。

总结

这两期的面试题都偏理论性的，要求小伙伴有很好的数据结构的基础，深入源码分析，多理解不要死记硬背。好了，今天的分享就到这里，拜拜。