JAVA进阶之HashMap底层实现解析

首先我们来通过下面的图看看JDK1.7时代的HashMap是如何通过数组+链表的形式进行值储存的。

由图中的描述可以清楚地看出来,当数组第一次被定义并且第一次被赋值的时候,这个时候的操作很简单,就是将这个值赋值到我们的table数组上面去。这个操作完成以后,然后我们进行二次put:

如图左下角描述所示的情况,当数组table下标出现了相等的情况的时候,此时此刻还是将肝铁侠2的值赋值给tablle[i]的,这里讲述的是JDK1.7版本下HashMap中插入的头插法,而JDK1.8版本中是用的尾插法。插入以后,我们要让数组指向链表的头部,那么链表的头部也就是头节点是不是就是table[i]的位置呀。

如上,最终插入完成以后的模型就是这样的:

那我们此时此刻是不是就可以大胆地猜测,在HashMap中,使用map.get(“name”)获取到它的value的时候,是不是就是通过int hash = “name”.hashcode,然后获取到对应table下的数组下标int i = hash % table.length获取到table[i]的具体位置的链表,然后再通过hash去对应table[i]上的链表中找到对应的值呢?

有了这个思维,我们再去看HashMap的源码就会轻松许多许多。下一期为大家带来HashMap的手动实现。

再顺带两个基本的关于HashMap的问题:

HashMap底层是怎么实现的呢?

在JDK1.7中是通过数组+链表实现的。JDK1.8中是通过数组+链表+树(红黑树)组成的。

为什么要用链表呢?

①HashMap数组元素为链表的时候,插入直接使用头插,插入复杂度O(1),即操作的数量为常数,与输入的数据的规模无关,效率是非常快的;当链表较短时候,查找数据时对性能并没有什么影响,但是如果链表一长,查找起来就很影响性能了。

②在Java8中,如果链表长度到达了8个,就会转化为红黑树,提高了查找的性能,但每次插入新的数据,都得维护红黑树的结构,复杂度为O(log n)。其实算是对查找和插入元素时性能的一个权衡,毕竟存入的效果就是用来查询的。

这个问题的答案不唯一,可以自行了解一下。

以上就是JAVA进阶之HashMap底层实现解析的详细内容,更多关于HashMap底层实现的资料请关注我们其它相关文章!

(0)

相关推荐

  • HashMap底层实现原理详解

    一.快速入门 示例:有一定基础的小伙伴们可以选择性的跳过该步骤 HashMap是Java程序员使用频率最高的用于映射键值对(key和value)处理的数据类型.随着JDK版本的跟新,JDK1.8对HashMap底层的实现进行了优化,列入引入红黑树的数据结构和扩容的优化等.本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的数据结构实现和功能原理. Java为数据结构中的映射定义了一个接口java.uti.Map,此接口主要有四个常用的实现类,分别是HashMap,LinkedHas

  • Java LinkedHashMap 底层实现原理分析

    在实现上,LinkedHashMap很多方法直接继承自HashMap,仅为维护双向链表覆写了部分方法.所以,要看懂 LinkedHashMap 的源码,需要先看懂 HashMap 的源码. 默认情况下,LinkedHashMap的迭代顺序是按照插入节点的顺序.也可以通过改变accessOrder参数的值,使得其遍历顺序按照访问顺序输出. 这里我们只讨论LinkedHashMap和HashMap的不同之处,LinkedHashMap的其他操作和特性具体请参考HashMap 我们先来看下两者的区别:

  • JAVA进阶之HashMap底层实现解析

    首先我们来通过下面的图看看JDK1.7时代的HashMap是如何通过数组+链表的形式进行值储存的. 由图中的描述可以清楚地看出来,当数组第一次被定义并且第一次被赋值的时候,这个时候的操作很简单,就是将这个值赋值到我们的table数组上面去.这个操作完成以后,然后我们进行二次put: 如图左下角描述所示的情况,当数组table下标出现了相等的情况的时候,此时此刻还是将肝铁侠2的值赋值给tablle[i]的,这里讲述的是JDK1.7版本下HashMap中插入的头插法,而JDK1.8版本中是用的尾插法

  • java进阶解析Springboot上传excel存入数据库步骤

    目录 一.导入依赖 二.前端实现 三.后台逻辑 三.页面效果 四.可能会遇到的问题 一.导入依赖 这里还是用了Apache的POI插件,现在一般的springboot解析excel基本都用它 . <!-- 文件上传,解析文件需要的依赖--> <!--poi对excel2007以上版本的支持--> <dependency> <groupId>org.apache.poi</groupId> <artifactId>poi-ooxml&l

  • Java同步关键字synchronize底层实现原理解析

    目录 1 字节码层实现 1.1 InterpreterRuntime::monitorenter 1.1.1 函数参数 JavaThread *thread 1.1.2 函数体 2 偏向锁 2.1 偏向锁的意义 2.2 偏向锁的获取 2.2.1 markOop mark = obj->mark() 2.2.2 判断mark是否为可偏向状态 2.2.3 判断mark中JavaThread的状态 2.2.4 通过CAS原子指令 2.2.5 如果执行CAS失败 2.3 偏向锁的撤销 2.4 轻量级锁

  • java 中的HashMap的底层实现和元素添加流程

    目录 HashMap 底层实现 HashMap 插入流程 为什么要将链表转红黑树? 哈希算法实现 总结 前言: HashMap 是使用频率最高的数据类型之一,同时也是面试必问的问题之一,尤其是它的底层实现原理,既是常见的面试题又是理解 HashMap 的基石,所以重要程度不言而喻. HashMap 底层实现 HashMap 在 JDK 1.7 和 JDK 1.8 的底层实现是不一样的,在 JDK 1.7 中,HashMap 使用的是数组 + 链表实现的,而 JDK 1.8 中使用的是数组 + 链

  • SpringBoot整合log4j日志与HashMap的底层原理解析

    一,SpringBoot与日志 1.springboot整合log4j日志记录 1.在resources目录下面创建日志文件,并引入: 代码如下(示例): #log4j.rootLogger=CONSOLE,info,error,DEBUG log4j.rootLogger=info,error,CONSOLE,DEBUG log4j.appender.CONSOLE=org.apache.log4j.ConsoleAppender log4j.appender.CONSOLE.layout=o

  • Java进阶之FileUpload完成上传的实例

     Java进阶之FileUpload完成上传的实例 FileUpload是Apache commons下面的一个子项目,用来实现Java项目下的文件上传功能,常见的文件上传还有SmartUpload,Servlet3.0,Struts2. 在这里我用的是commons- fileupload-1.2.1,下面就是一个简单实例,解析过程都写到代码中的注释上了,注释很详细 //创建磁盘文件项工厂 DiskFileItemFactory diskFileItemFactory=new DiskFile

  • Java中迭代器Iterator的使用解析

    什么是迭代器 在Java中,有很多的数据容器,对于这些的操作有很多的共性.Java采用了迭代器来为各种容器提供了公共的操作接口.这样使得对容器的遍历操作与其具体的底层实现相隔离,达到解耦的效果. 在Iterator接口中定义了三个方法: Java集合类中Map接口下的相关类并没有像Collection接口的相关类一样实现get()方法,因此在要实现遍历输出的场景中没法直接用get()方法来取得对象中的数据,但Java本身提供了另一种遍历数据的方法,即用Iterator迭代器,虽然Iterator

  • 基于Java并发容器ConcurrentHashMap#put方法解析

    jdk1.7.0_79 HashMap可以说是每个Java程序员用的最多的数据结构之一了,无处不见它的身影.关于HashMap,通常也能说出它不是线程安全的.这篇文章要提到的是在多线程并发环境下的HashMap--ConcurrentHashMap,显然它必然是线程安全的,同样我们不可避免的要讨论散列表,以及它是如何实现线程安全的,它的效率又是怎样的,因为对于映射容器还有一个Hashtable也是线程安全的但它似乎只出现在笔试.面试题里,在现实编码中它已经基本被遗弃. 关于HashMap的线程不

  • Java进阶之高并发核心Selector详解

    一.Selector设计 笔者下载得是openjdk8的源码, 画出类图 比较清晰得看到,openjdk中Selector的实现是SelectorImpl,然后SelectorImpl又将职责委托给了具体的平台,比如图中框出的 linux2.6以后才有的EpollSelectorImpl Windows平台是WindowsSelectorImpl MacOSX平台是KQueueSelectorImpl 从名字也可以猜到,openjdk肯定在底层还是用epoll,kqueue,iocp这些技术来实

  • java进阶之了解SpringBoot的配置原理

    一.Spring Boot的特点 首先我们要知道 Spring Boot 在底层已经为我们添加好了很多依赖.比如我们常用的Tomcat,Spring,SpringMVC这些,甚至连mysql数据库的依赖也为我们添加好了 不过 SpringBoot 2.5.0 使用的mysql依赖版本是8.0.25的,如果还在使用 mysql 5 版本的小伙伴们就需要在项目的 pom.xml 文件中再次指定自己所用的依赖版本号.(因为 maven 在引入依赖时采取就近原则,你如果指定了依赖版本号的话,它会加载离它

随机推荐