Java进阶--深入理解ArrayList实现原理

太过爱你忘了你带给我的痛 2022-05-22 02:08 176阅读 0赞

## ArrayList简介 ##

ArrayList就是动态数组，用MSDN中的说法，就是Array的复杂版本，它提供了动态的增加和减少元素，实现了Collection和List接口，可以灵活的设置数组的大小。要注意的是ArrayList并不是线程安全的，因此一般建议在单线程中使用ArrayList。

--------------------

## ArrayList的继承关系 ##

![这里写图片描述][SouthEast]

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

由上可知ArrayList继承AbstractList 并且实现了List和RandomAccess，Cloneable, Serializable接口。

--------------------

## ArrayList的方法使用和源码解析 ##

①构造方法

//1-----------------------
    public ArrayList() {
            this(10);
            //调用ArrayList(10) 默认初始化一个大小为10的object数组。
        }
    
    //2-------------------------
    public ArrayList(int initialCapacity) {    
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
             //如果用户初始化大小小于0抛异常，否则新建一个用户初始值大小的object数组。 
            this.elementData = new Object[initialCapacity];
        } 
    
    //3--------------------------
    public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            size = elementData.length;
            // 当c.toArray返回的不是object类型的数组时，进行下面转化。
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        }

由上面三种构造方法可知，默认情况下使用ArrayList会生成一个大小为10的Object类型的数组。也可以调用`ArrayList(int initialCapacity)` 来初始化Object数组的大小。并且用户可以往ArrayList中传入一个容器只要这个容器是Collection类型的。调用`ArrayList(Collection<? extends E> c)`接口的时候会将容器数组化处理并将这个数组值赋给Object数组。

实例：

public static void main(String[] args) {
            ArrayList<Integer> list_2=new ArrayList<Integer>(20);
            //list_2中添加元素
            for(int i=0;i<10;i++)
                list_2.add(i);
    
            ArrayList<Integer> list_3=new ArrayList<Integer>(list_2);
            //输出list_2中元素
            for(Integer a:list_2)
                System.out.print(a+" ");
            //输出list_3中元素
            for(Integer a:list_3)
                System.out.print(a+" ");
        }
    //输出
    /* list_2 : 0 1 2 3 4 5 6 7 8 9 ----------------------- list_3 : 0 1 2 3 4 5 6 7 8 9 */

--------------------

②indexOf(Object o)方法   
功能：查找某个元素在ArrayList中第一次出现的位置。

public int indexOf(Object o) {
      //ArrayList中的元素可以为null，如果为null返回null的下标
            if (o == null) {
                for (int i = 0; i < size; i++)
                    if (elementData[i]==null)
                        return i;
    
            } else {
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
            //如果没有找到对应的元素返回-1。
            return -1;
        }

对于indexof方法做几点说明：ArrayList中可以存放null元素，indexof是返回elementData数组中值相同的首个元素的下标，indexof中比较方法是equals而equals是比较元素的值，因此必须对null单独查找。如果未找到该元素则返回-1 。

public static void main(String[] args) {
    
            ArrayList<Integer> list=new ArrayList<Integer>();
    
            list.add(1); 
            list.add(2); 
            list.add(null); 
            list.add(2);
            list.add(3);
    
            System.out.println("null: "+list.indexOf(null));
            System.out.println("-------------------------");
            System.out.println("2: "+list.indexOf(2));
            System.out.println("-------------------------");
            System.out.println("4: "+list.indexOf(4));
        }
        //输出
        /* null: 2 ------------------------- 2: 1 ------------------------- 4: -1 */

③lastIndexOf(Object o)方法   
功能：查找某个元素在ArrayList中最后出现的位置。

public int lastIndexOf(Object o) {
            if (o == null) {
            //如果o为null从后往前找到第一个为null的下标
                for (int i = size-1; i >= 0; i--)
                    if (elementData[i]==null)
                        return i;
            } else {
            //从后往前找到第一个值为o的下标
                for (int i = size-1; i >= 0; i--)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }

上面代码做几点说明：lastIndexOf(Object o)在ArrayList中从后往前找到第一个跟要查找值相同的元素的下标，因为是按值查找所以对于 null 要单独查找。如果未找到则返回-1；

--------------------

④get(int index)方法   
功能：返回ArrayList中指定下标为index的元素。

public E get(int index) {
     //检查index的值是否大于ArrayList的大小
            rangeCheck(index);
     //返回index下标的元素 
            return elementData(index);
        }
    
       E elementData(int index) {
            return (E) elementData[index];
        }  
     //这里值检查index >= size的情况，因为index<0时会自动抛出异常，所以并未检查index<0的情况。
     private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

对上面代码做几点说明：上面代码中只检查了index>=size的情况，在index<0的情况下也会抛出异常，只是这个异常是由系统抛出的。index>=size要检查的原因是有可能数组的大小大于index，然而有效里面的元素`<index`这时不抛异常就会返回无效值。举个例子ArrayList的初始化大小为10，现在往里面放5个元素，如果index>=5时，应该要抛出异常，而不是返回 null。因为null 是可以主动放在ArrayList中的。

--------------------

⑤set(int index, E element)方法   
功能：将element放到ArrayList下标为index的位置，如果index<0或index>=size 抛异常，set(int index, E element)只能覆盖ArrayList中原来的元素，返回值为被覆盖的元素。

//1
    public E set(int index, E element) {
    //检查index是否小于size，如果不是抛异常
            rangeCheck(index);
            E oldValue = elementData(index);
            elementData[index] = element;
            //覆盖ArrayList中index上的元素。
            return oldValue;
            //返回被覆盖的元素。
        }
    //2 
     private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

*  1
 *  2
 *  3
 *  4
 *  ⑥add(E e)方法

功能：往ArrayList中添加元素。

//1-----------------------
    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // 加入元素前检查数组的容量是否足够
            elementData[size++] = e;
            return true;
        }
    //2----------------------- 
    private void ensureCapacityInternal(int minCapacity) {
            modCount++;
            // 如果添加元素后大于当前数组的长度，则进行扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        } 
    //3----------------------- 
    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            //将数组的长度增加原来数组的一半。
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
                //如果扩充一半后仍然不够，则 newCapacity = minCapacity;minCapacity实际元素的个数。
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
                //数组最大位2^32
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

add方法比较复杂，涉及到扩充数组容量的问题。其中要弄清楚size和elementData.length的区别，size指的是数组中存放元素的个数，elementData.length表示数组的长度，当new一个ArrayList系统默认产生一个长度为10的elementData数组，elementData.length=10，但是由于elementData中还未放任何元素所有size=0。如果加入元素后数组大小不够会先进行扩容，每次扩容都将数组大小增大一半比如数组大小为10一次扩容后的大小为10+5=10;ArrayList的最大长度为 2^32 .

--------------------

⑦add(int index, E element)方法   
功能：往ArrayList指定index上添加元素，添加元素后ArrayList的大小增1。index及以后的元素都会向后移一位。

//1-------------------------
    public void add(int index, E element) {
            rangeCheckForAdd(index);
    //检查index的值是否在0到size之间，可以为size。
            ensureCapacityInternal(size + 1);  // 看elementData的长度是否足够，不够扩容
     //将elementData从index开始后面的元素往后移一位。 
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
    //2-------------------------
    private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
     //3------------------------- 
     private void ensureCapacityInternal(int minCapacity) {
            modCount++;
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

add(int index, E element)往指定index中加入元素，加入元素之前先检查数组的大小，如果小了在原来基础上增大一半，将ArrayList只能怪index及以后的元素往后移一位，将element放到index位置。

--------------------

⑧remove(int index)方法   
功能：删除ArrayList指定位置的元素。

public E remove(int index) {
            rangeCheck(index);
    //如果index>=size抛出异常
            modCount++;
            E oldValue = elementData(index);
    //获取删除元素的值
            int numMoved = size - index - 1;
            //将index后面所有的元素往前移一位。
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // Let gc do its work
    //返回要删除的原数。
            return oldValue;
        }

⑨remove(Object o)方法   
功能：删除ArrayList中值为o的元素

public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }

[SouthEast]: /images/20220522/e419a1543ea742c9b51c6d0b0c3f33fb.png