HashMap的容量与扩容

avatar 2018年03月06日21:08:11 6 2979 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();



  • 微信
  • 交流学习,资料分享
  • weinxin
  • 个人淘宝
  • 店铺名:言曌博客咨询部

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

发表评论

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

  

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