资讯专栏INFORMATION COLUMN

HashMap源码分析(一):JDK源码分析系列

wdzgege / 831人阅读

摘要:当一个值中要存储到的时候会根据的值来计算出他的,通过哈希来确认到数组的位置,如果发生哈希碰撞就以链表的形式存储在源码分析中解释过,但是这样如果链表过长来的话,会把这个链表转换成红黑树来存储。

正文开始 注:JDK版本为1.8

HashMap1.8和1.8之前的源码差别很大

目录

简介

数据结构

类结构

属性

构造方法

增加

删除

修改

总结

1.HashMap简介

HashMap基于哈希表的Map接口实现,是以key-value存储形式存在。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)

HashMap 的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。在 JDK1.8 中,HashMap 是由 数组+链表+红黑树构成,新增了红黑树作为底层数据结构,结构变得复杂了,但是效率也变的更高效。

1.2 HashMap数据结构

在 JDK1.8 中,HashMap 是由 数组+链表+红黑树构成,新增了红黑树作为底层数据结构,结构变得复杂了,但是效率也变的更高效。当一个值中要存储到Map的时候会根据Key的值来计算出他的

hash,通过哈希来确认到数组的位置,如果发生哈希碰撞就以链表的形式存储在Object源码分析中解释过,但是这样如果链表过长来的话,HashMap会把这个链表转换成红黑树来存储。

来看依一下HashMap的存储结构

但是这样的话问题来了,HashMap为什么要使用红黑树呢,这样结构的话不是更麻烦了吗??

这个问题我也没有想过,其实很多在看的时候只会在乎红黑树的实现而忽略到了为什么要使用的这个问题,我也是在写本文的时候突发疑惑。参考了网上的例子,同时也解释了为什么阀值为8:

因为Map中桶的元素初始化是链表保存的,其查找性能是O(n),而树结构能将查找性能提升到O(log(n))。当链表长度很小的时候,即使遍历,速度也非常快,但是当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。至于为什么阈值是8,我想,去源码中找寻答案应该是最可靠的途径。

参考地址:https://dwz.cn/nPFXmXwJ

2.类结构

我们来看一下类结构

在阅读源码的时候一直有个问题很困惑就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口,那为什么HashMap还要在实现Map接口呢?同样在ArrayList中LinkedList中都是这种结构。

据 java 集合框架的创始人Josh Bloch描述,这样的写法是一个失误。在java集合框架中,类似这样的写法很多,最开始写java集合框架的时候,他认为这样写,在某些地方可能是有价值的,直到他意识到错了。显然的,JDK的维护者,后来不认为这个小小的失误值得去修改,所以就这样存在下来了。

Cloneable 空接口,表示可以克隆

Serializable 序列化

AbstractMap 提供Map实现接口

3.属性

初始化容量(必须是二的n次幂)

集合最大容量(必须是二的幂)

负载因子,默认的0.75

当链表的值超过8则会转红黑树(1.8新增)

当链表的值小于6则会从红黑树转回链表

当Map里面的数量超过这个值时,表中的桶才能进行树形化 ,否则桶内元素太多时会扩容,而不是树形化 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD

table用来初始化(必须是二的n次幂)

用来存放缓存

HashMap中存储的数量

用来记录HashMap的修改次数

用来调整大小下一个容量的值计算方式为(容量*负载因子)

哈希表的加载因子

重点属性

table 在JDK1.8中我们了解到HashMap是由数组加链表加红黑树来组成的结构其中table就是HashMap中的数组

Size 为HashMap中K-V的实时数量

loadFactor 加载因子,是用来衡量 HashMap 满的程度,计算HashMap的实时加载因子的方法为:size/capacity,而不是占用桶的数量去除以capacity。capacity 是桶的数量,也就是 table 的长度length。

threshold 计算公式:capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容),扩容后的 HashMap 容量是之前容量的两倍

4.构造方法

开始看构造方法。

4.1 HashMap()

构造一个空的 HashMap ,默认初始容量(16)和默认负载因子(0.75)。

4.2 HashMap(int initialCapacity)

构造一个空的 HashMap具有指定的初始容量和默认负载因子(0.75)。

4.3 HashMap(int initialCapacity, float loadFactor)

构造一个空的 HashMap具有指定的初始容量和负载因子。我们来分析一下。

最后调用了tableSizeFor,来看一下方法实现:

5.增加

现在我们开始分析put()方法

我们可以看到put调用的是putVal来进行数据插入,但是要注意到key在这里执行了一下hash()方法,来看一下Hash方法是如何实现的。

从上面可以得知HashMap是支持Key为空的,而HashTable是直接用过Key来获取HashCode所以key为空会抛异常其实上面就已经解释了为什么HashMap的长度为什么要是2的幂因为HashMap 使用的方法很巧妙,它通过 hash & (table.length -1)来得到该对象的保存位,前面说过 HashMap 底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当 length 总是2的n次方时,hash & (length-1)运算等价于对 length 取模,也就是 hash%length,但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)。

现在看putVal()方法,看看它到底做了什么。

主要参数:

hash key的hash值

key 原始Key

value 要存放的值

onlyIfAbsent 如果true代表不更改现有的值

evict 如果为false表示table为创建状态

完整源码分析,放图片的话会太长了,所以就截取了一下分为两部。

暂时分析到添加 ,首发乱敲代码公众号

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/75286.html

相关文章

  • HashSet源码分析:JDK源码系列

    摘要:简介继续分析源码,上一篇文章把的分析完毕。本文开始分析简单的介绍一下。存储的元素是无序的并且允许使用空的元素。 1.简介 继续分析源码,上一篇文章把HashMap的分析完毕。本文开始分析HashSet简单的介绍一下。 HashSet是一个无重复元素集合,内部使用HashMap实现,所以HashMap的特征耶继承了下来。存储的元素是无序的并且HashSet允许使用空的元素。 HashSe...

    用户83 评论0 收藏0
  • java源码

    摘要:集合源码解析回归基础,集合源码解析系列,持续更新和源码分析与是两个常用的操作字符串的类。这里我们从源码看下不同状态都是怎么处理的。 Java 集合深入理解:ArrayList 回归基础,Java 集合深入理解系列,持续更新~ JVM 源码分析之 System.currentTimeMillis 及 nanoTime 原理详解 JVM 源码分析之 System.currentTimeMi...

    Freeman 评论0 收藏0
  • JDK源码(容器篇)

    摘要:三系列用于保存键值对,无论是,还是已弃用的或者线程安全的等,都是基于红黑树。是完全基于红黑树的,并在此基础上实现了接口。可以看到,只有红黑树,且红黑树是通过内部类来实现的。 JDK容器 前言 阅读JDK源码有段时间了,准备以博客的形式记录下来,也方便复习时查阅,本文参考JDK1.8源码。 一、Collection Collection是所有容器的基类,定义了一些基础方法。List、Se...

    Soarkey 评论0 收藏0
  • HashMap源码分析JDK8)

    摘要:哈希表碰撞攻击就是通过精心构造数据,使得所有数据全部碰撞,人为将哈希表变成一个退化的单链表,此时哈希表各种操作的时间均提升了一个数量级,因此会消耗大量资源,导致系统无法快速响应请求,从而达到拒绝服务攻击的目的。 showImg(https://segmentfault.com/img/remote/1460000013650897); 前言 似乎所有的java面试或者考察都绕不开has...

    Muninn 评论0 收藏0
  • HashMap 源码详细分析(JDK1.8)

    摘要:则使用了拉链式的散列算法,并在中引入了红黑树优化过长的链表。如果大家对红黑树感兴趣,可以阅读我的另一篇文章红黑树详细分析。构造方法构造方法分析的构造方法不多,只有四个。 1.概述 本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap。HashMap 最早出现在 JDK 1.2中,底层基于散列算法实现。HashMap 允许 null 键和 null 值,在计算哈键的哈希值...

    monw3c 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<