HashMap 里利用& （ 2 的 N 次方减一）来取模对于非 2 的 N 次方无效吧？

[esolve]

hash & (table.length - 1) 上面这个是 hash 对 hashtable 元素个数取模 hashtable 元素个数默认 16,是 2 的 4 次方 但是如果 hashtable 元素个数不是 2 的 N 次方 这不就无效了？

[h4x3rotab]

是的

[esolve]

@h4x3rotab 照你这意思，用 hashmap 的时候，元素个数必须是 2 的 N 次方？

[msg7086]

@esolve 表的长度必须是 2 的幂。元素个数不需要。

[stackpop]

如果要让 a % x == a & (x - 1)
那就需要让 x 是 2 的幂

但是，在哈希表里面，这个运算并不需要保证绝对等于模运算，只要保证一致性，并且一定落在表大小以内就行。

所以并不需要所有哈希表大小都是 2 的幂。

[stackpop]

任何一个无符号的整数值 & (x-1) 后的数值，肯定是在 0 到 x-1 之间的，而且这个运算是一致的。

[wuyukai]

HashMap 结构是数组加链表的形式，计算方式是除以 bucket （桶）的数量取余， Bucket 的数量就是数组的长度，也就是你这里的 table.length ，而不是所有的元素。所以数组的长度（桶的数量）必须是 2 的幂，至于 Bucket 中链表存了多少元素并不需要管啊。 HashMap 的存取数的原理就是快速的定位到桶的位置，有了桶的位置就可以把数放到链表的头节点或者遍历链表把需要的数取出来。比如 1000 个数，你可以放 4 个桶中，也可以放 8 个桶中，只要桶的数量为 2 的幂就行的。

[domty]

HashMap 里有这个初始化容量的方法

```Java
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
```

理论上初始化的容量都是 2 的 n 次幂。