7

可能重复：
Java HashMap 默认初始容量

我正在阅读 java.util.HashMap 中 HashMap 的实现。初始容量、最大容量等是 2 的幂。

从 java.util.HashMap 复制的部分声明

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


 /**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;


/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;

评论表明尺寸必须是 2 的幂。为什么二的力量如此重要？

4

2 回答 2

17

使用 2 的幂可以简化实现并提高其性能。

例如，从它可以使用的哈希码中找到一个桶，hash & (SIZE -1)而不是abs(hash) % SIZE

于 2012-05-17T08:55:49.043 回答
1

从理论上讲，只有当操作随着地图中元素数量的增加而变得可以忽略不计时，我们才能摊销扩展列表的成本。每次达到负载因子时将大小加倍是确保分摊条目扩展和重新加载的一种方法。

它最初是 2 的幂的原因是，当我们散列一个元素时，得到的整数（32 位）可以截断到前 k 位，其中 k 是对数 (N)，其中 N 是当前容量。

于 2012-05-17T09:04:31.533 回答