原创

3秒种搞定HashMap

JDK1.8

总结

定位元素

HashMap定位元素位置是通过键key经过扰动函数扰动后得到hash值,然后再通过hash(key) & (length - 1)代替取模的方式进行元素定位的。

负载因子

HashMap的负载因子表示哈希表空间的使用程度(或者说是哈希表空间的利用率)。当负载因子越大,则HashMap的装载程度就越高。也就是能容纳更多的元素,元素多了,发生hash碰撞的几率就会加大,从而链表就会拉长,此时的查询效率就会降低。当负载因子越小,则链表中的数据量就越稀疏,此时会对空间造成浪费,但是此时查询效率高。

扩容

resize()主要做两件事:2倍扩容与拷贝



1.7

 头插法,多线程情况下会造成死循环

1.8

 尾插法,无法保证上一次put的值,下一秒还是原值

树化条件

链表长度超过8

数组长度大于等于64

  原因:

  链表长度大于8的时候就会调用treeifyBin方法转化为红黑树,但是在treeifyBin方法内部却有一个判断,当只有数组长度大于64的时候,才会进行树形化,否则就只是resize扩容。因为链表过长而数组过短,会经常发生hash碰撞,这个时候树形化其实是治标不治本,因为引起链表过长的根本原因是数组过短。执行树形化之前,会先检查数组长度,如果长度小于 64,则对数组进行扩容,而不是进行树形化

0.75 16 8 64

0.75

  提高空间利用率和减少查询成本的折中,主要是泊松分布,0.75的话碰撞最小



16

  理论上2的幂都行,但是如果是2,4或者8会不会有点小,添加不了多少数据就会扩容,也就是会频繁扩容,这样岂不是影响性能,如果是32或者更大,浪费空间了空间,所以16就作为一个非常合适的经验值保留了下来



2的幂

 

 1.服务位运算

  如果length为2的次幂  则length-1 转化为二进制必定是11111……的形式,位运算要比算数运算快

 2.均匀散列

  奇数的最后一位为1,这样便保证了h&(length-1)的最后一位为0,也可能为1(这取决于h的值),即与后的结果可能为偶数也可能是奇数。这样便可以保证散列的均匀性,

  而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间。所以,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。



8

          \* 0:    0.60653066

          \* 1:    0.30326533

          \* 2:    0.07581633

          \* 3:    0.01263606

          \* 4:    0.00157952

          \* 5:    0.00015795

          \* 6:    0.00001316

          \* 7:    0.00000094

          \* 8:    0.00000006

    如果 hashCode的分布离散良好的话,那么红黑树是很少会被用到的,因为各个值都均匀分布,很少出现链表很长的情况。在理想情况下,链表长度符合泊松分布,各个长度的命中概率依次递减,注释中给我们展示了1-8长度的具体命中概率,当长度为8的时候,概率概率仅为0.00000006,这么小的概率,HashMap的红黑树转换几乎不会发生,因为我们日常使用不会存储那么多的数据,你会存上千万个数据到HashMap中吗?当然,这是理想的算法,但不妨某些用户使用HashMap过程导致hashCode分布离散很差的场景,这个时候再转换为红黑树就是一种很好的退让策略。



 64

 

   链表长度大于8的时候就会调用treeifyBin方法转化为红黑树,但是在treeifyBin方法内部却有一个判断,当只有数组长度大于64的时候,才会进行树形化,否则就只是resize扩容。因为链表过长而数组过短,会经常发生hash碰撞,这个时候树形化其实是治标不治本,因为引起链表过长的根本原因是数组过短。执行树形化之前,会先检查数组长度,如果长度小于 64,则对数组进行扩容,而不是进行树形化

  

图解

数组+链表+红黑树

思考

以HashMap为例,重写equals方法的时候需要重写hashCode方法呢?

    两个对象 equals() 返回 true 的时候,那它们的 hashCode() 值需要相等;

    如果两个对象的 hashCode() 值相等,那它们 equals() 不一定是 true;(哈希冲突)

    所以在这种情况下,如果要判断两个对象是否相等,除了要覆盖 equals() ,也要覆盖 hashCode(),否则就会发生意料之外的问题。

看到这里就点个赞吧?分享更多技术文章,去帮助更多的人,这里有我所有知识库哟~

https://www.yuque.com/yingwenerjie

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

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

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3秒搞定ConcurrentHashMap

    1、ConcurrentHashMap,是Java并发包中自JDK1.5后提供的一个线程安全且高效的HashMap实现,可以用来替代HashTable。直接实现...

    老兵程序员
  • 3秒搞定ArrayList

    底层是一个Object[],添加到ArrayList中的数据保存在了elementData属性中。

    老兵程序员
  • Spring Boot 启动,1 秒搞定!

    原文: dev.to 翻译: ImportNew.com - 唐尤华 译文: http://www.importnew.com/30647.html

    Java技术栈
  • 【译文】epoll() 3步搞定

    并不久远之前,设置单个Web服务器以支持10,000个并发连接还是一项伟大的壮举。有许多因素使开发这样的Web服务器成为可能,例如nginx,它比以前的服务器可...

    袁承兴
  • 2年java,蚂蚁一面,卒

    其实我一个都没答上来。并不是因为我笨,是因为我不会。在大扰的帮助下,现在我会了,求求你再给我一个机会。

    美的让人心动
  • 2年java,蚂蚁一面,卒

    作为程序员,我也希望做一枚运营狗。可惜并没多少时间,所以每到过节都发水文。端午快乐。

    xjjdog
  • 一文搞定HashMap的实现原理和面试

    HashMap在日常开发中基本是天天见的,而且都知道什么时候需要用HashMap,根据Key存取Value,但是存和取的时候那些操作却是很少去研究。同时在面试中...

    秃头哥编程
  • 一文搞定HashMap的实现原理和面试

    HashMap在日常开发中基本是天天见的,而且都知道什么时候需要用HashMap,根据Key存取Value,但是存和取的时候那些操作却是很少去研究。同时在面试中...

    Java_老男孩
  • 一文搞定HashMap的实现原理和面试

    HashMap在日常开发中基本是天天见的,而且都知道什么时候需要用HashMap,根据Key存取Value,但是存和取的时候那些操作却是很少去研究。同时在面试中...

    美的让人心动
  • 海量数据相似度计算之simhash短文本查找

    在前一篇文章 《海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力。但是随着业务的增长 simhash的数据...

    smy
  • 3个案例秒懂,大数据是如何搞定用户交易画像的

    如何构建用户交易画像? 基于交易行为,我们可以依据 3 个关键指标进行用户分群。 1. 流失风险。看每个用户上一次交易距今的时间,上次交易距今时间越远流失风险越...

    BestSDK
  • Stackoverflow上人气最旺的10个Java问题

    我一直认为Java是引用传递;然而,我看了一堆博客(例如这篇)声称不是这样的。我认为我没有理解它们之间的区别。

    哲洛不闹
  • Stackoverflow上人气最旺的10个Java问题

    我一直认为Java是引用传递;然而,我看了一堆博客(例如这篇)声称不是这样的。我认为我没有理解它们之间的区别。

    哲洛不闹
  • Hutool工具类

    一个 Java 基础工具类,对文件、流、加密解密、转码、正则、线程、XML 等 JDK 方法进行封装,组成各种 Util 工具类,同时提供以下组件:

    java后端指南
  • 3. 搞定收工,PropertyEditor就到这

    上篇文章介绍了PropertyEditor在类型转换里的作用,以及举例说明了Spring内置实现的PropertyEditor们,它们各司其职完成 String...

    YourBatman
  • 如何对flv视频进行压缩,3种方法教你搞定

    很多人都喜欢在有无线网的情况下,喜欢把自己爱看的电视剧,综艺,电影,这些都给缓存下来,慢慢看,但是理想是美好的,现实很骨感,当你下载的过程中,发现视频还没下载完...

    高效办公
  • 通过欧拉计划学Rust编程(第650题)

    由于研究Libra等数字货币编程技术的需要,学习了一段时间的Rust编程,一不小心刷题上瘾。

    申龙斌
  • 3分钟搞定图片懒加载

    图片的懒加载就是在页面打开的时候,不要一次性全部显示页面所有的图片,而是只显示当前视口内的图片,一般在移动端使用(PC端主要是前端分页或者后端分页)。

    Daotin
  • 3步搞定GWAS中的Gene Set Analysis

    GWAS中的Gene Set Analysis, 简称GSA分析,是从基因或者通路水平来进行关联分析,是建立在SNP水平的的GWAS分析结果基础上的,在更高的层...

    生信修炼手册

扫码关注云+社区

领取腾讯云代金券