ArrayList源码解析

Posted on | In
Words count in article: 2.3k | Reading time ≈ 10

ArrayList源码解析

简介

ArrayList是Java SDK中提供的动态数组。相比于普通的数组，它的容量能自动增长，继承于AbstractList抽象类，实现了List、RandomAccess、Cloneable和Serializable接口。

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

实现了RandomAccess接口，意味着它提供了随机访问的功能，可以方便地通过ArrayList.get(index)获取指定位置上的元素。

实现了Cloneable接口，重写了clone函数。

实现了Serializable接口，意味着ArrayList可以被序列化。

实现逻辑

ArrayList内部是使用一个数组来实现的。每当添加元素的时候超过了数组的大小，就会自动扩容。这些逻辑下个章节一一讲清楚。

主要属性

  • DEFAULT_CAPACITY： 数组的默认大小。初始为10
  • EMPTY_ELEMENTDATA：空数组对象
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认构造函数创建的ArrayList，使用这个空对象数组
  • elementData：对象存放数组
  • size：ArrayList中的元素个数
  • modCount：ArrayList中元素被改变的次数，用于快速失败

主要函数

下面就看看ArrayList中常用的一些函数是怎么实现的。

构造函数

默认无参构造函数

作用：生成一个默认的ArrayList

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

调用此方法创建出来的数组容量为10，大小为0.当第一次调用add方法时，数组的size才会变成10.

有参构造函数（指定初始化容量大小）

作用：创建一个指定容量的ArrayList

调用此方法创建执行容量的ArrayList。需要注意的是，在new完成之后，调用size()方法，返回的还是0.只有在第一次add之后，size才会变为指定的初始化容量大小。

1
2
3
4
5
6
7
8
9
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);
        }
    }

有参构造函数（集合类对象）

作用：根据其他集合类的对象，生成一个ArrayList

1
2
3
4
5
6
7
8
9
10
11
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;
        }
    }

通过集合类对象创建一个ArrayList

boolean add(E e)方法

作用：添加一个元素到ArrayList的最后。

实现：首先通过ensureCapacityInternal方法，确保数组有足够的空间容纳新的一个元素。然后赋值，返回。

1
2
3
4
5
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

再看看ensureCapacityInternal方法

ensureCapacityInternal(int newCapacity)方法

ensureCapacityInternal方法又调用了ensureExplicitCapacity和calculateCapacity方法

1
2
3
private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

calculateCapacity(Object[] elementData, int minCapacity)方法

这个方法计算对象数组的大小。如果对象数组是空数组，也就是第一次添加元素的时候，那么它返回数组的默认大小10，否则，返回minCapacity。

总的来说，就是，如果是第一次添加元素，返回10，否则，返回minCapacity。

1
2
3
4
5
6
private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

ensureExplicitCapacity(int minCapacity)方法

1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

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

如果minCapacity大于当前数组长度，调用grow方法，对数组进行扩容。

grow(int minCapaticy)方法

ArrayList默认的扩容策略是扩容一半。

int newCapacity = oldCapacity + (oldCapacity >> 1);

如果扩容一半之后，还是不够，那就使用minCapacity。

如果新容量超过了最大的数组大小，MAX_ARRAY_SIZE（值为Integer.MAX_VALUE - 8).调用hugeCapacity方法，确保大小不会溢出。

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

hugeCapacity(int minCapacity)

数组最大大小只能到Integer.MAX_VALUE

1
2
3
4
5
6
7
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add(int index, Object 0)方法

作用：将元素添加到ArrayList的指定位置上

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

首先做范围检查，通过之后再确保容量足够数量的元素。而后将指定位置之后的元素统一后移，再将o值赋值给index上。

remove(int index)方法

作用：删除指定位置上的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        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

        return oldValue;
    }
  1. 范围校验
  2. 获取旧值保存
  3. 计算需要移动的元素个数
  4. 将index之后的所有元素前移一个单位
  5. 原size位置的元素值置为null
  6. 返回旧值

remove(Object o)方法

作用：删除某个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean remove(Object o) {
        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++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
  1. 如果待删除的为null，直接调用fastRemove方法，移动元素，返回
  2. 如果待删除的元素不为null，通过equals方法获得指定元素后，调用fastRemove方法，移动元素，返回

fastRemove(int index)方法

作用：计算需要前移的元素个数，将元素前移一个单位

1
2
3
4
5
6
7
8
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
    }

size()方法

作用：返回当前ArrayList的大小

实现：直接返回size变量

1
2
3
public int size() {
        return size;
    }

get(int index)方法

作用：返回ArrayList上指定索引位置的值

实现：通过索引范围检查之后，直接从数组中获取。

1
2
3
4
5
public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

set(int index, Object o)方法

作用：将ArrayList指定索引上的值，设置为o，并返回旧值

实现，通过校验之后，直接赋值给指定索引位置。

1
2
3
4
5
6
7
public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

isEmpty()方法

作用：返回当前ArrayList是否为空

实现：直接判断size是否为0

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

contains(Object o)方法

作用：返回ArrayList中是否包含某个具体的元素

实现：调用方法indexOf(Object o)，判断它返回的索引是否大于等于0。大于等于0表示存在，

1
2
3
public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

indexOf(Object o)方法

作用：返回某个对象第一次出现在ArrayList中的索引，如果不存在，则返回-1.

实现：分null对象和非null对象，遍历一遍数组寻找

1
2
3
4
5
6
7
8
9
10
11
12
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;
        }
        return -1;
    }

null对象直接用==比较，非null对象调用equals方法比较

lastIndexOf方法

作用：返回某个对象最后一次在ArrayList中出现的索引，否则返回-1

实现：和indexOf差不多，唯一不同的是，它是从ArrayList的末尾开始遍历，而indexOf是从ArrayList的头部开始遍历

1
2
3
4
5
6
7
8
9
10
11
12
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;
        }
        return -1;
    }

clone()方法

作用：返回当前ArrayList的浅拷贝

1
2
3
4
5
6
7
8
9
10
11
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);
        }
    }

clear()方法

作用：清空数组里面的所有元素，并将size置为0

1
2
3
4
5
6
7
8
9
public void clear() {
        modCount++;

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

        size = 0;
    }

将ArrayList数组列表中的每个元素置为null，然后size置0.这样比起new一个ArrayList是要效率高一点的，因为它会保存原数组的capacity。

iterator()方法

作用：生成一个ArrayList的迭代器，用于遍历ArrayList

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

iterator的实现类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}

        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];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

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

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

注意到在调用remove的时候，都会调用checkForComodification()方法。这个方法做的是，每次调用的时候判断一下expectModCount是否和ArrayList的modCount相同，如果不相同的话，表示该ArrayList在迭代的过程中被人修改过了。就会引发一个ConcurrentModificationException异常。

0%