hashmap底层原理

hashmap是由数组+链表构成的,在数组里面嵌套了链表,链表使用的结构为头插法。链表里面可以放多个entry即key, value防止冲突。#Java工程师面试常考题##学习路径#
全部评论
https://zhuanlan.zhihu.com/p/76735726
1 回复
分享
发布于 2021-05-17 03:43
两个常用的方法:hashmap.put和get
点赞 回复
分享
发布于 2021-05-17 03:09
阅文集团
校招火热招聘中
官网直投
hashmap的默认初始长度为16,每次自动扩展或者手动扩展时,长度必须是2的幂
点赞 回复
分享
发布于 2021-05-17 03:11
对于HashMap,我们最常使用的是两个方法:Get 和 Put。 1.Put方法的原理 调用Put方法的时候发生了什么呢? 比如调用 hashMap.put("apple", 0) ,插入一个Key为“apple"的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置(index): index = Hash(“apple”)
点赞 回复
分享
发布于 2021-05-17 03:14
如何实现一个尽量均匀分布的Hash函数呢?我们通过利用Key的HashCode值来做某种运算。 位运算的方式实现:(Length是HashMap的长度): index = HashCode(Key) & (Length - 1)
点赞 回复
分享
发布于 2021-05-17 03:16
下面我们以值为“book”的Key来演示整个过程: 1.计算book的hashcode,结果为十进制的3029737,二进制的101110001110101110 1001。 2.假定HashMap长度是默认的16,计算Length-1的结果为十进制的15,二进制的1111。 3.把以上两个结果做与运算,101110001110101110 1001 & 1111 = 1001,十进制是9,所以 index=9。 可以说,Hash算法最终得到的index结果,完全取决于Key的Hashcode值的最后几位。
点赞 回复
分享
发布于 2021-05-17 03:18
如果不是2的幂,会导致不均匀。只要是2的幂,并且保证hashcode是均匀分布的,那么得出的结果就是均匀的
点赞 回复
分享
发布于 2021-05-17 03:20
第一:当length为2的N次方的时候,h & (length-1) = h % length 为什么&效率更高呢?因为位运算直接对内存数据进行操作,不需要转成十进制,所以位运算要比取模运算的效率更高 第二:当length为2的N次方的时候,数据分布均匀,减少冲突 此时我们基于第一个原因进行分析,此时hash策略为h & (length-1)。
点赞 回复
分享
发布于 2021-05-17 03:34
https://mp.weixin.qq.com/s/-xFSHf7Gz3FUcafTJUIGWQ
点赞 回复
分享
发布于 2021-05-17 03:42

相关推荐

6 13 评论
分享
牛客网
牛客企业服务