HashMap的容量与扩容

avatar 2018年03月06日21:08:11 6 3111 views
博主分享免费Java教学视频，B站账号：Java刘哥 ，长期提供技术问题解决、项目定制：本站商品点此
紧接着上一篇文章  HashMap 实现原理和源码分析，因为上篇文章在扩容方面写得并不详细，博主于是在网上找了一篇比较好的关于 HashMap 的扩容的文章

原文地址：http://blog.csdn.net/gaopu12345/article/details/50831631



有几个重要的常量：
  1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//默认的桶数组大小
  2. static final int MAXIMUM_CAPACITY = 1 << 30;//极限值（超过这个值就将threshold修改为Integer.MAX_VALUE（此时桶大小已经是2的31次方了），表明不进行扩容了）
  3. static final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子（请阅读下面体会这个值的用处）

（一）调用HashMap()构造方法


这个构造方法长这样：
  1. public HashMap() {
  2.         this.loadFactor = DEFAULT_LOAD_FACTOR; //设置一个默认的负载因子，默认为0.75，下面说它有啥用
  3. }

这就完了，然后用于hash的桶数组为null，当我们第一次put的时候，会到达这段代码：
  1. Node<K,V>[] tab; int n;
  2.     //table就是桶数组，初始为null
  3.     if ((tab = table) == null || (n = tab.length) == 0)
  4.         n = (tab = resize()).length;

所以会进入resize()方法，到达这段代码：
  1. //取消多余的代码，我直接贴上进入的这个分支的代码
  2. else {
  3.       newCap = DEFAULT_INITIAL_CAPACITY;
  4.       newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  5. }

newCap的意思是：即将用于hash的桶数组的长度，这里的默认值是16
newThr的意思是：当桶中的键值对的个数超过这个值时就进行扩容，这时候上面提到的负载因子就起作用了，所以这里的newThr为0.75×16 = 12

所以经过这个默认构造方法，并且进行第一次put后，桶数组建立了，桶容量为16，极限值为12。


（二）调用HashMap(int initialCapacity)构造方法

  1. public HashMap(int initialCapacity) {
  2.     //这个方法实际调用另一个构造方法，所以这个构造方法就不分析了，直接看第三个的分析
  3.     this(initialCapacity, DEFAULT_LOAD_FACTOR);
  4. }


（三）调用HashMap(int initialCapacity, float loadFactor)构造方法

  1. public HashMap(int initialCapacity, float loadFactor) {
  2.     //桶数组的大小小于0时抛异常
  3.     if (initialCapacity < 0)
  4.         throw new IllegalArgumentException("Illegal initial capacity: " +
  5.                                                initialCapacity);
  6.     //如果桶数组的大小超过最大值，则简单的将桶容量修改为最大值2的30次方
  7.     if (initialCapacity > MAXIMUM_CAPACITY)
  8.         initialCapacity = MAXIMUM_CAPACITY;
  9.     //如果负载因子不符合规范，那么抛异常
  10.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  11.         throw new IllegalArgumentException("Illegal load factor: " +
  12.                                                loadFactor);
  13.     this.loadFactor = loadFactor;
  14.     //这个意思是根据桶数组的大小求一个“极限值threshold”，当桶中的键值队个数超过这个大小就进行扩容
  15.     //tableSizeFor方法求得的数字是刚超过initialCapacity的一个2的n次方的数，例如initialCapacity是1000，那么得到的threshold就是1024
  16.     this.threshold = tableSizeFor(initialCapacity);
  17.     }



所以经过这个方法之后，桶容量确定了，极限值也确定了，但是桶数组还是null。
当第一次put时，触发如下代码：
  1. //发现桶数组是null，所以需要新建一个桶数组
  2. if ((tab = table) == null || (n = tab.length) == 0)
  3.     n = (tab = resize()).length;



接着看resize()中触发了哪些代码：
  1. Node<K,V>[] oldTab = table;
  2. int oldCap = (oldTab == null) ? 0 : oldTab.length;//看这里，oldCap会是0
  3. int oldThr = threshold;//看这里，oldThr不会是0，因为有tableSizeFor()方法，确保oldThr至少是1
  4. int newCap, newThr = 0;
  5. if (oldCap > 0) {
  6.     if (oldCap >= MAXIMUM_CAPACITY) {
  7.         threshold = Integer.MAX_VALUE;
  8.         return oldTab;
  9.     }
  10.     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  11.             oldCap >= DEFAULT_INITIAL_CAPACITY)
  12.         newThr = oldThr << 1; // double threshold
  13. }
  14. //所以肯定会进入这个分支，将桶数组的大小改为极限值大小。然后在下面创建一个newCap大小的桶数组
  15. else if (oldThr > 0) // initial capacity was placed in threshold
  16.     newCap = oldThr;

然后还会进入下面这个分支：
  1. if (newThr == 0) {
  2.             float ft = (float)newCap * loadFactor;
  3.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  4.                       (int)ft : Integer.MAX_VALUE);
  5.         }

这个分支会按负载因子设置极限值


（四）超过极限值后的扩容


在每次put之后，会有下面这个判断：
  1. if (++size > threshold)
  2.     resize();

就是说超过极限值时会进行扩容，扩容方式如下：
  1. Node<K,V>[] oldTab = table;
  2. int oldCap = (oldTab == null) ? 0 : oldTab.length;
  3. int oldThr = threshold;
  4. int newCap, newThr = 0;
  5. //肯定会进入这个分支
  6. if (oldCap > 0) {
  7.     if (oldCap >= MAXIMUM_CAPACITY) {
  8.         threshold = Integer.MAX_VALUE;
  9.         return oldTab;
  10.     }
  11.     //如果我们是这样调用：HashMap(7，任意满足条件的值），那么经过第一次调用put()会初始化桶数组的大小和极限值一样，这里即为8。所以这里不会进入这个分支，但是newCap会变为16
  12.     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  13.             oldCap >= DEFAULT_INITIAL_CAPACITY)
  14.         newThr = oldThr << 1; // double threshold
  15. }
  16. //所以会进入这里
  17. if (newThr == 0) {
  18.     float ft = (float)newCap * loadFactor;
  19.     newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  20.             (int)ft : Integer.MAX_VALUE);
  21. }
  22. threshold = newThr;//计算的出这里的threshold即极限值会由刚才的8变为12（和负载因子大小有关）

接上面这个例子，下一次扩容会如何？
  1. if (oldCap > 0) {
  2.     if (oldCap >= MAXIMUM_CAPACITY) {
  3.         threshold = Integer.MAX_VALUE;
  4.         return oldTab;
  5.     }
  6.     //因为桶容量变为了16，所以这次会进入这个分支，桶容量和极限值都会加倍。
  7.     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  8.             oldCap >= DEFAULT_INITIAL_CAPACITY)
  9.         newThr = oldThr << 1; // double threshold
  10. }

直到…………

当桶容量加倍到最大值会怎么样？
  1. //因为每次都是加倍，所以最终肯定会加倍到MAXIMUM_CAPACITY，会进入这个分支。
  2. if (oldCap >= MAXIMUM_CAPACITY) {
  3.     threshold = Integer.MAX_VALUE;
  4.     return oldTab;
  5. }

桶容量变为最大值时，紧接着的一次扩容只是简单的将极限值修改为Integer.MAX_VALUE。桶数组大小并不会继续加倍


（五）如果HashMap中的键值对数量超过Integer.MAX_VALUE了呢？


我们仔细看一下这段代码：
  1. //这个size类型是int，那么最大就是Integer.MAX_VALUE，所以不会有++size > threshold的情况，往后都不会进行扩容了。
  2. if (++size > threshold)
  3.     resize();



历史上的今天
三月
06日
  • 微信
  • 交流学习，资料分享
  • weinxin
  • 个人淘宝
  • 店铺名：言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

avatar 登录者：匿名
匿名评论，评论回复后会有邮件通知

  

已通过评论：0   待审核评论数：0