胖胖的枫叶

流水要争先，争的是滔滔不绝。

0%

Java-ArrayList

发表于 更新于 分类于
本文字数： 13k 阅读时长 ≈ 12 分钟

本章是整理知识内容，为强化知识长期更新。

List 是是一个有序的集合，是Collection的实现类之一。

概述

  • list接口是Java Collection Framework的成员。
  • 列队允许添加重复的元素。
  • 列队允许null存在。
  • 列队是从0开始，也就是列队头元素的下标是0。
  • 列队支持泛型，这样可以避免ClassCastException异常。

数组与数组列表

​ Array(数组)它是在内存中划分出一块连续的地址空间进行元素的存储，由于它直接操作内存，所以性能比其他的集合要高一点点。但是数组也有一个严重的缺陷，就是需要指定初始化大小，并且在后续的操作中不能修改数组的结构，这很不友好。

​ ArrayList可以很好的进行动态扩容，它会随之元素的不断增加而调整数组大小。它的底层是基于数据实现的，所以也集成了数组的一些特性。比如查找、修改很快，但是新增和删除比较慢。

Array数组

ArrayList底层是由数组实现的，那么就回顾下Java中数组的特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Array1Test {

    @Test
    public void test1() {
        String[] arr = new String[5];
        System.out.println("数组的长度" + arr.length);
        for (int i = 0 ; i < arr.length ; i++) {
            arr[i] = String.valueOf(i);
            System.out.print(" ");
        }
        System.out.println(arr[0].toString());
        // 打印出0 , 数组的下表是从0开始的。
        arr[6] = null;
        // 强行添加一个元素到6的位置,然后取出来抛出ArrayIndexOutOfBoundsException。数组的大小是不能修改的。
    }
}

输出：

1
2
3
数组的长度5
	0
java.lang.ArrayIndexOutOfBoundsException: 6

List列表

Java的List是一个有序的集合，List是Collection接口的扩展接口。

List特性

  • Java List接口是Java Collection Framework的成员。
  • 列表允许添加重复的元素。
  • 列表允许有null元素。
  • 列表索引是从0开始，和数组一样的。
  • 列表接受泛型，尽量使用它。以免出现ClassCastException

源码分析

ArrayList中的常量以及变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 默认初始化容器的大小
private static final int DEFAULT_CAPACITY = 10;

// 空的对象数组。
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认的对象数组。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 被transient修饰不会被序列化，集合中元素个数。
transient Object[] elementData; // non-private to simplify nested class access

// 容器中元素的个数
private int size;

// 容器的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

创建ArrayList的实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
@Test
public void test3(){
    List list1 = new ArrayList();
    List list2 = new ArrayList(3);
    String[] vowels = {"a","e","i","o","u"};
    // 使用Arrays工具将数组转换成列表。
    List<String> vowelsList = Arrays.asList(vowels);
    List list3 = new ArrayList(vowelsList);
	
    System.out.println(list1.toString());
    System.out.println(list2.toString());
    System.out.println(list3.toString());
}
1
2
3
[]
[]
[a, e, i, o, u]

这分别使用了ArrayList三个构造方法。

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
// list1
public ArrayList() {
    // 参数为空的构造方法，元素是空的数组。
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 // list2
 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);
     }
 }
    
 // 对应list3
 public ArrayList(Collection<? extends E> c) {
    // 将一个Collection容器的元素都复制进来。
    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;
    }
 }

这让我想起了面试题目。

1
2
3
4
@Test
public void test4(){
    List list = new ArrayList(20);
}

题目是：生成list实例需要扩容几次。实际上是0次。因为创建的时候就指定了大小。

add方法

1
2
3
4
5
6
7
@Test
public void test4(){
    List list = new ArrayList();
    System.out.println(list.add(1));
    list.add(0,2);
    System.out.println(list.toString());
}

输出

1
2
true
[2, 1] // 是不是很神奇，下标0的位置是2，下标1位置值是1。

带着上面的疑问我们好好看看，顺便看看经常说ArrayList到底是如何扩容的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 直接添加元素
public boolean add(E e) {
    // 确保内部容量足够，不够就扩容。 size 是当前容器的数量
    ensureCapacityInternal(size + 1);  // Increments modCount!! 
    // 将元素添加到数组中
    elementData[size++] = e;
    return true;
}

// 在指定索引的位置添加元素。
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++;
}

System.arraycopy 是一个本地静态方法，使用它可以对数组之间进行复制。

1
2
3
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);
  • src:源数组；
  • srcPos:源数组要复制的起始位置；
    dest:目的数组；
    destPos:目的数组放置的起始位置；
  • length:复制的长度。

上面的操作结果就是将数组中的元素位置进行了移动，当然神奇的地方是这个方法可以自己复制自己。

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
// 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
        int oldCapacity = elementData.length;
        // 位运算 ， 新的容量大小 = 当前数组长度 右移动一位  就是 newCapacity = oldCapacity + (oldCapacity / 2) 取整。也就是经常说的扩容1.5倍。
        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:
        // 关键的时候来了，通过Arrays.copyOf复制元素并指定新的数组大小。这个方法最终还是调用了System.arraycopy方法，其它参数是由Array.copyOf预设好的。
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
// 4 抛出OutOfMemoryError异常咯。内存溢出
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

每次扩容都是通过Arrays.copyOf(elementData, newCapacity)的来实现的。

set方法

这个方法其实就是更新方法。

1
2
3
4
5
6
7
@Test
public void test5(){
    List list = new ArrayList();
    list.add(1);
    System.out.println(list.set(0,1));
    System.out.println(list.toString());
}

输出

1
2
1
[1]

看下源代码。

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;				// 返回原始的值
}

remove方法

1
2
3
4
5
6
7
8
9
10
11
12
@Test
public void test6(){
    List list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("b");
    list.add("c");
    list.add("d");
    System.out.println(list.toString());
    list.remove("b"); //根据元素匹配删除
    System.out.println(list.toString());
}

输出

1
2
[a, b, b, c, d]
[a, b, c, d] //会删除匹配到的第一个元素
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
// 根据下标删除元素。删除成功就返回被删除的元素。
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;
}

// 删除元素，如果删除成功返回true
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;
}

// 删除索引上的元素
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
}

这两个删除方法可以看出，动作都比较大。这种操作会慢很多。

get方法。

相比上面3种方法确实轻量级太多了。

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

    return elementData(index);
}

平时也就听大家说新增修改删除慢，也就访问速度比较快。看了源码之后才清晰很多。

contains方法

这也是一个重量级的方法

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
// 判断对象存在与当前集合中。
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the lowest index <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 */
public int indexOf(Object o) {
    // 当找不到该对象的时候返回-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;
}

安全删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@Test
    public void test2(){
        //  1、创建一个二维数组
        String[] vowels = {"a","e","i","o","u"};
        //  2、将二维数组转换成列表,在转换成容器
        Collection<String> collection = new ArrayList(Arrays.asList(vowels));
        // 3、获取容器迭代器实例
        Iterator<String> itr = collection.iterator();
        // 4、逻辑判断itr 中下个元素是否存在。
        while (itr.hasNext()){
            String var = itr.next(); // 获取将要访问的下一个元素。
            // 5、尝试修改其中的一个元素。
            if(var == "a"){
                // 5、删除掉 `a`
                itr.remove();
            }else{
                System.out.print(var);
            }
        }
    }

线程安全

由于所有的方法都没有进行同步。所以很直观的认为有线程安全的问题，还是亲自测试下避免迷迷糊糊的。

场景一：多线程对一个ArrayList进行操作。

假设我们需要添加10000个元素进ArrayList

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
public class ArrayListTest2 {

    /**
     * 10线程对一个ArrayList进行操作。
     *
     * @param args
     */
    public static void main(String[] args) throws InterruptedException {
        List list = new ArrayList();
        ExecutorService executorService = Executors.newFixedThreadPool(20);
        for (int sum = 0 ; sum < 10 ; sum ++){<