携程旅游网站建设的定位,怎么样做个网站,网站建立平台 cms,网站优化策略分析论文注意#xff1a;文章若有错误的地方#xff0c;欢迎评论区里面指正 #x1f36d; 系列文章目录 面试题分享之Java基础篇#xff08;二#xff09;面试题分享之Java基础篇#xff08;三#xff09; 面试题分享之Java集合篇#xff08;一#xff09;、 面试题分享之Ja… 注意文章若有错误的地方欢迎评论区里面指正 系列文章目录 面试题分享之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位有什么好处? 右移16位正好是32位的一半高半区和低半区做异或操作就是为了混合原始哈希码的高位与地位以此来加大低位的随机性。设计者考虑到现在hashCode分布的已经不错了而且当发生较大碰撞时也用树形存储降低了冲突仅仅异或一下少了系统的开销也不会造成因为高位没有参与下标的计算从而引起碰撞。
二、HashMap如何解决hash冲突 不清楚什么是hash冲突小伙伴可以参考 面试题分享之Java基础篇二-CSDN博客 1、链地址法也称为拉链法
当两个或多个键的哈希值相同时它们不会被存储在同一个桶bucket中而是会被链接到同一个桶内的链表中。HashMap在内部使用NodeK,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 实现的。两者主要区别
HashSetHshMap数据结构和存储方式实现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 的实现发生了较大的变化主要采用了CASCompare-And-Swap操作、Synchronized关键字以及Node红黑树的存储结构。 CAS 操作CAS 是一种无锁算法它通过比较并交换操作来实现对共享变量的原子操作。在 ConcurrentHashMap 中CAS 操作被用于实现节点的插入、更新和删除等操作。由于 CAS 操作具有原子性因此可以保证多线程环境下的数据一致性。Synchronized虽然 JDK 1.8 中的 ConcurrentHashMap 摒弃了分段锁机制但它仍然使用了 Synchronized 关键字来保证对共享变量的同步访问。具体来说ConcurrentHashMap 的每个节点Node在更新数据时都会使用 Synchronized 来保证操作的原子性。Node红黑树在 JDK 1.8 中ConcurrentHashMap 的内部存储结构由 SegmentHashEntry 改为了 Node红黑树。具体来说当某个桶bucket中的链表长度超过一定的阈值默认为 8时会将该链表转换为红黑树以提高查询效率。红黑树是一种自平衡的二叉搜索树它的查询、插入和删除操作的时间复杂度都是 O(logN)。 总结
这两期的面试题都偏理论性的要求小伙伴有很好的数据结构的基础深入源码分析多理解不要死记硬背。好了今天的分享就到这里拜拜。
