为什么HashMap默认初始容量为2次幂?不是2次幂会怎样?讲讲 HashMap 扰动函数?

为什么HashMap默认初始容量为2次幂?不是2次幂会怎样?讲讲 HashMap 扰动函数?关于HashMap的详解文章请移步:链接:HashMap源码研究——源码一行一行的注释通过看源码,我们发现,判断桶的索引的实现是i=(n-1)&hash,其中n是map的容量。任何2的整数幂-1得到的二进制都是1,如:16-1=15(1111);32-1=31(11111)而n-1与hash做的是与运算(&),与运算是两个都为1,才为1既然我们的n-1永远都是1,那(n-1)&hash的计算结果就是低位的hash

关于HashMap的详解文章请移步:

链接: HashMap源码研究——源码一行一行的注释

为什么初始容量是 2次幂?

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 ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果没有hash碰撞则直接插入元素
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else { 
   
    	......
	}
}

通过看源码,我们发现,判断桶的索引的实现是 i = ( n – 1 ) & hash,其中 n 是 map 的容量。

任何 2 的整数幂 – 1 得到的二进制都是 1,如:16 – 1 = 15(1111);32 – 1 = 31(11111)

而 n-1 与 hash 做的是与运算(&),与运算是 两个都为1,才为1

既然我们的 n-1 永远都是 1,那 ( n – 1 ) & hash 的计算结果就是 低位的hash 值。如:

    00100100 10100101 11000100 00100101    // Hash 值 
&   00000000 00000000 00000000 00001111    // 16 - 1 = 15
----------------------------------
    00000000 00000000 00000000 00000101    // 高位全部归零,只保留末四位。


那容量不是 2次幂会怎么样?我们来做个试验。

2次幂的情况:
在这里插入图片描述
非2次幂的情况,假设 n = 10:
在这里插入图片描述
对比来看,哪种发生哈希碰撞的概率更低一目了然,如果 n 为 2次幂,可以保证数据的均匀插入,降低哈希冲突的概率,毕竟冲突越大,代表数组中的链表/红黑树越大,从而降低Hashmap 的性能。

如果指定了不是2的次幂的容量会发生什么?

答案:会获得最接近的一个2的次幂作为容量

有一个初始容量参数的构造方法HashMap(int initialCapacity)

参数:initialCapacity 初始容量

public HashMap(int initialCapacity) { 
   
        //此处通过把第二个参数负载因子使用默认值0.75f,然后调用有两个参数的构造方法
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

这个一个参数的构造方法,使用HashMap的默认负载因子,把该初始容量和默认负载因子作为入参,调用HashMap的两个参数的构造方法

有两个参数的构造方法HashMap(int initialCapacity, float loadFactor)

参数:initialCapacity 初始容量
参数:loadFactor 负载因子

/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * 通过指定的初始容量和负载因子初始化一个空的HashMap * * @param initialCapacity the initial capacity 初始化容量 * @param loadFactor the load factor 负载因子 * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive * 如果初始容量或者负载因子为负数,则会抛出非法数据异常 */
    public HashMap(int initialCapacity, float loadFactor) { 
   
        if (initialCapacity < 0)   //如果初始容量小于0,抛出异常
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)  //如果初始容量超过最大容量(1<<32)
            initialCapacity = MAXIMUM_CAPACITY;  //则使用最大容量作为初始容量
        if (loadFactor <= 0 || Float.isNaN(loadFactor))  //如果负载因子小于等于0或者不是数字,则抛出异常
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;                //把负载因子赋值给成员变量loadFactor
 
//调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果,并赋给成员变量threshold
        this.threshold = tableSizeFor(initialCapacity); 
    }

我们下面看看tableSizeFor()这个方法是如何计算的,这个方法的实现原理很巧妙,源码如下:

/** * Returns a power of two size for the given target capacity. */
    static final int tableSizeFor(int cap) { 
   
        int n = cap - 1;      //容量减1,为了防止初始化容量已经是2的幂的情况,最后有+1运算。
        n |= n >>> 1;         //将n无符号右移一位再与n做或操作
        n |= n >>> 2;         //将n无符号右移两位再与n做或操作
        n |= n >>> 4;         //将n无符号右移四位再与n做或操作
        n |= n >>> 8;         //将n无符号右移八位再与n做或操作
        n |= n >>> 16;        //将n无符号右移十六位再与n做或操作
        //如果入参cap为小于或等于0的数,那么经过cap-1之后n为负数,n经过无符号右移和或操作后仍未负 
        //数,所以如果n<0,则返回1;如果n大于或等于最大容量,则返回最大容量;否则返回n+1
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

首先,为什么要对cap做减1操作。int n = cap – 1;
这是为了防止,cap已经是2的幂。如果cap已经是2的幂, 又没有执行这个减1操作,则执行完后面的几条无符号右移操作之后,返回的capacity将是这个cap的2倍。如果不懂,要看完后面的几个无符号右移之后再回来看看。
下面看看这几个无符号右移操作:
如果n这时为0了(经过了cap-1之后),则经过后面的几次无符号右移依然是0,最后返回的capacity是1(最后有个n+1的操作)。
这里只讨论n不等于0的情况。
第一次右移

n |= n >> 1;

由于n不等于0,则n的二进制表示中总会有一bit为1,这时考虑最高位的1。通过无符号右移1位,则将最高位的1右移了1位,再做或操作,使得n的二进制表示中与最高位的1紧邻的右边一位也为1,如000011xxxxxx。
第二次右移

n |= n >>> 2;

注意,这个n已经经过了n |= n >>> 1; 操作。假设此时n为000011xxxxxx ,则n无符号右移两位,会将最高位两个连续的1右移两位,然后再与原来的n做或操作,这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx 。
第三次右移

n |= n >>> 4;

这次把已经有的高位中的连续的4个1,右移4位,再做或操作,这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。
以此类推
注意,容量最大也就是32bit的正数,因此最后n |= n >>> 16; ,最多也就32个1,但是这时已经大于了MAXIMUM_CAPACITY ,所以取值到MAXIMUM_CAPACITY 。

但是,请注意,在构造方法中,并没有对table这个成员变量进行初始化,table的初始化被推迟到了put方法中,在put方法中会对threshold重新计算。

扰动函数

HashMap 中的扰动函数是一个通过对 key 值类型自带的哈希函数生成的散列值进行位移计算来扰乱散列值,以达到降低哈希碰撞的概率的方法。源码中对应的是 hash(),但具体是如何进行移位和降低碰撞概率的??

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

我们分析一下hash(),key.hash() 调用的是key类型自带的哈希函数,返回的是 int 类型的散列值。

如果没有扰动函数的情况下,我们拿着散列值作为下标找到 hashmap 中对应的桶位存下即可(不发送哈希冲突的情况下),但 int 类型是 32 位,很少有Hashmap的数组有40亿这么大,所以, key 类型自带的哈希函数返回的散列值不能拿来直接用。如果我们取低几位的 hash 值来做数组映射行不行,但是如果低位相同,高位不同的 hash 值就碰撞了,如:

// Hash 碰撞示例:
00000000 00000000 00000000 00000101 & 1111 = 0101 // H1
00000000 11111111 00000000 00000101 & 1111 = 0101 // H2

为了解决这个问题,HashMap 想了个办法,用扰动函数降低碰撞的概率。将 hash 值右移16位(hash值的高16位)与 原 hash 值做异或运算(^),从而得到一个新的散列值。如:

00000000 00000000 00000000 00000101 // H1
00000000 00000000 00000000 00000000 // H1 >>> 16
00000000 00000000 00000000 00000101 // hash = H1 ^ (H1 >>> 16) = 5

00000000 11111111 00000000 00000101 // H2
00000000 00000000 00000000 11111111 // H2 >>> 16
00000000 00000000 00000000 11111010 // hash = H2 ^ (H2 >>> 16) = 250

H1,H2 两个 hash 值经过扰动后,很明显不会发生碰撞。

总结
总的来说,不管是规定 Hashmap 的 n 为 2次幂,还是扰动函数,都是为了一个目标,降低哈希冲突的概率,从而使 HashMap 性能得到优化。而规定 n 为 2次幂,是在新建 Hashmap对象初始化时,规定其容量大小的角度来优化。而扰动函数是插入 key 值时改变 key 的散列值来达到优化效果。

今天的文章为什么HashMap默认初始容量为2次幂?不是2次幂会怎样?讲讲 HashMap 扰动函数?分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/5927.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注