Java容器源码攻坚战--第二战：ArrayList

张风捷特烈

发布于 2018-10-08 10:26:24

6510

发布于 2018-10-08 10:26:24

基于java10.1

零、前言

如果想读读源码测试功力，或读读源码修养身心，或读读源码满足自虐倾向，我建议第一个类是：ArrayList 第一、常用----所以用法比较熟悉，看完源码你也会更明白如何去用第二、相对简单----1595行代码，刨去注释的一大堆也没有太多，还是hold的住的

总得来说ArrayList源码最主要的是对System.arraycopy的理解，很多操作都是基于此

void arraycopy( Object src, //源数组
                    int  srcPos,//源数组中的起始位置
                    Object dest,//目标数组
                    int destPos,//目的地数据中的起始位置
                    int length);//要复制的数组元素的数量

一.继承与实现：

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

image

二、成员变量

    //serialVersionUID来验证版本一致性
    private static final long serialVersionUID = 8683452581122892189L;
    
    //默认列表的容量
    private static final int DEFAULT_CAPACITY = 10;
    
    //一个空的Object数组--空数组(本文中别名：空1)
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    //另一个空的Object数组--默认容量空数组(本文中别名：空2)
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

     //列表中盛放的数组
    transient Object[] elementData; //非私有来简化内部类访问
    
    //内部元素个数
    private int size;
    
    //最大数组尺寸，这里是Integer最大值-8
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

二.构造方法

1.构造方法1：无参构造

使用无参构造ArrayList,在未添加元素前,内部数组的长度是为0。在添加第一个元素时，才会扩容到10

    //无参构造：elementData=空2
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2.构造方法2：一参构造：指定初始容量

     //入参initialCapacity：初始容量
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//入参>0有效
            //创建长度为入参的Object数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//入参<0异常
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
    }

3.构造方法3：用已有Collection对象，创建ArrayList

    // 入参c：已有的容器对象
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();//传入的集合转化为数组并赋值给elementData
        //获取数组长度赋值值给size，当size不为0
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                //Arrays.copyOf见：A--01
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {//入参 = 0 时：elementData=空1
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

A--01:java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>)

将一个数组拷贝指定长度，变为另一种类型的数组

@param <U> 初始数组类型
@param <T> 返回数组类型
@param original 被拷贝数组
@param newLength 拷贝的长度
@param newType 返回的数组类型
@return 
     
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {

    T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

三.常用方法的源码分析

1.添加: 代号m1

m1 : java.util.ArrayList#add(E)

modCount:父类AbstractList中的protected变量,每次添加和移除都会+1，记录所有的修改次数作用：在Iterator使用时校验期望修改的次数与真实修改次数是否相同

*@param e 添加的元素
    public boolean add(E e) {
        modCount++;//列表在结构上修改的次数
        add(e, elementData, size);//此处调用三参的添加方法：见：m1-1
        return true;//返回是否添加成功
    }

m1-1 : java.util.ArrayList#add(E, java.lang.Object[], int)

*@param e 添加的元素
*@param elementData 数组
*@param s 索引位置
    private void add(E e, Object[] elementData, int s) {
        //要添加的索引为等于数组的长度时进行扩容操作
        if (s == elementData.length)
            elementData = grow();//grow()返回一个扩容后的数组：见：m-1-1
        //将传入的元素放到数组的最后一位
        elementData[s] = e;(注：由于数组标号从零开始，新数组长度s+1,最后一个元素下标号为s)
        size = s + 1;//将成员变量size+1
    }

m-1-1 : java.util.ArrayList#grow()

扩容操作

    private Object[] grow() {
        return grow(size + 1);//调用了一参的grow()方法
    }
    
    *@param minCapacity 最小容量
    private Object[] grow(int minCapacity) {
        //newCapacity(minCapacity)扩容核心操作：见m-1-1-1
        return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
    }

m-1-1-1：java.util.ArrayList#newCapacity

扩容核心操作: 最小容量size+1,旧容量:数组长，新容量：1.5倍旧容量拿教室举例：minCapacity就是班级学生数量+1，oldCapacity就是扩建前的座位数，newCapacity就是扩建后的座位数

    *@param minCapacity 最小容量
    private int newCapacity(int minCapacity) {
        //oldCapacity：旧容量  newCapacity：1.5倍旧容量
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//即+50%
       
        if (newCapacity - minCapacity <= 0) { //新容量小于等于最小容量
            //如果elementData=空2，扩容到DEFAULT_CAPACITY(即10)，这就是分空1和空2的目的
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
         //新容量大于最小容量时， newCapacity没达到最大尺寸返回newCapacity，否则hugeCapacity(minCapacity)
        return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity);
    }
    
    //minCapacity大于数组最大尺寸，返回整型的最大值，否则返回数组最大尺寸
     private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE;
    }

2.定位添加：代号：m2

m2 : java.util.ArrayList#add(int, E)

     * @param 插入的索引位置
     * @param 插入的元素
    public void add(int index, E element) {
        rangeCheckForAdd(index);//m2-1:检查索引合法性
        modCount++;
        final int s;//局部变量，记录方法执行前size值
        Object[] elementData//局部变量，记录方法执行前elementData数组
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();//扩容1.5倍
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);//m2-2：核心方法
        elementData[index] = element;
        size = s + 1;
    }

m2-1 ：java.util.ArrayList#rangeCheckForAdd

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)//索引在(0,size)之外报异常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

m2-2 ：java.util.ArrayList#rangeCheckForAdd

    //将[源数组src]从[指定位置srcPos]选取连续[长度length]个元素复制到[目标数组dest]的[指定位置destPos]。
    public static native 
    void arraycopy( Object src, //源数组
                    int  srcPos,//源数组中的起始位置
                    Object dest,//目标数组
                    int destPos,//目的地数据中的起始位置
                    int length);//要复制的数组元素的数量

arraycopy.png

3.添加所有：代号m3

     * @param 已有的容器对象
     * @return 列表是否已被修改
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();//将容器对象转化为数组a
        modCount++;//修改次数+1
        int numNew = a.length;//临时变量numNew记录a的长度
        if (numNew == 0)//a的长度为0
            return false;//说明列表未被修改
        Object[] elementData;//临时变量elementData:数组
        final int s;//临时变量s：数组长度
        //加入的元素大于数组容积和当前元素个数之差，也就是放入这些元素后会占满
        if (numNew > (elementData = this.elementData).length - (s = size))
            //扩容
            elementData = grow(s + numNew);
        //将a数组，从0开始，拷贝numNew个元素到elementData数组的s索引处
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;//维护size
        return true;////说明列表被修改
    }

4.定点添加所有：代号m4

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);//见：m2-1
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);//至此同上m3
        int numMoved = s - index;//添加的位置之后的元素个数
        if (numMoved > 0)//说明index在元素个数之内
        //将elementData数组，从index开始，拷贝numMoved个元素到elementData数组的index + numNew索引处
        //相当于挪一下索引位后的元素
            System.arraycopy(elementData, index,
                             elementData, index + numNew,
                             numMoved);
        //将a数组，从0开始，拷贝numNew个元素到elementData数组的index索引处
        System.arraycopy(a, 0, elementData, index, numNew);
        size = s + numNew;
        return true;
    }

5.根据索引删除：代号m5

m5 : java.util.ArrayList#remove(int)

  public E remove(int index) {
        Objects.checkIndex(index, size);//检查索引合法性
        final Object[] es = elementData;//将集合赋予临时变量es

        E oldValue = (E) es[index];//临时变量记录删除值
        fastRemove(es, index);//m5-1:删除的核心方法
        return oldValue;//返回删除的值
    }

m5-1 : java.util.ArrayList#fastRemove

    /**
     * 私有的移除方法：跳过边界检查并且不反会移除的值
     */
    private void fastRemove(Object[] es, int i) {
        modCount++;//修改次数+1
        final int newSize;//新尺寸：元素总量-1
        if ((newSize = size - 1) > i)//索引在元素总量-1之内
            //将es数组，从i + 1开始，拷贝size - (i+1)个元素到es数组的i索引处
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }

6.移除指定元素

    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);//m5-1:删除的核心方法
        return true;
    }

7.移除所有指定元素：代号m7

    public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false, 0, size);//batchRemove见:m7-1
    }

m7-1:java.util.ArrayList#batchRemove

boolean batchRemove(Collection<?> c, boolean complement,
                        final int from, final int end) {
        Objects.requireNonNull(c);
        final Object[] es = elementData;//es变量记录当前数组
        int r;
        // Optimize for initial run of survivors
        for (r = from;; r++) {
            if (r == end)//没有找到该元素
                return false;
            if (c.contains(es[r]) != complement)//包含但还没有全部扫描
                break;
        }
        int w = r++;
        try {
            for (Object e; r < end; r++)
                if (c.contains(e = es[r]) == complement)
                    es[w++] = e;
        } catch (Throwable ex) {
            System.arraycopy(es, r, es, w, end - r);
            w += end - r;
            throw ex;
        } finally {
            modCount += end - w;
            //shiftTailOverGap:见m7-1-1
            shiftTailOverGap(es, w, end);
        }
        return true;
    }

7-1-1.范围移除

    private void shiftTailOverGap(Object[] es, int lo, int hi) {
        //将es数组，从hi开始，拷贝size - hi个元素到es数组的lo索引处
        System.arraycopy(es, hi, es, lo, size - hi);
        for (int to = size, i = (size -= hi - lo); i < to; i++)
            es[i] = null;//将移除的元素置空
    }

8.获取元素：代号m8

m8 : java.util.ArrayList#get

    /**
     * 返回列表中指定位置的元素
     */
    public E get(int index) {
        //m8-1:检查索引是否合法(1.9开始有)
        Objects.checkIndex(index, size);
        return elementData(index);//m8-2
    }

m8-1 : java.util.Objects#checkIndex

    public static
    int checkIndex(int index, int length) {
        return Preconditions.checkIndex(index, length, null);//m8-1-1
    }

m8-1-1 : jdk.internal.util.Preconditions#checkIndex

    //判断索引值是否在(0,length)
    public static <X extends RuntimeException>
    int checkIndex(int index, int length,
                   BiFunction<String, List<Integer>, X> oobef) {
        if (index < 0 || index >= length)
            throw outOfBoundsCheckIndex(oobef, index, length);//这就是经常遇到的角标越界
        return index;
    }

m8-2 : java.util.ArrayList#elementData

    E elementData(int index) {
        return (E) elementData[index];//返回数组在索引上的值
    }

9.修改元素

    public E set(int index, E element) {
        //检查索引是否越界
        Objects.checkIndex(index, size);
        //记录旧值
        E oldValue = elementData(index);
        //设置新值
        elementData[index] = element;
        //返回旧值
        return oldValue;
    }

四、其他方法

1.获取集合大小：java.util.ArrayList#size

    public int size() {
        return size;
    }

2.是否非空：java.util.ArrayList#isEmpty

    public boolean isEmpty() {
        return size == 0;
    }

3.清空：java.util.ArrayList#clear

    public void clear() {
        modCount++;//操作数+1
        final Object[] es = elementData;//es存储当前数组
        for (int to = size, i = size = 0; i < to; i++)
            es[i] = null;//全部置空
    }

4.元素出现的索引位

indexOf(el) 元素第一次出现的索引位置

    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;//从头开始找，直到相等时，返回i
        }
        return -1;//找不到返回-1
    }

lastIndexOf(el) 元素最后一次出现的索引位置

    public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;//从后往前找，直到相等时，返回i
        }
        return -1;//找不到返回-1
    }

5.是否包含某元素

    public boolean contains(Object o) {
        return indexOf(o) >= 0;//找到有索引就ok
    }

4.转换为数组：java.util.ArrayList#toArray(T[])

   public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

五、迭代器：

1.Iterator上一篇讲的挺详细：见--Java容器源码攻坚战--第一战：Iterator

2.这里主要讲ArrayList特有的私人迭代器：ListIterator

可以认为是Iterator的升级版，继承自Iterator，而且多了一些操作

ListIterator

public interface ListIterator<E> extends Iterator<E> {
    
    boolean hasNext();//是否有下一元素
    E next();//下一元素
    boolean hasPrevious();//是否有前一元素
    E previous();//前一元素
    int nextIndex();//下一个元素索引
    int previousIndex();//前一个元素索引

    void remove();//移除
    void set(E e);//设置
    void add(E e);//添加
}

public ListIterator<E> listIterator() {
      return new ListItr(0);
  }
  
public ListIterator<E> listIterator(int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}

ListIterator实现类

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {//构造函数传入索引值
        super();
        cursor = index;//游标处于索引位
    }
    public boolean hasPrevious() {
        return cursor != 0;//游标不为0说明有前元素
    }
    public int nextIndex() {
        return cursor;
    }
    public int previousIndex() {
        return cursor - 1;
    }
    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        //索引为游标-1
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        //elementData储存当前数组
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;//游标-1
        return (E) elementData[lastRet = i];//返回元素
    }
    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        try {
            //设置最后返回的那个元素索引
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    public void add(E e) {
        checkForComodification();
        try {
            int i = cursor;
            //在最后返回的那个元素索引处添加元素
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

就酱紫，ArrayList还有个SubList没有接触过，暂时就不看了

后记：捷文规范

1.本文成长记录及勘误表

项目源码	日期	备注
V0.1--无	2018-10-2	Java容器源码攻坚战--第二战：ArrayList
V0.2--无	-	-

2.更多关于我

笔名	QQ	微信	爱好
张风捷特烈	1981462002	zdl1994328	语言
我的github	我的简书	我的CSDN	个人网站

3.声明

1----本文由张风捷特烈原创,转载请注明 2----欢迎广大编程爱好者共同交流 3---个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 4----看到这里，我在此感谢你的喜欢与支持

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.10.03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度

Java容器源码攻坚战--第二战：ArrayList

Java容器源码攻坚战--第二战：ArrayList

零、前言

总得来说ArrayList源码最主要的是对System.arraycopy的理解，很多操作都是基于此

一.继承与实现：

二、成员变量

二.构造方法

1.构造方法1：无参构造

2.构造方法2：一参构造：指定初始容量

3.构造方法3：用已有Collection对象，创建ArrayList

A--01:java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>)

三.常用方法的源码分析

1.添加: 代号m1

m1 : java.util.ArrayList#add(E)

m1-1 : java.util.ArrayList#add(E, java.lang.Object[], int)

m-1-1 : java.util.ArrayList#grow()

m-1-1-1：java.util.ArrayList#newCapacity

2.定位添加：代号：m2

m2 : java.util.ArrayList#add(int, E)

m2-1 ：java.util.ArrayList#rangeCheckForAdd

m2-2 ：java.util.ArrayList#rangeCheckForAdd

3.添加所有：代号m3

4.定点添加所有：代号m4

5.根据索引删除：代号m5

m5 : java.util.ArrayList#remove(int)

m5-1 : java.util.ArrayList#fastRemove

6.移除指定元素

7.移除所有指定元素：代号m7

m7-1:java.util.ArrayList#batchRemove

7-1-1.范围移除

8.获取元素：代号m8

m8 : java.util.ArrayList#get

m8-1 : java.util.Objects#checkIndex

m8-1-1 : jdk.internal.util.Preconditions#checkIndex

m8-2 : java.util.ArrayList#elementData

9.修改元素

四、其他方法

1.获取集合大小：java.util.ArrayList#size

2.是否非空：java.util.ArrayList#isEmpty

3.清空：java.util.ArrayList#clear

4.元素出现的索引位

indexOf(el) 元素第一次出现的索引位置

lastIndexOf(el) 元素最后一次出现的索引位置

5.是否包含某元素

4.转换为数组：java.util.ArrayList#toArray(T[])

五、迭代器：

1.Iterator上一篇讲的挺详细：见--Java容器源码攻坚战--第一战：Iterator

2.这里主要讲ArrayList特有的私人迭代器：ListIterator

ListIterator

​

ListIterator实现类

后记：捷文规范

1.本文成长记录及勘误表

2.更多关于我

3.声明

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐