哈尔滨专业做网站,绵阳住房和城乡建设厅官方网站,太原西北建设有限公司网站,海口网站建设推广HashMap的hash函数#xff08;1.8#xff09;
首先1.7的是四次扰动#xff0c;1.8做了优化。 简单的说就是对key做hashCode操作#xff0c;然后将得到的32为散列值向右位移16位#xff0c;再与hashCode做异或计算。实质上是把一个数的低16位与他的高16位做异或运算。
st…HashMap的hash函数1.8
首先1.7的是四次扰动1.8做了优化。 简单的说就是对key做hashCode操作然后将得到的32为散列值向右位移16位再与hashCode做异或计算。实质上是把一个数的低16位与他的高16位做异或运算。
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}
首先 h key.hashCode()是key对象的一个hashCode每个不同的对象其哈希值都不相同其实底层是对象的内存地址的32位的散列值h 16的意思是将hashcode右移16位然后高位补0然后再与(h key.hashCode()) 异或运算得到最终的h值。 为什么是异或运算呢 当然我们知道目的是为了让h的低16位更有散列性但为什么是异或运算就更有散列性呢而不是与运算或者或运算呢这里我自己证明一下为什么异或就能够得到更好散列性。
先来看一下下面的这组运算
【与运算 100, 000, 010 都等于0 111 3次0,1次1】
【或运算 101, 111, 011 都等于1 000 3次1,1次0】
【异或运算 000, 110而另外011, 101 2次1,2次0】 上面是将0110和0101分别进行与、或、异或三种运算得到不同的结果我们主要来看计算的过程 与运算其中111其他三种情况100, 000, 010 都等于0可以看到与运算的结果更多趋向于0这种散列效果就不好了运算结果会比较集中在小的值 或运算其中000其他三种情况 101, 111, 011 都等于1可以看到或运算的结果更多趋向于1散列效果也不好运算结果会比较集中在大的值 异或运算其中000, 110而另外011, 101 可以看到异或运算结果等于1和0的概率是一样的这种运算结果出来当然就比较分散均匀了 总的来说与运算的结果趋向于得到小的值或运算的结果趋向于得到大的值异或运算的结果大小值比较均匀分散这就是我们想要的结果这也解释了为什么要用异或运算因为通过异或运算得到的h值会更加分散进而 h (length-1)得到的index也会更加分散哈希冲突也就更少。
为什么使用 hash (length - 1) 作为数组的寻址算法 首先我们如果把数据存在一个数组中我们会使用数组中的值hash % length取模操作为每个值寻找存在数组中的位置但是这种取模的操作性能不是很好比起位运算差远了后来发现当数组的容是2的n次方的时候hash (length - 1) hash % length所以就使用hash (length - 1) 来替代取模运算这样操作效率高而且数据均匀分布hash碰撞少。
使用hash (length - 1) 作为寻址算法也是jdk1.8的优化。
寻址算法的优化使用与运算替代取模提升性能。
那为什么要用数组值的hash值的高16与它的低16做异或呢 首先我们的寻址算法优化了是使用hash (length - 1) 假设我们不适用新的优化后的hash算法我们就直接使用数组中的值的hashcode不使用高16与低16做异或因为n-1的值通常是很小的n-1通常高16为都是0那么这个hash的高16为和n-1做与运算hash的高16位就不起作用了就相当于与之与两个都是低16位的值做与预算而我们的目的就是为了hash更加散列很少甚至不起hash冲突。所以如果使用hash值的高16与低16做异或让他的低16为同时保持了高低16为的特征尽量避免了hash冲突。
HashMap的容量为什么建议是2的幂次方
关键就在于把当前数据存放到哪一个桶中这个算法就是取模运算。
假设
lengthHashMap的容量
hash当前key的哈希值
取模运算为 hash % length 但是在计算机中直接取模运算的效率不如位运算什么是位运算就是对于二进制数据的按位运算1和1才得1其他都得0比如1011 1100 1000 sun公司的大牛们发现当容量为2的n次方时hash (length - 1) hash % length 于是就在源码中做了优化通过 hash (length - 1) 来替代取模运算而前提就是容量必须为2的n次方。这样做的好处在于
1. 提高操作运算效率位运算效率 取模运算效率
2. 减少碰撞数据均匀分布提高HashMap查询效率
为什么可以减少碰撞举个例子现在两个hash分别是2和3,
比如 length 为 9 的情况3(9-1)0 2(9-1)0 都在0上碰撞了
比如 length 为 8 的情况3(8-1)3 2(8-1)2 不同位置上不碰撞
为什么不采用AVL树或B树B树
红黑树和AVL树都是最常用的平衡二叉搜索树。
但是两者之间有些许不同 AVL树更加严格平衡因此可以提供更快的査找效果。因此对于查找密集型任务使用AVL树没毛病。 但是对于插入密集型任务红黑树要好一些。
通常AVL树的旋转比红黑树的旋转更难实现和调试。
红黑树更通用再添加删除来说表现较好AVL虽能提升一些速度但是代价太大了。
而不用B/B树的原因 B和B树主要用于数据存储在磁盘上的场景比如数据库索引就是用B树实现的。这两种数据结构的特点就是树比较矮胖每个结点存放一个磁盘大小的数据这样一次可以把一个磁盘的数据读入内存减少磁盘转动的耗时提高效率。而红黑树多用于内存中排序也就是内部排序。 为什么树化阈值是8为什么树退化为链表的阈值是6 根据泊松分布。当我们计算的哈希冲突到了8次概率就非常小了可以看到当链表长度为8时候的概率为千万分之6概率极低。所以取该值作为树化阈值。
