hashmap底层原理

hashmap是由数组+链表构成的，在数组里面嵌套了链表，链表使用的结构为头插法。链表里面可以放多个entry即key, value防止冲突。#Java工程师面试常考题##学习路径#

全部评论

推荐最新楼层

蜗牛20191023145836

楼主

四川大学 Java

https://zhuanlan.zhihu.com/p/76735726

2 回复分享

发布于 2021-05-17 03:43

蜗牛20191023145836

楼主

四川大学 Java

https://mp.weixin.qq.com/s/-xFSHf7Gz3FUcafTJUIGWQ

点赞回复分享

发布于 2021-05-17 03:42

蜗牛20191023145836

楼主

四川大学 Java

第一：当length为2的N次方的时候，h & (length-1) = h % length 为什么&效率更高呢？因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高第二：当length为2的N次方的时候，数据分布均匀，减少冲突此时我们基于第一个原因进行分析，此时hash策略为h & (length-1)。

点赞回复分享

发布于 2021-05-17 03:34

蜗牛20191023145836

楼主

四川大学 Java

如果不是2的幂，会导致不均匀。只要是2的幂，并且保证hashcode是均匀分布的，那么得出的结果就是均匀的

点赞回复分享

发布于 2021-05-17 03:20

蜗牛20191023145836

楼主

四川大学 Java

下面我们以值为“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

蜗牛20191023145836

楼主

四川大学 Java

如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。位运算的方式实现:（Length是HashMap的长度）： index = HashCode（Key） & （Length - 1）

点赞回复分享

发布于 2021-05-17 03:16

蜗牛20191023145836

楼主

四川大学 Java

对于HashMap，我们最常使用的是两个方法：Get 和 Put。 1.Put方法的原理调用Put方法的时候发生了什么呢？比如调用 hashMap.put("apple", 0) ，插入一个Key为“apple"的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）： index = Hash（“apple”）

点赞回复分享

发布于 2021-05-17 03:14

蜗牛20191023145836

楼主

四川大学 Java

hashmap的默认初始长度为16，每次自动扩展或者手动扩展时，长度必须是2的幂

点赞回复分享

发布于 2021-05-17 03:11

蜗牛20191023145836

楼主

四川大学 Java

两个常用的方法:hashmap.put和get