文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

HashMap的底层原理是什么

2023-06-04 23:17

关注

这篇文章将为大家详细讲解有关HashMap的底层原理是什么,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。

一:HashMap的节点:HashMap是一个集合,键值对的集合,源码中每个节点用Node<K,V>表示

static class Node<K,V> implements Map.Entry<K,V> {   final int hash;   final K key;   V value;   Node<K,V> next;

Node是一个内部类,这里的key为键,value为值,next指向下一个元素,可以看出HashMap中的元素不是一个单纯的键值对,还包含下一个元素的引用。

二:HashMap的数据结构:HashMap的数据结构为 数组+(链表或红黑树),上图:

HashMap的底层原理是什么

image.png

为什么采用这种结构来存储元素呢?

数组的特点:查询效率高,插入,删除效率低。

链表的特点:查询效率低,插入删除效率高。

在HashMap底层使用数组加(链表或红黑树)的结构完美的解决了数组和链表的问题,使得查询和插入,删除的效率都很高。

三:HashMap存储元素的过程:

有这样一段代码:

HashMap<String,String> map = new HashMap<String,String>();map.put("刘德华","张惠妹");map.put("张学友","大S");

现在我要把键值对 “刘德华”,”张惠妹”存入map:

计算出键“刘德华”的hashcode,该值用来定位要将这个元素存放到数组中的什么位置.

什么是hashcode?

在Object类中有一个方法:

public native int hashCode();

该方法用native修饰,所以是一个本地方法,所谓本地方法就是非java代码,这个代码通常用c或c++写成,在java中可以去调用它。

调用这个方法会生成一个int型的整数,我们叫它哈希码,哈希码和调用它的对象地址和内容有关.

哈希码的特点是:

对于同一个对象如果没有被修改(使用equals比较返回true)那么无论何时它的hashcode值都是相同的

对于两个对象如果他们的equals返回false,那么他们的hashcode值也有可能相等

明白了hashcode我们再来看元素如何通过hashcode定位到要存储在数组的哪里,通过hashcode值和数组长度取模我们可以得到元素存储的下标。

刘德华的hashcode为20977295 数组长度为 16则要存储在数组索引为 20977295%16=1的地方

HashMap的底层原理是什么

jpg

可以分两种情况:

数组索引为1的地方是空的,这种情况很简单,直接将元素放进去就好了。

已经有元素占据了索引为1的位置,这种情况下我们需要判断一下该位置的元素和当前元素是否相等,使用equals来比较。

如果使用默认的规则是比较两个对象的地址。也就是两者需要是同一个对象才相等,当然我们也可以重写equals方法来实现我们自己的比较规则最常见的是通过比较属性值来判断是否相等。

如果两者相等则直接覆盖,如果不等则在原元素下面使用链表的结构存储该元素

HashMap的底层原理是什么

jpg

每个元素节点都有一个next属性指向下一个节点,这里由数组结构变成了数组+链表结构,红黑树又是怎么回事呢?

因为链表中元素太多的时候会影响查找效率,所以当链表的元素个数达到8的时候使用链表存储就转变成了使用红黑树存储,原因就是红黑树是平衡二叉树,在查找性能方面比链表要高.

四:HashMap中的两个重要的参数:HashMap中有两个重要的参数:初始容量大小和加载因子,初始容量大小是创建时给数组分配的容量大小,默认值为16,用数组容量大小乘以加载因子得到一个值,一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍,专业术语叫做扩容.

在做扩容的时候会生成一个新的数组,原来的所有数据需要重新计算哈希码值重新分配到新的数组,所以扩容的操作非常消耗性能.

HashMap的底层原理是什么

关于HashMap的底层原理是什么就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

阅读原文内容投诉

免责声明:

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

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

软考中级精品资料免费领

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

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

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

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

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

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

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