JDK源码阅读之ArrayList

Author：带翅膀的猫
发布时间：September 24, 2019
2952views
No comments
1556 words
Categories： JDK源码

ArrayList

在学习JAVA集合中初次学习的容器就是ArrayList，我们深深的感到它的强大，和数组相比它能实现容量的自动增长。但是大部分人对它的了解都是不够详细的，现在跟随我的步伐窥探一下吧！

类图

      ArrayList 继承了AbstractList，实现了List。它是一个数组，提供了相关的添加、删除、修改、遍历等功能。
      ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。
      ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
      ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

重要属性

transient Object[] elementData; //用于存储数据
private int size;//ArrayList大小(Object[]包含的元素数目)
private static final int DEFAULT_CAPACITY = 10;//默认初始化大小为10

可以发现ArrayList的底层是通过Object[]实现的。

构造方法

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

不指定容量则默认容量为10。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

如果初始化容量小于0则抛出IllegalArgumentException异常。

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

我们可以通过另外的Collection创建ArrayList。

List<Integer> list1 = new ArrayList<>();
list1.add(1);
list1.add(2);
list1.add(3);
List<Integer> list2 = new ArrayList<>(list1);//直接使用另一个Collection创建list2
for(Integer i:list2){
    System.out.println(i);
}
/**
 * 1
 * 2
 * 3
 */

add相关

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //确保对象数组elementData有足够的容量，可以将新加入的元素e加进去
    elementData[size++] = e;//加入新元素e，size加1
    return true;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);//需要扩容
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量是原容量的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;//新的容量依旧不足则为minCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);//新容量大于最大容量(Integer.MAX_VALUE-8),调用hugeCapacity方法重新计算
    // 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;
}

ArrayList不仅仅可以一个个的添加元素，还可以通过另外一个list直接批量添加。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // 容量检查
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;//若加入的是空集合则返回false
}

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
List<Integer> list2 = new ArrayList<>();
list2.addAll(list);
for(Integer i:list2){
    System.out.println(i);
}
/**
 * 1
 * 2
 * 3
 */

get(int index)

public E get(int index) {
    rangeCheck(index);//index合法性检查

    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));//越界
}

set(int index,E element)

public E set(int index, E element) {
    rangeCheck(index);//index合法性检查

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;//返回旧值
}

remove相关

/**
 *根据下标删除元素
 */
public E remove(int index) {
    rangeCheck(index);//index合法性检查

    modCount++;
    E oldValue = elementData(index);//获取旧值

    int numMoved = size - index - 1;//计算出需要移动的元素个数 （因为需要将后续元素左移一位 此处计算出来的是后续元素的位数）
    if (numMoved > 0)//如果这个值大于0 说明后续有元素需要左移  是0说明被移除的对象就是最后一位元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);//index右边的所有元素左移一位,覆盖掉index位置上的元素
    elementData[--size] = null; // 将最后一个元素赋值为null，这样就可以被gc回收了

    return oldValue;//返回被删除的元素
}

/*
 *删除特定的对象（第一个出现的）
 */
public boolean remove(Object o) {
    if (o == null) {//如果元素是null 遍历数组移除第一个null
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);//遍历找到第一个null元素的下标 调用下标移除元素的方法
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {//找到元素对应的下标 调用下标移除元素的方法
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

contains(Object o)

判断list中是否有指定的对象。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
//indexOf返回第一个出现的对象o的索引
public int indexOf(Object o) {
    //一个个遍历list寻找符合的对象，找到则返回第一次出现下标，否则返回-1
    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;
    }
    return -1;
}

与indexOf相对的还有lastIndexOf方法，它返回最后一个o的索引。

clear()

使用clear对list进行清空。

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

clone()

使用clone方法可以拷贝一个相同的list。注意这是浅拷贝。

static class Stu{
    public String name;
    public Stu(String name){
        this.name = name;
    }
    public String toString(){
        return name;
    }
}
public static void main(String[] args) {
    ArrayList<Stu> list = new ArrayList<>();
    list.add(new Stu("Java"));
    list.add(new Stu("Pyhton"));
    list.add(new Stu("Ruby"));
    System.out.println("list："+list);
    ArrayList<Stu> listCopy = (ArrayList<String>)list.clone();
    System.out.println("listCopy："+list);
    System.out.println("修改：");
    list.get(0).name = "C++";
    System.out.println("list："+list);
    System.out.println("listCopy："+listCopy);
    /**
     * list：[Java, Pyhton, Ruby]
     * listCopy：[Java, Pyhton, Ruby]
     * 修改：
     * list：[C++, Pyhton, Ruby]
     * listCopy：[C++, Pyhton, Ruby]
     */
}

实现深拷贝。

static class Stu implements Cloneable{
    public String name;
    public Stu(String name){
        this.name = name;
    }
    public String toString(){
        return name;
    }
    @Override
    public Stu clone(){
        return new Stu(this.name);
    }
}
public static void main(String[] args) {
    ArrayList<Stu> list = new ArrayList<>();
    list.add(new Stu("Java"));
    list.add(new Stu("Pyhton"));
    list.add(new Stu("Ruby"));
    System.out.println("list："+list);
    ArrayList<Stu> listCopy = new ArrayList<>();
    for (Stu stu:list){
        listCopy.add(stu.clone());
    }
    System.out.println("listCopy："+list);
    System.out.println("修改：");
    list.get(0).name = "C++";
    System.out.println("list："+list);
    System.out.println("listCopy："+listCopy);
    /**
     * list：[Java, Pyhton, Ruby]
     * listCopy：[Java, Pyhton, Ruby]
     * 修改：
     * list：[C++, Pyhton, Ruby]
     * listCopy：[Java, Pyhton, Ruby]  //没有改变，说明是深拷贝
     */
}

iterator()

我们除了可以使用for循环遍历list，我们也可以使用iterator遍历列表。

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // 表示下一个元素的索引位置
    int lastRet = -1; // 表示上一个元素的索引位置
    int expectedModCount = modCount;//预期被修改的次数，用于判断是否在遍历的过程中，是否发生了add、remove操作
        //这是集合迭代中的一种“fast-fial”机制，这种机制提供迭代过程中集合的安全性。

    Itr() {}

    public boolean hasNext() {
        return cursor != size;//如果cursor==size，说明已经遍历完了
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();//检测在遍历的过程中，是否发生了add、remove操作
        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];
    }

    public void remove() {//使用迭代器删除元素
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;//统一expectedModCount和modCount
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {//检测是否修改了list
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();//在迭代的过程中如果进行了修改（add/remove）则抛出异常。remove指的是不使用迭代器进行删除。
    }
}

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
    list.remove(2);//迭代过程不使用迭代器进行删除，抛异常
}
/**
  * Exception in thread "main" java.util.ConcurrentModificationException
  */

如果我们使用迭代器进行删除则不会出错。

ArrayList<String> list = new ArrayList<>();
list.add("abc");
list.add("def");
list.add("ghi");
System.out.println("删除前："+list);
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
    if("def".equals(iterator.next())){
        iterator.remove();//迭代过程使用迭代器进行删除
    }
}
System.out.println("删除后："+list);
/**
 * 删除前：[abc, def, ghi]
 * 删除后：[abc, ghi]
 */

与ArrayList类似的容器还有Vector，不过我们需要注意的是ArrayList是线程不安全的，而Vector是线程安全的。

版权属于：带翅膀的猫
本文链接：https://www.chengpengper.cn/archives/40/
转载时须注明出处及本声明

Last modification：September 24th, 2019 at 03:01 pm

如果觉得我的文章对你有用，请随意赞赏

JDK源码阅读之ArrayList

带翅膀的猫 • 2019 年 09 月 24 日

ArrayList

类图

重要属性

transient Object[] elementData; //用于存储数据
private int size;//ArrayList大小(Object[]包含的元素数目)
private static final int DEFAULT_CAPACITY = 10;//默认初始化大小为10

可以发现ArrayList的底层是通过Object[]实现的。

构造方法

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

不指定容量则默认容量为10。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

如果初始化容量小于0则抛出IllegalArgumentException异常。

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

我们可以通过另外的Collection创建ArrayList。

List<Integer> list1 = new ArrayList<>();
list1.add(1);
list1.add(2);
list1.add(3);
List<Integer> list2 = new ArrayList<>(list1);//直接使用另一个Collection创建list2
for(Integer i:list2){
    System.out.println(i);
}
/**
 * 1
 * 2
 * 3
 */

add相关

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  //确保对象数组elementData有足够的容量，可以将新加入的元素e加进去
    elementData[size++] = e;//加入新元素e，size加1
    return true;
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);//需要扩容
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量是原容量的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;//新的容量依旧不足则为minCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);//新容量大于最大容量(Integer.MAX_VALUE-8),调用hugeCapacity方法重新计算
    // 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;
}

ArrayList不仅仅可以一个个的添加元素，还可以通过另外一个list直接批量添加。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // 容量检查
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;//若加入的是空集合则返回false
}

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
List<Integer> list2 = new ArrayList<>();
list2.addAll(list);
for(Integer i:list2){
    System.out.println(i);
}
/**
 * 1
 * 2
 * 3
 */

get(int index)

public E get(int index) {
    rangeCheck(index);//index合法性检查

    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));//越界
}

set(int index,E element)

public E set(int index, E element) {
    rangeCheck(index);//index合法性检查

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;//返回旧值
}

remove相关

/**
 *根据下标删除元素
 */
public E remove(int index) {
    rangeCheck(index);//index合法性检查

    modCount++;
    E oldValue = elementData(index);//获取旧值

    int numMoved = size - index - 1;//计算出需要移动的元素个数 （因为需要将后续元素左移一位 此处计算出来的是后续元素的位数）
    if (numMoved > 0)//如果这个值大于0 说明后续有元素需要左移  是0说明被移除的对象就是最后一位元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);//index右边的所有元素左移一位,覆盖掉index位置上的元素
    elementData[--size] = null; // 将最后一个元素赋值为null，这样就可以被gc回收了

    return oldValue;//返回被删除的元素
}

/*
 *删除特定的对象（第一个出现的）
 */
public boolean remove(Object o) {
    if (o == null) {//如果元素是null 遍历数组移除第一个null
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);//遍历找到第一个null元素的下标 调用下标移除元素的方法
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {//找到元素对应的下标 调用下标移除元素的方法
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

contains(Object o)

判断list中是否有指定的对象。

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
//indexOf返回第一个出现的对象o的索引
public int indexOf(Object o) {
    //一个个遍历list寻找符合的对象，找到则返回第一次出现下标，否则返回-1
    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;
    }
    return -1;
}

与indexOf相对的还有lastIndexOf方法，它返回最后一个o的索引。

clear()

使用clear对list进行清空。

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

clone()

使用clone方法可以拷贝一个相同的list。注意这是浅拷贝。

static class Stu{
    public String name;
    public Stu(String name){
        this.name = name;
    }
    public String toString(){
        return name;
    }
}
public static void main(String[] args) {
    ArrayList<Stu> list = new ArrayList<>();
    list.add(new Stu("Java"));
    list.add(new Stu("Pyhton"));
    list.add(new Stu("Ruby"));
    System.out.println("list："+list);
    ArrayList<Stu> listCopy = (ArrayList<String>)list.clone();
    System.out.println("listCopy："+list);
    System.out.println("修改：");
    list.get(0).name = "C++";
    System.out.println("list："+list);
    System.out.println("listCopy："+listCopy);
    /**
     * list：[Java, Pyhton, Ruby]
     * listCopy：[Java, Pyhton, Ruby]
     * 修改：
     * list：[C++, Pyhton, Ruby]
     * listCopy：[C++, Pyhton, Ruby]
     */
}

实现深拷贝。

static class Stu implements Cloneable{
    public String name;
    public Stu(String name){
        this.name = name;
    }
    public String toString(){
        return name;
    }
    @Override
    public Stu clone(){
        return new Stu(this.name);
    }
}
public static void main(String[] args) {
    ArrayList<Stu> list = new ArrayList<>();
    list.add(new Stu("Java"));
    list.add(new Stu("Pyhton"));
    list.add(new Stu("Ruby"));
    System.out.println("list："+list);
    ArrayList<Stu> listCopy = new ArrayList<>();
    for (Stu stu:list){
        listCopy.add(stu.clone());
    }
    System.out.println("listCopy："+list);
    System.out.println("修改：");
    list.get(0).name = "C++";
    System.out.println("list："+list);
    System.out.println("listCopy："+listCopy);
    /**
     * list：[Java, Pyhton, Ruby]
     * listCopy：[Java, Pyhton, Ruby]
     * 修改：
     * list：[C++, Pyhton, Ruby]
     * listCopy：[Java, Pyhton, Ruby]  //没有改变，说明是深拷贝
     */
}

iterator()

我们除了可以使用for循环遍历list，我们也可以使用iterator遍历列表。

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // 表示下一个元素的索引位置
    int lastRet = -1; // 表示上一个元素的索引位置
    int expectedModCount = modCount;//预期被修改的次数，用于判断是否在遍历的过程中，是否发生了add、remove操作
        //这是集合迭代中的一种“fast-fial”机制，这种机制提供迭代过程中集合的安全性。

    Itr() {}

    public boolean hasNext() {
        return cursor != size;//如果cursor==size，说明已经遍历完了
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();//检测在遍历的过程中，是否发生了add、remove操作
        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];
    }

    public void remove() {//使用迭代器删除元素
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;//统一expectedModCount和modCount
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {//检测是否修改了list
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();//在迭代的过程中如果进行了修改（add/remove）则抛出异常。remove指的是不使用迭代器进行删除。
    }
}

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
    list.remove(2);//迭代过程不使用迭代器进行删除，抛异常
}
/**
  * Exception in thread "main" java.util.ConcurrentModificationException
  */

如果我们使用迭代器进行删除则不会出错。

ArrayList<String> list = new ArrayList<>();
list.add("abc");
list.add("def");
list.add("ghi");
System.out.println("删除前："+list);
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
    if("def".equals(iterator.next())){
        iterator.remove();//迭代过程使用迭代器进行删除
    }
}
System.out.println("删除后："+list);
/**
 * 删除前：[abc, def, ghi]
 * 删除后：[abc, ghi]
 */

与ArrayList类似的容器还有Vector，不过我们需要注意的是ArrayList是线程不安全的，而Vector是线程安全的。

版权属于：带翅膀的猫
本文链接：https://www.chengpengper.cn/archives/40/
转载时须注明出处及本声明

JDK源码阅读之ArrayList

ArrayList

类图

重要属性

构造方法

add相关

get(int index)

set(int index,E element)

remove相关

contains(Object o)

clear()

clone()

iterator()

Leave a Comment Cancel reply

手机扫码，文章阅读转移功能

Nginx场景实战之跨域访问

JDK源码阅读之Thread

一致性哈希算法

折腾Redis之主从复制

JDK源码阅读之Float

Vim爱恨情仇之Vim的配置

Java8实战之行为参数化

线程核心基础之实现线程

线程核心基础之线程状态

JDK源码阅读之ArrayList

ArrayList

类图

重要属性

构造方法

add相关

get(int index)

set(int index,E element)

remove相关

contains(Object o)

clear()

clone()

iterator()