为什么使用1 ＜＜ 4而不是16? [英] Why use 1<<4 instead of 16?

问题描述

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

The OpenJDK code for java.util.HashMap includes the following line:

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

为什么在这里使用1 << 4而不使用16?我很好奇.

Why is 1 << 4 used here, and not 16? I'm curious.

推荐答案

要强调的是，数字是2的幂，而不是完全任意的选择.因此，它警告开发人员尝试不同的数字，他们应该在模式中使用其他数字(例如，1 << 3或1 << 5，而不是20)，这样他们就不会破坏依赖于两个要求的幂的方法. .有评论

It's to emphasize that the number is a power of two, and not a completely arbitrary choice. It thus alerts developers experimenting with different numbers that they should use other numbers in the pattern (e.g., 1 << 3 or 1 << 5, rather than 20) so they don't break the methods which rely on the power of two requirement. There is a comment 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的容量(表长度)始终是2的幂.之所以这样设计，是因为它允许使用快速按位AND操作(&)将每个键的哈希码包装到表的长度范围内，如

The capacity (table length) of any java.util.HashMap is always a power of two. It's designed that way because that allows the use of a fast bitwise AND operation (&) to wrap each key's hash code into the range of the length of the table, as done 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包装哈希值以适合该范围，为该哈希选择表的适当存储区.

There, n is the capacity, and (n - 1) & hash wraps the hash value to fit that range, selecting the appropriate bucket of the table for that hash.

(如果n不是2的幂，则公式将需要为Math.abs(hash % n)，使用取模运算符计算除以n后的余数，再加上额外的步骤来处理负哈希值想象一下，这是可行的，但速度较慢.想象一下 decimal 中的示例，其中您具有一些任意的哈希值193,498,212，表的任意长度为1,234； 193498212 % 1234恰好是842并不明显，但表长度为 ten 的精确幂，因此193498212 % 1000的结果仅为212(最后3位数字).在 binary 中，193498212 % 1000的幂em> two 是1，后跟一定数量的0，所以可能有类似的技巧.)

(If n were not a power of two, the formula would need to be Math.abs(hash % n), using the modulo operator to calculate the remainder after division by n, plus an extra step to deal with negative hash values. That would work, but be slower. Imagine an example in decimal, where you have some arbitrary hash value 193,498,212, and an arbitrary table length of 1,234; it's not obvious that 193498212 % 1234 happens to be 842, but with a table length that is an exact power of ten, the result of 193498212 % 1000 is simply 212, the last 3 digits. In binary, a power of two is a 1 followed by some number of 0s, so a similar trick is possible.)

这篇关于为什么使用1 ＜＜ 4而不是16?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！