在Java开发中,我们经常会像如下方式以下创建一个HashMap:
Map<String, String> map = new HashMap<String, String>();
但是上面的代码中,我们并没有给HashMap指定容量,那么,这时候一个新创建的HashMap的默认容量是多少呢?为什么呢?
一、什么是容量?
在Java中,保存数据有两种比较简单的数据结构:数组和链表。HashMap底层就是数组+链表(jdk1.8后底层是数组+链表+红黑树)。 在HashMap中,有两个比较容易混淆的关键字段:size和capacity ,这其中capacity就是Map的容量,而size我们称之为Map中的元素个数。 简单打个比方就更容易理解了:HashMap就是一个“桶”,那么容量(capacity)就是这个桶当前最多可以装多少元素--也就是数组的长度,而元素个数(size)表示这个桶已经装了多少元素。Map<String, String> map = new HashMap<String, String>();
map.put("hello", "Java");
map.put("hell", "Java");
map.put("hel", "Java");
map.put("he", "Java");
/*
* 通过反射获取
*/
Class<?> mapType = map.getClass();
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("capacity : " + capacity.invoke(map));
Field size = mapType.getDeclaredField("size");
size.setAccessible(true);
System.out.println("size : " + size.get(map));
通过上面的代码,我们发现了,当我们创建一个HashMap的时候,如果没有指定其容量,那么会得到一个默认容量为16的Map,那么,这个容量是怎么来的呢?又为什么是这个数字呢?
实际上这个数字与hash有一定的关系,下面我们看一下hash。
二、什么是hash?
我们知道,容量就是一个HashMap中”桶”的个数,那么,当我们想要往一个HashMap中put一个元素的时候,需要通过一定的算法计算出应该把他放到哪个桶中,这个过程就叫做hash。三、hash的实现
hash的具体实现上,由两个方法int hash(Object k)和int indexFor(int h, int length)(在jdk1.8后没有这个方法了)来实现。int hash(Object k):该方法主要是将Object转换成一个整型数。 int indexFor(int h, int length):该方法主要是将hash()生成的整型数转换成链表数组中的下标。我们先来看下源码:
static int indexFor(int h, int length) {
return h & (length-1);
}
在JDK8中无indexFor方法,变为以下源码中的i=(n-1)&hash
(h = k.hashCode()) ^ (h >>> 16)
得到hash值
indexFor方法通过h & (length-1)
得到下标。其中的两个参数h表示元素的hash值,length表示HashMap的容量。
i=(n-1)&hash
和上面的运算一样。其中的两个参数n表示HashMap的容量,hash表示元素的hash值。
那么h & (length-1) 是什么意思呢?
其实就是取模。Java之所以使用位运算(&)来代替取模运算(%),最主要的考虑就是效率。
位运算(&)效率要比代替取模运算(%)高很多,主要原因是位运算直接对内存数据(二进制)进行操作,不需要转成十进制,因此处理速度非常快。那么,为什么可以使用位运算(&)来实现取模运算(%)呢?实现的原理如下:
a%b在当b为2^n时可简化为a&(b-1)
证明:
1.当b为2^n时,b-1的二进制为011..11(0后面跟n个1).此时a&(b-1)即取a二进制右面n位
2.当b为2^n时,a/b的意义就是a右移n位。而右移的n位的值,就是a%b的值
理论不好理解,就找几个例子用计算器试一下。
6 % 8 = 6 ,6 & 7 = 6
10 % 8 = 2 ,10 & 7 = 2
17 % 8 = 1 ,17 & 7 = 1
所以,h & (length-1)只要保证length是2^n的话,就可以实现取模运算了。
所以,因为位运算要比取模运算的效率更高,所以HashMap在计算元素要存放在数组中的下标的时候,使用位运算代替了取模运算。要实现位运算代替取模运算,要求HashMap的容量一定要是2^n 。
那么,既然是2^n ,为啥一定要是16呢?为什么不能是4、8或者32、64等等呢?
关于这个默认容量的选择,JDK并没有给出官方解释。
这应该就是个经验值,既然一定要设置一个默认的2^n 作为初始值,那么就需要在效率和内存使用上做一个权衡。
4、8太小了就有可能频繁发生扩容,扩容就需要重建哈希表,影响效率。32、64等等太大了又浪费空间,不划算。
所以,16就作为一个经验值被采用了。
在JDK 8中,关于默认容量的定义如上源码 ,其故意把16写成1<<4,就是提醒开发者,这个地方要是2的幂。注释中的 aka 16 也是jdk1.8中新增的,Also Known As 16 -- 又名16既然我们需要把容量设置为2^n,那么HashMap是如何保证其容量一定可以是2^n的呢? 要做到这一类型容量,HashMap在指定容量初始化时以及自动扩容时都做了处理。
四、指定容量初始化
以下是《Java开发手册》中的一段话:int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
和Part 2:
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
Part 2比较简单,就是做一下判断,然后把Part 1得到的数值+1。
Part 1怎么理解呢?其实是对一个二进制数依次无符号右移,然后与原值取或。
拿一个二进制数,套一遍上面的公式就发现其目的:
1100 1100 1100 >>>1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 >>>2 = 0011 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 >>>4 = 1111 1111 1111
1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
···以此类推
通过几次无符号右移和按位或运算,我们把1100 1100 1100转换成了1111 1111 1111 ,再把1111 1111 1111加1,就得到了1 0000 0000 0000,次数就是大于1100 1100 1100的第一个2的幂。
可以用程序试验一下:
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
System.out.println((n < 0) ? 1 : (n >= 1 << 30) ? 1 << 30 : n + 1);
五、自动扩容
指定容量初始化后,往集合中put元素时,元素个数超过阈值后怎么办呢?这时候就需要扩容了。 HashMap有扩容机制,就是当达到扩容条件时会进行扩容。扩容条件就是当HashMap中的元素个数(size)超过阈值(threshold)时就会自动扩容,通过resize方法进行扩容。newCap = oldCap << 1;
newThr = oldThr << 1;
从上面两行代码可以看出,扩容后的capacity和threshold变为原来的两倍。
可见,当HashMap中size>threshold时就会自动扩容,扩容成原容量的2倍,即从16扩容到32、64、128 …阈值也从12到24,48,96...
所以,通过保证初始化容量均为2的幂,并且扩容时也是扩容到之前容量的2倍,所以,保证了HashMap的容量永远都是2的幂,从而保证了位运算代替取模运算,从而提升了效率。
可以看到初始化之后容量和阈值是一样的,
当放入第一个元素后,重新计算阈值,新的阈值=容量X负载因子。
可以用程序实验一下:
HashMap m = new HashMap(15);
Class<?> mapType = m.getClass();
Field threshold = mapType.getDeclaredField("threshold");
threshold.setAccessible(true);
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("容量:" + capacity.invoke(m) + " 阈值:" + threshold.get(m) + " 元素数量:" + m.size());
for (int i = 0; i < 25; i++) {
m.put(i, i);
System.out.println("容量:" + capacity.invoke(m) + " 阈值:" + threshold.get(m) + " 元素数量:" + m.size());
}