专栏首页Java学习ING*HashMap实现原理及源码学习(JDK 1.8.0)*
原创

*HashMap实现原理及源码学习(JDK 1.8.0)*

*HashMap实现原理及源码学习(JDK 1.8.0)*

说明:

(1)笔者对于红黑树还比较懵懂,故在此不做过多解析。

(2)对于HashMap的源码,也只是部分学习。(如有错误之处,欢迎指正)

一、前言部分注释

图-1.1

译>:HashMap的实例有两个影响其性能的参数——“初始容量initial capacity”和“负载因子load factor”,容量指的是哈希表中桶(buckets)的数目,初始容量即为创建哈希表时桶的数目;负载因子是衡量哈希表在自动扩容之前的填充程度的度量,即当哈希表中的条目数超过(负载因子与当前容量的乘积)时,哈希表将会自动扩容为原来桶数目的2倍,然后将已有数据进行重新映射(即内部数据结构将被重建)。

图-1.2

译>:通常,默认负载因子为0.75,该值在时间和空间成本之间提供了很好的折中,较高的值会减少空间开销,但同时会增加查找成本。设置初始容量时,应考虑映射中的预期条目数和负载因子,以最大程度地减少重新哈希操作的数量,如果,初始容量大于预期条目数除以负载因子(即 初始容量*负载因子 > 预期条目数),则不会发生任何重新哈希的操作。

图-1.3

译>:如果要在HashMap的实例中存储许多映射,则创建具有足够大容量的哈希表比让其根据需要自动扩容进行重新哈希操作更有效地存储映射。(使用许多具有相同{@code hashCode()}的键是降低任何哈希表性能的原因之一,为了改善影响,当键为{@link Comparable}时,此类可以使用键之间的比较顺序帮助打破这种局面。)

图-1.4

译>:由此类(HashMap)提供的所有“集合视图方法”(如keySet(),valueSet(),entrySet())返回的迭代器都为“<i>fail-fast</i>”,即:如果在创建迭代器后的任何时间对Map进行结构修改(结构修改是添加或删除一个或多个映射的任何操作;仅更改与实例已经包含的键相关联的值不是结构修改。),除了通过迭代器本身的 <tt>remove</tt>方法,迭代器将抛出异常 {@link ConcurrentModificationException}。因此,面对(同步)并发修改,迭代器会快速干净地失败操作,不会冒任意不确定行为的风险。(迭代器的快速失败行为仅用于检测错误,不能用于保证正确性。)

二.HashMap的内部实现机制

1.HashMap基本属性

图-2.1.1

注:使用无参构造new一个HashMap实例的时候,系统会默认指定初始容量为16(2的4次方),当然我们也可以通过有参构造自己指定初始容量大小,但必须是2的次幂(且小于等于2的30次方)。同样,也可以在有参构造中指定负载因子,如果不指定则为默认值0.75。(由于迭代遍历所需的时间与桶的数量以及键值映射对的数量成正比,因此如果迭代性能很重要,则不要将初始容量设置过大(负载率过低))

图-2.1.2
图-2.1.3

注:如图所示,Node<K,V>是HashMap的一个内部类,它既是HashMap底层数组的组成元素,又是每个链表的组成元素,其中包括了数组元素所需要的key和value,以及链表元素所需要的next域,hash值是系统在创建Node时通过一定的算法计算出来的int值。

图-2.1.4

注:key不为null时,先调用hashCode(),然后右移16位进行按位异或运算(后面会有进一步的介绍)

图-2.1.5

注:关于tableSizeFor(int cap)中这个精巧的算法,请看https://blog.csdn.net/dagelailege/article/details/52972970

图-2.1.6

*更正:threshold表示数组的扩容阈值(即 当前容量*当前负载因子),并非数组容量。

2.HashMap的构造函数

注:JDK1.8中,HashMap提供了4种构造函数

图-2.2.1

3.HashMap的常用方法

图-2.3.1
图-2.3.2
图-2.3.3
图-2.3.4
图-2.3.5
图-2.3.6
图-2.3.7
图-2.3.8
图-2.3.9

注:对于HashMap的 put 功能实现和扩容操作将单独分析。

4.HashMap的 put 功能具体实现

图解来源:https://www.cnblogs.com/xawei/p/6747660.html

图-2.4.1

源码如下:

图-2.4.2

注:

第1步:

判断table是否为空,若为空,则调用resize()方法进行扩容,实现对数组的初始化,这一点和JDK 1.7有所不同,JDK 1.7是在HashMap的构造函数中进行初始化(即定义的时候),此处是在进行第一次put操作时初始化,可理解为“懒加载”,即用到了才进行初始化。

第2步:

计算元素所要存储的位置,并进行合理添加

图-2.4.3

可以看到,首先将得到key对应的哈希值:【h = key.hashCode()】,然后通过hashCode()的高16位与低16位异或【(h = k.hashCode()) ^ (h >>> 16)】,最后进行取模运算【(n - 1) & hash】得到最终的索引位置。

*>> hashCode()方法是Object类的方法,返回的是对象的经过处理后的内存地址,由于每个对象的内存地址都不一样,所以哈希码也不一样。这个是native方法,取决于JVM的内部设计,一般是某种C地址的偏移。

*>> 关于高16位与低16位异或:在JDK1.8的实现中,优化了高位运算的算法,主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

*>> 关于取模运算:这个n是table的长度,那么(n - 1)就是table数组元素应有的下标。这个方法非常巧妙,它通过hash & (table.length -1)来得到该对象的存储位置,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,hash & (length - 1) 运算等价于对length取模,也就是hash % length,但是 & 比 % 具有更高的效率。

具体解释请看下图:

来源:https://www.jianshu.com/p/17177c12f849

图-2.4.4

第3步:

判断是否超过最大容量,若超过则进行扩容操作。(下面具体介绍扩容)

5.扩容机制的实现

源码如下:

图-2.5.1

关于链表重排的过程,请耐心看下图:

来源:https://www.jianshu.com/p/17177c12f849

图-2.5.2

三、其他内容(推荐几篇笔者认为挺好的他人博客)

1.HashMap底层实现原理及面试问题

https://blog.csdn.net/suifeng629/article/details/82179996

2.HashMap源码分析——基于jdk1.8

https://www.cnblogs.com/developer_chan/p/10481558.html

3.HashMap线程不安全的体现

首先需要强调一点,HashMap的线程不安全体现在会造成死循环、数据丢失、数据覆盖这些问题。其中死循环(迁移数据使用头插法导致环形链表)和数据丢失是在JDK1.7中出现的问题,在JDK1.8中已经得到解决(迁移数据使用尾插法),然而1.8中仍会有数据覆盖这样的问题。

https://www.cnblogs.com/developer_chan/p/10450908.html

4.哈希表&哈希碰撞&解决办法

https://blog.csdn.net/hotchange/article/details/80159671

5.面试必备:HashMap/HashTable/ConcurrentHashMap的原理与区别

https://www.cnblogs.com/heyonggang/p/9112731.html

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • *LinkedList实现原理及源码学习(JDK 1.8.0)*

    (1)继承自抽象类AbstractSequentialList(而AbstractSequentialList又继承自AbstractList);

    一半是我
  • *ArrayList实现原理及源码学习(JDK 1.8.0)*

    (5)实现了Serializable接口,并重写了序列化和反序列化方法,使得ArrayList拥有更好的序列化性能。

    一半是我
  • 其他篇之操作系统——进程管理

    (2)不考虑缓存情况,CPU能且只能对内存进行读写,不能访问外设(输入输出设备);

    一半是我
  • 远程桌面链接内网服务器(外网和内网)详细介绍

    编程软文
  • 基于空间矢量的机器人动力学建模与对比分析

    普通的矢量属于3D矢量,即每个3D矢量是由空间的三个标量表示,举例来说,空间的某个位置矢量是由三个XYZ轴的标量值得到,空间的力矢量是力在XYZ轴的标量值合成,...

    ZC_Robot机器人技术
  • bootstrap3 js

    用户5760343
  • 机器人模块化关节:电机空间矢量控制SVPWM技术

    交流永磁同步电动机由定子、转子及位置传感器构成。定子为三相对称正弦绕组结构,转子贴有多对磁性体,多对磁极导致了电机的电角度与机械角度的倍数关系,位置传感器一般为...

    ZC_Robot机器人技术
  • Vue cli 资源文件的引用 原

          assets下含有image , js ,css3个文件, 分别放各个资源文件

    tianyawhl
  • 聊一聊战神这款游戏

    (《游戏机实用技术》《掌机王SP》原编辑;《东东不死传说》作者;现就职于“腾讯光子工作室群”)

    江西恐龙
  • 2013 移动行业数据分析报告(终端篇)

    2013年移动大战全面打响,从终端、行业到用户,都经历了翻天覆地的变化。 今天开始,大讲堂将一连三天跟大家独家分享由腾讯移动分析新鲜出炉的【2013移动行业分析...

    腾讯大讲堂

扫码关注云+社区

领取腾讯云代金券