HashMap底层详解-002-hash算法、长度的秘密

第二天，小粉粉和小灰灰又遇见了……

微信公众号：JavaWeb架构师
微信公众号：JavaWeb架构师
微信公众号：JavaWeb架构师
微信公众号：JavaWeb架构师
微信公众号：JavaWeb架构师
微信公众号：JavaWeb架构师

之前咱们说过，有一个hash方法，用于计算元素的下标值。

index = hash(key)

在hash方法内部，我们通过key的hashCode值与HashMap的长度做某种运算，可以得到最后的index值。

微信公众号：JavaWeb架构师

index = key.hashCode() % hashMap.length

微信公众号：JavaWeb架构师

1.对hash值进行调整

/**
 * 如果Key值为null，返回0；如果Key值不为空，返回原hash值和原hash值无符号右移16位的值按位异或的结果。
 * 按位异或就是把两个数按二进制，相同就取0，不同就取1。
 * 所以这个hash()函数对于非null的hash值，仅在其大于等于2^16的时候才会重新调整其值。
 */

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

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;
        // n的值是表长
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

        // (n - 1) & hash，与hash值进行与元素
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

       //…………

我们知道 n-1 的二进制值是 1111，它与任何数进行与运算，结果都是那个数的最后四位（<=15）。

微信公众号：JavaWeb架构师 微信公众号：JavaWeb架构师 微信公众号：JavaWeb架构师 微信公众号：JavaWeb架构师 微信公众号：JavaWeb架构师 微信公众号：JavaWeb架构师

欢迎加入交流群：451826376

更多信息：www.itcourse.top

完整教程PDF版本下载