ArrayList扩容分析
博客专区 > modprobe 的博客 > 博客详情
ArrayList扩容分析
modprobe 发表于1年前
ArrayList扩容分析
  • 发表于 1年前
  • 阅读 4
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

一段java代码

1 String e = "q3234v"; 2 List<String> list = new ArrayList<String>(); 3 for (int i = 0; i < 25; i++) { 4  list.add(e); 5 }

执行这段代码,list会扩容几次

查看ArrayList的add方法,在添加元素之前会执行ensureCapacityInternal方法

这个时候size为0

1   public boolean add(E e) { 2         ensureCapacityInternal(size + 1);  // Increments modCount!!
3         elementData[size++] = e; 4         return true; 5     }

 

继续看ensureCapacityInternal方法,DEFAULT_CAPACITY的值为10,此时minCapacity为1

private static final int DEFAULT_CAPACITY = 10;

 

1 private void ensureCapacityInternal(int minCapacity) { 2     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 3         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 4  } 5  ensureExplicitCapacity(minCapacity); 6 }

这时候执行:ensureExplicitCapacity

此时minCapacity的值为10,接下来执行扩容方法

1 private void ensureExplicitCapacity(int minCapacity) { 2     modCount++; 3     // overflow-conscious code
4     if (minCapacity - elementData.length > 0) 5  grow(minCapacity); 6 }

 

 

 1  private void grow(int minCapacity) {  2         // overflow-conscious code
 3         int oldCapacity = elementData.length;  4         int newCapacity = oldCapacity + (oldCapacity >> 1);  5         if (newCapacity - minCapacity < 0)  6             newCapacity = minCapacity;  7         if (newCapacity - MAX_ARRAY_SIZE > 0)  8             newCapacity = hugeCapacity(minCapacity);  9         // minCapacity is usually close to size, so this is a win:
10         System.out.println(minCapacity+"------"+newCapacity); 11 
12         elementData = Arrays.copyOf(elementData, newCapacity); 13 }

minCapacity的值为10

新空间大小的值为 0+0>>1 = 0

所以第一次扩容完 后新空间大小为10

接下当list.add()执行到第11次的时候

minCapacity=11

newCapacity = 10+10>>1 = 15(1010>>1 = 101= 5)

i执行到16的时候,此时又发现空间不够了

minCapacity=16

newCapacity = 15+15>>1 = 22(1111>>1 = 7)

所以容量到25还需要再执行一次扩容

一共会执行4次扩容

这时候可能会发现在扩容的时候会执行 elementData = Arrays.copyOf(elementData, newCapacity)方法

所以为了减少copyOf的操作

在大概知道List的长度的情况下,在创建的时候应该给一个容量,在容量不够的情况下才会执行扩容操作

 1 public ArrayList(int initialCapacity) {  2         if (initialCapacity > 0) {  3             this.elementData = new Object[initialCapacity];  4         } else if (initialCapacity == 0) {  5             this.elementData = EMPTY_ELEMENTDATA;  6         } else {  7             throw new IllegalArgumentException("Illegal Capacity: "+
 8  initialCapacity);  9  } 10     }

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 1
博文 35
码字总数 0
×
modprobe
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: