HashMap中的hash函数为什么要和高16位异或

/ 默认分类 / 0 条评论 / 1015浏览

HashMap中的hash()函数详细分析

前面我写过HashMap的源码分析笔记,里面已经介绍了在HashMap中使用&操作来作为散列函数(hash函数),原理就是 真正初始化的hashmap的数组容量长度都是2的n次幂,这样&运算后得到的数据一定小于数组的长度,这篇文章主要 详细介绍下HashMap中的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) {
        ......省略
                   }
        //没有出现hash冲突
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
    
    //hash值就是通过这个函数计算的
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

1.为什么计算待插入的元素的hash值需要(h = key.hashCode()) ^ (h >>> 16),为什么不直接使用hashCode()方法?

首先hashCode函数返回的是一个int类型的数据,也就是4个字节,32位,如果直接使用这个32位的数据作为待插入元素的hash值来和(n-1)进行&运算,那么 该hash值真正起到作用的基本就是低位的数据,因为在hashmap中,常规的使用中,hashmap的数组长度不会特别长,很少有业务场景会使用 hashmap导致其扩容的数组长度达到2^31,所以hash值和(n-1)进行&运算真正能起到作用的位数更多的时候只有低位,所以为了让 hash值的高位也参与&运算,让hashmap的散列函数变得更加合理,不易发送冲突,所以在计算hash值的时候,让hashCode值的高16位和低16位 进行异或运算,将异或结果作为真正的hash()得到的值,然后用这个值来和(n-1)进行&操作. 这样进行hashCode的高位和低位就都可以参与到运算 中,提高hash函数分散度.

2.为什么是异或操作不是&或|呢?

首先这里的有符号右移>>>其实就是取高16位(这些是运算操作,自行了解),之后之所以使用异或是因为异或可以保留异或双方的不同点特征, 如果使用&或者|则使得到的结果偏向于其中一方,这样就适得其反了.

3.为什么异或可以保留双方的特征?

这是一个计算机运算问题,所谓异或运算,就是不同为1,相同为0,所以两个数进行异或, 最终的结果留下的(1的部分)一定是两个数不同的位,相同的位都被删掉了,这就相当于两张图给你找不同,其实也就是异或的操作;

关于异或运算的简单知识,可以参考这个回答 ,很形象.

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/09/13 18:06