计算hash值的方法

小灰灰 2023-10-05 14:41 30阅读 0赞

## 计算hash值的方法： ##

对于key的hashCode做hash操作，无符号右移16位然后做异或运算。  
还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移16位异或运算效率是最高的。  
集合中的初始化容量（必须是二的n次幂）

//默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

static final int hash(Object key) 
     {
        
            int h;
         	/*
         	1）如果key等于null：
         	可以看到当key等于null的时候也是有哈希值的，返回的是0.
         	2）如果key不等于null：
         	首先计算出key的hashCode赋值给h,然后与h无符号右移16位后的二进制进行按位异或得到最后的hash值
         	*/
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
     }

计算过程如下所示：

说明：
    
    	1）key.hashCode()；返回散列值也就是hashcode。假设随便生成的一个值。
    
    	2）n表示数组初始化的长度是16
    
    	3）&（按位与运算）：运算规则：相同的二进制数位上，都是1的时候，结果为1，否则为零。
    
        4）^（按位异或运算）：运算规则：相同的二进制数位上，数字相同，结果为0，不同为1。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMTA1Nw_size_16_color_FFFFFF_t_70]  
简单来说就是：

*  高16 bit 不变，低16 bit 和高16 bit 做了一个异或（得到的 hashcode 转化为32位二进制，前16位和后16位低16 bit和高16 bit做了一个异或）
 *  (n-1) & hash = -> 得到下标 (n-1) n表示数组长度16，n-1就是15
 *  取余数本质是不断做除法，把剩余的数减去，运算效率要比位运算低。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMTA1Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020112817185871.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMTA1Nw==,size_16,color_FFFFFF,t_70