Skip to content

Latest commit

 

History

History
206 lines (176 loc) · 8.8 KB

ArrayList.md

File metadata and controls

206 lines (176 loc) · 8.8 KB

JDK14 ArrayList 分析

1.概述

作为程序员，一定很熟悉 ArrayList, 可调整大小的数组的实现List接口。实现所有可选列表操作，并允许所有元素，包括null 。除了实现List 接口之外，该类还提供了一些方法来操纵内部使用的存储列表的数组的大小。（这个类是大致相当于Vector，不同之处在于它是不同步的）。

该size，isEmpty，get，set，iterator和listIterator操作在固定时间内运行。 add操作以摊余常数运行 ，即添加n个元素需要O（n）个时间。 所有其他操作都以线性时间运行（粗略地说）。 与LinkedList实施相比，常数因子较低。

每个ArrayList实例都有一个容量 。 容量是用于存储列表中的元素的数组的大小。 它总是至少与列表大小一样大。 当元素添加到ArrayList时，其容量会自动增长。 没有规定增长政策的细节，除了添加元素具有不变的摊销时间成本。

应用程序可以添加大量使用ensureCapacity操作元件的前增大ArrayList实例的容量。 这可能会减少增量重新分配的数量。

请注意，此实现不同步。 如果多个线程同时访问884457282749实例，并且至少有一个线程在结构上修改列表，则必须在外部进行同步。 （结构修改是添加或删除一个或多个元素的任何操作，或明确调整后台数组的大小;仅设置元素的值不是结构修改。）这通常是通过在一些自然地封装了列表。 如果没有这样的对象存在，列表应该使用Collections.synchronizedList方法“包装”。 这最好在创建时完成，以防止意外的不同步访问列表：

  List list = Collections.synchronizedList(new ArrayList(...));

The iterators returned by this class's个 iterator和listIterator方法是快速失败的 ：如果列表在任何时间从结构上修改创建迭代器之后，以任何方式除非通过迭代器自身remove种或add方法，迭代器都将抛出一个ConcurrentModificationException。 因此，面对并发修改，迭代器将快速而干净地失败，而不是在未来未确定的时间冒着任意的非确定性行为。

请注意，迭代器的故障快速行为无法保证，因为一般来说，在不同步并发修改的情况下，无法做出任何硬性保证。 失败快速迭代器尽力投入ConcurrentModificationException 。 因此，编写依赖于此异常的程序的正确性将是错误的：迭代器的故障快速行为应仅用于检测错误。

2.源码分析

2.1 主要成员变量

  • 默认长度 
    private static final int DEFAULT_CAPACITY = 10;
  • 当构造时参数为 0 指定的集合 
    private static final Object[] EMPTY_ELEMENTDATA = {};
  • 空的构造方法时使用 
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  • 集合元素的缓冲区 
    transient Object[] elementData;
  • 最终集合的长度 
    private int size;

2.2 构造方法

  • 无参构造

     public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

  • 有参构造

    • 指定初始容量
    public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

    这里对入参进行了校验，根据参数的不同进行不同的处理

    • 将集合传入
     public ArrayList(Collection<? extends E> c) {
     //将集合转换成数组
     elementData = c.toArray();
     //当传入的数据组长度大于0时
     if ((size = elementData.length) != 0) {
           //为了防止c.toArray() Object[]
         if (elementData.getClass() != Object[].class)
             elementData = Arrays.copyOf(elementData, size, Object[].class);
     } else {
         this.elementData = EMPTY_ELEMENTDATA;
     }
 }

2.3 添加方法

  • add(E e)

    public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
private Object[] grow() {
      return grow(size + 1);
}

    从上面的代码我们可以看出,当执行add()时,首先会对父类AbstractList 元素进行++ 操作, 此变量主要是为了检查是否存在共修改，最终会导致throw new ConcurrentModificationException() 当执行add(e, elementData, size)时,首先会判断elementData.length与size是否相等, grow()主要时对长度进行加一的操作，(这里我们也可以看出，为什么说，ArrayList是线程不安全的, 当初线程同时添加数据,size+1会失去原子操作,导致数据出现问题)接下来就是对指定下标的进行赋值, 并对size进行赋值;

  • add(int index, E element)

    public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

    rangeCheckForAdd只要对下标进行校验,剩下的就是和之前的差不多了,只不过这里用了System.arraycopy,比较耗性能

  • set(int index, E element)

    public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

    当我们执行set时,首先也会对下标进行校验,首先根据指定下标获取到要替换值,再根据下标进行从新赋值,再将原有的旧值进行返回

  • remove(int index)

    public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

    根据下标进行删除的时,首先还是会校验入参，然后获取要修改的值，执行fastRemove方法， 这里也有modCount , 首先我们要判断要删除的位置，如果下标位置是size, 那直接将其重置为null ,否则将进行进行copy,过程如下: javaLogo

  • remove(Object o)

       public boolean remove(Object o) {
       final Object[] es = elementData;
       final int size = this.size;
       int i = 0;
       found: {
           if (o == null) {
               for (; i < size; i++)
                   if (es[i] == null)
                       break found;
           } else {
               for (; i < size; i++)
                   if (o.equals(es[i]))
                       break found;
           }
           return false;
       }
       fastRemove(es, i);
       return true;
   }

    此方法是根据给的的元素进行删除，由于集合内可以存在null ,所以当我传递为null直接跳出循环 这里说明一下,found: {} 是一个代码块,我们可以直接跳出次代码块,通过found: {}我们可以计算出 要删除元素的下标,再次执行fastRemove(es, i)方法,当集合内存在多个元素且值完全相同,只会删除第一个元素,执行的过程和上边的根据下标删除类似

关于ArrayList还有很多方法，比如set() clear().....,如果你掌握了上边的源码，再看其他的方法也是类似的

总结

  • ArrayList 是实现不安全的,在add(),remove()方法既可以看出
  • ArrayList 查询的速度非常快,它可以根据下标快速定位,但是新增的效率就相对耗时的多(System.arraycopy)