草庐IT

对于HashMap的容量的一些分析

dollar 2023-04-19 原文
在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 >>> 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方法进行扩容。
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 < 25; 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的sectiondatastrongJava

有关对于HashMap的容量的一些分析的更多相关文章

  1. ruby-on-rails - 如何生成传递一些自定义参数的 `link_to` URL？ - 2

    我正在使用RubyonRails3.0.9，我想生成一个传递一些自定义参数的link_toURL。也就是说，有一个articles_path(www.my_web_site_name.com/articles)我想生成如下内容:link_to'Samplelinktitle',...#HereIshouldimplementthecode#=>'http://www.my_web_site_name.com/articles?param1=value1¶m2=value2&...我如何编写link_to语句“alàRubyonRailsWay”以实现该目的？如果我想通过传递一些

  2. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

  3. ruby - 找一些句子 - 2

    我想找到在某些文本中找到一些(让它是两个)句子的好方法。什么会更好-使用正则表达式或拆分方法？你的想法？应JeremyStein的要求-有一些例子示例:输入:ThefirstthingtodoistocreatetheCommentmodel.We’llcreatethisinthenormalway,butwithonesmalldifference.IfwewerejustcreatingcommentsforanArticlewe’dhaveanintegerfieldcalledarticle_idinthemodeltostoretheforeignkey,butinthis

  4. ruby block 并从 block 中返回一些东西 - 2

    我正在使用ruby​​1.8.7。p=lambda{return10;}deflab(block)puts'before'putsblock.callputs'after'endlabp以上代码输出为before10after我将相同的代码重构到这里deflab(&block)puts'before'putsblock.callputs'after'endlab{return10;}现在我收到LocalJumpError:意外返回。对我来说，这两个代码都在做同样的事情。是的，在第一种情况下我传递了一个过程，在第二种情况下我传递了一个block。但是&block将该block转换为pro

  5. 建模分析 | 平面2R机器人(二连杆)运动学与动力学建模(附Matlab仿真) - 2

    目录0专栏介绍1平面2R机器人概述2运动学建模2.1正运动学模型2.2逆运动学模型2.3机器人运动学仿真3动力学建模3.1计算动能3.2势能计算与动力学方程3.3动力学仿真0专栏介绍?附C++/Python/Matlab全套代码?课程设计、毕业设计、创新竞赛必备！详细介绍全局规划(图搜索、采样法、智能算法等)；局部规划(DWA、APF等)；曲线优化(贝塞尔曲线、B样条曲线等)。?详情：图解自动驾驶中的运动规划(MotionPlanning)，附几十种规划算法1平面2R机器人概述如图1所示为本文的研究本体——平面2R机器人。对参数进行如下定义：机器人广义坐标

  6. ruby - 如果键存在，向散列值添加一些东西？ - 2

    我在Ruby中有一个哈希:hash=Hash.new里面有一些键值对，比如说:hash[1]="One"hash[2]="Two"如果散列包含键2，那么我想将“Bananas”添加到它的值中。如果散列没有键2，我想创建一个新的键值对2=>"Bananas"。我知道我可以通过首先使用has_key?检查散列是否具有key2来做到这一点，然后采取相应的行动。但这需要一个if语句和不止一行。那么是否有一种简单、优雅的单行代码可以实现这一目标？ 最佳答案 这个有效:hash[2]=(hash[2]||'')+'Bananas'如果您希望所有

  7. 网站日志分析软件--让网站日志分析工作变得更简单 - 2

    网站的日志分析，是seo优化不可忽视的一门功课，但网站越大，每天产生的日志就越大，大站一天都可以产生几个G的网站日志，如果光靠肉眼去分析，那可能看到猴年马月都看不完，因此借助网站日志分析工具去分析网站日志，那将会使网站日志分析工作变得更简单。下面推荐两款网站日志分析软件。第一款：逆火网站日志分析器逆火网站日志分析器是一款功能全面的网站服务器日志分析软件。通过分析网站的日志文件，不仅能够精准的知道网站的访问量、网站的访问来源，网站的广告点击，访客的地区统计，搜索引擎关键字查询等，还能够一次性分析多个网站的日志文件，让你轻松管理网站。逆火网站日志分析器下载地址：https://pan.baidu.

  8. ABB-IRB-1200运动学分析MATLAB RVC工具分析+Simulink-Adams联合仿真 - 2

    一、机器人介绍        此处是基于MATLABRVC工具箱，对ABB-IRB-1200型号的微型机械臂进行正逆向运动学分析，并利Simulink工具实现对机械臂进行具有动力学参数的末端轨迹规划仿真，最后根据机械模型设计Simulink-Adams联合仿真。 图1.ABBIRB 1200尺寸参数示意图ABBIRB 1200提供的两种型号广泛适用于各作业，且两者间零部件通用，两种型号的工作范围分别为700 mm 和 900 mm，大有效负载分别为 7 kg 和5 kg。 IRB 1200 能够在狭小空间内能发挥其工作范围与性能优势，具有全新的设计、小型化的体积、高效的性能、易于集成、便捷的接

  9. 关于Qt程序打包后运行库依赖的常见问题分析及解决方法 - 2

    目录一.大致如下常见问题：（1）找不到程序所依赖的Qt库version`Qt_5'notfound(requiredby（2）CouldnotLoadtheQtplatformplugin"xcb"in""eventhoughitwasfound（3）打包到在不同的linux系统下，或者打包到高版本的相同系统下，运行程序时，直接提示段错误即segmentationfault，或者Illegalinstruction(coredumped)非法指令（4）ldd应用程序或者库，查看运行所依赖的库时，直接报段错误二.问题逐个分析，得出解决方法：（1）找不到程序所依赖的Qt库version`Qt_5'

  10. ruby-on-rails - 如何使用 ruby​​-prof 和 JMeter 分析 Rails - 2

    我想使用ruby​​-prof和JMeter分析Rails应用程序。我对分析特定Controller/操作/或模型方法的建议方法不感兴趣，我想分析完整堆栈，从上到下。所以我运行这样的东西:RAILS_ENV=productionruby-prof-fprof.outscript/server>/dev/null然后我在上面运行我的JMeter测试计划。然而，问题是使用CTRL+C或SIGKILL中断它也会在ruby​​-prof可以写入任何输出之前杀死它。如何在不中断ruby​​-prof的情况下停止mongrel服务器？ 最佳答案

随机推荐