Java HashMap初始容量的取值示例
HashMap中底层数据的长度总是2的n次方
在某个元素存入HashMap底层数组时，为确定其位置，最直接的方式是对其取模，这样能够均匀的分布到数组中。这里比较取巧的是，当数组长为2的n次方时，通过h&(length-1)能够高效的算出hash值。
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
HashMap默认初始容量为16，负载因子loadFactor为0.75，也就是说只能存储12个元素，当put第13个元素时就需要resize数组将容量扩充到32。
确定初始容量
最初一直通过手动计算算出初始容量，算出大于数据size的最小的2的n次方，当然也要考虑加载因子。这样每次计算都很麻烦，将负载因子设为1可以简单计算。但查看源码，HashMap做了Size计算。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
可以看出我们定义的initialCapacity先赋值于threshold，threshold为rehash的标志。在inflateTable中会算上loadFactor重新计算threshold的值。所以要避免HashMap使用过程出现rehash，initialCapacity不能直接传元素个数，initialCapacity必须大于等于（元素length/loadFactor），所以负载因子使用默认值0.75，初始容量设为1.333…*length，一般习惯1.4*length。
函数highestOneBit
在JDK1.6时，取最小的2的n次方使用while循环连续比较，在jdk1.7时如上做了改动。先取number值最高位，再向左移一位。highestOneBit实现：
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
通过移位后i的值从最高位1开始都是1，在右移相减得到最高位的值。
您可能感兴趣的文章：
Java HashMap初始容量的取值示例
深入解析Java对象的初始化过程
将一个二维数组转换为 hashmap 哈希表
Java的HashMap源码实现分析教程
HashMap在Android和Java中的不同实现
java中关于Map的几大问题总结
【golang】HashMap原理和实现
Java 8 新特性之泛型的类型推导
关于php中变量的初始化以及赋值方式的介绍
PHP变量的初始化以及赋值方式介绍