数据结构与算法之线性表(ArrayList原理&源码分析)

ArrayList概述

ArrayList是List接口的大小可变数组的实现,允许存储null元素,容量可自动增加,非线程安全。多线程并发操作可以使用CopyOnWriteArrayList或者Collections.synchronizedList方法包装。

类结构图

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList继承了AbstractList抽象类，实现了RandomAccess、Serializable、Cloneable接口，支持快速随机访问、支持克隆和序列化操作。

属性

/**
     *默认初始化容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
    
      ArrayList arrayList=new ArrayList(0);
     * 创建ArrayList指定容量为0时,返回的空数组
     
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     ArrayList arrayList=new ArrayList();
     *当调用无参构造方法，返回的是该数组。刚创建一个ArrayList 时,数据量为0。
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     存储ArrayList元素数组,ArrayList的容量就是该数组的长度,当elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA时,第一个元素添加到ArrayList,
     elementData数组扩容到DEFAULT_CAPACITY大小
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList元素个数，不一定等于elementData.length
     *
     * @serial
     */
    private int size;

    /**
     * 分派给arrays的最大容量
     某些vm中会在数组中保留一些头字节，这样会导致数组容量大于vm limit,因此减去8
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造器

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
           //初始容量大于0，初始化elementData大小为容量大小
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //初始化容量为0，EMPTY_ELEMENTDATA赋给elementData
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        //初始化容量小于0抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    
    public ArrayList() {
    //初始化容量为10的空列表,这里没有指定大小，当第一次add时,elementData的默认长度为10
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    
     /**
     * 创建一个包含指定collection的元素列表，列表元素的排列顺序是按照collection迭代器返回的元素顺序排列
     */
    public ArrayList(Collection<? extends E> c) {
        //将collection转换成数组,然后赋给elementData
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            /**
             此处需要判断的原因是，有些方式创建的collection,即使转换城object类型数组,还是原本类型
             比如：Integer[] array = {1, 2};
             List list = Arrays.asList(array);
             list元素还是Integer类型
        
            **/
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果collection长度为0，将空数组EMPTY_ELEMENTDATA赋给elementData
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    

主要方法

方法名	功能
E get(int index)	获取指定位置元素
boolean add(E e)	末尾添加元素
void add(int index, E element)	指定位置添加元素
E remove(int index)	删除指定位置元素
boolean remove(Object o)	删除值为o的第一个元素
E set(int index, E element)	设置指定位置元素值
void removeRange(int fromIndex, int toIndex)	删除两个索引之间的所有元素，包含fromIndex不包含toIndex
int indexOf(Object o)	返回列表中制定元素第一次出现的索引，如果列表中不包含此元素，返回-1
int lastIndexOf(Object o)	返回列表中制定元素最后一次次出现的索引，如果列表中不包含此元素，返回-1
boolean contains(Object o)	判断列表中是否包含元素o
boolean removeAll(Collection<?> c)	删除列表中与c交集部分
boolean retainAll(Collection<?> c)	删除列表中与c差集部分
void clear()	清空列表
Iterator iterator	返回元素的迭代器用户遍历列表数据

get(int index)

public E get(int index) {
       //检测索引位置是否合法
        rangeCheck(index);
    //返回数组指定位置值
        return elementData(index);
    }

boolean add(E e) 列表末尾添加元素

public boolean add(E e){
    //确保内部容量,如果容量不够容量+1,调用add方法一次,modCount++这个跟fail-fast机制有关参数,后面细讲
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
//数组容量检测,不够进行扩容
 private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

 private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           // 如果数组为空,则minCapacity取默认容量DEFAULT_CAPACITY=10，这个// 就是使用无参构造器创建时默认容量为10的原理
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        //如果需要的最小容量大于当前数组的容量，需要扩容
        if (minCapacity - elementData.length > 0)
           //扩容
            grow(minCapacity);
    }
  
    private void grow(int minCapacity) {
        // overflow-conscious code
        //当前数组容量
        int oldCapacity = elementData.length;
        //扩容容量=当前容量+当前容量*1/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //扩容后容量还小于当前需要容量
        if (newCapacity - minCapacity < 0)
           //直接将扩容后的容量设置成需要的最小容量
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //如果扩容后的容量大于最大容量值，则进行大容量分配
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
            //如果需要分配的容量大于最大容量值,则分配Integer.MAX_VALUE，否///则分配容量值为MAX_ARRAY_SIZE
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }    
    

void add(int index, E element) 列表指定位置添加元素

 public void add(int index, E element) {
       //检测添加位置是否合法
        rangeCheckForAdd(index);
      //确保容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
     //数组复制,空出i位置,i之后元素往后移动一个位置
     System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //设置指定位置数组值
        elementData[index] = element;
        //列表长度+1
        size++;
    } 

remove(int index)

 public E remove(int index) {
        //检测位置是否合法
        rangeCheck(index);
        modCount++;
        //index位置 值
        E oldValue = elementData(index);
        //需要移动元素数量，index位置之后的元素需要往前移动一个位置
        int numMoved = size - index - 1;
        if (numMoved > 0)
        //arraycopy(原数组，源数组中的起始位置，目标数组，目标数据中的起始///位置，要复制的数组元素的数量)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //elementData最后一个元素设置为null
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

remove(Object o)

   public boolean remove(Object o) {
        //删除元素为null
        if (o == null) {
            for (int index = 0; index < size; index++)
                //数组中第一个为null元素删除,后面元素往前移动一个位置
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
           //删除元素不为null,遍历元素，元素值等于o的第一个元素删除,后面元素往前移动一个位置
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    //快速删除指定位置元素
 private void fastRemove(int index) {
        //修改次数+1
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //最后一个元素设置为null
        elementData[--size] = null; // clear to let GC do its work
    }

set(int index, E element)

   public E set(int index, E element) {
        //检测索引
        rangeCheck(index);
       //获取index位置老数据
        E oldValue = elementData(index);
        //设置index位置新值
        elementData[index] = element;
        //返回老值
        return oldValue;
    }

removeRange(int fromIndex, int toIndex)

    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        //需要移动的元素个数
        int numMoved = size - toIndex;
        //移动数据
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        //新数组长度
        int newSize = size - (toIndex-fromIndex);
        //删除元素设置为null，好让垃圾回收机制回收内存
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

indexOf(Object o)

    public int indexOf(Object o) {
    //元素为null,遍历数组中等于null元素，然后返回索引
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
         //元素不为null,判断查询元素o与数组中元素是否相等，相等直接返回索引
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
           //列表中不包含o,直接返回-1
        return -1;
    }

lastIndexOf(Object o)

    public int lastIndexOf(Object o) {
        //元素为null,从size-1位置往前遍历数组中等于null元素，然后返回索引
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
        //元素不为null,从size-1位置往前判断查询元素o与数组中元素是否相等，相等直接返回索引
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        //列表中不包含o,直接返回-1
        return -1;
    }

contains(Object o)

   public boolean contains(Object o) {
        //indexOf包含元素返回索引位置 不包含元素返回-1
        return indexOf(o) >= 0;
    }

removeAll(Collection<?> c)

   public boolean removeAll(Collection<?> c) {
        //检测c集合是否为null,如果为null抛出空指针异常
        Objects.requireNonNull(c);
        //批量删除元素
        return batchRemove(c, false);
    }
    
     private boolean batchRemove(Collection<?> c, boolean complement) {
        //原始数据
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                //遍历elementData元素
                //此处分2种情况 remvoveAll complement=false，将集合c中没有的元素赋值到elementData
                //retainAll complement=true,将集合c中有的元素赋值到elementData
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
        //finally语句主要是防止c.contains有异常抛出时能保证elementData数据的完整性
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            //elementData没有遍历完
            if (r != size) {
             //没有遍历到的元素复制到elementData
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
               //size - r的大小等于没有遍历到的元素
                w += size - r;
            }
            //元素有删除
            if (w != size) {
                // clear to let GC do its work
                //删除的元素设置为null
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

retainAll(Collection<?> c)

   public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        //complement=true,batchRemove
        //if (c.contains(elementData[r]) == complement)
        //            elementData[w++] = elementData[r];
        //            将集合c中有的元素赋值到elementData
        return batchRemove(c, true);
    }

clear()

public void clear() {
        //修改次数+1
        modCount++;

        // clear to let GC do its work
        //设置数组中所有元素为null
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        //列表大小设置为0
        size = 0;
    }

iterator()

  public Iterator<E> iterator() {
        //返回内部类Itr
        return new Itr();
    }
    
     private class Itr implements Iterator<E> {
        //下一个迭代元素的数组下表
        int cursor;       // index of next element to return
        //记录最后一个返回元素的数组下表,如果没有返回-1
        int lastRet = -1; // index of last element returned; -1 if no such
        //expectedModCount则是modCount的值，主要用来检测在迭代器使用期间有没有修改过ArrayList，修改了之//后如果调用迭代器内的next方法，则会抛出ConcurrentModificationException异常。这个就是fail-fast机制。
        int expectedModCount = modCount;

        Itr() {}
        //是否有下一个元素
        public boolean hasNext() {
            return cursor != size;
        }
        //返回下一个元素
        @SuppressWarnings("unchecked")
        public E next() {
             //检测List是否倍修改，如果被修改抛出异常
            checkForComodification();
            int i = cursor;
            //如果下一个元素的索引大于等于数组长度抛出异常,因为数组最大下标是size-1
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            //下标越界抛出异常
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
       ///移除最后一个调用next返回的元素
        public void remove() {
            //如果最后一次调用next元素不存在抛出异常
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                //调用ArrayList的remove方法
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                //此处保证expectedModCount=modCount，因此调用Iterator的remove方法不会抛出异常
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

      
        @Override
        //JDK1.8加入的遍历集合方法，Consumer函数式接口,调用此方法传入一个自定义的consumer接口，每个元素就可以执行函数中定义的操作
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            //调用consumer.accept遍历数组数据
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

什么是快速失败(fail-fast)与安全失败(fail-safe)

在JAVA Collection集合框架的类中，有线程安全和不安全的2类。对线程不安全的类并发情况下修改可能会出现fail-fast，而线程安全类可能出现fail-safe情况。

fail-fast快速失败

当遍历一个集合对象时，如果集合对象结构被修改(添加,删除,修改)，会抛出ConcurrentModificationException。

   ArrayList arrayList = new ArrayList(Arrays.asList(1, 2, 3, 4));
        Iterator iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            Object i = iterator.next();
            arrayList.remove(i);
            // iterator.remove();这样调用不会抛出异常
        }
        
    Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
    

单线程环境下如果不想抛出异常,可以调研Iterator的remove()方法。

ArrayList是怎么样实现fail-fast机制了？

在ArrayList集成的抽象类AbstractList中有个属性

//集合被修改次数,调用add remove等方法时，modCount++
  protected transient int modCount = 0;

当调用ArrayList.iterator()返回对象，有个一属性expectedModCount，这个属性会被赋值为modCount,相当于这个点modCount的副本，expectedModCount的值在iterator内部不会变化，但是modCount的值会在外部有修改情况下变化。
当调研iterator.remove为什么不会抛出异常,因为这个方法内部没有使用modCout++操作,而是 expectedModCount = modCount。

fail-safe安全失败

fail-fast机制发生时程序会抛出异常，fail-safe机制发生程序不会抛出异常，但是它返回的数据时某个时间点的快照，并发容器的iterate方法返回的数据内部保存的是集合对象的一个快照，没有是有modCount值做校验，所以fail-fast机制返回的数据不是集合本身的最终正确数据,CopyOnWriteArrayList就是fail-fast机制。

 public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }
  static final class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array */
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            //快照
            snapshot = elements;
        }

本文地址：https://blog.csdn.net/RenPeng_Ben/article/details/107624058

如对本文有疑问， 点击进行留言回复！！