理解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)


相关推荐

  • Java中XML运用总结

    Java中XML运用总结XML 简介:可扩展标记语言(eXtensibleMarkupLanguage)。特性:1.xml具有平台无关性,是一门独立的标记语言.2.xml具有自我描述性为什么学习XML?1.网络数据传输.2.数据存储3.配置文件XML文件.XML文件是保存XML数据的一种方式XML数据也可以以其他的方式存在(如在内存中构建XML数据)。不要将XML语言狭隘的理解成XML文件。XML语法格式1.XML文档声明<?xmlversio..

  • 如何更改linux文件目录拥有者及用户组

    如何更改linux文件目录拥有者及用户组

    2021年10月19日
  • 角色权限表怎么设计_用户角色权限在数据库表中怎样实现

    角色权限表怎么设计_用户角色权限在数据库表中怎样实现设计一个灵活、通用、方便的权限管理系统。      在这个系统中,我们需要对系统的所有资源进行权限控制,那么系统中的资源包括哪些呢?我们可以把这些资源简单概括为静态资源(功能操作、数据列)和动态资源(数据),也分别称为对象资源和数据资源,后者是我们在系统设计与实现中的叫法。系统的目标就是对应用系统的所有对象资源和数据资源进行权限控制,比如应用系统的功能菜单、各个界面的按钮、数据显示的列以

  • c语言的单片机delay延时函数详解

    c语言的单片机delay延时函数详解c语言及单片机delay延时函数延时函数1、是什么2、为什么3、用在哪里?4、怎么做1、循环延时延时函数延时函数,作为一种常用函数,在不同的领域有不同的用处。而在嵌入式以及C语言的编写中,我们常常遇到需要自己来编写延时函数的情况,这种情况之下,了解其原理就显得必要。1、是什么简单来说,延时函数的目的就在于等,实际上就是要等一段时间再来执行接下来的代码。而这种简单的等,又可以采用多种方法来实现。例如:名称描述循环采用for或者while循环,让计算机跑无用的代码,从而达到延时的

  • Linux下使用rm删除文件,并排除指定文件(亲测可行)[通俗易懂]

    Linux下使用rm删除文件,并排除指定文件(亲测可行)

  • mybatis 缓存的使用, 看这篇就够了「建议收藏」

    mybatis 缓存的使用, 看这篇就够了「建议收藏」缓存的重要性是不言而喻的。使用缓存,我们可以避免频繁的与数据库进行交互,尤其是在查询越多、缓存命中率越高的情况下,使用缓存对性能的提高更明显。mybatis也提供了对缓存的支持,分为一级缓存和二级缓存。但是在默认的情况下,只开启一级缓存(一级缓存是对同一个SqlSession而言的)。以下的项目是在mybatis初步使用(IDEA的Maven项目,超详细)的基础上进行。…

发表回复

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

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