理解HashMap(jdk8)[通俗易懂]

理解HashMap(jdk8)

大家好,又见面了,我是你们的朋友全栈君。

HashMap 数据结构

616953-20160304192851940-1880633940.png

 图中的 “table” 在 HashMap 中是一个 Node<K,V> 数组 。HashMap 内部数据结构是由数组链表树形结构组合而成的。

 

什么是hash?

 百度百科:hash 一般被翻译为 “散列”, 也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

wikipedia : 

哈希函数 : 哈希函数就是能将任意长度的数据映射为固定长度的数据的函数。哈希函数返回的值被叫做哈希值、哈希码、散列,或者直接叫做哈希。一个使用场景就是哈希表,哈希表被广泛用于快速搜索数据。

哈希表:哈希表是一种能实现关联数组的抽象数据结构,能把很多「键」映射到很多「值」上。哈希表使用哈希函数来计算索引,一个索引对应一个值。

 

HashMap 初始化

// initialCapacity 初始化容量大小
// loadFactor 负载因子
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // threshold 是HashMap是否要进行扩容的标记量
        this.threshold = tableSizeFor(initialCapacity);
    }

initialCapacity , loadFactor  这两个参数都影响着HashMap的性能。initialCapacity 决定了下一次 resize 后的容量(capacity << 1) ,  loadFactor  决定了 resize 发生的条件 (size > (capacity * loadFactor )) (一般情况下 , 极端情况下是 size > Integer.MAX_VALUE) 。如果初始化时不指定这两个参数,会使用默认值 , capacity  = 16 , loadFactor  = 0.75 。对于 16 的容量空间,如果不能充分利用的话会造成空间资源的浪费。(个人认为高手之所以高都体现在细节之中)

 

散列过程

散列的过程就是将存入的元素均匀的分布到HashMap内部Node数据的过程。均匀分布指的是 , 数组中的每个位置尽量都存储了一个Node节点,并且该位置上的链表只有一个元素。散列分布的越均匀进行碰撞检测的次数就越少,查询性能就越高。

这就是一个散列较为均匀的 , 查询时最好情况下可以直接定位 , 最坏情况下需要进行一次碰撞检测。

理解HashMap(jdk8)[通俗易懂]

 

这是一个散列的不均匀的,查询时会进行多次碰撞检测造成效率较低。

理解HashMap(jdk8)[通俗易懂]

 

碰撞检测

((capacity – 1) & hash) 会计算出 key 存储在 Node 数组中的那个位置上 (得到的值始终会落在 Node数组的长度范围内 , 等同于 hash % capacity  , 不过位运算的效率更高), 如果发现该位置上已经存在Node 了,会将新存入的数据作为链表的尾节点。这样存储和查询时都会进行碰撞检测。碰撞检测其实就是比较传入的 key 的 hash 与同一 bucket 上所有的 key 的 hash 是否一致的过程。 jdk8 在这方面做了优化,加入了树型结构来弥补链表线性结构性能较低的不足。

提高碰撞检测的性能 , 从代码中也能看出来  , 该运算的最理想情况(hash 相等情况下)是执行两步 , 比较 hash , 比较 key 。 最坏情况是执行 4 步 , 只要取最好情况就达到了提高性能的目的 。以此类推 key 就可以用一些 String , Enum 这之类的数据类型。

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) {
  // .......
}

 

reszie

rezise 是一个较为消耗性能的过程 , 在首次向HashMap中存入元素的时候会进行首次resize ,  在之后每当产生新节点(这里的节点指的是Node) , 同时 size > threshold 的时候会进行 resize ,resize 的过程也是 rehash 的过程。本篇尽量不分析源码只是做整体的,概念上的了解。

 

并发安全

HashMap 是不支持并发的 , 在并发修改时它采用 fail-fast 的策略 , 抛出 ConcurrentModificationException 。 多线程环境下操作HashMap有可能会造成死循环 , 在 resize 的过程当中。不要在多线程场景下使用HashMap 。

转载于:https://my.oschina.net/j4love/blog/1797058

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107573.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 基于ZigBee和STM32的智能家居控制系统的设计与实现(五)–终结篇

    基于ZigBee和STM32的智能家居控制系统的设计与实现(五)–终结篇说明首先祝贺自己顺利的完成了毕业答辩工作,想起整个过程还是挺让自己感动的。最后还被评为优秀毕业设计,虽然并没有什么luan用,但是,马上毕业了,还是挺让人怀念的。整个资料从第一篇博客说起就说会全部开源的,期间承蒙各位朋友的支持,给与资助,在此感谢了。虽然资料中私人信息删除了一些,但是不免有疏漏,所以有关个人信息还挺各位删除掉,小

  • IP地址范围怎么算_ip地址数目怎么算

    IP地址范围怎么算_ip地址数目怎么算1、如果掩码、IP等信息如下:2、我们可以看到,子网掩码为255.255.255.240,因为0-255有256个数字,所以256-240=16。也就是这个网段有16个IP地址。3、我们现在使用的IP地址是什么,或者是网关,最后的一个数字就好。IP是203,网关是193。4、找到IP段就能判断可用IP是多少。这时因为每个IP段都是由四部分组成,分别是网络号、网关、可用IP、广播号。…

    2022年10月19日
  • java 异或加密_Java异或技操作给任意的文件加密原理及使用详解

    java 异或加密_Java异或技操作给任意的文件加密原理及使用详解异或简单介绍:异或是一种基于二进制的位运算,用符号XOR或者^表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。简单理解就是不进位加法,如1+1=0,,0+0=0,1+0=1。需求描述在信息化时代对数据进行加密是一个很重要的主题,在做项目的过程中,我也实现了一个比较复杂的加密算法,但是由于涉及到的技术是保密的,所以在这里我实现一个比较简单的版本,利用文件的输入输出流和异或操…

  • maven镜像还有不支持发型版本5

    maven镜像还有不支持发型版本5maven镜像<mirror> <id> alimaven </id> <mirrorOf> central </mirrorOf> <name> aliyunmaven </name> <url> http://maven.aliyun.com/nexus/content/repositories/central/ </u

  • pytest的使用_实例调用和类调用

    pytest的使用_实例调用和类调用Pytest执行用例规则Pytest在命令行中支持多种方式来运行和选择测试用例1.对某个目录下所有的用例pytest2.对模块中进行测试pytesttest_mod.py3.对文件夹进行

  • Linux 的 sendfile[通俗易懂]

    Linux 的 sendfile[通俗易懂]作者:DraganStancevic,2003-01-01原文地址:http://www.linuxjournal.com/article/6345译者:Love.Katherine,2007-03-25译文地址:http://blog.csdn.net/lovekatherine/archive/2007/03/25/1540291.aspx如今几乎每个人都听说过Li

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号