我的编程空间,编程开发者的网络收藏夹
学习永远不晚

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

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

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

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

今天我们来讲解分析下

一、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 个的时候,链表结构就会转为红黑树结构。

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

  • 红黑树查询:其访问性能近似于折半查找,时间复杂度 O(logn);
  • 链表查询:这种情况下,需要遍历全部元素才行,时间复杂度 O(n);

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

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

  • 每个节点要么是红色,要么是黑色,但根节点永远是黑色的;
  • 每个红色节点的两个子节点一定都是黑色;
  • 红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色);
  • 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;
  • 所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);
  • 在树的结构发生改变时(插入或者删除操作),往往会破坏上述条件 3 或条件 4,需要通过调整使得查找树重新满足红黑树的条件;

 

免责声明:

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

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

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

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

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

HashMap是Java中最常用的集合类框架,也是Java语言中非常典型的数据结构,同时也是我们需要掌握的数据结构,更重要的是进大厂面试必问之一;

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

日常开发中,集合是我们经常用到的一种数据结构,当然,集合也并不是一种,也没有所谓的最好的集合,只有最适合的;今天我们就来聊聊LinkedList底层实现和原理。

详解 HashMap 的底层实现原理

作为一名程序员,你可能经常使用 HashMap 这个重要的数据结构,但你对它的底层实现原理可能不够了解。本文将通过图文结合的方式,为你详细解析 HashMap 的底层实现原理,并回答一些常见问题,让你能够更好地理解和应用 HashMap。

Redis数据结构SortedSet的底层原理解析

目录概述一些常用命令实现跳跃表跳表的插入压缩列表概述一些常用命令存储:zadd key score value获取:zrange key start end获取:同时获取分数:zrange key start end with scor
2022-07-13

数据库索引原理与底层数据结构解析

通过本文的介绍,我们了解了数据库索引的原理和底层数据结构。我们知道了IO操作对于索引的重要性,以及如何通过分块读取和局部性原理来优化IO性能。

详解SpringBoot底层原理实现

笔者记得差不多在2015年以前,要部署一个Web应用,那得准备各种Web容器,比如Tomcat,然后打war包,然后部署到Web容器的特定目录下,以此来完成一个应用的部署,而且应用中的web.xml配置文件是必不可少的。可是近几年使用了Sp

Redis 哈希Hash底层数据结构详解

这篇文章主要介绍了Redis 哈希Hash底层数据结构详解的相关资料,需要的朋友可以参考下
2022-11-13

PHP数组在底层的实现原理详解

PHP数组由哈希表和顺序元素数组实现。哈希表将键映射到元素数组索引,元素数组顺序存储元素。数组元素通过键哈希为哈希表索引,再利用索引获取元素数组中元素位置,快速高效访问。插入和删除元素时,哈希表会调整索引,维持数组结构。数组性能受哈希函数、哈希表大小和访问模式影响。优化策略包括选择合适哈希函数、调整哈希表大小、使用有序数组和避免哈希表重新哈希。
PHP数组在底层的实现原理详解
2024-04-02

redis底层数据结构如何实现的

Redis 底层数据结构的实现redis 是一种内存中的数据结构存储,它使用高效的数据结构来实现各种数据类型。这些底层数据结构包括:1. 哈希表(Hash Table)哈希表用于存储键值对,其中键被哈希成一个值,并指向对应的数据。Re
redis底层数据结构如何实现的
2024-06-12

Redis List 底层三种数据结构原理剖析

Redis 的 List 与 Java 中的 LinkedList 类似,是一种线性的有序结构,可以按照元素被推入列表中的顺序来存储元素,能满足先进先出的需求,这些元素既可以是文字数据,又可以是二进制数据。
RedisListJava2024-11-30

深入详解Vue3ref底层实现原理

随着现在vue3越来越普及,相应的面试题也多了起来。说到vue3的面试题,有一个最经典的就是对于实现ref和reactive这两个方法的底层原理,本文就来和大家简单讲讲吧
2023-05-17

深入理解MySQL索引底层数据结构

索引本质上是一种排好序的数据结构,了解了MySQL索引的底层数据结构及存储原理,可以帮助我们更好地进行SQL优化。其实数据库索引调优是一项技术活,不能仅仅靠理论,因为实际情况千变万化,而且MySQL本身存在很复杂的机制,如查询优化策略和各种

MySQL索引底层数据结构怎么理解

这篇文章主要介绍“MySQL索引底层数据结构怎么理解”,在日常操作中,相信很多人在MySQL索引底层数据结构怎么理解问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”MySQL索引底层数据结构怎么理解”的疑惑有所
2023-06-25

热门标签

编程热搜

编程资源站

目录