HashMap五大核心问题总结

简介: HashMap五大核心问题总结

Jdk8的hashmap与Jdk7的hashmap有什么区别

1. JDK8中新增了红黑树,JDK8是通过数组+链表+红黑树来实现的

2. JDK7中链表的插入是用的头插法,而JDK8中则改为了尾插法

3. JDK8中的因为使用了红黑树保证了插入和查询了效率,所以实际上JDK8中 的Hash算法实现的复杂度降低了

4. JDK8中数组扩容的条件也发了变化,只会判断是否当前元素个数是否超过了阈值,而不再判断当前put进来的元素对应的数组下标位置是否有值。

5. JDK7中是先扩容再添加新元素,JDK8中是先添加新元素然后再扩容

HashMap中put方法的流程

1. 通过key计算出一个hashcode

2. 通过hashcode与“与操作”计算出一个数组下标

3. 在把put进来的key,value封装为一个entry对象

4. 判断数组下标对应的位置,是不是空,如果是空则把entry直接存在该数组位置

5. 如果该下标对应的位置不为空,则需要把entry插入到链表中

6. 并且还需要判断该链表中是否存在相同的key,如果存在,则更新value

7. 如果是JDK7,则使用头插法

8. 如果是JDK8,则会遍历链表,并且在遍历链表的过程中,统计当前链表的元 素个数,如果超过8个,则先把链表转变为红黑树,并且把元素插入到红黑树中

Jdk8中链表转换为红黑树的条件

1. 链表中的元素的个数为8个或超过8个

2. 同时,还要满足当前数组的长度大于或等于64才会把链表转变为红黑树。因为链表转变为红黑树的目的是为了解决链表过长,导致查询和插入效率慢的问题,而如果要解决这个问题,也可以通过数组扩容,把链表缩短也可以解决这个问题。所以在数组长度还不太长的情况,可以先通过数组扩容来解决链表过长的问题。

HashMap的扩容流程

1. HashMap的扩容指的就是数组的扩容, 因为数组占用的是连续内存空间, 所以数组的扩容其实只能新开一个新的数组,然后把老数组上的元素转移到新数组上来,这样才是数组的扩容

2. 在HashMap中也是一样,先新建一个2倍数组大小的数组

3. 然后遍历老数组上的每一个位置,如果这个位置上是一个链表,就把这个链表上的元素转移到新数组上去

4. 在这个过程中就需要遍历链表,当然jdk7,和jdk8在这个实现时是有不一样 的,jdk7就是简单的遍历链表上的每一个元素,然后按每个元素的hashcode结合新数组的长度重新计算得出一个下标,而重新得到的这个数组下标很可能和之前的数组下标是不一样的,这样子就达到了一种效果,就是扩容之后,某个链表会变短,这也就达到了扩容的目的,缩短链表长度,提高了查询效率

5. 而在jdk8中,因为涉及到红黑树,这个其实比较复杂,jdk8中其实还会用到 一个双向链表来维护红黑树中的元素,所以jdk8中在转移某个位置上的元素 时,会去判断如果这个位置是一个红黑树,那么会遍历该位置的双向链表,遍 历双向链表统计哪些元素在扩容完之后还是原位置,哪些元素在扩容之后在新 位置,这样遍历完双向链表后,就会得到两个子链表,一个放在原下标位置, 一个放在新下标位置,如果原下标位置或新下标位置没有元素,则红黑树不用 拆分,否则判断这两个子链表的长度,如果超过八,则转成红黑树放到对应的 位置,否则把单向链表放到对应的位置。

6. 元素转移完了之后,在把新数组对象赋值给HashMap的table属性,老数组会被回收。

为什么HashMap的数组大小是2的幂次方

JDK7的HashMap是数组+链表实现的

JDK8的HashMap是数组+链表+红黑树实现的

当某个key-value对需要存储到数组中时,需要先生成一个数组下标index,并且这个 index不能越界。在HashMap中,先得到key的hashcode,hashcode是一个数字,然后通过  hashcode & (table.length - 1) 运算得到一个数组下标index,是通过与运算计算出 来一个数组下标的,而不是通过取余,与运算相比于取余运算速度更快,但是也有一 个前提条件,就是数组的长度得是一个2的幂次方数。

目录
打赏
0
4
4
0
41
分享
相关文章
【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(下)
在阅读了上篇文章《【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)》之后,相信您对HashMap的基本原理和基础结构已经有了初步的认识。接下来,我们将进一步深入探索HashMap的源码,揭示其深层次的技术细节。通过这次解析,您将更深入地理解HashMap的工作原理,掌握其核心实现。
84 0
【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(下)
蚂蚁金服Java研发岗二面:redis 常见数据结构以及使用场景分析
redis简单来说 就是一个数据库,不过与传统数据库不同的是 redis 的数据是存在内存中的,所以存写速度非常快,因此 redis 被广泛应用于缓存方向。另外,redis 也经常用来做分布式锁。redis 提供了多种数据类型来支持不同的业务场景。除此之外,redis 支持事务 、持久化、LUA脚本、LRU驱动事件、多种集群方案。所以在面试中我们经常可以看到redis的身影,今天给大家带来一道redis的面试真题以及解析,后面会给大家分享今年来redis常考试的一些真题。
216 0
|
4月前
|
深入剖析Java Map:不只是存储数据,更是设计艺术的体现!
【10月更文挑战第17天】在Java编程中,Map是一种重要的数据结构,用于存储键值对,并展现了设计艺术的精髓。本文深入剖析了Map的设计原理和使用技巧,包括基本概念、设计艺术(如哈希表与红黑树的空间时间权衡)、以及使用技巧(如选择合适的实现类、避免空指针异常等),帮助读者更好地理解和应用Map。
146 3
|
4月前
|
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
114 2
如何打造既安全又高效的B端产品?五大核心策略
在B端市场,安全性与易用性常被视为矛盾体。企业用户既需要严密的数据保护机制,又希望产品具备优秀的用户体验以提高效率。尤其在金融、医疗、政府等行业,如何平衡两者成为关键挑战。本文探讨B端产品在安全性与易用性之间的平衡策略,满足高安全需求行业的需求。通过合理的技术手段、灵活的权限管理和智能化交互方式,找到最佳平衡点,确保数据安全的同时提升用户体验。
【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)
HashMap是基于Map接口构建的数据结构,它以键值对的形式存储元素,允许键和值都为null。由于键的唯一性,HashMap中只能有一个键为null。HashMap的特点是元素的无序性和不重复性。
79 1
【深入挖掘Java技术】「源码原理体系」盲点问题解析之HashMap工作原理全揭秘(上)
|
9月前
|
大数据Java工程师必备____2021年数据结构思维导图!
大数据Java工程师必备____2021年数据结构思维导图!
143 0
HashMap 的设计与优化(上)
hashmap 是一个 key-value 形式的键值对集合。(本文内容基于 JDK1.8)下面是一个简单的 hashmap 的结构。 本文主要是通过源码的方式分析 HashMap 的实现和优化。主要是围绕源码本身展开,以添加注释的方式进行记录和分析
168 0
HashMap 的设计与优化(上)
HashMap 的设计与优化(下)
hashmap 是一个 key-value 形式的键值对集合。(本文内容基于 JDK1.8)下面是一个简单的 hashmap 的结构。 本文主要是通过源码的方式分析 HashMap 的实现和优化。主要是围绕源码本身展开,以添加注释的方式进行记录和分析
136 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等