网站首页 > 知识剖析 正文
HashMap是基于哈希表的数据结构实现的集合。底层是由一个Node数组构成的,在jdk1.8之后采用数组+(链表或红黑树)的方式实现。
transient Node[] table
node数组的长度在初始化或者扩容(resize)时会被指定,无论怎么变,数组长度始终都是2的n次方。
为什么要是2的n次方?
key在table中的定位是由(length - 1) & hash确定的,length为数组的长度。因为length是2的n次方,所以length-1的二进制肯定是11111....11的形式,此时length-1和hash进行&运算时不会有空间的浪费,且位运算效率很高。假设length不是2的次幂,比如length为15,则 length-1为14,二进制为1110,和hash进行&操作,最后一位都为0,增加了碰撞,使得一些空间被浪费。
总结就是这样做可以减少哈希冲突,均匀分布元素,从代码上来说就是按位“与”的时候,每一位都能&1。
如何保证是2的n次方的?
1)初始化指定容量时,通过tableSizeFor方法返回一个目标容量的2次幂的值(如果目标容量值不是2的n次方,就会返回一个大于该目标值的最小二次幂,如cap为10则返回16)。
2)扩容即resize()得到的新数组长度也是2的n次方。实际数组初始化也是首次put值时通过resize方法完成的。
扩容得到的新数组的长度newCap有三处赋值,可以看到都是2的n次幂。对应图中:1是通过位运算扩容为原长度的2倍;2是hashmap初始化时指定的;3是默认值16。
这里源码中还有个小细节的处理,就是hash()对key的处理并不是只取hashcode。可以说每一个细节都在尽可能的优化,存在必有其原因。
- 上一篇: C语言字符数组和字符串
- 下一篇: C# 基础知识系列- 3 集合数组
猜你喜欢
- 2025-03-11 C语言sizeof()、strlen()、string的length()和size()的用法
- 2025-03-11 C# 基础知识系列- 3 集合数组
- 2025-03-11 C语言字符数组和字符串
- 2025-03-11 JUC并发—8.并发安全集合一
- 2025-03-11 大话C语言:数组
- 2025-03-11 你会喜欢的新数组方法:array.at(index)
- 2025-03-11 数组-一文搞定前缀和数组
- 2025-03-11 灵魂拷问:如何检查 Java 数组中是否包含某个值?
- 2025-03-11 Java中怎样将bytes转换为long类型?
- 2025-03-11 2022-05-06:给你一个整数数组 arr,请你将该数组分隔为长度最多
- 最近发表
-
- jQuery EasyUI使用教程:创建展开行详细编辑表单的CRUD应用
- CSDN免登陆复制代码的几种方法(csdn扫码登录怎么实现的)
- LayUi提高-Select控件使用(layui form select)
- 用 Playwright MCP 让 AI 改它自己写的屎山代码
- multiple-select.js中手动设置全选和取消全选
- 前端实现右键自定义菜单(html 自定义右键菜单)
- JavaScript脚本如何断言select下拉框的元素内容?
- 广州蓝景分享—实用的CSS技巧,助你成为更好的前端开发者
- MyBatis-Plus码之重器 lambda 表达式使用指南,开发效率瞬间提升80%
- Go语言之select的使用和实现原理(go select case)
- 标签列表
-
- xml (46)
- css animation (57)
- array_slice (60)
- htmlspecialchars (54)
- position: absolute (54)
- datediff函数 (47)
- array_pop (49)
- jsmap (52)
- toggleclass (43)
- console.time (63)
- .sql (41)
- ahref (40)
- js json.parse (59)
- html复选框 (60)
- css 透明 (44)
- css 颜色 (47)
- php replace (41)
- css nth-child (48)
- min-height (40)
- xml schema (44)
- css 最后一个元素 (46)
- location.origin (44)
- table border (49)
- html tr (40)
- video controls (49)