hashmap底层原理
hashmap是由数组+链表构成的，在数组里面嵌套了链表，链表使用的结构为头插法。链表里面可以放多个entry即key, value防止冲突。#Java工程师面试常考题##学习路径#
2021-05-17 03:08 四川大学 Java
关注
全部评论
蜗牛20191023145836 楼主
楼主 四川大学 Java
https://zhuanlan.zhihu.com/p/76735726
蜗牛20191023145836 楼主
楼主 四川大学 Java
两个常用的方法:hashmap.put和get
蜗牛20191023145836 楼主
楼主 四川大学 Java
hashmap的默认初始长度为16，每次自动扩展或者手动扩展时，长度必须是2的幂
蜗牛20191023145836 楼主
楼主 四川大学 Java
对于HashMap，我们最常使用的是两个方法：Get 和 Put。 1.Put方法的原理 调用Put方法的时候发生了什么呢？ 比如调用 hashMap.put("apple", 0) ，插入一个Key为“apple"的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）： index = Hash（“apple”）
蜗牛20191023145836 楼主
楼主 四川大学 Java
如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。 位运算的方式实现:（Length是HashMap的长度）： index = HashCode（Key） & （Length - 1）
蜗牛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值的最后几位。
蜗牛20191023145836 楼主
楼主 四川大学 Java
如果不是2的幂，会导致不均匀。只要是2的幂，并且保证hashcode是均匀分布的，那么得出的结果就是均匀的
蜗牛20191023145836 楼主
楼主 四川大学 Java
第一：当length为2的N次方的时候，h & (length-1) = h % length 为什么&效率更高呢？因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高 第二：当length为2的N次方的时候，数据分布均匀，减少冲突 此时我们基于第一个原因进行分析，此时hash策略为h & (length-1)。
蜗牛20191023145836 楼主
楼主 四川大学 Java
https://mp.weixin.qq.com/s/-xFSHf7Gz3FUcafTJUIGWQ
相关推荐
点赞 评论 收藏
分享
投递阿里巴巴等公司10个岗位
查看10道真题和解析
