HashMap如何计算数组下标

讨论 代码环境为JDK1.8.0 211

HashMap如何计算数组下标

首先我们看看String的hashCode是如何计算的（出自JDK1.8.0 211 java.lang.String 1452行—1476行）

/** * Returns a hash code for this string. The hash code for a * {@code String} object is computed as * <blockquote><pre> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] * </pre></blockquote> * using {@code int} arithmetic, where {@code s[i]} is the * <i>i</i>th character of the string, {@code n} is the length of * the string, and {@code ^} indicates exponentiation. * (The hash value of the empty string is zero.) * * @return a hash code value for this object. */
    public int hashCode() { 
        int h = hash;
        if (h == 0 && value.length > 0) { 
            char val[] = value;

            for (int i = 0; i < value.length; i++) { 
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

String类重写了hashCode()函数，计算字符串的hashCode的公式为：
s [ 0 ] ∗ 3 1 n − 1 + s [ 1 ] ∗ 3 1 n − 2 + . . . + s [ n − 1 ] s[0]*31^{n-1}+s[1]*31^{n-2}+…+s[n-1] s[0]∗31n−1+s[1]∗31n−2+...+s[n−1]
我们来举个例子：
经过debug我们得知三个字符串的hashCode()返回值，我们来通过计算公式模拟一下：
字符串“a”，长度n=1，字符‘a’=97，代入公式得：
s [ 0 ] ∗ 3 1 n − 1 + s [ 1 ] ∗ 3 1 n − 2 + . . . + s [ n − 1 ] = 97 ∗ 3 1 1 − 1 = 97 s[0]*31^{n-1}+s[1]*31^{n-2}+…+s[n-1]=97*31^{1-1}=97 s[0]∗31n−1+s[1]∗31n−2+...+s[n−1]=97∗311−1=97
字符串“ab”，长度n=2，字符‘a’=97，‘b’=98，代入公式得：
s [ 0 ] ∗ 3 1 n − 1 + s [ 1 ] ∗ 3 1 n − 2 + . . . + s [ n − 1 ] = 97 ∗ 3 1 2 − 1 + 98 ∗ 3 1 1 − 1 = 3105 s[0]*31^{n-1}+s[1]*31^{n-2}+…+s[n-1]=97*31^{2-1}+98*31^{1-1}=3105 s[0]∗31n−1+s[1]∗31n−2+...+s[n−1]=97∗312−1+98∗311−1=3105
好了知道了如何计算String的hashCode，再来看看HashMap的hash()函数是如何利用hashCode的：

如果key对象为null的话，就返回一个0，当然String对象为null的话，强行计算hashCode()是会抛出空指针异常的。如果key对象不是为null，那么获取key的hashCode，然后与右移位16位后的hashCode进行异或操作（关于异或操作，总结：不同，结果为1，相同，结果为0），异或的结果就位hash()函数返回值。我们以String的hashCode()为例，图解计算一次hash()返回值：

通过debug，我们知道“my name is suser！”的hashCode返回值为：244633208，然后通过进制转换为二进制，方便计算

我们图解一下计算过程：

得到hash(key)=244629740后，下一步计算数组下标，我们看源码中第630行：

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

在JDK1.8中，HashMap底层为数组+链表或红黑树
i是什么？i就是数组下标；
n是什么？n是数组长度，默认为16
hash就是hash(key)函数的返回值，244629740为例，这里要得出下标，需要进行一次&（与运算）（同为1，则1，不然则为0）
这里，假设HashMap刚刚创建，也没有经过扩容操作，数组长度这时为默认的16，来算算下标：

最终计算得下标值为12。
下面，通过debug结果，给出证据，证明其下标值确定为12：

625行debug信息显示hash(key)返回值，key值等关键信息
630行debug信息显示此时HashMap数组长度为默认16，还未经过扩容操作
631行debug信息显示i的值为12，与我推想的结果一致

总结一下： HashMap中数组下标值的计算过程，大致分为如下几步：获取key.hashCode()，然后将hashCode高16位和低16位异或（^）操作，然后与当前数组长度-1结果进行与（&）操作，最终结果就是数组的下标值。
至于由于当前结点（键值对）的加入，导致当前HashMap中容量超过了阈值而扩容2倍，扩容后导致每个结点重新计算下标值（称为新下标值），新下标值只有两种可能：一、key的hash()返回值新加入与（&）操作计算的一位为0，则下标值与原下标值相同。二、key的hash()返回值新加入与（&）操作计算的一位为1，则计算出来的下标值=原下标值+原数组长度。
如果key对象为Integer，他的hashCode()直接返回的value。