文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

hashmap底层实现原理

2023-10-29 13:29

关注

一、hashmap底层实现原理

HashMap是基于哈希表的Map接口的非同步实现。元素以键值对的形式存放,并且允许null键和null值,因为key值唯一(不能重复),因此,null键只有一个。另外,hashmap不保证元素存储的顺序,是一种无序的,和放入的顺序并不相同(此类不保证映射的顺序,特别是它不保证该顺序恒久不变)。HashMap是线程不安全的。

二、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。

三、HashMap的数据存储结构

HashMap由数组(键值对entry组成的数组主干)+ 链表(元素太多时为解决哈希冲突数组的一个元素上多个entry组成的链表)+ 红黑树(当链表的元素个数达到8链表存储改为红黑树存储)进行数据的存储。

HashMap采用table数组存储Key-Value的,每一个键值对组成了一个Node节点(JDK1.7为Entry实体,因为jdk1.8加入了红黑树,所以改为Node)。Node节点实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Node节点,以此来解决Hash冲突的问题。

四、HashMap的重要参数

HashMap 的实例有两个参数影响其性能:初始容量和加载因子。容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。在Java编程语言中,加载因子默认值为0.75,默认哈希表元为101。

五、数组+链表的数据结构

HashMap最基础的底层结构是一个数组。每一个数组元素(或称为桶)是一个链表或者红黑树,用于存储多个键值对。当两个不同的键通过哈希函数映射到同一索引上时,会在同一个链表中以节点形式存储。

六、负载因子和扩容机制

负载因子是一个用于衡量HashMap何时进行扩容的指标。当HashMap中的元素数量超过数组大小与负载因子的乘积时,会触发扩容操作。扩容意味着数组大小的增加以及所有现有元素的重新哈希。

七、数据插入与获取过程

数据插入和获取都依赖于哈希函数,该函数将键映射到数组的一个特定索引。插入操作时,如果目标索引处没有元素,则直接存储;如果有元素,则添加到链表或红黑树的末尾。获取操作通过键的哈希值快速找到对应的索引,然后在链表或红黑树中进行搜索。

八、Java与Python中的HashMap实现

在Java中,HashMap是一个广泛使用的数据结构,实现在java.util包内。Python中的字典(dict)与HashMap有类似的功能和实现机制,但具体细节略有不同。

常见问答:

Q1: 为什么 HashMap 不是线程安全的?

答:默认情况下,HashMap 的方法没有同步机制,所以在多线程环境下可能会出现数据不一致的问题。

Q2: 什么情况下会使用红黑树而不是链表?

答:当一个数组索引位置上的元素数量超过一定阈值时,链表会被转换为红黑树,以提高检索效率。

Q3: 负载因子是什么?它如何影响 HashMap 的性能?

答:负载因子是 HashMap 中元素数量与数组大小的比值。一个过高的负载因子会导致检索效率下降,而一个过低的负载因子会导致存储空间的浪费。

Q4: HashMap和HashTable有什么不同?

HashMap是非线程安全的,而HashTable是线程安全的。此外,HashMap允许键或值为null,而HashTable不允许。

Q5: 如何选择合适的负载因子?

一般来说,较低的负载因子会导致更多的空间浪费,而较高的负载因子可能会降低查询速度。默认的负载因子通常设置为0.75。

Q6: 链表和红黑树在HashMap中的应用有什么不同?

当一个桶中的元素数量超过一定阈值时,链表会转换为红黑树,以减少查找时间。红黑树提供了更高效的查找性能。

阅读原文内容投诉

免责声明:

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

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

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

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

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

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

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

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

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