Java容器框架源码阅读笔记（一）List

| |

java.uti.List框架：
List

ArrayList

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

介绍

  1. 继承自AbstractList。实现了List。实现了RandomAccess标记接口表示可以随机访问。实现了Cloneable标记接口但是是浅拷贝。实现了Seriable可以进行序列化。
  2. ArrayList是一个基于数组实现的可变数组，数组长度取决于使用的构造函数和传的初始参数，在添加元素过程中可以动态以1.5倍扩容。数组中的元素是有序的，元素可以是null。因此随机访问元素的时间复杂度为O(1)，但是插入和删除元素的时间复杂度为O(n)刚好和LinkedList相反(用链表实现的)。
  3. 非线程安全，如果需要线程安全需要使用Vector、Collections.synchronizedList(new ArrayList())、CopyOnWriteArrayList
  4. 数组初始容量(DEFAULT_CAPACITY)是10

部分源码分析

ArrayList(int initialCapacity)

如果设置的初始容量为0，数组指向长度为0的数组。

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()

如果没有指定数组长度，将默认指向另一个(区别于设置的初始长度为0)长度为0的数组。
这里和上面形参为0指向的长度为0的数组不一样，目的是可以以此为标识，在首次添加元素时，执行不同的的扩容操作。无参构造函数在首次添加元素时，数组会扩容成10(0 -> 10 -> 20)，而形参为0的构造函数在首次添加元素时，只会在0的基础上1.5倍扩容（0 -> 1 -> 2 -> 3 -> 4 -> 6）。至于这么做的原因，暂时没想到性能上会带来哪些提升，唯一能想到的就是为了统一？？为了区分不同的构造函数？？TODO。。。 下面是Java Doc：

Shared empty array instance used for default sized empty instances. We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.

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

ArrayList(Collection<? extends E> c)

主要是第二个if，其他两个构造函数逻辑比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 将容器c中的元素构造成一个ArrayList，主要看第二个if
 * */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        // 防止继承ArrayList的子类重写toArray返回数组元素类型不是Object，比如是String,当add(1)时候就会抛StoreException异常。
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

add(E e)

添加元素，主要涉及了一些扩容的逻辑

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
70
71
72
/**
 * 添加元素：先判断数组容量，然后在添加
 * */
public boolean add(E e) {
    // 先判断数组是否已满或者说判断数组是否还有空间
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 添加元素
    elementData[size++] = e;
    return true;
}
/**
 * 确保数组容量够
 * */
private void ensureCapacityInternal(int minCapacity) {
    // 先判断是否是初次添加元素
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 判断是否需要扩容
    ensureExplicitCapacity(minCapacity);
}

/**
 * 判断是否需要扩容
 * */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    // 如果需要的容量大于当前数组的容量 => 1.5倍扩容
    if (minCapacity - elementData.length > 0)
    	// 扩容
        grow(minCapacity);
}

/**
 * 将elementData指向一个新的数组
 * */
private void grow(int minCapacity) {
    // 获取旧数组长度
    int oldCapacity = elementData.length;
    // 扩大1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩容以后还比需要的容量小，则将需要的容量赋值给新容量
    /* 比如使用的是第三个构造函数，传入的c的size为1。
       此时elementData.length = 1;如果调用add，此时传入的minCapacity = size + 1 = 2;
       但是newCapacity = 1 + 1 /2 = 1 < minCapacity，所以有的这个if

       在或者 使用形参为0的构造函数
    */
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果扩容以后大于数组设置的最大容量，如果当前需要的容量小于数组最大容量，就扩展到数组的最大容量，否则就设置为Integer.MAX_VALUE
    // 设置 最大容量的一个目的是：有些虚拟机会在数组中保留一些头部信息，所以可能会造成内存溢出，所以不到万不得已，尽量不超过MAX_ARRAY_SIZE，下面是Java Doc
    // Some VMs reserve some header words in an array. Attempts to allocate larger arrays may result in OutOfMemoryError: Requested array size exceeds VM limit
    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);
}

/**
 * 如果minCapacity小于MAX_ARRAY_SIZE就不需要扩容那么大，直接返回MAX_ARRAY_SIZE
 * */
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, E element)

在指定下标添加元素，主要是理解这个函数的使用System.arraycopy(elementData, index, elementData, index + 1, size - index)下同↓

1
2
3
4
5
6
7
8
9
10
11
12
public void add(int index, E element) {
    // 检查下标
    rangeCheckForAdd(index);
    // 判断数组容量是否可以在继续放元素，来决定是否进行扩容。
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 从原数组index开始拷贝到从目的数组的index + 1开始的元素。 挨个往后拱 
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 此时index下标的元素已经放到index + 1，将index元素重新赋值即可。
    elementData[index] = element;
    // 增加数量
    size++;
}

remove(int index)

删除指定位置元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public E remove(int index) {
 	// 下标检查，防止越界
    rangeCheck(index);
    // 修改次数
    modCount++;
    // 获取当前下标对应元素
    E oldValue = elementData(index);
    // 如果删除的是最后一个元素，直接删除，不用移动数组其它元素。
    int numMoved = size - index - 1;
    // 如果删除的不是最后一个元素，需要进行移动。
    if (numMoved > 0)
        // 就是将原数组的index + 1 拷贝到原数组的index开始以后的元素。 参数特点是原数组和目的数组一样。
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 方便GC及时回收
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

trimToSize()

扩容的反义词：缩容。重新创建一个数组，长度为ArryList中的size。目的是为了防止进行多次remove操作以后，数组长度特别大，但是仅有几个元素导致空间浪费。可以调用此方法重新修剪数组长度。

1
2
3
4
5
6
7
8
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

boolean contains(Object o)

是否包含指定元素o

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

int indexOf(Object o)

找到指定元素o第一次出现的下标

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

int lastIndexOf(Object o)

找到指定元素o最后出现的下标

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

LinkedList

介绍

  1. 继承自AbstractSequentialList抽象类(只是非常简单地实现了List相关方法)
  2. 实现了List接口、Deque接口(继承自Queue接口，说明LinkedList间接实现了Queue接口)、有关于栈Stack的操作(push、pop)。可以当作一个双向链表、双端队列、FIFO队列、栈。并且可以添加null，这点区别于ArrayDeque。
  3. 非线程安全,如果需要线程安全需要用到List list = Collections.synchronizedList(new LinkedList(...));

部分源码分析(翻译:))

public LinkedList(Collection<? extends E> c)

接收一个Collection类型的变量构造一个LinkedList

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
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查索引范围
    checkPositionIndex(index);
    // 将参数c转化成数组
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    // 定义两个指针变量
    Node<E> pred, succ;
    // 链表还没有元素，此时index == 0 && size == 0;
    if (index == size) {
        succ = null;
        pred = last;
    // 链表已经有元素，在原有基础上又要添加元素
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

public void clear()

清除链表中的元素，额外置空操作的意思是将节点之间的链接都断开，虽然不是必须的，但是有助于分代GC 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

其它

实现了队列(Queue)/双端队列(Deque)接口

  • 队列接口主要方法
    • peek();element()获取队头元素，如果队列为空，则返回null/则抛异常
    • offer(E e)队尾入队列
  • 双端队列接口主要方法
    • offerFirst(E e);offerLast(E e)从队头/对尾入队列
    • peekFirst();peekLast()获取队头/队尾元素
    • pollFirst();pollLast()获取并移除队头/队尾元素

包含了栈(Stack)操作

  • push(E e) 入栈
  • pop() 出栈

JavaDoc建议用ArrayQueue作为队列或者栈的接口实现,因为它有着比LinkedList更好的性能。 不再建议使用Stack stack = new Stack();

Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage. They are not thread-safe; in the absence of external synchronization, they do not support concurrent access by multiple threads. Null elements are prohibited. This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

总结

LinkedList适合用来做链表/双向链表、双端队列的实现。当用到FIFO队列或者栈时，建议使用ArrayDeque作为实现。比如：
Deque<Integer> stack = new ArrayDeque<Integer>();
Queue<Integer> queue = new ArrayDeque<Integer>();

Q&A

ArrayList和LinkedList本质区别就是数组和链表的区别

ArrayList是如何扩容的？

  • 当添加元素之前需要判断当前数组的容量和需要的容量的差异，当需要的容量大于数组的当前容量，就会重新申请1.5倍旧数组大小的新数组，然后将旧数组元素拷贝到新数组。注意的是扩容过程中可能会由于需要的空间大小超出最大值(Integer.MAX_VALUE)而出现OOM。

ArrayList和LinkedList的区别？

  • ArrayList用数组实现，数组占据了一段连续的内存空间，支持通过首地址+偏移量进行时间复杂度为O(1)的随机访问。但是随机插入/删除元素的时间复杂度为O(n)。
  • LinkedList用链表实现，链表中的每个节点在物理内存中并不相邻，所以不支持随机访问。随机插入/删除元素的时间复杂度为O(1)。

这里要区分一下随机访问和顺序访问，维基百科定义：

  • 随机访问/存取(Random access)
    In computer science, random access (more precisely and more generally called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any other, no matter how many elements may be in the set.

总结就是，访问任意一个元素所用的时间 time(注意是时间，不是时间复杂度)，都是一样的。

  • 顺序访问(Sequential access)
    In computer science, sequential access means that a group of elements (such as data in a memory array or a disk file or on magnetic tape data storage) is accessed in a predetermined, ordered sequence.

总结就是，如果要访问一个元素，就需要从前向后依次访问过去，直到目标元素，明显，访问任意一个元素所用时间是不一样的。

fail-fast机制？

当使用List的迭代器Iterator的进行操作时，如果List的结构被其它线程修改了(比如添加/删除了一个元素),当前线程在迭代过程中会抛出ConcurrentModificationException。 在生成迭代器的时候会拷贝一份modcount变量到expectedModCount(modcount变量用来记录List被修改的次数)，每次迭代时会判断expectedModCount是否等于modcount变量，如果不相等就说明其它线程对List做了修改,此时会抛出异常而不是继续冒险以一种不确定的行为执行下去。

if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

fail-fast机制是用来检测BUG的，不能依赖这个异常来保证程序的正确性。抛出这个异常说明代码写的有问题。

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

参考

Related Posts