【Java面试小短文】HashMap中的hash方法为什么要右移16位并异或？

小灰灰 2023-09-28 20:40 16阅读 0赞

> 欢迎关注`Java`面试系列，不定期更新面试小短文。欢迎一键三连！

## HashMap中的hash方法为什么要右移16位并异或？ ##

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

原因是为了让`hash`值的散列度更高，尽可能的去减少`hash`表的`hash`冲突，从而去提升数据的查找性能。

public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }
    
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;          
            // .......源码自行查看，只展示关键部分
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            // .......源码自行查看，只展示关键部分
        }

在`HashMap`的`put`方法里面，是通过`key`的`hash`值与数组的长度取模计算得到的一个数组位置。而在绝大部分情况下，`n`的值一般是小于`2^16`(就是`65536`)，这就意味着 `i` 的值始终是使用`hash`值的低`16`位与`(n - 1)`进行取模计算，这是由 `&` 运算符的特点决定的，这样就会造成`key`的散列度不是很高，导致大量的`key`集中存储在一个固定的几个数组位置上，很显然这会影响到数据的查找性能。因此为了提升`key`的`hash`值的一个散列度，在`hash`方法里面做了一个位移运算。

所以在`hash`方法里面，首先使用`key`的`hashCode`无符号右移`16`位，意味着把`hashCode`的高位移动到了低位，然后再用`hashCode`与右移之后的值进行异或运算。就相当于把高位和低位的特征进行了组合，这样通过高位和低位组合后的`hashCode`通过 `&` 运算符进行运算后，它得到的一个数组的位置的散列度一定会更高，通过这种方式，可以去降低`hash`冲突的概率。

> 上面说是通过`key`的`hash`值与数组的长度取模计算得到的一个数组位置。取模计算？哪里取模了？`(n - 1) & hash`是取模吗？  
> 真的是取模，**只要n是2的指数幂，就可以将取模运算改成位运算**  
> 比如：13 % 4 = 1 —> 13 & (4 - 1) = 1  
>  00001101 （13）  
> & 00000011 (4 - 1)  
> = 00000001  (1)  
> 比如 14 % 8 = 6 —> 14 & (8 - 1) = 6  
>  00001110 （14）  
> & 00000111 (8 - 1)  
> = 00000110  (6)  
>   
>   
> 你学到了吗

欢迎一键三连~  
  
有问题请留言，大家一起探讨学习  
  
\----------------------Talk is cheap, show me the code-----------------------