ArrayList源码

ArrayList

1、ArrayList的底层 – 数组

数组结构的优缺点：

数组查询块，根据地址和索引直接获取元素

数组增删改慢，每次都需要创建新数组。且移动元素位置

2、ArrayList继承关系

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

2.1、Serializable标记性接口

1、介绍

类的序列化有实现java.io.Serializable接口的类启用。不实现此接口的类将不会使任何状态序列化或反序列化。可序列化类的所有子类型都是可序列化的。序列化接口没有方法或字段，仅用于标识可串行化的语义。

序列化：将对象的数据写入到文件。

反序列化：将文件中对象的数据读取出来。

2、java.io.Serializable源码：

public interface Serializable {
}

3、 Serializable的使用：

创建一个Student类：

public class Student implements java.io.Serializable{
    private String name;
    private Integer age;

    public Student() {
    }

    public Student(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

一个测试：

public static void main(String[] args) throws IOException, ClassNotFoundException {
    //调用方法
    writeObject();

    readObject();
}

//定义一个方法，将对象写入文件中
private static void writeObject() throws IOException {
    //创建对象操作流---> 序列化，将对象写入文件
    ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream("obj.txt"));
    //创建需要写入的对象
    Student student1 = new Student("j", 32);
    //调用对象操作流写对象的方法。
    objectOutputStream.writeObject(student1);
    //关闭流
    objectOutputStream.close();
}
//定义一个方法，将文件中的数据读取出来
private static void readObject()throws IOException,ClassNotFoundException{
    //创建对象操作流---->反序列化，将数据从文件中读取出来
    ObjectInput objectInput = new ObjectInputStream(new FileInputStream("obj.txt"));
    //调用方法读取对象
    Student o = (Student)objectInput.readObject();
    //关闭流
    objectInput.close();
    //打印对象
    System.out.println(o);
}

结果：

在控制台中打印出对象

我们可以测试，如果Student对象不继承Serializable接口，结果会怎样。

明显看出：NotSerializableException，没有序列化接口

2.2、Cloneable标记性接口

1、介绍

一个类实现Cloneable接口来指示Object.clone()方法。该方法对于该类的实例进行字段的复制时合法的。

在不实现Cloneable接口的实例上调用对象的克隆方法会导致异常CloneNotSupportedException。

克隆就是依据已经有的数据，创造一份新的完全一样的数据拷贝

2、Cloneable源码：

public interface Cloneable {
}

3、克隆的前提条件

• 被克隆对象所在的类必须实现Cloneable接口
• 必须重写clone方法

4、clone的基本使用

public static void main(String[] args){

    ArrayList<String> strings1 = new ArrayList<>();

    strings1.add("1");
    strings1.add("2");
    strings1.add("3");
    strings1.add("4");
    strings1.add("5");

    Object strings2 = strings1.clone();

    System.out.println(strings1 == strings2);   //false
    System.out.println(strings1);   //[1, 2, 3, 4, 5]
    System.out.println(strings2);   //[1, 2, 3, 4, 5]
    
}

5、clone底层实现

在ArrayList中克隆函数的重写：

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

ArrayList继承AbstractList，但super.clone()；并不是AbstractList类中的，他是Object中的克隆方法，而这个方法的底层时通过C来写的

protected native Object clone() throws CloneNotSupportedException;

下面这句是克隆的主体：copyof是Arrays中的方法：

v.elementData = Arrays.copyOf(elementData, size);

我们具体来看copyof()方法：它返回了一个数组，调用重载函数

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

copyof()的重载函数：

如果(Object)newType == (Object)Object[].class 为 true，直接创建一个数组，如果不为真，调用

Array.newInstance()方法创建具有指定组件类型和尺寸的新数组。

System.arraycopy()方法：将指定源数组中的数组从指定位置复制到目标数组位置

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    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;
}

6、案例：学生1姓名A，年龄18，将该对象的数据复制到另一个对象学生2中，并且此后学生1，2两个对象的数据不会互相影响。

方法一：浅拷贝：

在Student类中重写clone方法

注意：需要将权限修饰符改为public，将返回对象改为Student

@Override
public Student clone() throws CloneNotSupportedException {
    return (Student) super.clone();
}

public static void main(String[] args) throws CloneNotSupportedException {
    //创建一个对象
    Student student = new Student("A",18);
    //克隆
    Student student1 = student.clone();
    //比较两个学生的地址是否一项
    System.out.println(student.hashCode() == student1.hashCode());   //false
    //比较两个学生的数据是否一样
    System.out.println(student);      //Student{name='A', age=18}
    System.out.println(student1);     //Student{name='A', age=18}
    //改变一个学生数据，看是否影响另一个学生
    student1.setName("C");
    System.out.println(student);      //Student{name='A', age=18}
    System.out.println(student1);     //Student{name='C', age=18}
}

浅拷贝的局限性：

基本数据类型可以达到完全复制，而引用数据类型不可以

原因：在学生对象student被克隆的时候，引用数据类型仅仅是拷贝了一份引用，因此当克隆对象引用数据类型的值发生改变时，被克隆对象student的引用数据类型的值也会跟随改变。

也就是说，浅拷贝只是克隆了引用数据类型的地址。

我们新写一个类：Book类：

public class Book{
    private String bookName;
    public Book(String bookName) {
        this.bookName = bookName;
    }

    public String getBookName() {
        return bookName;
    }

    public void setBookName(String bookName) {
        this.bookName = bookName;
    }

    @Override
    public String toString() {
        return "Book{" +
                "bookName='" + bookName + '\'' +
                '}';
    }
}

在Student类中

public class Student implements Cloneable {
    private String name;
    private Integer age;
    private Book book;
    public Student() {
    }

    public Student(String name, Integer age, Book book) {
        this.name = name;
        this.age = age;
        this.book = book;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", book=" + book +
                '}';
    }

    @Override
    public Student clone() throws CloneNotSupportedException {
        return (Student) super.clone();
    }

测试：我们发现修改Book的名称，两个学生的Book数据都会改变

public static void main(String[] args) throws CloneNotSupportedException {
    Book chineseBook = new Book("Chinese");
    //创建一个对象
    Student student = new Student("A",18,chineseBook);
    //克隆
    Student student1 = student.clone();
    //比较两个学生的地址是否一项
    System.out.println(student.hashCode() == student1.hashCode());   //false
    //比较两个学生的数据是否一样
    System.out.println(student);      
    //Student{name='A', age=18, book=Book{bookName='Chinese'}}
    System.out.println(student1);     
    //Student{name='A', age=18, book=Book{bookName='Chinese'}}
    //改变一个学生数据，看是否影响另一个学生
    chineseBook.setBookName("Chinese1");
    System.out.println(student);      
    //Student{name='A', age=18, book=Book{bookName='Chinese1'}}
    System.out.println(student1);     
    //Student{name='A', age=18, book=Book{bookName='Chinese1'}}
}

方法二：深拷贝：重写clone()方法

在Book中继承Cloneable接口：在Book类中重写clone方法：

@Override
protected Object clone() throws CloneNotSupportedException {
    return super.clone();
}

在Student类中重写Clone方法

    @Override
    public Student clone() throws CloneNotSupportedException {
//        return (Student) super.clone();

        Student stu = (Student) super.clone();

        Book book = (Book)this.book.clone();

        stu.setBook(book);

        return stu;

    }

测试：同样一段代码：student的Book数据改变，但student1没有改变

public static void main(String[] args) throws CloneNotSupportedException {
    Book chineseBook = new Book("Chinese");
    //创建一个对象
    Student student = new Student("A",18,chineseBook);
    //克隆
    Student student1 = student.clone();
    //比较两个学生的地址是否一项
    System.out.println(student.hashCode() == student1.hashCode());   //false
    //比较两个学生的数据是否一样
    System.out.println(student);      
    //Student{name='A', age=18, book=Book{bookName='Chinese'}}
    System.out.println(student1);     
    //Student{name='A', age=18, book=Book{bookName='Chinese'}}
    //改变一个学生数据，看是否影响另一个学生
    chineseBook.setBookName("Chinese1");
    System.out.println(student);      
    //Student{name='A', age=18, book=Book{bookName='Chinese1'}}
    System.out.println(student1);     
    //Student{name='A', age=18, book=Book{bookName='Chinese'}}
}

2.3、RandomAccess标记接口

标记接口有List实现，以表明它们支持快速（通常为恒定时间）随机访问。

此接口的主要目的时允许通用算法更改其行为，以便应用于随机访问列表或顺序访问列表时提供良好的性能。

2.4、AbstractList类

该类提供的骨干实现的List接口以最小化来实现该接口由一个“随机访问”数据存储备份所需的工作。

3、ArrayList源码

3.1、构造函数

1、空参构造

//elementData    集合真正存储数据的容器
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA;   默认空容量的数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

2、构造具有指定初始容量的空列表

public ArrayList(int initialCapacity) {
    //如果大于0，创建指定长度的数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //如果等于0，不需要创建新数组，ArrayList提供了一个空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        //如果小于0，异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

3、构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。

public ArrayList(Collection<? extends E> c) {
    //将参数中的集合转变为数组，并赋值给数组a
    Object[] a = c.toArray();
    //判断，
    if ((size = a.length) != 0) {
        //判断类型
        if (c.getClass() == ArrayList.class) {
            //赋值给ArrayList中的数组
            elementData = a;
        } else {
            //否则复制指定的数组，并传入ArrayList中的数组中
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.替代为一个空数组
        elementData = EMPTY_ELEMENTDATA;
    }
}

3.2、add方法

1、将指定的元素追加到此列表的末尾

ArrayList<String> str = new ArrayList<>(5);
str.add("A");

源码：

public boolean add(E e) {
    //数组是否需要扩容，
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

//ensureCapacityInternal()方法
//elementData是当前ArrayList中元素
//minCapacity是当前ArrayList中最少的空间
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//调用calculateCapacity()方法
//得到当前的最小的空间。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  //记录着集合的修改次数
	
    // overflow-conscious code
    //如果需要的最小空间比当前空间大，需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//minCapacity是当前需要的最小空间

private void grow(int minCapacity) {
    // overflow-conscious code
    //得到原来的arrayList的长度
    int oldCapacity = elementData.length;
    //一个新的长度，是原数组长度的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果新数组的长度比需要的最小长度还要小，则直接将最小长度赋值给新数组的长度
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    
    //将数组复制到arrayList中的数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

我们在回到add()方法的源码中。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //arrayList中数组的长度为10
    //Size是数组中元素的个数
    //size++：元素个数加1
    //将数据存储到小标为size的位置
    elementData[size++] = e;
    return true;
}

2、在此列表的指定位置插入指定元素

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");
//在位置1插入D   1是指数组的下标
str.add(1,"D");

源码：

public void add(int index, E element) {
    //检查是否越界
    rangeCheckForAdd(index);
	//判断是否需要扩容，上文以详细介绍
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //没有元素都向后移动一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //将下标为index的位置赋值为element
    elementData[index] = element;
    //数组元素个数加1
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

关于System.arraycopy()方法，我们无法读到源码，但我们可以写一些例子来了解这个方法：

int[] ints = {1,2,3,0,0,0};
System.arraycopy(ints,1,ints,2,2);

for (int anInt : ints) {
    System.out.print(anInt + "\t");  //1	2	2	3	0	0	
}

3、按指定集合的Iterator返回的顺序将指定集合中的元素追加到此列表的末尾

ArrayList<String> str = new ArrayList<>();
ArrayList<String> str1 = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

str1.add("D");
str1.add("E");
str1.add("F");

str.addAll(str1);

源码：

public boolean addAll(Collection<? extends E> c) {
    //将需要添加的集合转变成数组
    Object[] a = c.toArray();
    //得到该数组的长度
    int numNew = a.length;
    //判断是否需要扩容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //将a中的元素从0开始赋值给elementData中，且elementData是从size开始。
    //共赋值numNew次
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

4、将指定集合中的元素插入此列表中，从指定的位置开始。

ArrayList<String> str = new ArrayList<>();
ArrayList<String> str1 = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

str1.add("D");
str1.add("E");
str1.add("F");

str.addAll(1,str1);

源码：

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;
    //将arrayList中的数据，从第index个开始，向后移动numNew个位置
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
	//将需要添加的元素赋给arrayList中的数组
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

3.3、set方法

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

str.set(1,"D");

源码：

public E set(int index, E element) {
    //检查是否越界
    rangeCheck(index);
	//得到下标为index的元素
    E oldValue = elementData(index);
    
   	//下标为index处赋新值
    elementData[index] = element;
    //返回原来的元素
    return oldValue;
}

3.4、get方法

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

str.get(1);

源码：

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

3.5、toString方法

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

str.toString();

toString()方法是AbstractCollection类中的方法，它是AbstractList是父类。

public String toString() {
    //获取迭代器
    Iterator<E> it = iterator();
    //如果迭代器为空，直接返回[]
    if (! it.hasNext())
        return "[]";
	
    //创建StringBuilder
    StringBuilder sb = new StringBuilder();
    //先添加一个[
    sb.append('[');
    for (;;) {
        E e = it.next();
        sb.append(e == this ? "(this Collection)" : e);
        //没有元素了，就不再添加‘，’,直接返回
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}

3.6、迭代器

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

Iterator<String> it = str.iterator();

while(it.hasNext()){
    System.out.println(it.next());
}

源码：

public Iterator<E> iterator() {
    //返回一个Itr()对象
    return new Itr();
}

//arrayList中的内部类
private class Itr implements Iterator<E> {
    //光标，默认为0
    int cursor;       // index of next element to return
    //最后一次移动的光标的位置
    int lastRet = -1; // index of last element returned; -1 if no such
    //将集合实际修改的次数赋值给预期修改的次数
    int expectedModCount = modCount;

    Itr() {}
	//判断当前光标与arrayList中元素个数
    //如果相等，返回false，如果不等返回true
    public boolean hasNext() {
        return cursor != size;
    }

    
    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        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];
    }

在迭代器中checkForComodification();方法有什么用呢？

下面举一个例子：

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

Iterator<String> it = str.iterator();

while(it.hasNext()){
    String s = it.next();
    //当等于A是，删除这个元素
    if(s.equals("A")){
        str.remove("A");
    }
}

System.out.println(str);

运行结果：

我们在api文档中查看这个异常：

当不允许这样的修改时，可以通过检测到对象的并发修改的方法来抛出此异常。

//在进入迭代器之前，expectedModCount就被赋值为modCount，
//我们直到，modCount是指修改的次数，调用remove方法，modCount就会改变
//判断，如果两个不等，返回ConcurrentModificationException
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

//remove方法
public boolean remove(Object o) {
    //如果删除元素为空
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //调用fastMove方法
                fastRemove(index);
                return true;
            }
    } else {
        //否则，遍历整个arrayList，找到o
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                //调用fastMove方法
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    //修改次数加1
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //上文已经介绍，前移一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //arrayList中元素个数减1
    elementData[--size] = null; // clear to let GC do its work
}

但是：值得注意的是，如果我们删除的是倒数第二个元素：不会抛出异常。

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

Iterator<String> it = str.iterator();

while(it.hasNext()){
    String s = it.next();
    if(s.equals("B")){
            str.remove("B");
    }
}

System.out.println(str);   //[A, C]

这是因为在删除完后，arrayList中的长度变为了：2，在进行下一次迭代时，需要判断size和光标的大小：

//此时光标为2，size也为2，返回false，因此不会循环了
public boolean hasNext() {
    return cursor != size;
}

那么如果删除元素？

迭代器为我们提供了一个方法：remove()：

从底层集合删除此迭代器返回的最后一个元素

public void remove() {
    //最后一次迭代的下标
    if (lastRet < 0)
        throw new IllegalStateException();
    //上文已介绍
    checkForComodification();

    try {
        //删除上一个迭代的元素
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        ////////*********将实际修改的次数赋给预期修改次数
        //我们发现，迭代器中的删除元素的方法实际上还是arrayList中的方法
        //但是这一步保证了程序不会出现异常
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

3.7、clear方法

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

str.clear();

源码：

public void clear() {
    //修改次数加1
    modCount++;

    // clear to let GC do its work
    //将所有元素置为null
    for (int i = 0; i < size; i++)
        elementData[i] = null;
	
    //将size置为0
    size = 0;
}

3.8、contains方法

如果此列表包含指定元素，则返回true

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

str.contains("A");

源码：

//调用indexof()方法
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 {
        //遍历找到o
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

3.9、isEmpty方法

如果此列表不包含元素，返回true

ArrayList<String> str = new ArrayList<>();

str.add("A");
str.add("B");
str.add("C");

str.isEmpty();

源码：

//如果arrayList中数组长度为空，返回true
public boolean isEmpty() {
    return size == 0;
}