运维开发网
广告位招商联系QQ:123077622
 
广告位招商联系QQ:123077622

2021-2-17:Java HashMap 的中 key 的哈希值是如何计算的,为何这么计算?

运维开发网 https://www.qedev.com 2021-02-19 08:09 出处:51CTO 作者:zhxdick
首先,我们知道HashMap的底层实现是开放地址法+链地址法的方式来实现。即数组+链表的实现方式,通过计算哈希值,找到数组对应的位置,如果已存在元素,就加到这个位置的链表上。在Java8之后,链表过长还会转化为红黑树。这个数组并不是一开始就很大,而是随着HashMap里面的值变多,达到LoadFactor的界限之后,就会扩容。刚开始的数组很小,默认只有16。这个数组大小一定是2的n次方,因为找到数

首先,我们知道 HashMap 的底层实现是开放地址法 + 链地址法的方式来实现。

2021-2-17:Java HashMap 的中 key 的哈希值是如何计算的,为何这么计算?

即数组 + 链表的实现方式,通过计算哈希值,找到数组对应的位置,如果已存在元素,就加到这个位置的链表上。在 Java 8 之后,链表过长还会转化为红黑树。

这个数组并不是一开始就很大,而是随着 HashMap 里面的值变多,达到 LoadFactor 的界限之后,就会扩容。刚开始的数组很小,默认只有 16。

这个数组大小一定是 2 的 n 次方,因为找到数组对应的位置需要通过取余计算,取余计算是一个很耗费性能的计算,而对 2 的 n 次方取余就是对 2 的 n 次方减一取与运算。所以保持数组大小为 2 的 n 次方,这样就可以保证计算位置高效。

那么这个哈希值究竟是怎么计算的呢?假设就是用 Key 的哈希值直接计算。假设有如下两个 key,哈希值分别是:

key1:

0000 0000 0010 1111 1001 0000 0110 1101

key2:

0000 0000 0010 0000 1001 0000 0110 1101

如果直接使用数组默认大小,取余之后 key1 与 key2 就会到数组同一个下标。其实 key1 和 key2 的高位是不一样的。

由于数组是从小到达扩容的,为了优化高位被忽略这个问题,HashMap 源码中对于计算哈希值做了优化,采用高位16位组成的数字与源哈希值取异或而生成的哈希值作为用来计算 HashMap 的数组位置的哈希值

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么要用异或?首先,对于一个数字,转换成二进制之后,其中为的 1 的位置代表这个数字的特性.对于异或运算,如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。0与0异或是0,0与1异或是1,这样相当于让高位的特性在低位得以体现,所以采用这种算法,减少碰撞。

微信搜索“我的编程喵”关注公众号,每日一刷,轻松提升技术,斩获各种offer:

2021-2-17:Java HashMap 的中 key 的哈希值是如何计算的,为何这么计算?

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消