泛泛读过几次,整体设计思路也大体了解,但长久不接触,触及一些细节代码时,还是陷入了思考泥潭,反省,应该存在细节盲点,又从整体和细节仔细品味了一番,记录。
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
单看hash方法很难理解,需要一起看indexFor方法,也就是hashmap的定位bucket方法。
static int indexFor(int h, int length) {
return h & (length-1);
}
为了追求快,hashmap的size为2的次方,定位因此可以简单高效地用位与运算,但些方法带来一个内部问题,对于超出length的hashcode, 高位不参与定位,所以所有高位相同的对象会被indexFor定位到一个bucket, hash方法的目的就是把高位的影响弄到低位,让高位也参与到定位,解决不至于所有低位相等的对象分到同一个bucket。
核心设计思路:hash要尽量均匀的打散数据分布。无论从应用层还是核心层。
碰撞概率大的话,hash不均,造成局部数过多,hash效率有O(n)的趋势。
虽然应用层出现低位相等,高位不同的对象的概率不大,但从架构层面上考虑,需要解决所有问题,你不能保证这种小概率事件不会出现,需要解决这种小概率事件,这就是hash方法的作用。
分享到:
相关推荐
HashMap源码深度剖析,面试必备
HashMap源码(JDK1.7,含注释)
HashMap的部分源码解析
一个delphi写的hashmap源代码, 包括TIntegerHashList, TStringHashList, TObjectHashList. 十万条记录查找只用 400毫秒.
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
hashmap源码,可以看看http://blog.csdn.net/wabiaozia/article/details/50684556
HashMap源码分析
HashMap源码流程图 一图解析HashMap源码流程 // 默认的HashMap中数组的长度 16 static final int DEFAULT_INITIAL_CAPACITY = 1 ; // aka 16 // HashMap中的数组的最大容量 static final int MAXIMUM_CAPACITY = 1 ...
主要hashMap源码,包括put,get等,其中将代码风格修改为更易懂的风格,注释也更简洁明了,可以帮助学习hashMap的同学更简单的学习hashMap
精确的版本号是jdk-7u80。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
精确的版本号是jdk-8u181。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
java代码-使用java解决手写hashMap的源代码 ——学习参考资料:仅用于个人学习使用!
HashMap之resize()方法源码解读,分两部分概述扩容方法涉及到的处理:创建新数组,将旧数组元素转移到新数组上
本人源码阅读理解, 基于jdk1.7 和jdk 1.8的java HashMap源码的理解, 希望对你理解java源码有作用
HashMap源码实现红黑树添加元素和删除元素
hashmap的底层及源码解析,很适合大家的学习,不要积分。
易语言源码易语言HashMap类源码.rar
HashMap源码剖析共10页.pdf.zip