HashMap位运算你可知一二
我们平时在写代码过程中用的位运算操作比较少，因为我们更关注于可读性而不是性能，如果为了性能而使用较多的位运算，我想我们的同事会疯掉。但在框架里位运算却非常常见，因为框架的性能是我们关注的点。下面就来一起回顾一下常见的位运算操作：
<< : 左移运算符，num << 1,相当于num乘以2 低位补0 >> : 表示右移，如果该数为正，则高位补 0，若为负数，则高位补 1。 >>> : 表示无符号右移，也叫逻辑右移，即若该数为正，则高位补 0，而若该数为负数，则右移后高位同样补 0。 % : 模运算 取余 ^ : 位异或 第一个操作数的的第n位于第二个操作数的第n位相反，那么结果的第n为也为1，否则为0 & : 与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0 | : 或运算 第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1，那么结果的第n为也为1，否则为0 ~ : 非运算 操作数的第n位为1，那么结果的第n位为0，反之，也就是取反运算（一元操作符：只操作一个数） 复制代码
HashMap的hash函数算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码
此时我们心中会有两个疑惑：
- 为什么要无符号右移 16 位后做异或运算
- key 本身的 hashCode 直接拿来用不行吗
来看这样一个例子：
将 h 无符号右移 16 为相当于将高区 16 位移动到了低区的 16 位，再与原 hashcode 做异或运算，可以看作是 将高低位二进制特征混合起来 。
从上图中可以看出，高位的 16 位与原 hashcode 相比没有发生变化，低位的 16 位发生了变化。
上面的 (h = key.hashCode ()) ^ (h >>> 16) 进行运算后，可以把高区与低区的二进制特征混合到低区，那么为什么要这么做呢？
我们要知道，上面计算出来的hashcode值接下来要参与到hashmap中数组槽位的计算，其计算公式是：(n - 1) & hash，现在假设数组槽位大小是16，那么槽位计算过程如下：
观察可以看出，如果我们不做刚才移位异或运算，那么在计算槽位时将丢失高区特征。也许你可能会说，即使丢失了高区特征，不同 hashcode 也可以计算出不同的槽位来，但是细想当两个哈希码很接近时，那么这高区的一点点差异就可能导致一次哈希碰撞，所以这也是将性能做到极致的一种体现。
为什么要采用异或运算
异或运算能更好的保留各部分的特征，如果采用 & 运算计算出来的值会向 1 靠拢，采用 | 运算计算出来的值会向 0 靠拢。
为什么槽位数必须使用 2^n
这里假设槽位数不是 16，而是 17，那么槽位计算公式就变成：(17 - 1) & hash。
可以看出计算结果将会大大趋同，hashcode 参加 & 运算后被更多位的 0 屏蔽，计算结果只剩下两种，分别是0 和 16，这对于 hashmap 来说是一种灾难。
总结
HashMap当中运用了很多精巧的位运算操作，这对于提高性能有很大帮助，更多的，很多的优化点，最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升 hashmap 的运行效率。
参考文章
[1] https://zhuanlan.zhihu.com/p/149583558 [2] https://juejin.im/entry/5e1a960d5188254c257c38e5 [3] https://www.jianshu.com/p/eb9ab4211163 复制代码
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
