【夯实Java基础】(五)轻松掌握 HashMap 源码

简介: 【夯实Java基础】(五)轻松掌握 HashMap 源码

文章目录


引子

图解 HashMap 的数据结构

详细分析 HashMap 源码的代码


引子


计算机中如果存储数据的话,我们该怎么办?

数据在计算机中存储的一个方式/结构(数据结构)

如果我们对 HashMap 底层的数据结构都搞清楚,那应该能有助于我们看懂源码。


数据结构?? 数组、链表、树形、图形


20191205144639112.png


图解 HashMap 的数据结构


Key,value---------------------> HashMap 的数据结构应该比较吊

我们可以大胆的猜测 HashMap 应该是将 数组和链表的优势结合起来

数组+链表的形式 -----------> HashMap 的数据结构 jdk1.8 红黑树


20191205150939986.png


紫色部分即代表哈希表本身(其实是一个数组),数组的每个元素都是一个单链表的头节点,链表是用来解决hash地址冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中保存。


详细分析 HashMap 源码的代码


数组的表示:Node table[]


20191205151753799.png


默认初始容量为16


20191205151941173.png


20191205152121843.png


数组的大小可能会不够用 扩大


问题是? 什么时候进行扩大? 数组16已经用到16的时候再扩大呗?


从感性层面和理性层面来看,我们可以看到 16*0.75=12 数组扩大的一个标准


Java是面向对象的,从上图的双向链表来看,我们可以猜测用代码实现双向链表大概如下:

class Node{
    Object data;
    Node prev;
    Node next;
  }


这在LinkedList源码中得到验证。


20191205145456794.png


链表的长度不能无限大,怎么叫做一个上限?

链表和红黑树之间的转变----------> 相对适合它们各自效率的一个节点


20191205153103285.png


20191205153223509.png


记录一下数组使用格子的数量


size=0 size++


20191205153454242.png


来了一个 key,value 组成了 Node 节点后, 这个节点到底该何去何从?


数组的大小 16

Random.next(16) 0-15

如果落点的算法仅仅是这样的话,就未免太low了

数组的 16 个位置要充分利用其中的 12 个


----------------------------->


生成出一个算法 hash 算法

(1) Int

Key,value -----------------------> key Object ------------------>key.hashCode()

32434535(一个哈希值) hash


(2) 0-15 数组的大小范围

Hash%16 0-15


(3) 尽可能充分利用数组的每一个位置


20191205164232671.png


到了这里,我对 Node 节点的属性都已了然于心。


继续看源码,数组先进行了初始化:

Node[] table = new Node[16];

Resize() 功能 是可以对数组进行初始化操作


20191205164755411.png


把数组的默认大小 和 16*0.75


20191205164936673.png


threshold = 12


20191205165059326.png


(1) 数组原本的位置为空

(2) 数组原本的位置不为空,且下面是链表结构


20191205184014869.png


(3) 数组原本的位置不为空,且下面是红黑树结构


20191205173701919.png


n-1{15} & hash <------------------------ > hash % n{16} 0-15


20191205183055274.png


Key.hashCode() 高16位和16位进行异或运算,这样结果才能尽可能不同


20191205183240834.png


20191205153454242 (1).png


Resize() 数组的初始化操作 数组的扩容的操作


20191205185226386.png


Double 2 倍 为什么是两倍进行扩大数组呢??


20191205190854523.png


16 ------> 32

12 ------> 24


20191205191515940.png


为什么下面还要有代码呢??


因为节点不要总是赖在原来的数组中,也要往新的数组中移动。(重新散列)


老数组进行判断,如果下面是空,进行重新hash 得到一个新的位置


20191205191757161.png


如果为0,保持在原来的位置不动

如果不为0,加上原来的capacity

Hash n-1


1.8 中实现了

TreeNode Parent left right

Treelfy_Threshold 8 超过了这个8 链表----红黑树

Put 判断链表的长度


目录
相关文章
|
3月前
|
存储 安全 Java
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
58 3
|
3月前
|
XML Java 编译器
Java注解的底层源码剖析与技术认识
Java注解(Annotation)是Java 5引入的一种新特性,它提供了一种在代码中添加元数据(Metadata)的方式。注解本身并不是代码的一部分,它们不会直接影响代码的执行,但可以在编译、类加载和运行时被读取和处理。注解为开发者提供了一种以非侵入性的方式为代码提供额外信息的手段,这些信息可以用于生成文档、编译时检查、运行时处理等。
90 7
|
4月前
|
Java
Java之HashMap详解
本文介绍了Java中HashMap的源码实现(基于JDK 1.8)。HashMap是基于哈希表的Map接口实现,允许空值和空键,不同步且线程不安全。文章详细解析了HashMap的数据结构、主要方法(如初始化、put、get、resize等)的实现,以及树化和反树化的机制。此外,还对比了JDK 7和JDK 8中HashMap的主要差异,并提供了使用HashMap时的一些注意事项。
158 2
Java之HashMap详解
|
4月前
|
数据采集 人工智能 Java
Java产科专科电子病历系统源码
产科专科电子病历系统,全结构化设计,实现产科专科电子病历与院内HIS、LIS、PACS信息系统、区域妇幼信息平台的三级互联互通,系统由门诊系统、住院系统、数据统计模块三部分组成,它管理了孕妇从怀孕开始到生产结束42天一系列医院保健服务信息。
63 4
|
14天前
|
存储 缓存 安全
Java HashMap详解及实现原理
Java HashMap是Java集合框架中常用的Map接口实现,基于哈希表结构,允许null键和值,提供高效的存取操作。它通过哈希函数将键映射到数组索引,并使用链表或红黑树解决哈希冲突。HashMap非线程安全,多线程环境下需注意并发问题,常用解决方案包括ConcurrentHashMap和Collections.synchronizedMap()。此外,合理设置初始化容量和加载因子、重写hashCode()和equals()方法有助于提高性能和避免哈希冲突。
48 17
Java HashMap详解及实现原理
|
4月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
141 2
|
2天前
|
Java 调度
【源码】【Java并发】【线程池】邀请您从0-1阅读ThreadPoolExecutor源码
当我们创建一个`ThreadPoolExecutor`的时候,你是否会好奇🤔,它到底发生了什么?比如:我传的拒绝策略、线程工厂是啥时候被使用的? 核心线程数是个啥?最大线程数和它又有什么关系?线程池,它是怎么调度,我们传入的线程?...不要着急,小手手点上关注、点赞、收藏。主播马上从源码的角度带你们探索神秘线程池的世界...
25 0
【源码】【Java并发】【线程池】邀请您从0-1阅读ThreadPoolExecutor源码
|
17天前
|
JavaScript 安全 Java
智慧产科一体化管理平台源码,基于Java,Vue,ElementUI技术开发,二开快捷
智慧产科一体化管理平台覆盖从备孕到产后42天的全流程管理,构建科室协同、医患沟通及智能设备互联平台。通过移动端扫码建卡、自助报道、智能采集数据等手段优化就诊流程,提升孕妇就诊体验,并实现高危孕产妇五色管理和孕妇学校三位一体化管理,全面提升妇幼健康宣教质量。
45 12
|
21天前
|
人工智能 监控 安全
Java智慧工地(源码):数字化管理提升施工安全与质量
随着科技的发展,智慧工地已成为建筑行业转型升级的重要手段。依托智能感知设备和云物互联技术,智慧工地为工程管理带来了革命性的变革,实现了项目管理的简单化、远程化和智能化。
35 4
|
2月前
|
JavaScript Java 测试技术
基于Java+SpringBoot+Vue实现的车辆充电桩系统设计与实现(系统源码+文档+部署讲解等)
面向大学生毕业选题、开题、任务书、程序设计开发、论文辅导提供一站式服务。主要服务:程序设计开发、代码修改、成品部署、支持定制、论文辅导,助力毕设!
67 6

热门文章

最新文章