Java集合源码—ArrayList

╰半橙微兮° 2021-11-09 22:58 479阅读 0赞

## ArrayList源码分析 ##

### 1.ArrayList概述 ###

ArrayList是Java中常用的集合之一, 其底层实现是数组.因为数组在内存空间中是连续的, 所以他的特点就是查找数据快, 但因为插入和删除元素都需要移动其他元素的位置, 所以插入和删除会慢一些. 另外, ArrayList是可以动态增长和缩减的索引序列.

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

我们通过类描述可以看到ArrayList的继承关系

*  继承AbstractList抽象类 : 体现出面向对象的继承的思想, 通过继承AbstractList类, 拿到其一些通用的方法, 然后再实现的抽象方法.
 *  实现List接口 : 应该是一个错误的地方, 因为没什么影响, 就一直留到了现在
 *  实现RandomAccess接口 : 这是一个标记性接口, 作用是用来快速随机存取, 有关效率的问题. 另外如果实现了该接口, 使用普通的for循环来遍历性能会更高
 *  实现Cloneable接口 : 实现了该接口, 就可以使用Object.Clone()方法了
 *  实现Serializable接口 : 实现该序列化接口, 表明该类可以被序列化.

### 2.类中的属性 ###

//版本号
    	private static final long serialVersionUID = 8683452581122892189L;
    	//默认容量
        private static final int DEFAULT_CAPACITY = 10;
    	//空数组对象
        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;
    	//数组最大大小
    	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

### 3.构造方法 ###

ArrayList共有三个构造方法

#### 1>无参构造方法 ####

//构造一个初始容量为10的空list
    	public ArrayList() {
        
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

可是这里并没有赋值啊, 等会会提到

#### 2>有参构造方法 (int) ####

//自定义初始数组容量
    	public ArrayList(int initialCapacity) {
        
            if (initialCapacity > 0) {
        
                //参数值大于零, new一个大小为参数值的新数组对象并赋值给elementData
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
        
                //若参数值等于0, 直接将空list赋给 elementData
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
        
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

#### 3>有参构造方法(Collection) ####

//参数是一个集合对象, 将该集合对象转化为ArrayList类型
    	public ArrayList(Collection<? extends E> c) {
        
            //先转化
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
        
                // 每个集合的toArray()实现方式不同, 可能会返回非Object[]的对象
                //这时需要将其改造成Object[]的对象
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
        
                // 数组长度为0,给elementData赋空数组
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

### 4.核心方法 ###

#### 1>add()方法 ####

//添加一个特定元素到list的末尾
    	public boolean add(E e) {
        
            //确定内部容量是否够了, size是数组中数据个数, 所以判断添加一个元素, 即size+1个元素能否放得下
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //将元素放到当前位置, 并让size自增
            elementData[size++] = e;
            return true;
        }

**ensureCapacityInternal()方法:**

private void ensureCapacityInternal(int minCapacity) {
        
            //先调用calculateCapacity(elementData, minCapacity)方法作为
            //ensureExplicitCapacity()方法的参数
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }

//计算容量
    	private static int calculateCapacity(Object[] elementData, int minCapacity) {
        
            //如果当前的数组对象还是默认的空数组对象
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
                //选择默认容量(10)和传入参数中大的那个数
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }

**ensureExplicitCapacity()方法:**

//现在这个方法传入的参数就是真正的需要的最小容量大小
    	private void ensureExplicitCapacity(int minCapacity) {
        
            modCount++;
    
            // 需要的容量大于目前数组的容量了, 进行扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

**grow()方法:** 进行数组扩容

//ArrayList最为核心的方法, 对数组进行扩容
    	private void grow(int minCapacity) {
        
            // overflow-conscious code
            int oldCapacity = elementData.length;
            //扩容后大小为原来容量的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //这里就是对于length=0时,将10赋值给newCapacity
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            //如果数组容量大于最大容量了,就调用该方法, 其实就是将最大值赋给它
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // 新容量已经确定好了, 就copy数组, 改变容量大小
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

**第二个add()方法:** 向指定位置插入元素

//向指定的位置插入一个元素
    	public void add(int index, E element) {
        
            //检查插入位置是否合法, 插入的位置不能<0,也不能>size
            rangeCheckForAdd(index);
    		//同样检查是否需要扩容
            ensureCapacityInternal(size + 1); 
            //将index位置及其之后的元素都向后移动一位
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            //给index位置放上元素
            elementData[index] = element;
            size++;//size加一
        }

#### 2>删除方法 ####

**remove(int ) :** 移除指定位置上的元素

//
    	public E remove(int index) {
        
            //检查index是否合法
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    		//计算需要移动的元素的个数
            int numMoved = size - index - 1;
            if (numMoved > 0)
                //将index后的数据向前移动一位
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            //将之前最后一个位置置空, 让GC回收它
            elementData[--size] = null; // clear to let GC do its work
    		//返回被删除的元素
            return oldValue;
        }

**remove(Object) :** 删除指定的一个元素

public boolean remove(Object o) {
        
            //从这里我们可以看出,ArrayList是可以存放null的
            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++)
                    //找到o所在的位置
                    if (o.equals(elementData[index])) {
        
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }

**clear() :** 将数组中每一个位置都置为null

public void clear() {
        
            modCount++;
    		
           	//让GC去收集
            // clear to let GC do its work
            for (int i = 0; i < size; i++)
                elementData[i] = null;
    
            size = 0;
        }

\*\*removeAll(Collection) : \*\* 删除数组中包含在参数集合中的元素

public boolean removeAll(Collection<?> c) {
        
            //检测c不为空
            Objects.requireNonNull(c);
            
            return batchRemove(c, false);
        }

**batchRemove(Collection, boolean) :**

//该方法共有两个参数, 第一个参数是集合, 第二个参数是一个布尔变量, 若为false, 则表示该方法用于removeAll(); 若为true, 则表示该方法用于retainAll()
    	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++)
                    if (c.contains(elementData[r]) == complement)
                        elementData[w++] = elementData[r];
            } finally {
        
                
                //如果contains()报异常,将剩下的元素都赋给数组 
                if (r != size) {
        
                    System.arraycopy(elementData, r,
                                     elementData, w,
                                     size - r);
                    w += size - r;
                }
                //用于removeAll()
                //w没有达到size, 证明有元素被删除了, 将w之后的位置置null进行GC
                if (w != size) {
        
                    // clear to let GC do its work
                    for (int i = w; i < size; i++)
                        elementData[i] = null;
                    modCount += size - w;
                    //更新size大小
                    size = w;
                    modified = true;
                }
            }
            return modified;
        }

#### 3>其他方法: ####

**set(int, E):**

public E set(int index, E element) {
        
            //检测index是否合法
            rangeCheck(index);
    		
            E oldValue = elementData(index);
            //放入该位置, 并返回旧值
            elementData[index] = element;
            return oldValue;
        }

**indexOf(Object) :** 确定指定元素在数组中 的下标值

public int indexOf(Object o) {
        
            //若为空
            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;
        }
    	//与此方法对应的是lastIndexOf(), 从数组尾部开始查找

\*\*get(int) : \*\*获取指定位置上的元素

public E get(int index) {
        
            //先进行index范围检查
            rangeCheck(index);
    		//返回数组该位置上的元素
            return elementData(index);
        }
    
    	//@suppresswarnings就是告诉编译器忽略警告。不用在编译完成后出现警告
        @SuppressWarnings("unchecked")
        E elementData(int index) {
        
            //向下转型
            return (E) elementData[index];
        }

### 5.总结 ###

*  ArrayList中的数组 其实就是一个Object数组, 每个方法都是围绕这个数组进行的
 *  grow()方法是整个类的核心方法, 用于数组扩容
 *  removeAll(Collection)删除数组中包含在指定集合中的元素. clear()删除数组中的所有元素
 *  ArrayList实现了RandomAccess, 所以遍历的时候推荐使用for循环