Java 理论概念·HashMap 面试大全

作者 : jamin 本文共1145个字,预计阅读时间需要3分钟 发布时间: 2020-10-18 共1176人阅读

HashMap 面试大全

关于 HashMap 参考前文 Java HashMap

001 HashMap 的结构

哈希表结构(链表散列:数组+链表)实现,结合数组和链表的优点。当链表长度超过 8 时,链表转换为红黑树。

002 Get 方法的流程

先调用 Key 的 hashcode 方法拿到对象的 hash 值,然后用 hash 值对第一维数组的长度进行取模,得到数组的下标。这个数组下标所在的元素就是第二维链表的表头。然后遍历这个链表,使用 Key 的 equals 同链表元素进行比较,匹配成功即返回链表元素里存放的值。

003 Get 方法的时间复杂度

O(1),虽然 Get 方法的流程里需要遍历链表,但链表的长度很短,相比总元素的个数可以忽略不计,所以不是 O(n) 而是 O(1)。

004 为什么红黑树来代替链表

关键在于如果 Key 的 hashcode 不是随机的,而是人为特殊构造的话,那么第二维链表可能会无比的长,而且分布极为不均匀,这个时候就会出现性能问题。比如我们把对象的 hashcode 都统一返回一个常量,最终的结果就是 hashmap 会退化为一维链表,Get 方法的性能巨降为 O(n),使用红黑树可以将性能提升到 O(log(n))。

005 参数 loadFactor 作用

loadFactor 表示 HashMap 的拥挤程度,影响 hash 操作到同一个数组位置的概率。默认 loadFactor 等于 0.75,当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时,表示 HashMap 太挤了,需要扩容,在 HashMap 的构造器中可以定制 loadFactor。

006 HashMap 是否线程安全

当然不是,线程安全的 HashMap 是 ConcurrentHashMap。

007 ConcurrentHashMap 的并发度

程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16,且可以在构造函数中设置。当用户设置并发度时,ConcurrentHashMap 会使用大于等于该值的最小 2 幂指数作为实际并发度(假如用户设置并发度为 17,实际并发度则为 32)。

008 ConcurrentHashMap 比 HashTable 效率要高

HashTable 使用一把锁(锁住整个链表结构)处理并发问题,多个线程竞争一把锁,容易阻塞;

ConcurrentHashMap:

  • JDK 1.7 中使用分段锁(ReentrantLock + Segment + HashEntry),相当于把一个 HashMap 分成多个段,每段分配一把锁,这样支持多线程访问。锁粒度:基于 Segment,包含多个 HashEntry。
  • JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度:Node(首结点)(实现 Map.Entry<K,V>)。锁粒度降低了。
本站所提供的部分资源来自于网络,版权争议与本站无关,版权归原创者所有!仅限用于学习和研究目的,不得将上述内容资源用于商业或者非法用途,否则,一切后果请用户自负。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源。如果上述内容资对您的版权或者利益造成损害,请提供相应的资质证明,我们将于3个工作日内予以删除。本站不保证所提供下载的资源的准确性、安全性和完整性,源码仅供下载学习之用!如用于商业或者非法用途,与本站无关,一切后果请用户自负!本站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。如有侵权、不妥之处,请联系站长以便删除!
金点网络 » Java 理论概念·HashMap 面试大全

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用?
本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
是否提供免费更新服务?
持续更新,永久免费
是否经过安全检测?
安全无毒,放心食用

提供最优质的资源集合

立即加入 友好社区
×