ArrayList详解

ArrayList是什么?

ArrayList就是动态数组，是List接口的可调整大小的数组实现；除了实现List接口之外，该类还提供了一些方法来操纵内部使用的存储列表的数组大小。它的主要底层实现是数组Object[] elementData。

为什么要设计ArrayList？

大家在使用数组的时候需要在初始化的时候去指定这个数组的长度，对于元素数量不确定的场景如果使用数组则需要预估所需的数组容量，如果估少了还需要重新申请空间并对原数组进行拷贝，因此ArrayList应运而生，用来解决数组无法动态扩容的缺陷,实现了动态扩容的效果。

数组的特点

遍历查询速度快——数组在内存是连续空间，可以根据地址+索引的方式快速获取对应位置上的元素。但是它的增删速度慢——每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。

ArrayList的特性

1.允许插入的元素重复
2.插入的元素是有序的
3.动态扩容
4.非线程安全，异步
5.基于动态数组的数据结构
6.擅长随机访问(get set)

类结构图

ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList ，实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速访问、复制、序列化的。

常用方法

add(Object e)
add(int index ,Object e)
addAll(Collection c)
addAll(int index , Collection c)
size()
get(int index)
set(int index,Object e)
indexOf(Object c)
lastIndexOf(Object c)
isEmpty()
remove(int index)
remove(Object c)
removeAll(Collection c) contains(Object c) containsAll(Collection c)
clear()
clone()
iterator()
retainAll(Collection c)
subList(int fromIndex,int toIndex)
trimToSize() 回收多余容量
toArray()
toArray(T[] a)

部分方法使用案例

 
    @Test
    public void addTest() {
        ArrayList list = new ArrayList();
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3); // 此时list : 0 1 2 3
        print("list", list);
        list.add(0, 4); //  在指定位置插入元素
        print("list", list); //  此时list ；4 0 1 2 3
        List newList = list.subList(2, 4); //截取list ，不包含最后一位
        print("newList", newList); //  此时 newList ： 1 2
        list.addAll(2, newList); //新增list，新的list元素默认排在原来元素的后面 ,此时newList 不能再使用了
        print("list", list); // 此时，list : 4 0 1 2 1 2 3
        System.out.println("list size " + list.size());
        list.set(0, 1); //在指定位置替换元素
        print("list", list); // 此时 list : 1 0 1 2 1 2 3
        System.out.println(list.indexOf(1));
        System.out.println(list.lastIndexOf(1));
        System.out.println(list.isEmpty());
 
    }
 
    private void print(String flag, List list) {
        System.out.print(flag + ":");
        list.forEach(System.out::print);
        System.out.println();
    }
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

构造方法

无参构造

示例

  private List<User> list = new ArrayList<>();  
  
1
2

源码

    //初始化一个空数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
1
2
3
4
5
6

ArrayList(int initialCapacity)

构造具有指定初始容量的List

示例

    private List<User> list = new ArrayList<>(10);
1

源码

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //将传入的 10作为参数初始化数组长度
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
1
2
3
4
5
6
7
8
9
10
11

ArrayList(Collection c)

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

案例

    private List<User> list = new ArrayList<>(new ArrayList<>());
1

源码

    public ArrayList(Collection<? extends E> c) {
        // 将传入的List 赋值给 elementData 
        elementData = c.toArray();
        //如果size != 0 代表有元素
        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 {
           // size== 0 初始化空数组 
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

add()方法解析

案例

private List<String> list = new ArrayList<>();
  list.add("test");
1
2

源码

添加元素e到容器

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

调用方法对内部容量进行校验

      private void ensureCapacityInternal(int minCapacity) {
       //判断集合存数据的数组是否等于空容量的数组 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         //通过最小容量和默认容量 出较大值 (用于第一次扩容)
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
         //将if中计算出来的容量传递给下一个方法,继续校验 
        ensureExplicitCapacity(minCapacity);
    }
1
2
3
4
5
6
7
8
9

确保数组的容量足够存放新加入的元素，若不够，要扩容

    private void ensureExplicitCapacity(int minCapacity) {
    //实际修改集合次数++ (在扩容的过程中没用,主要是用于迭代器中)
        modCount++;

        // overflow-conscious code
         //判断最小容量    - 数组长度是否大于    0 
        if (minCapacity - elementData.length > 0)
           //扩容
            grow(minCapacity);
    }
1
2
3
4
5
6
7
8
9
10

扩容

    private void grow(int minCapacity) {
        // overflow-conscious code
        //先获取数组的长度
        int oldCapacity = elementData.length;
        //在原有长度的基础上扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //判断新容量-最小容量是否小于0, 如果是第一次调用add方法必然小于
        if (newCapacity - minCapacity < 0)
            //还是将最小容量赋值给新容量
            newCapacity = minCapacity;
           //判断新容量-最大数组大小是否>0,如果条件满足就计算出一个超大容
        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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

获取最大值

private static int hugeCapacity(int minCapacity) {
       // 如果数组个数小于0抛出OutOfMemoryError异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();       
       // 如果最数组个数大于最大容量 就返回最大值，否则返回最大容量
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}
1
2
3
4
5
6
7
8
9

get(int index)

通过下标获取元素

案例

private List<String> list = new ArrayList<>();
 for (int i = 0; i <list.size() ; i++) {
                String s = list.get(i);
            }
1
2
3
4

源码

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

校验该下标是否超过数组长度

    private void rangeCheck(int index) {
        //如果下标超过数组长度直接报数组越界异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
1
2
3
4
5

通过下标获取元素

    E elementData(int index) {
        //通过下表从数组中获取元素
        return (E) elementData[index];
    }
1
2
3
4

remove()删除元素

public E remove(int index) {
       //指定位置检查
        rangeCheck(index);
        modCount++;       
       //保留要删除的值
        E oldValue = elementData(index);
       //要移动元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
        //通过拷贝使数组内位置为 index+1到 （size-1）的元素往前移动一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //清除末尾元素让GC回收
        elementData[--size] = null; // clear to let GC do its work
        //返回删除的值
        return oldValue;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

ArrayList动态扩容

扩容的大小是原先数组的1.5倍；
若值newCapacity比传入值minCapacity还要小，则使用传入minCapacity，若newCapacity比设定的最大容量大，则使用最大整数值；

    private void grow(int minCapacity) {
        // overflow-conscious code
        //先获取数组的长度
        int oldCapacity = elementData.length;
        //在原有长度的基础上扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //判断新容量-最小容量是否小于0, 如果是第一次调用add方法必然小于
        if (newCapacity - minCapacity < 0)
            //还是将最小容量赋值给新容量
            newCapacity = minCapacity;
           //判断新容量-最大数组大小是否>0,如果条件满足就计算出一个超大容
        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);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

为什么扩容是扩充1.5倍?

可以充分利用前面已经释放的空间 如果大于等于2 心容量刚好永远大于过去所有废弃的数组容量
1.5可以充分利用位移运算减少浮点数或者运算时间和运算次数

解决频繁扩容导致的性能低问题

ArrayList底层是数组实现的，那么每次添加数据时会不断地扩容，这样的话会占内存，性能低，所以导致时间很长。
我们可以用ArrayList的指定初始化容量的构造方法来解决性能低的问题。