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

基于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----看到这里,我在此感谢你的喜欢与支持

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JavaEdge

二叉树的常用算法递归2 非递归3 小结4 实战coding5序列化和反序列化判断一棵二叉树是否是平衡二叉树判断一棵树是否是搜索二叉树、判断一棵树是否是完全二叉树

58790
来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

10320
来自专栏Android研究院

数据结构-线性表(顺序表与链表的基本知识 以及ArrayList 源码分析)

比如:美女和野兽,抽象的事物表示美女:头发长 前凸后翘。。。 可以表示为一个数据单元,野兽也是一个数据单元。

28310
来自专栏一枝花算不算浪漫

Java中常见数据结构List之ArrayList

394120
来自专栏格子的个人博客

Java源码阅读之ArrayList - JDK1.8

当你对某件事情很感兴趣的时候,时间的流逝在感知中都模糊了(是不是很文艺,绕口得都快听不懂了),通俗来说,就是时间过得很快。

20650
来自专栏desperate633

LintCode 数组剔除元素后的乘积题目代码

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。

10810
来自专栏彭湖湾的编程世界

【算法】二叉查找树(BST)实现字典API

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

54590
来自专栏开发之途

Java集合框架源码解析之ArrayList

19440
来自专栏小灰灰

JDK容器学习之ArrayList:底层存储和动态扩容

ArrayList 底层存储和动态扩容逻辑 ArrayList 作为最常用的容器之一,通常用来存储一系列的数据对象,O(1)级别的数据读写 I. 底层数据模型...

20270
来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

29640

扫码关注云+社区

领取腾讯云代金券