ArrayList源码解析(一)

  • 2019 年 10 月 24 日
  • 筆記

欢迎转载，转载烦请注明出处，谢谢。

https://www.cnblogs.com/sx-wuyj/p/11177257.html

自己学习ArrayList源码的一些心得记录..

1.1 ArrayList的体系

  • Iterable : iterable接口里定义了返回iterator的方法，相当于对iterator的封装，同时实现了iterable接口的类可以支持for each循环;
  • Collction : 集合框架中的根接口,下面有三大子接口.List Set Queue;
  • AbstractCollection: 实现了Collection的一些接口,同时也定义了一些抽象方法交给子类实现.
  • List : List接口定义了一些公用的接口,比如 toArray() size() add()等接口;

  • AbstractList :AbstractList 是一个抽象类，实现了List接口，是隶属于Java集合框架中的根接口 Collection 的分支

    1.2 ArrayList构造方法.

    /**       *  有参构造  int类型  集合的大小       */      public ArrayList(int initialCapacity) {          //如果参数大于0,缓冲数组的大小就为该参数          if (initialCapacity > 0) {              this.elementData = new Object[initialCapacity];          //如果参数等于0,创建一个空的实例数组          } else if (initialCapacity == 0) {              this.elementData = EMPTY_ELEMENTDATA;          } else {              //异常为非法容量 + 参数              throw new IllegalArgumentException("Illegal Capacity: "+                                                 initialCapacity);          }      }         /**       * Constructs an empty list with an initial capacity of ten.       * 无参构造       */      public ArrayList() {          //缓冲数组为空的默认大小的共享实例          this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;      }         //有参构造   参数为任意类或者E的子类      //任意类或者E的子类,孙子类等collection都可以构造一个ArrayList出来      public ArrayList(Collection<? extends E> c) {          //转为缓存数组          elementData = c.toArray();          //将数组的长度赋值给size,如果数组长度不等于0          if ((size = elementData.length) != 0) {              // c.toArray might (incorrectly) not return Object[] (see 6260652)              //缓存数组的class不等于object类型数组的class              if (elementData.getClass() != Object[].class)                  //copyOf方法:返回一个数组                  elementData = Arrays.copyOf(elementData, size, Object[].class);          } else {              // replace with empty array.              //替换为一个空的数组              this.elementData = EMPTY_ELEMENTDATA;          }      }

以上就是ArrayList的构造方法,注释是我自己一行一行写出来的,可能会有所误解,欢迎批评指正.

1.3 arrayList常用的方法

  • add() : 向集合内部添加元素,这个方法其实是Collection接口中定义的,AbstractCollection抽象类中实现这个方法,ArrayList中重写了这个方法.如果直接调用AbstractCollection中的add方法,那么只会抛出一个不支持操作的异常.需要注意一点就是add()一共有两个,但是其中一个是有boolean的返回值,另一个是void并没有返回值.

boolean返回值add(),元素添加是为最后一位.

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

首先看一下 ensureCapacityInternal(size + 1)这个方法

    private void ensureCapacityInternal(int minCapacity) {            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {              //max方法为一个三元运算,参数类型为int类型,(a >= b) ? a : b;              //size+1 大于等于 初始值 返回初始值10              minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);          }            ensureExplicitCapacity(minCapacity);      }  又调用了ensureExplicitCapacity()方法        private void ensureExplicitCapacity(int minCapacity) {              modCount++;              //需要的大小大于底层数组的大小              if (minCapacity - elementData.length > 0)                  grow(minCapacity);          }  继续调用了grow()方法,这个方法很关键,先看源码        private void grow(int minCapacity) {          //数组长度赋值给oldCapacity          int oldCapacity = elementData.length;          //oldCapacity >> 1 相当于 oldCapacity / 2          //newCapacity 为数组长度的1.5倍          int newCapacity = oldCapacity + (oldCapacity >> 1);          //newCapacity小于minCapacity          if (newCapacity - minCapacity < 0)              //minCapacity赋值于newCapacity              newCapacity = minCapacity;          //newCapacity大于MAX_ARRAY_SIZE          if (newCapacity - MAX_ARRAY_SIZE > 0)              newCapacity = hugeCapacity(minCapacity);          //通过copyOf方法返回一个数组          elementData = Arrays.copyOf(elementData, newCapacity);      }

整体来说 如果size+1小于10,那么minCapacity就是10,10就是默认大小.如果大于10,那么minCapacity则为size+1.

minCapacity-lementData.length 如果size+1比底层数组小,那么可以继续向默认数组中添加元素.如果size+1大于底层数组,就调用grow()进行扩容.

grow()这个方法就是arrayList自动扩容的方法.newCapacity为数组的1.5倍,先判断newCapacity是否小于
minCapacity,也就是size+1
如果小于那么将minCapacity赋值于newCapacity.

再判断newCapacity是否大于MAX_ARRAY_SIZE,关于MAX_ARRAY_SIZE下面有代码.

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;

如果大于就调用hugeCapacity()方法

    private static int hugeCapacity(int minCapacity) {          //minCapacity 小于 0 报错          if (minCapacity < 0) // overflow              throw new OutOfMemoryError();          //minCapacity大于MAX_ARRAY_SIZE吗?          //大于返回Integer.MAX_VALUE          //小于返回MAX_ARRAY_SIZE          return (minCapacity > MAX_ARRAY_SIZE) ?              Integer.MAX_VALUE :              MAX_ARRAY_SIZE;      }

最后将elementData,也就是底层数组.lenth变为newCapacity.
总结起来说,arrayList的扩容机制其实就修改底层数组的大小.
继续回头add()方法往下看:

elementData[size++] = e;

这个其实很好理解了,e就是你要添加的那个新的元素,size++就是新元素在底层数组中的位置.

return true;
最后返回一个 true 添加成功

void add(),

    public void add(int index, E element) {          //校验index          rangeCheckForAdd(index);          ensureCapacityInternal(size + 1);  // Increments modCount!!          System.arraycopy(elementData, index, elementData, index + 1,                           size - index);          elementData[index] = element;          size++;      }

rangeCheckForAdd(index);

 private void rangeCheckForAdd(int index) {       //如果index大于size或者index小于0 就抛出异常          if (index > size || index < 0)              throw new IndexOutOfBoundsException(outOfBoundsMsg(index));      }

ensureCapacityInternal(size + 1);

这个在前面有说过,就不在细说,可以去看一下前面add()带返回值的那个解析.

System.arraycopy(elementData, index, elementData, index + 1,size – index);

调用System提供的arraycopy(),这是一个静态native方法,native这里不进行说明,可以百度进行查看.这个方法就是现数组之间的复制。

    elementData:底层数组.      index:数组要复制的起始位置.      elementData:复制后的数组.      index + 1:数组放置的起始位置.      size - index:复制的长度

elementData[index] = element;

将要添加的元素放入指定的位置.

size++

将集合的长度+1.

由于arrayList源码较为庞大,暂且先写一部分,后续会继续更新.

以上博文个人手写,如果有错,希望各位大佬多多体谅,欢迎批评指正.

VirMach 便宜 VPS

QNews

QNews