动态数组在某个临界点反复扩容和缩容时会不会增加系统开销？

Question

比如在视频中在10这个临界点如果增加一个元素，数组扩容为20，此时再删除一个元素，数组将缩容为10，如此反复，每次都是开辟一个新数组，并将遍历数组，会不会增加系统开销？

Answer 1

提问者 慕先生7991853 2018-04-26 18:32:21

已经在“均摊复杂度和防止复杂度震荡”中看到分析，解决方案是在缩容时使用“懒惰”策略，当原数组元素个数减为原来的1/4时，此时再进行缩容为原来的1/2，可在较大程度上避免此类情况下出现的震荡。

注意边界判断情况：以初始容量为10为例仅考虑缩容，当元素个数减为10/4=2时，容量减为10/2=5，当元素个数减为5/4=1时，容量减为5/2=2，当元素个数减为2/4=0时，此时size指向0，应减为的容量为2/2=0，在创建数组时不能创建长度为0的数组，故应在边界判断上再加上data.length/2!=0。

另外，“在创建数组时不能创建长度为0的数组”不是指的java中不能创建长度为0的数组，int[] a=new int[0];可以正常运行，只是基于此例创建长度为0的数组没意义，size无法指向，并且在扩容时0乘以任何数等于0，故应加边界控制条件避免此类情况发生。

• liuyubobobo #1

  大赞！继续加油：）

• 二段媒介 #2

  @weixin_天意_0, 感觉你的第二段话说的有问题：
  1. 元素个数减为10 / 4 = 2个时，容量减为10 / 2 = 5;
  2. 元素个数减为 5/4 = 1个时， 容量减为 5 / 2 = 2;
  3. 元素个数减为 2/4 = 0个时，容量减为 2 / 2 = 1（这里是1，而不是0。。。），此时就没法进行remove操作了，只能add，所以不会出现new int[0]的操作

• 二段媒介 #3

  data.length = 1, size = 0, 就会存在data.length / 2 = 0的情况，我的锅、