Collection (一)：List 解析

Posted on | In | Visitors:

写在前面

  • 由于个人水平有限，故部分内容可能会出现错误，还请包涵

List 接口

1
public interface List<E> extends Collection<E>

List 是一个元素有序的、可以重复、可以为 null 的集合
List 中有具体实现的方法如下文

replaceAll (UnaryOperator operator)

具体实现

源码如下

1
2
3
4
5
6
7
default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        li.set(operator.apply(li.next()));
    }
}

作用是按照一个自定义的规则将 List 中的所有元素进行替换

具体使用

1
2
3
4
5
6
public class MyUnarary implements UnaryOperator<Integer> {
	@Override
	public Integer apply(Integer t) {
		return t*2 + 1;
	}
}
1
2
3
List<Integer> list = Arrays.asList(1, 3, 2, 4, 6, 5);
list.sort(new MyUnarary());
System.out.println(list);

输出结果为：[13, 11, 9, 7, 5, 3]

sort(Comparator<? super E> c)

源码如下

1
2
3
4
5
6
7
8
9
10
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

底层调用了 Array.sort 方法

具体使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class MyComparator implements Comparator<Integer>{

	@Override
	public int compare(Integer o1, Integer o2) {
		// TODO Auto-generated method stub
		if (o1 > o2)
			return -1;
		else if (o1 == o2)
			return 0;
		else {
			return 1;
		}
	}

}
1
2
3
4
5
List<Integer> list = Arrays.asList(1, 3, 2, 4, 6, 5);
list.sort(null);
System.out.println(list);
list.sort(new MyComparator());
System.out.println(list);

输出结果为

1
2
[1, 2, 3, 4, 5, 6]
[6, 5, 4, 3, 2, 1]

List.subList(int fromIndex, int toIndex)

此方法返回 List 在 fromIndex 与 toIndex 范围内的子集，注意是左闭右开

subList 返回的仍是 List 原来的引用，只不过把开始位置 offset 和 size 改了下，即对 subList 的操作会影响到原有的 List。List.subList() 在 AbstractList 抽象类中实现的源码如下 ：

1
2
3
4
5
6
7
8
9
10
11
12
public List<E> subList(int start, int end) {
    if (start >= 0 && end <= size()) {
        if (start <= end) {
            if (this instanceof RandomAccess) {
                return new SubAbstractListRandomAccess<E>(this, start, end);
            }
            return new SubAbstractList<E>(this, start, end);
        }
        throw new IllegalArgumentException();
    }
    throw new IndexOutOfBoundsException();
}

ArrayList 类

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

ArrayList 底层的数据结构仍然是数组

1
2
// 存放元素的数组
transient Object[] elementData;

ArrayList 默认的初始容量为 10

构造函数

ArrayList 重载了 3 个构造函数，分别是无参、传入一个 int 型数以及传入一个 Collection<? extends E> c
源码如下

1
2
3
4
// 使用默认的空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
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(E e)

源码如下

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

ensureCapacityInternal 方法的作用是确保数组的容量足够，源码如下

1
2
3
4
5
6
7
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

从源码中可以看到，若元素组是空数组，则调用 add 方法时，原数组的容量将一般增至 DEFAULT_CAPACITY，即为 10。因为传入的 minCapacity 一般等于 1。接着调用 ensureExplictCapacity 方法，源码如下

1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

重点在于 grow 方法，源码如下

1
2
3
4
5
6
7
8
9
10
11
12
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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:
    // 此处使用的是 Array.copyOf，但底层仍然是 System.arraycopy
    elementData = Arrays.copyOf(elementData, newCapacity);
}

grow 方法的主要作用就是将数组扩容，扩容后数组的容量为之前的 1.5 倍

add(int index, E element)

add 方法还有一个重载版本，用于在指定位置插入一个元素，源码如下

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

addAll(int index, Collection<? extends E> c)

源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean addAll(int index, Collection<? extends E> c) {
	// 检测 index 是否合法
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    // 若 index 等于 size，即在数组尾插入元素，直接将 c 中的所有元素复制至原数组尾部
    // 若 index 不等于 size，则先将原数组 index 之后的元素均往后挪 c.size() 个位置，然后再将 c 复制至原数组中
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

addAll(Collection<? extends E> c)

源码如下

1
2
3
4
5
6
7
8
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

或许可以内部调用 addAll(int index, Collection<? extends E> c)

clone()

源码如下

1
2
3
4
5
6
7
8
9
10
11
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

注意：clone 方法是浅拷贝（List 内部的元素本身并没有复制）

indexOf(Object o)

源码如下

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

此方法在 AbstractList 中有具体实现，实现的方式是采用迭代器进行遍历

forEach(Consumer<? super E> action)

源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

考虑到了并行情况，但是没有解决方案

remove(Object o)

源码如下

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

其中调用了 fastRemove 方法，阅读源码可发现其比 remove(int index) 方法减少了边界检查以及返回值的功能

removeAll(Collection<?> c)

源码如下

1
2
3
4
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

其中调用了 batchRemove 方法，源码如下

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
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    // r、w 相当于两个指针
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
	        // 若 c 中包含 elementData[r]，则跳过此元素
	        // 若不包含，则复制至 w 位置
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // 若在 try 代码块中抛出异常，也能将 r 位置之后的元素正确保存在新的位置
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        // 将 w 为之后的元素均置为空，这些元素均不再有作用
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

removeIf(Predicate<? super E> filter)

源码如下

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
@Override
// 同样考虑并行情况，但并未解决
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    // 先记录下满足条件的、要被移除的元素的位置
    int removeCount = 0;
    final BitSet removeSet = new BitSet(size);
    final int expectedModCount = modCount;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }

    // shift surviving elements left over the spaces left by removed elements
    // 将原数组中的元素往左移至新位置
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            i = removeSet.nextClearBit(i);
            elementData[j] = elementData[i];
        }
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let gc do its work
        }
        this.size = newSize;
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}

retainAll(Collection<?> c)

源码如下

1
2
3
4
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

同样调用 了 batchRemove 方法，相当于 replaceAll(Collection<?> c) 的一个互补操作

trimToSize()

源码如下

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

作用是将 elementData 减容至 size

LinkedList

1
2
3
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

底层的数据结构是双向链表，由内部私有类 Node 实现，可以被当作堆栈、队列及双端队列进行操作

add(int index, E element)

使用 add 方法可以实现在指定的位置插入一个新的节点，基本流程是先在原有链表中找到指定位置的节点，然后在该节点前面插入一个新节点。如何寻找指定位置的节点源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

通过与 size 的一半进行比较，若小于则代表在链表前半部分，即从头节点开始找；若大于则从尾节点开始找

LinkedList 可以当作 stack 使用，而 stack 中的 pop 和 push 方法的实现都是在 LinkedList 的头节点进行增删

LinkedList 具有的特性有：

  • 分配内存空间不一定是连续的
  • 插入、删除操作很快
  • 访问其中的某个元素比较慢，可能是从头往尾找，也可能是从尾往头找

Vector

Vector 本身和 ArrayList 差别并不大，底层的数据结构均是数组，不过还是有稍许区别：

  • Vector 可以指定每次的扩容长度，即 capacityIncrement。此外，Vector 扩容后容量是原来的两倍
  • Vector 是线程安全的，其部分方法使用了 synchronized 进行修饰，但其效率比不上 ArrayList

Vector 内部有一个 elements 方法，可以将数组内的所有元素转化为一个枚举类对象返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;

        public boolean hasMoreElements() {
            return count < elementCount;
        }

        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}