黑马程序员技术交流社区

标题: 【南京校区】arrayList源码分析 [打印本页]

---

作者: 大蓝鲸小蟀锅    时间: 2020-5-22 10:50
标题: 【南京校区】arrayList源码分析
ArrayList是最最最最常用的一种集合
那么他的缺点是什么呢？优点是什么呢？在什么情况下适合使用,我们平时使用的对吗?
缺点一:
    ArrayList实现底层是通过数组实现的, 数组的长度是固定的，java里面数组都是定长数组，比如数组大小设置为100，此时你不停的往ArrayList里面塞入这个数据，此时元素数量超过了100以后，此时就会发生一个数组的扩容，就会搞一个更大的数组，把以前的数组拷贝到新的数组里面去. 这个数组扩容+元素拷贝的过程，相对来说会慢一些. 所以不要频繁的往arralist里面去塞数据，如果数据过多,会导致ArrayList频繁的数组扩容，扩容的时候较差的性能会影响系统的运行.

缺点二：
    数组来实现，数组你要是往数组的中间加一个元素，是不是要把数组中那个新增元素后面的元素全部往后面挪动一位，所以说，如果你是往ArrayList中间插入一个元素，性能比较差，会导致他后面的大量的元素挪动一个位置

优点:
    基于数组来实现，非常适合根据索引来读数据，你可以随机的去读数组中的某个元素，list.get(10)，相当于是在获取第11个元素，这个随机读的性能是比较高的，随机读取ArrayList任何索引中的数据性能都很高，list.get(2)，list.get(20). 因为基于数组来实现，他在随机获取数组里的某个元素的时候，性能很高，他可以基于他底层对数组的实现来快速的随机读取到某个元素，直接可以通过内存地址来定位某个元素。

    ArrayList，常用，如果你不会频繁的在里面插入一些元素，不会导致频繁的元素的位置移动、数组扩容，就是有一批数据，查询出来，灌入ArrayList中，后面不会频繁插入元素了，主要就是遍历这个集合，或者是通过索引随机读取某个元素, 这些情况下使用ArrayList还是比较合适的.
    若果你涉及到了频繁的插入元素到list中的话，尽量还是不要用ArrayList，数组，定长数组，长度是固定的，元素大量的移动，数组的扩容+元素的拷贝. 项目开发的时候，大量的场景，需要一个集合，里面可以按照顺序灌入一些数据，ArrayList的话呢，他的最最主要的功能作用，就是说他里面的元素是有顺序的，我们在系统里的一些数据，都是需要按照我插入的顺序来排列的.

进去看看各种集合的实现原理，直接可以看JDK底层的源码

    默认的构造函数，直接初始化一个ArrayList实例的话，会将内部的数组做成一个默认的空数组，{}，Object[]，elementDate就是arrayList中,保存元素的组件.

那默认是空数组,在添加元素的时候怎么做呢? 看下arrayList的基本操作的源码.

（1）add()方法的源码

ensureCapacityInternal(size + 1); 就是arrayList最神奇的地方, 是如何做到可变数组的呢?
你每次往ArrayList中塞入数据的时候，人家都会判断一下，当前数组的元素是否塞满了，如果塞满的话，此时就会扩容这个数组，然后将老数组中的元素拷贝到新数组中去，确保说数组一定是可以承受足够多的元素的,把增删改查分析完后,再来分析这个方法.
初始化后arrayList中数据:
    elementData = []
    size = 0
执行: arrayList.add("张三");
    elementData[size++] = e;
    翻译为:
        element[0] = “张三”
        size++
执行后, arrayList中数据:
    elementData = [“张三”]
    size = 1
执行: arrayList.add("李四");
    elementData[size++] = e;
    翻译为:

        elementData[1] = “李四”
        size++
执行后, arrayList中数据:

    elementData = [“张三”, “李四”]
    size = 2
（2）set()方法的源码

set方法可以修改对应arrayList中elementData[]中对应索引的元素. 如果此时我们传入的index超过了arrayList.size长度了怎么办, 这样不就出现问题了吗? jdk在rangeCheck进行了判断.


大家是不是看到一个很熟悉的异常, 数组越界异常, 如果你输入的index >= size , 已经超出arrayList中元素长度了, 直接抛出异常.
已刚才arrayList中元素为例:
执行: set(3, “赵六”) => 典型的数组越界
执行: set(1, “赵六”)

    E oldValue = elementData(index);    // 获取到了1这个位置的元素的值，李四
此时oldValue: oldValue = “李四”
    elementData[1] = “赵六”
                return oldValue;
执行后, arrayList中数据:

    elementData = [“张三”, “赵六”]
    返回了一个”李四”
为啥大家看api文档的时候, 会说set方法执行后, 会把之前的旧值返回出来, 因为jdk源码就是这样写的呀.

（3）add(index, element)方法的源码

在执行之前和set方法一样,需要判断索引是否越界, 通过rangeCheckForAdd(index)方法. 如果不在可用范围内,直接抛出索引越界异常.

但是我们观看Jdk源码发现,此方法与add()方法有一点区别, 多了一个System.arraycopy(),这个方法是做什么呢? 通过名字分析,是用来拷贝数组的. 具体看下执行流程.
已之前arrayList为基础:
执行: add(1, “麻子”);
此时arrayList中数据为:
    index = 1
    size = 2
    elementData = [“张三”, “赵六”]
    此时会执行: System.arraycopy(elementData, index, elementData, index + 1, size - index);
    System.arraycopy(elementData, 1, elementData, 2, 1);
你可以认为他这个方法的意思，就是说：elementeData这个数组，从index = 1索引位开始（第二个元素），拷贝 (size - index) = 1个元素，到elementData这个数组（还是原来的这个数组），从 (index + 1) = 2 索引位置开始
此时arrayList中的数据为:
    elementData = [“张三”, “赵六”, “赵六”]
    size = 2
继续执行代码:
    elementData[1] = “麻子”
                 size++
此时arrayList中的数据为:

    elementData = [“张三”, “麻子”, “赵六”]

    size = 3

（4）get()方法的源码

这个方法是最简单了，直接elementData[index]，基于数组直接定位到这个元素，获取这个元素，这个是ArrayList性能最好的一个操作，是arrayList的优点所在

（5）remove()方法的源码

里面的方法我们都见过,就不去解释每一个方法来, 直接来分析执行流程.
已之前arrayList为基础:
此时arrayList中的数据为:
    size = 3
    index = 1
    elementData = [“张三”, “麻子”, “赵六”]

执行: arrayList.remove(1);

实际上jdk执行了:
    E oldValue = elementDate(index);

    int numMoved = size - index - 1;
    System.arraycopy(elementData, index + 1, elementData, index, numMoved);

翻译代码为:
    oldValue = "麻子";

    numMoved = 3 - 1 - 1 = 1
    System.arraycopy(elementData, 2, elementData, 1, 1);
把elementData数组中，从index = 2 开始的元素，一共有 munMoved = 1 个元素，拷贝到elementData数组中（原来的数组里），从index = 1开始，进行拷贝

相当于是不是要把后面的“赵六”要往前面挪动一位
此时arrayList中的数据为:
    size = 3
    index = 1
    elementData = [“张三”, “赵六”, “赵六”]
继续向下执行:
    elementData[--size] = null;
    return oldValue;
此时arrayList中的数据为:
    size = 3
    index = 1
    elementData = [“张三”, “赵六”]
返回oldValue = "麻子";


（6）源码分析的总结
remove(); add(index, element)
这个两个方法，都会导致数组的拷贝，大量元素的挪动，性能都不是太高，基于数组来做这种随机位置的插入和删除，其实性能真的不是太高.add()、add(index, element)，这两个方法，都可能会导致数组需要扩容，数组长度是固定的，默认初始大小是10个元素，如果不停的往数组里塞入数据，可能会导致瞬间数组不停的扩容，影响系统的性能. set()、get()，定位到索引的位置，替换那个元素，或者是获取那个元素，这个其实还是比较靠谱的，基于数组来实现随机位置的定位，性能是很高的.

ArrayList里面最关键的一块，ensureCapacityInternal(size + 1);

就是如果数组填充满了以后，arrayList如何进行自动扩容的.



先来看这个方法, 通过刚才的源码分析,知道arrayList空参构造,给我们创建的是一个空数组,那么数组没有长度,它是如何来保存元素的呢?
在add()方法中,会调用ensureCapacityInternal(size + 1);
在我们插入第一个值时,minCapacity就是1.
会先调用calculateCapacity(elementData,minCapacity)方法,
jdk会执行:
    if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
        return Math.max(DEFAULT_CAPACITY,minCapacity);
    }
其中涉及到两个默认值:

DEFAULTCAPACITY_EMPTY_ELEMENTDATA眼熟不眼熟, 就是我们在空参构造中给elementData指向的空数组. DEFAULT_CAPACITY就是默认的容器大小, 如果你是第一次添加元素, 通过Math.max()方法,得到两个里面的最大值, 第一次添加, 肯定是10大.

接下来会执行, ensureExplicitCapacity()方法, 如果Math.max()返回的值,超过的elementData数组的长度, 就会执行grow()方法, 对数组进行增长, 默认我们得到的是空数组, 默认长度是0, 所以需要进行增长, 那么增长多大呢? 看下grow()的源码.

有两种情况,
第一次插入元素:
    此时arrayList中属性情况:

    elementData = {};

执行:
    int oldCapacity = elementData.length;

    int newCapacity = oldCapacity + (oldCapacity >> 1);

结果为:
    oldCapacity = 0;
    newCapacity = 0;
执行:

   if(newCapacity - minCapacity < 0){
        newCapacity = minCapacity;

   }
elementData = Arrays.copyOf(elementData,newCapacity);
如增长后的长度, 还没有minCapacity大,那么拷贝数据到新数组的长度就使用minCapacity, minCapacity = DEFAULT_CAPACITY.
所以可以说, arrayList的默认长度是0, 也可以说arrayList的默认长度是10.
第十一次插入元素:
    此时arrayList中属性情况:
    elementData = {"0","1","2","3","4","5","6","7","8","9"};
    size = 10;
   elementData = 10;
执行:
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
结果为:
    oldCapacity = 10;
    newCapacity = 15;
执行:
   if(newCapacity - minCapacity < 0){
        newCapacity = minCapacity;
   }
elementData = Arrays.copyOf(elementData,newCapacity);
此时minCapacity = size + 1; 因为已经不是空数组了. 第十一次插入元素, 所以size = 10. minCapacity = 11;
if判断不进去, 直接执行Arrays.copyOf()方法, 所以此时elementData的增长长度是 5 , 也就是增长了百分之50. 源码中使用位移运算符, 为了提高效率.
此时arrayList中属性情况是:   
  elementData = {"0","1","2","3","4","5","6","7","8","9","11","","","",""};
  size = 10;
  elementData = 15;
看完了这个JDK的源码，非常简单的，算扩容的新数组的大小，就知道是怎么来计算的，搞一个新数组，Arrays.copyOf()工具方法，完成老数组到新数组的一个拷贝.

ArrayList源码就看完了,它是基于数组来玩儿，最大的问题就是不要频繁的往里面灌入大量的数据，导致频繁的数组的扩容，新老数组元素拷贝，中间的位置插入元素，删除元素，会导致大量的元素的移动. 随机获取一个元素，get(10)操作，性能极高，他适合随机读，不适合大量频繁的写入以及插入
ArrayList的话，玩儿好的话，一般来说，你应该都不是使用这个默认的构造函数，你构造一个ArrayList的话，基本上来说就是默认他里面不会有太频繁的插入、移除元素的操作，大体上他里面有多少元素，你应该可以推测一下的基本上最好是给ArrayList构造的时候，给一个比较靠谱的初始化的数组的大小，比如说，100个数据，1000,10000，避免数组太小，往里面塞入数据的时候，导致数据不断的扩容，不断的搞新的数组.

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2