初识Arraylist底层

发表于 | 阅读量 次 | 分类于 |

前言

ArrayList也叫数组列表，底层使用的是数组实现的，严格来说是动态数组。
一般情况下，一个问题的认识都是由具体到抽象，先看一个入门案例：

1
2
3
4
5
6
7
8
9
10
11
ArrayList<String> al=new ArrayList<>();
	al.add("hello");
	al.add("world");
	al.add("lol");
	System.out.println(al.size());
	System.out.println(al.get(0));
	System.out.println(al.get(1));
	System.out.println(al.get(2));
	al.remove(1);
	System.out.println(al.size());
	System.out.println(al.get(1));

测试结果：3 hello world lol 2
这个例子也很好理解，大概流程是先创建集合，在依次加入数据，依次取出和大小，在删除其中一个，在看大小和删除的数据是否存在，好了，入门程序就到这了，运用这几个方法我们可以把它复杂化运用到我们以后想要的上面。

至此下面将开始简单介绍一下add，get，remove方法的源码分析。
（当然我们也可以通过设置断点追踪源码）

add方法

在此之前，先介绍一下源码中的几个静态常量

1
2
3
private static final int DEFAULT_CAPACITY=10;//数组为空默认的最小分配数组容量
private static final Object[] EMPTY_ELEMENTDATA = {};//默认空数组
private int size;//数组长度，初始化默认为0；

下面就是add方法

1
2
3
4
5
6
public boolean add(E e) {
//保证数组容量的容量始终够用
     ensureCapacityInternal(size + 1);  
   //size是elementData数组中元素的个数，初始为0
     elementData[size++] = e;
      return true;}

首先进入第一个方法分析：

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
private void ensureCapacityInternal(int minCapacity) {
//如果数组没有元素，给数组一个默认大小，会选择实例化时的值与默认大小较大者
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //保证容量够用
        ensureExplicitCapacity(minCapacity);
    }
   private void ensureExplicitCapacity(int minCapacity) {
//数组发生size更改的次数，默认为0
        modCount++;
         //如果数组长度小于默认的容量10，则调用扩大数组大小的方法
             if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
//数组长度的上限
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  
   private void grow(int minCapacity) {
        // 保证数组容量扩大一倍
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 得到扩大容量后的新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
private static int hugeCapacity(int minCapacity) {
//返回新数组的大小
        if (minCapacity < 0) 
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

至此算是把add方法的底层分析了一遍，我们现在是不是可以假象一个简单例子来模拟流程

1
2
ArrayList<String> al=new ArrayList<>();
	al.add("hello");

大概执行流程，数组为空，分配一个默认大小为10的容量，容量动态扩充，然后size变化，最后将值赋给数组，说了这么多，还是有点，总之，可以自己模拟数据，然后进行断点调试，就大概了解其过程了。

get方法

在此之前先补充一下arraylist的构造函数，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//如果构造函数不指定大小，则将默认空对象给数组对象
public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
 
//指定初始化数组大小
public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

下面就来看一看get方法的执行过程

1
2
3
4
5
6
7
8
9
10
11
12
public E get(int index) {
//判断index是否合法
        rangeCheck(index);
      //得到相应的数组数据
        return elementData(index);
    }
private void rangeCheck(int index) {
//判断数组是否越界
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

可以看到它的执行过程就这两步

remove方法

这里先说明一下，由于删除操作会改变size，所以每次删除都需要把元素向前移动一个位置，然后把最后一个位置设置为null，一次删除操作完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public E remove(int index) {
   //判断index是否合法
        rangeCheck(index);
// size更改的次数
        modCount++;
//保存待删除的位置的元素
        E oldValue = elementData(index);
        //要移动的元素个数
        int numMoved = size - index - 1;
    //如果index不是最后一个元素，则从第index+1到最后一个位置，依次向前移动一个位置
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
 //元素的size-1并且最后一个元素位置设为null
        elementData[--size] = null; 
        return oldValue;
    }
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

很遗憾：断点调试中没有源码，因为其是native，是其他语言编写的，这里只做简单介绍
从指定源数组中复制一个数组，复制从指定的位置开始，到目标数组的指定位置结束。从 src 引用的源数组到 dest 引用的目标数组，数组组件的一个子序列被复制下来。被复制的组件的编号等于 length 参数。源数组中位置在 srcPos 到 srcPos+length-1 之间的组件被分别复制到目标数组中的 destPos 到 destPos+length-1 位置。

最后不得不提的是因为arraylist是动态增长的，即容量增产幅度遵循size/2+1，即默认为10，所以依次为：10,16,25.。。。。
这就造成arraylist是线程不安全的，多线程中产生问题，参考单例模式

快乐源于分享，总结溢于提高

热评文章