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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2798 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

hashtable

个数

Hash

次方

7 条回复 • 2017-03-27 17:24:43 +08:00

h4x3rotab

2017-03-27 13:26:01 +08:00 via iPhone

是的

esolve

2017-03-27 13:31:19 +08:00

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

msg7086

2017-03-27 13:42:39 +08:00

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

stackpop

2017-03-27 13:45:43 +08:00

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

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

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

stackpop

2017-03-27 13:48:19 +08:00

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

wuyukai

2017-03-27 14:47:39 +08:00

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

domty

2017-03-27 17:24:43 +08:00

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 次幂。