ArrayList源码解析

atatar

前言

本篇主要讨论ArrayList集合,本人使用的jdk1.8

正文

成员变量

1
2
3
4
5
6
7
8
9
10
11
12
   
    private static final int DEFAULT_CAPACITY = 10;
    
    private static final Object[] EMPTY_ELEMENTDATA = {};
   
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;
    
    private int size;
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  1. 默认初始化容量(未指定容量,并且要在调用add方法时才会用)
  2. 当ArrayList初始化时显示指定容量为0时的初始化数据
  3. 当ArrayList初始化时未显示指定容量时的初始化数据
  4. ArrayList中存取数据的数组
  5. 数组中实际存储数据的大小
  6. ArrayList中数组容量的最大值

构造方法

ArrayList有三个构造方法;

  • 初始化时显示指定容量

当显示指定容量为0时,使用EMPTY_ELEMENTDATA;

1
2
3
4
5
6
7
8
9
10
11
12

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);
        }
    }
    
  • 初始化时未指定容量

未显示指定数组容量时,使用 ` DEFAULTCAPACITY_EMPTY_ELEMENTDATA ` ;

1
2
3
4
5

 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
  • 将其他集合类转为ArrayList
1
2
3
4
5
6
7
8
9
10
11
12
13

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

常用的方法

add()方法

向ArrayList中添加元素;add方法有两种方式

  • 直接添加数据,不指定位置
1
2
3
4
5
6
7

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

该方法直接将数据存储到了数组的末尾,并且size会自增1,在增加数据之前会调用ensureCapacityInternal方法对数组容量进行校验,也就是自动扩容;扩容留到后边讲;

  • 添加数据,并指定数据存储的位置
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++;
    }
    

将数据存入数组指定位置,首先会调用 ` rangeCheckForAdd ` 检查 ` index ` 是否越界, 然后就是 ` ensureCapacityInternal ` 方法进行扩容校验, 然后在调用 ` System.arraycopy ` 方法对原数组进行复制, 将数组从下标为index到结尾的所有数据整体向后移一位, 这个方法是很耗费内存的(我百度看到的博客基本上都是这么说的), 这时候下标为 ` index ` 的那段空间就为空了,然后再将 ` element ` 插入数组中的指定位置;

System.arraycopy 方法图如下:

1
2
3

public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

remove()方法

删除ArrayList中的元素;remove方法也有两种方式

  • 根据下标删除
1
2
3
4
5
6
7
8
9
10
11
12

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

rangeCheck 方法检查 ` index ` 是否越界;可以看出最后就是调用 ` System.arraycopy ` 方法来复制数组,将下标之后的所有元素向前移一位,然后 ` size ` 再自减;并且清空最后的元素,最后返回删除的元素;

  • 传入元素删除数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 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 ` 方法删除元素;其中 ` fastRemove ` 方法与 ` remove(int index) ` 方法是一样的,只是没有返回值,这里就不贴代码了;
  2. 当传入 ` Object ` 不为 ` null ` 时,会循环数组,找到 ` o.equals(elementData[index]) ` 为true时的元素的第一个下标,然后调用 ` fastRemove ` 来删除元素

注意,都是删除的第一个相同的元素,后面的就不会管了;

现象:在才开始使用 ` ArrayList ` 的时候,用 ` for 循环来删除 ArrayList ` 中符合某一规则的元素,如果两个相同元素在连续的位置上,会出现不能全部删除现象,其实这是对ArrayListremove方法的源码不熟了;

remove方法是将数组复制了一遍,产生了新的数组,这时数组里面元素的下标都改变了,这时for循环并没有改变接着向后循环,所以相邻的一个元素就无法删除;

get()方法

获取ArrayList中的元素

就一种方式;根据下标获取元素

1
2
3
4
5
6

public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
    

先调用rangeCheck检查下标是否越界,在获取元素

set()方法

修改ArrayList中额元素;

也是就一种方式:根据传入的下标及元素来修改

1
2
3
4
5
6
7
8

  public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
    

首先调用rangeCheck检查下标是否越界,获取下标元素值,然后再用传入的元素替换掉原来的元素;最后返回原来的元素;

size()方法

1
2
3
4
5

 public int size() {
        return size;
    }
    

获取ArrayList中实际使用的容量;不是数组容量;

数组容量自动增长

我们在使用ArrayList的时候都是调用add方法来添加元素,但是我们知道ArrayList是使用的数组来存储元素,而数组是有长度,为什么我们使用add方法可以一直添加元素且不会报错?

代码如下:

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

    // 1
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    //2
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //3
    private void grow(int minCapacity) {
        // overflow-conscious code
        //3.1
        int oldCapacity = elementData.length;
        //3.2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //3.3
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //3.4
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //3.5
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    

扩容使用到了四个方法

  1. ensureCapacityInternal方法主要是判断如果当前ArrayList是默认未指定容量的初始化时,然后选取minCapacityDEFAULT_CAPACITY中的最大值赋予minCapacity,再传入下一个方法;

  2. ensureExplicitCapacity方法接受minCapacity参数,判断下标是否超过当前数组的容量,如果超过则调用grow方法,未超过则不调用;

  3. grow方法就是扩容的主要方法,选取扩容的值;

    3.1 首先获取原来数组的长度oldCapacity;

    3.2 进行扩容计算,代码中使用了位运算,增加的那部分为oldCapacity向右移一位的值,其实就是一半;

    3.3 判断扩容后是否满足minCapacity

    3.4 判断扩容后的newCapacity是否超过ArrayList允许的最大值,如果超过就用最大值替换

    3.5 调用Arrays.copyOf对数组进行扩容;

迭代器

代码如下:

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

    //1
    public Iterator<E> iterator() {
        return new Itr();
    }
    //2
    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;
        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();
            }
        }
       
    }
    

主要说Itr类中的三个变量及三个方法

三个变量:

  1. cursor :初始值为零,返回下一个元素的索引
  2. lastRet :返回的最后一个元素的索引;如果没有,则为-1
  3. expectedModCount :略

三个方法:

  1. hasNext方法,判断cursor是否与size相等;就相当于判断下标是否越界;
  2. next方法:获取下标为cursor 的元素,且cursor 自增1
  3. remove方法:调用了ArrayList中的remove方法删除下标为lastRet的元素,且cursor 变为lastRet的值,这就解决了两个连续元素不能删除的现象了;

总结

  • 容器底层采用数组存储,申请内存为连续空间,每次扩容为1.5倍
  • ArrayList的实现中大量调用了 Arrays.copyof()System.arraycopy()方法,其实Arrays.copyof()内部也是调用System.arraycopy()System.arraycopy()为Native方法
  • ArrayList随机元素时间复杂度O(1),插入删除操作需大量移动元素,效率较低
  • ArrayList可以存储null值
  • ArrayList线程是不安全的
  • ArrayList进行选择删除时,不能用for循环(ArrayList删除方法调用的System.arraycopy()这个方法,生成的是一个新的数组,下标也已经改变了),建议用迭代器进行删除。
坚持原创技术分享,您的支持将鼓励我继续创作!