为什么使用 1<<4 而不是 16？

Question

java.util.HashMap 的 OpenJDK 代码包括以下行：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

为什么这里用的是1 << 4，而不是16？我很好奇。

Answer 1

写 1 << 4 而不是 16 不会改变这里的行为。这样做是为了强调这个数字是 2 的幂 ，而不是一个完全随意的选择。因此，它提醒开发人员尝试不同的数字，他们应该坚持模式（例如，使用 1 << 3 或 1 << 5，而不是 20），这样他们就不会破坏所有依赖的方法它是二的幂。有评论just above:

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

无论java.util.HashMap增长多大，它的table容量（数组长度）都保持为2的幂。这允许使用快速按位与运算 (&) 到 select 存储对象的存储桶索引，如 in methods that access the table:

所示

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) { /// <-- bitwise 'AND' here
        ...

那里，n 是 table 容量，(n - 1) & hash 包装哈希值以适应该范围。

更多详情

一个散列 table 有一个 'buckets' 的数组（HashMap 称它们为 Node），其中每个桶存储映射的零个或多个键值对.

每次我们 get 或 put 键值对时，我们都会计算键的哈希值。散列是一些任意的（可能是巨大的）数字。然后我们从散列计算一个存储桶索引，到 select 存储对象的位置。

大于桶数的哈希值被“环绕”以适应table。例如，table 容量为 100 个桶，哈希值 5、105、205 将全部存储在桶 5 中。可以把它想象成圆上的度数，或钟面上的小时。

（哈希值也可以是负数。-95 的值可能对应于存储桶 5 或 95，具体取决于它的实现方式。确切的公式无关紧要，只要它大致均匀地分布哈希值即可水桶。）

如果我们的 table 容量 n 不是二的幂，则桶的公式将是 Math.abs(hash % n)，它使用取模运算符计算除以后的余数n，并使用 abs 来修复负值。那会起作用，但会慢一些。

为什么慢？想象一个 decimal 中的示例，其中您有一些随机散列值 12,459,217，以及任意 table 长度 1,234。 12459217 % 1234刚好是753不明显，很多长除法。但是，如果您的 table 长度是 ten 的精确幂，那么 12459217 % 1000 的结果就是最后 3 位数字：217.

写成二进制，two的幂是一个1后跟一些0，所以等效的技巧是可能的。例如，如果容量 n 是十进制的 16，那是二进制的 10000。因此，n - 1 是二进制的 1111，而 (n - 1) & hash 只保留与这些 1 对应的散列的最后几位，归零其余的部分。这也将符号位清零，因此结果不能为负。结果是从 0 到 n-1，包括在内。那是桶指数。

即使 CPU 变得更快并且它们的多媒体功能得到改进，整数除法仍然是您可以执行的最昂贵的单指令操作之一。它可能比按位 AND 慢 50 倍，在频繁执行的循环中避免使用它可以带来真正的改进。

Answer 2

我无法读懂开发人员的想法，但我们这样做是为了表明数字之间的关系。

比较这个：

int day = 86400;

对

int day = 60 * 60 * 24; // 86400

第二个例子清楚地显示了数字之间的关系，Java足够聪明，可以将其编译为常量。

Answer 3

我认为原因是开发人员可以很容易地更改值（根据 JavaDoc '/* 默认初始容量 - 必须是二的幂。*/'）例如 1 << 5或者 1 << 3 他不需要做任何计算。

为什么使用 1<<4 而不是 16？

Why use 1<<4 instead of 16?

java

openjdk

更多详情