ArrayList源码解析

妖狐艹你老母 2023-05-21 08:52 7阅读 0赞

### 文章目录 ###

*   *   *  实现的接口
         *   *   *  RandomAccess
                 *  Cloneable
                 *  java.io.Serializable
         *  成员变量
         *  构造函数
         *  clone方法
         *  get方法
         *  set方法
         *  add方法：此处会产生扩容
         *  扩容机制 grow(minCapacity);
         *  remove方法
         *  clear方法
         *  addAll方法
         *  迭代器
         *  其他方法

### 实现的接口 ###

*  本文基于Oracle JDK1.8展开讨论
 *  ArrayList位于java.util包下
 *  ArrayList类的声明：

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

*  ArrayList继承了AbstractList，看AbstractList源码，实现了List接口

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

*  而ArrayList再次实现了List接口，不觉得多余吗？实际上，这么设计是有原因的：
 *  List接口里面包含了很多方法，实现了List接口的类要重新全部的方法，而且各自的实现类具体的方法实现是不一样的，比如ArrayList和LinkedList对于add的具体实现肯定是不一样的。
 *  但是ArrayList和LinkedList对于某些方法的实现是一模一样的，比如size()方法
 *  这时候，如果每增加一个List的实现类，都要重复的写一些方法体一模一样的方法，无法复用代码
 *  这时候就利用了设计模式里的模板方法模式，把List的实现类的共有方法抽象到AbstractList里，并提供默认的实现，这样下层的实现类继承了AbstractList，直接继承共有的方法，而不需要重复的写一些代码

##### RandomAccess #####

*  此接口为一个空接口，目的是加快ArrayList随机访问的速度

public interface RandomAccess { }

##### Cloneable #####

*  此接口为一个空接口，实现了后可以重写clone方法实现深拷贝

public interface Cloneable { }

##### java.io.Serializable #####

*  此接口为一个空接口，目的是方便序列化

public interface Serializable { }

### 成员变量 ###

/** * 序列化ID */
        private static final long serialVersionUID = 8683452581122892189L;
    
        /** * 默认初始化容量 */
        private static final int DEFAULT_CAPACITY = 10;
    
        /** * 创建一个空ArrayList时，赋值使用 */
        private static final Object[] EMPTY_ELEMENTDATA = { };
    
        /** * 默认空的数组，在初始化时使用 */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    
        /** * 实际存放数据的数组 */
        transient Object[] elementData; // non-private to simplify nested class access
    
        /** * 数组内存放的实际元素个数 */
        private int size;

### 构造函数 ###

*  共三个构造函数  
    ![在这里插入图片描述][20200424171644356.png]
 *  无参构造函数

public ArrayList() { 
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    //elementData 为存放数据的数组
    transient Object[] elementData;    
    //无参初始化时，赋值为一个空的数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };

*  根据容量初始化构造函数

public ArrayList(int initialCapacity) { 
            if (initialCapacity > 0) { 
                //根据容量生成一个Object数组
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) { 
                //参数等于0 则赋值一个空数组
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

*  根据现有List初始化构造函数

public ArrayList(Collection<? extends E> c) { 
            elementData = c.toArray();
            if ((size = elementData.length) != 0) { 
                //如果返回的不是Object[]类型 则进行复制操作，Arrays.copyOf底层调用的System.arraycopy()
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else { 
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

### clone方法 ###

public Object clone() { 
            try { 
            	//先调用父类的clone克隆
                ArrayList<?> v = (ArrayList<?>) super.clone();
                //底层还是调用System.arraycopy();
                v.elementData = Arrays.copyOf(elementData, size);
                //修改次数设置为0
                v.modCount = 0;
                return v;
            } catch (CloneNotSupportedException e) { 
                // this shouldn't happen, since we are Cloneable
                throw new InternalError(e);
            }
        }

### get方法 ###

public E get(int index) { 
    		//首先检查index是否合法
            rangeCheck(index);
    
            return elementData(index);
    }
    /** *检查index是否合法 */    
    private void rangeCheck(int index) { 
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
        
    /** *返回index 位置的元素 */   
    E elementData(int index) { 
            return (E) elementData[index];
    }

### set方法 ###

public E set(int index, E element) { 
    		//检查index是否合法
            rangeCheck(index);
    		//取出旧元素
            E oldValue = elementData(index);
            //把index位置的元素替换为新元素
            elementData[index] = element;
            return oldValue;
    }

### add方法：此处会产生扩容 ###

public boolean add(E e) { 
    		//确定容量是否足够 不够则扩容
            ensureCapacityInternal(size + 1);
            elementData[size++] = e;
            return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) { 
            //如果数组为空数组 即第一次add元素 取一个最大的Capacity 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
       
    private void ensureExplicitCapacity(int minCapacity) { 
            //修改次数+1
            modCount++;
    
            //如果需要的Capacity 大于当前elementData的长度 则需要扩容
            if (minCapacity - elementData.length > 0)
            	//扩容
                grow(minCapacity);
    }

### 扩容机制 grow(minCapacity); ###

private void grow(int minCapacity) { 
            // 记录旧容量
            int oldCapacity = elementData.length;
            //新容量为 旧容量+ 旧容量的1/2
            //这里使用了移位运算 右移一位相当于除以2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //取一个最大值
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            //如果新容量超过Integer.MAX_VALUE - 8 则把newCapacity赋值为Integer.MAX_VALUE
            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();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                    Integer.MAX_VALUE :
                    MAX_ARRAY_SIZE;
        }

### remove方法 ###

public E remove(int index) { 
            //检查下标是否合法
            rangeCheck(index);
    
            //修改次数+1
            modCount++;
            //保存旧值
            E oldValue = elementData(index);
    
            //删除元素后 数组需要移动的元素数量
            int numMoved = size - index - 1;
            if (numMoved > 0)
                //移动数组
                System.arraycopy(elementData, index + 1, elementData, index,
                        numMoved);
            //置为null 方便gc
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }

### clear方法 ###

public void clear() { 
            //修改次数+1
            modCount++;
    
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }

### addAll方法 ###

public boolean addAll(int index, Collection<? extends E> c) { 
            //检查下标是否合法
            rangeCheckForAdd(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            //判断是否需要扩容
            ensureCapacityInternal(size + numNew);  // Increments modCount
    
            //计算需要移动的元素数量
            int numMoved = size - index;
            //此处的移动是把index之后的元素后移numMoved个 目的是给下面插入的元素腾出位置
            if (numMoved > 0)
                System.arraycopy(elementData, index, elementData, index + numNew,
                        numMoved);
            //把数据插入index处
            System.arraycopy(a, 0, elementData, index, numNew);
            size += numNew;
            return numNew != 0;
    }

### 迭代器 ###

public Iterator<E> iterator() { 
    		//平时使用的迭代器 实际上是ArrayList的一个内部类Itr
            return new Itr();
    }

*  迭代器解析

private class Itr implements Iterator<E> { 
            //指向下一个元素的游标
            int cursor;       // index of next element to return
            //上一个返回的元素
            int lastRet = -1; // index of last element returned; -1 if no such
            //此处注意！！！ 在获取迭代器的时候，expectedModCount只会被赋值一次
            // 所以当外部的modCount改变之后，内部类的expectedModCount并不会改变
            int expectedModCount = modCount;
    
            /** *判断是否有下一个元素 */
            public boolean hasNext() { 
                //直接判断游标是否==size
                return cursor != size;
            }
    
            @SuppressWarnings("unchecked")
            public E next() { 
                //判断修改版本是否一致
                checkForComodification();
                int i = cursor;
                //下标大于size 抛出异常
                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];
            }
    
            public void remove() { 
                if (lastRet < 0)
                    throw new IllegalStateException();
                checkForComodification();
    
                try { 
                    ArrayList.this.remove(lastRet);
                    cursor = lastRet;
                    lastRet = -1;
                    //此处会更新修改的版本
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException ex) { 
                    throw new ConcurrentModificationException();
                }
            }
    
            @Override
            @SuppressWarnings("unchecked")
            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();
                }
                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();
            }
        }

### 其他方法 ###

/** * 获取元素数量 */
        public int size() { 
            return size;
        }
    
        /** * 判断是否为空 */
        public boolean isEmpty() { 
            return size == 0;
        }
        
        /** * 判断是否包含元素o 这里就是调用indexOf 看一下元素的索引是不是>0 */
        public boolean contains(Object o) { 
            return indexOf(o) >= 0;
        }
        
        public int indexOf(Object o) { 
            if (o == null) { 
                //如果对象为空 则取数组里查找第一个对象为空的索引
                for (int i = 0; i < size; i++)
                    if (elementData[i] == null)
                        return i;
            } else { 
                //不为空 则遍历数组 使用equals判断
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }

[20200424171644356.png]: /images/20230521/8febe1beebf44e06b2565f693d440114.png