对于HashMap的容量的一些分析（hashmap描述错误的是）

　　本篇文章为你整理了对于HashMap的容量的一些分析（hashmap描述错误的是）的详细内容，包含有hashmap扩容 hashmap描述错误的是对hashmap的理解 hashmap的size 对于HashMap的容量的一些分析，希望能帮助你了解对于HashMap的容量的一些分析。

　　在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的功能是根据key来确定这个key-value对在链表数组中的下标的。

　　那么这个数组下标该怎么确定呢？其实简单，我们只要在hash方法中调用Object中的hashCode方法得到一个hash值，然后用这个值对HashMap的容量进行取模就可以得到数组下标了。

　　如果真的是这么简单的话，那HashMap的容量设置也就很简单，但是考虑到效率等问题，HashMap的hash实现被设计的比较复杂，这也造成了HashMap的容量设置有一定限制。

　　下面我们看一下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

　　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开发手册》中的一段话：

　　可以看到指定容量初始化是被推荐的。

　　当我们通过HashMap(int initialCapacity)这个构造方法设置初始容量的时候，HashMap并不一定会直接采用我们传入的initialCapacity，而是经过计算，得到一个新initialCapacity(例如3变为4，9变为16)。

　　以下为初始化的源码：

　　可以看到最底层就是用tableSizeFor方法得到最终的初始化容量。

　　可以把代码分为Part 1：

int n = cap - 1;

　　n = n

　　和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

　　System.out.println((n 0) ? 1 : (n = 1 30) ? 1 30 : n + 1);

　　五、自动扩容

　　指定容量初始化后，往集合中put元素时，元素个数超过阈值后怎么办呢？这时候就需要扩容了。

　　HashMap有扩容机制，就是当达到扩容条件时会进行扩容。扩容条件就是当HashMap中的元素个数（size）超过阈值（threshold）时就会自动扩容，通过resize方法进行扩容。

　　threshold = loadFactor * capacity。

　　loadFactor是负载因子，默认值为0.75f，设置成0.75有一个好处，那就是0.75正好是3/4，而capacity又是2的幂。所以，两个数的乘积都是整数。

　　对于一个默认的HashMap来说，默认情况下，当其size大于12(16*0.75)时就会触发扩容。

　　下面是HashMap中的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 i++) {

　　 m.put(i, i);

　　 System.out.println("容量：" + capacity.invoke(m) + " 阈值：" + threshold.get(m) + " 元素数量：" + m.size());

　　}

　　HashMap作为一种数据结构，元素在put的过程中需要进行hash运算，目的是计算出该元素存放在hashMap中的具体位置。

　　hash运算的过程其实就是先对key用hash()方法得到一个hash值，再用hash值对Map的容量进行取模得到下标，而JDK的工程师为了提升取模的效率，使用位运算代替了取模运算，这就要求Map的容量一定得是2的幂。

　　为了保证任何情况下Map的容量都是2的幂，HashMap在两个地方都做了限制。

　　首先是，如果用户制定了初始容量，那么HashMap会计算出比该数大的第一个2的幂作为初始容量。

　　另外，在扩容的时候，也是进行成倍的扩容，即16变成32，32变成64。

　　以上就是对于HashMap的容量的一些分析（hashmap描述错误的是）的详细内容，想要了解更多对于HashMap的容量的一些分析的内容，请持续关注盛行IT软件开发工作室。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

相关文章阅读