亲宝软件园·资讯

展开

深入探究HashMap二次Hash原因

程序员小潘 人气:0

1. 前言

HashMap对于Java程序员来说一定不陌生,除了平时开发会经常使用外,它也是面试官非常喜欢问的一个知识点。HashMap是哈希表的一个经典实现,底层数据结构是数组+链表,在JDK8中还引入了红黑树,以解决链表线性查找的效率问题。HashMap设计的非常优秀,源码两千多行,有很多可以拿出来讨论的点,本篇文章主要分析HashMap二次哈希的目的。

2. 哈希码的作用

首先,我们得先了解哈希码的作用是什么?HashMap底层采用数组+链表/红黑树的数据结构来存储键值对的映射关系,数组就是若干个哈希槽Solt,HashMap会通过Key算出的哈希码来计算下标Index,Index决定了键值对应该落在哪个槽里。不同的哈希码算出相同的下标Index,就会导致哈希碰撞,一旦发生哈希碰撞,HashMap的查找效率就会从O(1)退化成O(n)或者O(logn)。所以,一个好的哈希函数应该要尽可能的分散,否则就会影响到HashMap的效率。

3. 二次Hash

我们已经知道,HashMap会根据哈希码计算下标,哈希码的分散性越好,HashMap的效率也就越高。我们先看一下HashMap计算下标的过程,就知道它为啥要做二次Hash了。

static int indexFor(int h, int length) {
    return h & (length-1);
}

上面是HashMap根据二次Hash计算出的哈希码,计算键值对下标的代码,length是底层数组的长度。HashMap采用了位运算,而非我们常见的取模运算,这里你可以先略过,它俩的效果是一样的。

我们先来看看如果不做二次Hash的情况下,会出现什么问题。现在,我假设数组长度为16,那么当哈希码为5时,下标Index结果是5。

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

当哈希码为65541时,下标Index结果依然是5,不同的哈希码算出相同的下标,哈希碰撞了。

 00000000000000010000000000000101
&00000000000000000000000000001111
=00000000000000000000000000001101
=5

从这个与运算的过程,大家肯定也都发现了,就是哈希码的高位压根就没有参与运算,全部被丢弃了。不管哈希码的高位是多少,都不会影响最终Index的计算结果,因为只有低位才参与了运算,这样的哈希函数我们认为是不好的,它会带来更多的冲突,影响HashMap的效率。

如何解决这个问题呢?最简单的办法就是让高位也参与到运算,高位不一样也会导致最终的Index结果不一样,减少哈希碰撞的概率。事实上,HashMap也就是这么做的,下面是HashMap做二次Hash的源码:

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

HashMap通过将哈希码的高16位与低16位进行异或运算,得到一个新的哈希码,这样就可以让高位也参与到运算,这个函数也被称作「扰动函数」。

我们用同样的哈希码,来看看经过二次Hash后的哈希码,是否会带来不一样的效果。
仍然假设数组长度为16,那么当哈希码为5时,下标Index是5,结果不变。

 0000000000000101
^0000000000000000
=0000000000000101

 00000000000000000000000000000101
&00000000000000000000000000001111
=00000000000000000000000000000101
=5

当哈希码为65541时,下标Index结果是4,竟然没有发生哈希碰撞。

 0000000000000101
^0000000000000001
=0000000000000100

 00000000000000010000000000000100
&00000000000000000000000000001111
=00000000000000000000000000000100
=4

可以看到,HashMap通过加入一个扰动函数,让原本会发生碰撞的两个哈希码,不再冲突。

4. 为啥右移16位

HashMap的扰动函数,是拿高16位和低16位做异或运算,把高位的特征和地位的特征组合起来,以此来降低哈希碰撞的概率。为啥是16位?而不是8位或24位或其它位?

根据哈希码计算下标Index的过程,大家也发现了。实际上,只有数组长度以内的低位才会参与运算。例如数组长度是16,那么只有低4位会参与计算;如果数组长度是256,那么只有低8位会参与计算;如果数组长度是65536,那么只有低16位会参与计算。HashMap取16位是一个折中的数字,绝大部分情况下,HashMap数组的长度都不会超过65536。

5. 总结

HashMap底层采用数组+链表/红黑树来存储键值对,会根据Key的哈希码来计算键值对落在数组的哪个下标。如果不同的哈希码算出相同的下标,就会导致哈希碰撞,影响HashMap的性能。HashMap要做的,就是尽量避免哈希碰撞,所以加入了扰动函数。扰动函数会将哈希码的高16位与低16位做异或运算,让高位也参与到下标的计算过程中来,从而影响最终下标的计算结果,减少哈希碰撞的概率。至于为啥是16位,这是因为哪些位会参与到下标的计算,取决于HashMap数组的长度,在绝大部分情况下,数组的长度都不会超过65536,16位是一个折中的数字。

加载全部内容

相关教程
猜你喜欢
用户评论