转载请注明http://www.cnblogs.com/majianming/p/8006452.html

有人问我，java ArrayList底层是怎么实现的？我就回答数组，他再问我，那它是怎么实现数组的添加的呢？我也不知道，就不敢回答了。

回来赶紧看了一下java实现，明确的是ArrayList底层的确是用数组实现的，但是怎么实现数组的扩容的呢?

简单来说，就是创建一个新的比原来大的数组，把原来所有的元素复制到新的数组，然后添加新的数组进去

先从无参构造函数开始，无参构造函数创建了一个容量为0的空数组（这里要注意，在jdk1.8时采用的是创建空数组，在1.7还是创建了一个容量为10的数组，源码见附录1，2，这里以1.8为例）

然后就可以开始调用add方法添加元素，这里先以public boolean add(E e)方法为例

  1. 计算最小容量：判断是不是第一次添加，准确来说是不是一个空数组。如果是一个空数组，那么设置初始化大小（即最小容量）为10，如果不是，那么在原来基础上大小+1。
  2. 判断是否需要扩容：判断最小容量是不是大于数组长度（至少大1），如果是，进行第3步。为什么有这个判断？是最小容量是数组可以存放的元素个数，而数组长度是实际上存放的个数，那么就会出现数组还没放满的情况，比如第二次添加时，数组容量为10（第一次初始化时设置为10），元素加上新增加的只有两个，是不需要进行第3，4步的
  3. 扩容计算：复制旧元素到新数组：上一步计算的只是一个值，没有对原来的进行修改，也没有创建新的数组。接下来使用Arrays.copyOf将原来数组的所有元素复制到新数组（以最小容量创建的），并返回

    1. 取得已有元素的个数，准备设置新的容量为原来元素个数的1.5倍
    2. 将1中的新容量和最小容量相对比，取大的（所以初始化时原来元素的1.5倍为0小于最小容量10，设置为10）
    3. 将2中计算结果与Integer.MAX_VALUE – 8对比（为啥是-8 ，doc上是说明了一些虚拟机实现需要多存一些头信息，为了防止oom，其他没有说明，在stackoverflow上说明了为了存下数组的最大大小2,147,483,648所以需要（见附录3）），还大，那就没办法了，只能设置为Integer.MAX_VALUE。也就是说正常情况下数组最大容量为下最大值减8，否则就是最大值。这个时候放不下那就只能抛异常了呗！
  4. 复制旧元素到新数组：上一步计算的只是一个值，没有对原来的进行修改，也没有创建新的数组。接下来使用Arrays.copyOf将原来数组的所有元素复制到新数组（以3中计算的最后容量创建的），并返回
  5. 把添加的元素添加到新返回的数组最后，长度+1

 以上

附录

  1. jdk 1.7 ArrayList
  2. jdk 1.8 ArrayList
  3. 为什么-8

 参考

Java中ArrayList源码浅析

设定

jdk：1.8_102

 

 转载请注明http://www.cnblogs.com/majianming/p/8006452.html

 

版权声明：本文为majianming原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/majianming/p/8006452.html