文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

数据结构之HashMap底层实现原理详解

2024-12-14 00:47

关注

今天我们来讲解分析下

一、HashMap底层实现原理解析

我们常见的有数据结构有三种结构:数组结构 、链表结构 、哈希表结构

1、数组结构

存储区间是连续,且占用内存严重,空间复杂也很大,时间复杂为O(1)。

优点:是随机读取效率很高,原因数组是连续(随机访问性强,查找速度快)。

缺点:插入和删除数据效率低,因插入数据,这个位置后面的数据在内存中要往后移的,且大小固定不易动态扩展。

2、链表结构

区间离散,占用内存宽松,空间复杂度小,时间复杂度O(N)。

优点:插入删除速度快,内存利用率高,没有大小固定,扩展灵活。

缺点:不能随机查找,每次都是从第一个开始遍历(查询效率低)。

3、哈希表结构

结合数组结构和链表结构的优点,从而实现了查询和修改效率高,插入和删除效率也高的一种数据结构

常见的HashMap就是这样的一种数据结构

4、HashMap中的put()和get()的实现原理:

①、map.put(k,v)实现原理

(1)首先将k,v封装到Node对象当中(节点)。

(2)然后它的底层会调用K的hashCode()方法得出hash值。

(3)通过哈希表函数/哈希算法,将hash值转换成数组的下标,下标位置上如果没有任何元素,就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时,就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true,那么这个节点的value将会被覆盖。

②、map.get(k)实现原理

(1)先调用k的hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。

(2)通过上一步哈希算法转换成数组的下标之后,在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有,则返回null。如果这个位置上有单向链表,那么它就会拿着K和单向链表上的每一个节点的K进行equals,如果所有equals方法都返回false,则get方法返回null。如果其中一个节点的K和参数K进行equals返回true,那么此时该节点的value就是我们要找的value了,get方法最终返回这个要找的value。

5、为何随机增删、查询效率都很高的原因是?

原因: 增删是在链表上完成的,而查询只需扫描部分,则效率高。

HashMap集合的key,会先后调用两个方法,hashCode and equals方法,这这两个方法都需要重写。

6、为什么放在hashMap集合key部分的元素需要重写equals方法?

因为equals方法默认比较的是两个对象的内存地址

二、HashMap红黑树原理分析

相比 jdk1.7 的 HashMap 而言,jdk1.8最重要的就是引入了红黑树的设计,当hash表的单一链表长度超过 8 个的时候,链表结构就会转为红黑树结构。

为什么要这样设计呢?好处就是避免在最极端的情况下链表变得很长很长,在查询的时候,效率会非常慢。

简单的说,红黑树是一种近似平衡的二叉查找树,其主要的优点就是“平衡“,即左右子树高度几乎一致,以此来防止树退化为链表,通过这种方式来保障查找的时间复杂度为 log(n)。

关于红黑树的内容,网上给出的内容非常多,主要有以下几个特性:

 

来源:Android开发编程内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯