HashMap如何计算Entry在桶中的下标？

我们知道HashMap内部包含了一个 Entry 类型的数组 table。

transient Entry[] table;

Entry 存储着键值对。它包含了四个字段，从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶（bucket），一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值相同的 Entry。

那么是如何计算Entry在桶中的位置的呢？

HashMap中的代码如下：

int hash = hash(key);
int i = indexFor(hash, table.length);

1 计算 hash 值

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

2 取模

static int indexFor(int h, int length) {
    return h & (length-1);
}

这个位运算等同于：hash % length

是不是乍一看看不懂呢？ 来解释一下：

令 x = 1<<4，即 x 为 2 的 4 次方，它具有以下性质：

x : 00010000
x-1 : 00001111
令一个数 y 与 x-1 做与运算，可以去除 y 位级表示的第 4 位以上数：

y : 10110010
x-1 : 00001111
y&(x-1) : 00000010
这个性质使 y & （x - 1）和 y 对 x 取模效果是一样的：

y : 10110010
x : 00010000
y%x : 00000010

我们知道，位运算的代价比求模运算小的多，因此在进行这种计算时用位运算的话能带来更高的性能。

总结：HashMap确定桶下标的最后一步是将 key 的 hash 值对桶个数取模：hash%capacity。
如果能保证 capacity 为 2 的 n 次方，那么就可以将这个操作转换为位运算。
在平时的开发中我们也可以利用这个特性，对一些算法运算的效率进行优化。