“2的幂”的意义在java.util.HashMap实现中

问题描述

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

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

  / ** 
 *默认初始容量 - 必须是2的幂。 
 * / 
 static final int DEFAULT_INITIAL_CAPACITY = 16; 
 
 
 / ** 
 *最大容量，如果任何带参数的构造函数隐含指定较高值
 *，则使用该容量。 
 *必须是2的幂 * / 
 static final int MAXIMUM_CAPACITY = 1<< 30; 
 
 
 / ** 
 *表格根据需要调整大小。长度必须是2的幂。 
 * / 
瞬间Entry []表; 
  

评论建议大小必须是2的幂。为什么两个幂给予如此重要？

解决方案

使用两个幂可简化实现并提高其性能。 >

例如从哈希码中找到一个桶，它可以使用 hash& （SIZE -1）而不是 abs（散列）％SIZE

I was reading the implementation of HashMap in java.util.HashMap. The initial capacity,maximum capacity etc., are powers of two.

Parts of declaration copied from 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;

The comments suggest the sizes MUST be a power of two. Why is power of two given so much importance ?

解决方案

Using powers of two simplifies the implementation and improves its performance.

E.g. to find a bucket from a hash code it can use hash & (SIZE -1) instead of abs(hash) % SIZE

这篇关于“2的幂”的意义在java.util.HashMap实现中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！