java - 为什么使用 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

不管a有多大java.util.HashMap增长时，其表容量(数组长度)保持为 2 的幂。这允许使用快速按位与运算 (&) 来选择存储对象的存储桶索引，如 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是表容量，(n - 1) & hash包装哈希值以适合该范围。

更多详情

哈希表有一个“桶”数组(HashMap 称它们为Node)，其中每个桶存储映射的零个或多个键值对。

每次我们get或 put一个键值对，我们计算键的哈希值。散列是一些任意的(可能是巨大的)数字。然后我们从散列中计算一个桶索引，以选择对象的存储位置。

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

(哈希也可以是负数。-95 的值可以对应于桶 5 或 95，具体取决于它的实现方式。确切的公式并不重要，只要它在桶中大致均匀地分布哈希即可.)

如果我们的表容量n不是二的幂，桶的公式将是 Math.abs(hash % n) , 它使用模运算符计算除以 n 后的余数，并使用 abs修复负值。这会奏效，但会更慢。

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

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

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