专栏首页老男孩成长之路当我们创建HashMap时,底层到底做了什么?

当我们创建HashMap时,底层到底做了什么?

jdk1.7中的底层实现过程(底层基于数组+链表)

在我们new HashMap()时,底层创建了默认长度为16的一维数组Entry[ ] table。当我们调用map.put(key1,value1)方法向HashMap里添加数据的时候:

首先,调用key1所在类的hashCode()计算key1的哈希值,通过key1的hash值与数组的最大索引进行位运算以后,得到了在 Entry数组中的存放位置:

如果此位置上的数据为空,此时的key1-value1添加成功。

如果此位置上的数据不为空(意味着此位置已经存在一个或多个数据),比较key1和已经存在的一个或多个数据的哈希值:

如果key1的哈希值与已经存在的数据的哈希值都不相同,此时key1-value1添加成功。

如果key1的哈希值与已经存在的数据的某一个数据的哈希值相同,继续比较:调用key1所在类的equals()方法:

如果equals()返回false,此时key1-value1添加成功;

如果equals()返回true,使用value1替换value2。

需要注意的是,若原来位置已有数据,则此时key1-value1和原来的数据以链表的方式存储。

在不断的添加过程中,会涉及到扩容问题,当数组容量大于数组现有长度乘以加载因子(如16*0.75,默认的加载因子为0.75)的时候,就会进行数组扩容,以减少哈希冲突(哈希冲突是指哈希函数算出来的地址被别的元素占用了),提高查询效率。默认的扩容方式,扩容为原来容量的2倍,并将原有的数据复制过来。

jdk1.8的底层实现过程(底层基于数组+链表+红黑树)

jdk1.8与jdk1.7中底层的创建过程相似,但有不同,首先,new HashMap()底层没有创建出一个长度为16的数组,在调用put()方法时,判断数组是否存在,如果不存在创建长度为16的Node[ ]数组。接下来的过程与jdk1.7相似。最后,当某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组的长度>64时,此时此索引位置上的所有数据改为使用红黑树存储。

在jdk1.7中,即使在“数组容量大于数组现有长度乘以加载因子”时扩容,也不可避免地会有哈希冲突存在,因此,在jdk1.8中引入红黑树是为了进一步减少哈希冲突,提高查询效率。

红黑树是一种自平衡的二叉查找树,是一种数据结构,典型的用途是实现关联数组。根节点必须是黑色,其他每个节点要么是红色,要么是黑色。

结论:HashMap键是不能重复的,去除重复的条件是依赖键的hashCode方法和equals方法,如果键是自己的对象类型,必须要重写hashCode方法和equals方法,否则,不能去除重复的键。

关注我的工众号《老男孩的架构路》领取一线大厂Java面试题总结+各知识点学习思维导图+一份400页pdf文档的Java独家面试手册!

这些资料的内容都是面试时面试官必问的知识点,篇章包括了很多知识点,其中包括了有基础知识、Java集合、JVM、多线程并发、spring原理、微服务、Netty 与RPC 、Kafka、日记、设计模式、Java算法、数据库、Zookeeper、分布式缓存、数据结构等等。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 当我们谈论智慧零售时,到底在谈什么?

    ? 本文作者:杨凯,腾讯员工  原标题:《【智慧零售的设计赋能 】当下的智慧零售》 ? 从1852年世界上第一家百货商场Bon marche(廉价商场)在巴黎...

    腾讯大讲堂
  • 从Java流到Spring Cloud Stream,流到底为我们做了什么?

    首先,网络释义:流是一个相对抽象的概念,所谓流就是一个传输数据的通道,这个通道可以传输相应类型的数据。进而完成数据的传输。这个通道被实现为一个具体的对象。

    品茗IT
  • Java进阶(二)当我们说线程安全时,到底在说什么

    这一点,跟数据库事务的原子性概念差不多,即一个操作(有可能包含有多个子操作)要么全部执行(生效),要么全部都不执行(都不生效)。

    Jason Guo
  • 当我们和业务在讨论“预测”时,到底在讨论什么?

    所谓“预测”,统计学上是有精确定义的:是对事物的发展趋势和在未来时期的数量表现做出推测和估计的理论和技术——它是一个概率结论。可是当你在百度上搜索“预测”这个关...

    张俊红
  • 当谈论面向对象的时候,我们到底在谈论什么

    面向对象编程的英文缩写是 OOP,全称是 Object Oriented Programming。对应地,面向对象编程语言的英文缩写是 OOPL,全称是 Obj...

    码农架构
  • Java进阶(二)当我们说线程安全时,到底在说什么

    Jason Guo
  • 当高端超级计算机退役时,他们到底都干了些什么?

    ORNL的Coury Turczyn讲述了诸如Titan之类的高端超级计算机在退役后会发生什么的不为人知的故事。

    GPUS Lady
  • 5. java 对象是如何创建的?new背后到底做了什么

    虚拟机遇到一条new指令时,首先将去检查这个指令的参数是否能在常量池中定位到一个类的符号引用,并且检查这个符号引用代表的类是否已被加载、解析和初始化过。如果没...

    源码之路
  • 万字长文:K8s 创建 pod 时,背后到底发生了什么?

    本文基于 2019 年的一篇文章 What happens when ... Kubernetes edition![1] 梳理了 K8s 创建 pod(及其 ...

    CNCF
  • HashMap源码解析

    在前几篇中我们主要介绍了ArrayList、LinkedList、Vector、Stack等集合的底层实现及相关特性,并且我们知道在上述集合类中无论底层是采用数...

    吉林乌拉
  • IdentityHashMap集合源码解析

    在这一篇中我们将介绍一下IdentityHashMap集合的相关知识。看名字我们知道IdentityHashMap集合底层是通过HashMap集合实现的。那么按...

    吉林乌拉
  • 深入理解JDK7 HashMap

    在正式讨论HashMap之前,我们有必要把Map家族的继承实现关系展示出来,方便理解后续的内容。

    itlemon
  • 【Java核心面试宝典】Day15、“Java容器”高频面试题总结!✊✊✊

    集合、数组这些内容都是我们日常开发最常用到的东西,但是其中有很多能够被面试官拿来当做考察点的内容你知道嘛?今天就和小伙伴们剖析一下在容器的相关内容中,都会有...

    灰小猿
  • 【Java面试总结】Java集合

    双向循环链表:最后一个节点的 next 指向head,而 head 的prev指向最后一个节点,构成一个环。

    Rochester
  • 这几道Java集合框架面试题在面试中几乎必问

    本文会同步更新在我开源的Java学习指南仓库 Java-Guide (一份涵盖大部分Java程序员所需要掌握的核心知识,正在一步一步慢慢完善,期待您的参与)中,...

    用户2164320
  • 机器学习到底能创造什么价值?我们精选了9位从业者的答案

    来源 | HackerNews 编译 | 晓查 不温不火的机器学习忽然蹿红业界,也就是这两三年的事,于是不仅传统行业,连风光一时的互联网公司也开始疑惑:我们要不...

    AI科技大本营
  • 这几道Java集合框架面试题在面试中几乎必问

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结...

    Java技术江湖
  • 这几道Java集合框架面试题在面试中几乎必问

    本文会同步更新在我开源的Java学习指南仓库 Java-Guide (一份涵盖大部分Java程序员所需要掌握的核心知识,正在一步一步慢慢完善,期待您的参与)中,...

    Java知音
  • 《求求大厂给个Offer》Map面试题

    我,三歪,最近开始写面试系列。我给这个面试系列取了一个名字,叫做《求求大厂给个Offer》

    Java3y

扫码关注云+社区

领取腾讯云代金券