HashMap哲学中的数学原理

程序员文章站 2022-05-23 11:09:59

...

今天与群友畅谈HashMap的知识点，十分愉快。但恐于泛泛之言，寥寥数语难以概述清晰。幸甚至哉，作文咏志。
此文并不会讲解HashMap的数据结构。单单阐述HashMap涉及到的数学原理。

tableSizeFor

一般遇到的第一个问题就是tableSizeFor()。

HashMap哲学中的数学原理

我来解释一下这部分代码的作用：计算出大于或等于cap的第一个2的n次幂。注意：

cap参与计算之前要先-1
了解>>>、|的运算规则

他这个算法大概的意思就是先无符号右移m位，再将获得的结果与原值进行 | 运算。比如我们令cap=19,则n=18，二进制表示为10010，无符号右移1位之后是1001。如果将其对其为16位则表示为：0000 0000 0001 0010然后与原值0000 0000 0000 1001与运算结果为：0000 0000 0001 1011后面的几轮我们以此类推即可。
详细的演算过程如下：

HashMap哲学中的数学原理

上面的演算结果是11111，翻译为10进制就是31。

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

n < MAXIMUM_CAPACITY，所以返回：31 + 1 = 32。
使用移位和或运算，巧妙的化简了问题。注意这里有一个细节就是cap-1，为什么这么做呢。假设 x = 2^n，如果我们不处理得到的结果是2 * 2^n，这里就不符合要求。大于等于 x 的第一个值应该是 x 本身。不信的话，可以动手验证一下。

hash

这里我们不讨论hashCode产生的过程，我们只关心后部分。也就是大家所谓的扰动函数。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : 
    // 我们看最后一行作用
    (h = key.hashCode()) ^ (h >>> 16);
}

Jdk对此做出了相应解释。

Computes key.hashCode() and spreads (XORs) higher bits of hash

直译就是：计算key.hashCode()并扩展哈希的更高位
有必要思考一下：为什么已经得出key的hashCode之后还要大费周章进行移位异或的运算呢。假设我们不进行扰动呢，能有什么影响呢。我们知道HashMap中确定元素所在数组中的位置是通过 & 运算来实现的。

if ((p = tab[i = (n - 1) & hash]) == null)

一个key的hashCode足够大，而当前HashMap的容量不是足够大的时候，你发现了吗对该key进行定位的重大决定其实只是交给了最后几位。
假设当前容量是16，然后(n - 1) = 15，其实就是二进制的1111。无论hash有多少位，不足的我1111只管补足0即可。这时候一个非常尴尬的情况出现了。我管你hashCode多少位只要跟我1111进行 & 运算，除了最后四位前面的一律为0。也就是说hash看着位数足够多其实发挥作用的只有最后面的一部分。这样一来，两个hash只需要低位一致，高位就算多大差异他们最后一定定位再同一处。
这显然是源码作者不愿意看到的结果。其实这里高位参与运算就是为了打乱低位。这样高位不同，低位相同，定位就一定相同的僵局直接就会被打破。

容量的秘密

我们知道HshMap扩容至原来的2倍，初始容量是16，这么一来ta的容量其实永远都是2^n。在二进制中2^n的数字是极具特点的。转化成二进制之后首位为1，余位为0。那么2^n - 1之后呢，得到的结果更加有规律，一定得到全部为 1 的排列。
请你一定要记得任何数 -1 得到全部是 1 的排列那么这个数字一定是2^n

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  boolean evict)
    n = (tab = resize()).length;
    (n - 1) & hash

在put()方法中想要定位，其实就是获取到Key的hash之后对当前容量求余。但是求余在计算机的世界里比较消耗性能。我们可以将hash % n转化为(n - 1) & hash。
& 的运算规则是全部为 1 结果为 1，其余结果为 0。
我们令hash的值为a b c d，(n - 1)的值为m n x y，且上述变量取值范围为[0, 1]。
& 运算结果为t x y z，最完美的情况是：四位数值每一位都可能是 0 或者 1，那么得到的排列有2 * 2 * 2 * 2 = 16 种。我们继续假设如果m n x y其中有一个数字等于 0 呢？结果的排列就只剩下2 * 2 * 2 = 8种。出现两位为 0 的话排列就只剩下2 * 2 = 4种。
这么理论不免有些枯燥。因为我们是明确知道当前容量的。如果 n = 1110，n - 1 = 1101，相当于你数组长度为 14 时，只会出现 8 种排列，那么对应成HashMap的定位问题，就是说数组长度是 14 时，足足有 6 个位置是永远浪费的。如果存在这种大量浪费的情况，势必会导致HashMap频频扩容，损耗性能。
那怎么解决呢？怎么让所有的位置都有可能被定位，对应成上述数学模型解决方案其实就是(n - 1)所有位必须全为 1。
那如果(n - 1)所有位必须全为 1。则 n = 2^x 成立。

扩容的秘密

if ((e.hash & oldCap) == 0)
newTab[j] = loHead;
newTab[j + oldCap] = hiHead;

这里我当时看的时候百思不得其解，直到我发现这里(e.hash & oldCap)不是(e.hash & (oldCap - 1))这两者天壤之别。这句代码这里的意思就是其实就是判断oldCap最高位对应e.hash相对应位置上的值是否为 1。
这个很重要因为如果对应的位置为 1，直接表示ta需要搬家，而搬到哪里去呢？数组原来位置对应的数字加上原容量即可。如果是 0，那就待在原地即可。其实这里只要二进制和数学学的好的，应该是瞬间就可以反应的过来。
扩容之后(e.hash & (newCap - 1))其实只有newCap的最高位对应的e.hash的那一位可以发挥作用，newCap最高位前面的全是0不影响结果，后面呢跟(e.hash & (oldCap - 1))的结果又一摸一样也不影响结果。还不明白，那我就偷一张图：