HashMap

本贴最后更新于 2788 天前,其中的信息可能已经事过景迁

java.util.HashMap

一、特点
1、key 和 value 都允许为空,key 只允许有一个为 null。
2、无序(这个无序指的是遍历集合的时候取出元素的顺序基本不可能是 put 的顺序)。
3、线程不安全。

二、容量 Capacity 和负载因子 Load Factor
1 capacity 默认初始化容量为 16。
2 当 hashmap 中桶被装满的数量大于容量乘以负载因子的时候会进行 rehash。

三、put 方法
1 对 key 的哈希值做 hash,然后进行取余操作;
2 根据取余结果查找对应的桶,如果没碰撞直接插入;
3 如果碰撞,插入链表头部,当链表长度过长(默认是 8),就把链表转换成红黑树;
4 如果已经存在 key 相同的节点,就替换;
5 如果桶被装满的数量大于容量乘以负载因子,那么就会进行 rehash。

四、get 方法
1 根据 key 的哈希值做 hash,然后取余;
2 根据取余结果定位到具体的桶,然后通过 equals 方法逐个节点比较 key 是否相同直到找到节点或节点不存在。

五、hash(Object key)方法
1 key 为 null,直接返回 0;
2 根据 Object.hashCode()方法获取 key 的 hashcode;
3 然后这个 hashcode 的高 16 位不变,低 16 位和高 16 位做一个异或操作;(保证 32 位的 hashcode 都参与了后面的取余操作,降低碰撞几率)

取余操作,不是通过取余符号 %,而是通过按位与(&)运算。(位运算速度快)

六、rehash 死循环问题(JDK1.8 之前)
假设
oldTable[i]->node1->node2
rehash 为:
newTable[j]->node2->node1

e next = e.next e.next = newTable(i); newTable[i] = e; e = next

线程一执行了

e //node1 next = e.next //node2

然后失去 CPU。
线程二获得 CPU 并执行完 rehash,此时

newTable[j]->node2->node1

线程一又获得 CPU 了,因为变量 e 和 next 都是局部变量,属于线程私有,所以此时

e //node1 next = e.next //node2

执行了一个节点的插入后产生死循环

node1.next = node2; node2.next = node1;

这样 next 变量永远不可能为 null,循环就不会停止。

七、JDK1.8 resize 方法优化
每次扩容为之前的两倍,按位与的位数加 1,加的这一位只能为 0 或 1,0 的话结果不变,1 的话原位置 + 原容量。(省去重新计算 hash 的时间)。
JDK1.8 的链表元素不会倒置,因为设置了一个尾指针。

八、HashMap 的其他线程不安全问题
1 两个线程同时往同一个桶插入节点时,并发情况下会产生覆盖。

参考:
HashMap 源码
Java HashMap 工作原理及实现
Java 8 系列之重新认识 HashMap

相关帖子

回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • AngularJS

    AngularJS 诞生于 2009 年,由 Misko Hevery 等人创建,后为 Google 所收购。是一款优秀的前端 JS 框架,已经被用于 Google 的多款产品当中。AngularJS 有着诸多特性,最为核心的是:MVC、模块化、自动化双向数据绑定、语义化标签、依赖注入等。2.0 版本后已经改名为 Angular。

    12 引用 • 50 回帖 • 522 关注
  • 强迫症

    强迫症(OCD)属于焦虑障碍的一种类型,是一组以强迫思维和强迫行为为主要临床表现的神经精神疾病,其特点为有意识的强迫和反强迫并存,一些毫无意义、甚至违背自己意愿的想法或冲动反反复复侵入患者的日常生活。

    15 引用 • 161 回帖 • 1 关注
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    240 引用 • 224 回帖 • 1 关注
  • 思源笔记

    思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。

    融合块、大纲和双向链接,重构你的思维。

    26349 引用 • 109572 回帖
  • V2Ray
    1 引用 • 15 回帖 • 4 关注
  • OneDrive
    2 引用 • 4 关注
  • Electron

    Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖
  • OpenShift

    红帽提供的 PaaS 云,支持多种编程语言,为开发人员提供了更为灵活的框架、存储选择。

    14 引用 • 20 回帖 • 662 关注
  • Love2D

    Love2D 是一个开源的, 跨平台的 2D 游戏引擎。使用纯 Lua 脚本来进行游戏开发。目前支持的平台有 Windows, Mac OS X, Linux, Android 和 iOS。

    14 引用 • 53 回帖 • 563 关注
  • 电影

    这是一个不能说的秘密。

    123 引用 • 608 回帖
  • Access
    1 引用 • 3 回帖 • 3 关注
  • 黑曜石

    黑曜石是一款强大的知识库工具,支持本地 Markdown 文件编辑,支持双向链接和关系图。

    A second brain, for you, forever.

    25 引用 • 252 回帖
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 109 关注
  • 开源

    Open Source, Open Mind, Open Sight, Open Future!

    415 引用 • 3596 回帖
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 119 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 617 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 734 关注
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    173 引用 • 414 回帖 • 364 关注
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖
  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1062 引用 • 3455 回帖 • 150 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 643 关注
  • PWL

    组织简介

    用爱发电 (Programming With Love) 是一个以开源精神为核心的民间开源爱好者技术组织,“用爱发电”象征开源与贡献精神,加入组织,代表你将遵守组织的“个人开源爱好者”的各项条款。申请加入:用爱发电组织邀请帖
    用爱发电组织官网:https://programmingwithlove.stackoverflow.wiki/

    用爱发电组织的核心驱动力:

    • 遵守开源守则,体现开源&贡献精神:以分享为目的,拒绝非法牟利。
    • 自我保护:使用适当的 License 保护自己的原创作品。
    • 尊重他人:不以各种理由、各种漏洞进行未经允许的抄袭、散播、洩露;以礼相待,尊重所有对社区做出贡献的开发者;通过他人的分享习得知识,要留下足迹,表示感谢。
    • 热爱编程、热爱学习:加入组织,热爱编程是首当其要的。我们欢迎热爱讨论、分享、提问的朋友,也同样欢迎默默成就的朋友。
    • 倾听:正确并恳切对待、处理问题与建议,及时修复开源项目的 Bug ,及时与反馈者沟通。不抬杠、不无视、不辱骂。
    • 平视:不诋毁、轻视、嘲讽其他开发者,主动提出建议、施以帮助,以和谐为本。只要他人肯努力,你也可能会被昔日小看的人所超越,所以请保持谦虚。
    • 乐观且活跃:你的努力决定了你的高度。不要放弃,多年后回头俯瞰,才会发现自己已经成就往日所仰望的水平。积极地将项目开源,帮助他人学习、改进,自己也会获得相应的提升、成就与成就感。
    1 引用 • 487 回帖 • 4 关注
  • Office

    Office 现已更名为 Microsoft 365. Microsoft 365 将高级 Office 应用(如 Word、Excel 和 PowerPoint)与 1 TB 的 OneDrive 云存储空间、高级安全性等结合在一起,可帮助你在任何设备上完成操作。

    5 引用 • 34 回帖
  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息,资讯有时效性和地域性。

    56 引用 • 85 回帖
  • JRebel

    JRebel 是一款 Java 虚拟机插件,它使得 Java 程序员能在不进行重部署的情况下,即时看到代码的改变对一个应用程序带来的影响。

    26 引用 • 78 回帖 • 682 关注
  • CodeMirror
    2 引用 • 17 回帖 • 173 关注