Java Collection 概述

Posted on | In | Visitors:

写在前面

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

思维导图

Collection 接口

Collection 总体框架

Collection 定义的方法

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

Collection 没有 get 方法来取得某个元素，只能通过 iterator 遍历元素

Iterator 接口

Iterator 接口中主要包含两个方法：hasNext() 和 next()，提供了从前往后遍历集合的方式
两个方法的作用分别为判断是否还有下一个元素以及返回下一个元素

ArrayList 类中的私有内部类 Itr

可以查看 ArrayList 类中的私有内部类 Itr 源码来进一步了解 Iterator 包含的方法的具体实现，源码如下

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
/**
 * An optimized version of AbstractList.Itr
 */
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
	    // 判断是否存在并行情况，但并未解决
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        // cursor 往后移一位，然后返回 cursor 刚才指向位置的元素，同时 lastRet 指向 cursor 刚才的位置
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

	// 可以发现无法连续执行两次以至多次 remove 方法，会抛出 IllegalStateException 异常
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

ListIterator 接口

1
public interface ListIterator<E> extends Iterator<E>

增加了从后往前遍历的方式

注意 ListIterator 中的 nextIndex() 和 previousIndex() 方法，nextIndex() 方法返回的是调用 next() 方法（返回 ListIterator 当前指向的元素）之后返回的那个元素的 index，previousIndex() （返回 ListIterator 当前指向的元素的前一个元素）返回同理

ArrayList 类中的私有内部类 ListItr

可以查看 ArrayList 类中的私有内部类 Itr 源码来进一步了解 iterator 包含的方法的具体实现，源码如下

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
// 由于继承自 Itr 类，故 ListItr 内部并没有实现 next 等方法
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }

    public boolean hasPrevious() {
        return cursor != 0;
    }
	
	// 并不是 cursor 往后一位的位置
    public int nextIndex() {
        return cursor;
    }
	
	// 确实是 cursor 往前一位的位置
    public int previousIndex() {
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
	
	// 在 ListIterator 指向的位置加入新的元素
    public void add(E e) {
        checkForComodification();
		// 加入新的元素后，ListIterator 仍然指向同一个元素
        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

Arrays 工具类

Arrays 类是一个实现对数组操作的工具类，包括了各种各样的静态方法，可以实现数组的排序和查找、数组的比较和对数组增加元素，数组的复制和将数组转换成字符串等功能。这些方法都有对所有基本类型的重载方法

asList(T… a)

源码如下

1
2
3
public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

用传入的一系列参数来构造一个 List 对象

Arrays 查找采用的方法是二分查找

copyOf

copyOf 拥有多个重载版本，但底层的实现都是采用 System.arraycopy 方法，而此方法是 native 方法

1
2
3
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

equals(Object[] a, Object[] a2)

通过对比 a 和 a2 中的对应元素来判断两个数组是否相等，Arrays 类中还有一个 deepEquals 方法，其除了判断元素是否相等，还要判断 a 和 a2 是否为同一种类型的数组

fill

将一个值填充至数组中的所有选中位置

sort

源码如下

1
2
3
4
5
6
7
8
9
10
public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

可以发现，使用 sort 方法时，既可以传入一个 null 值，也可以传入一个实现自定义排序规则的、实现了 Comparator 接口的类的一个对象。重点在 sort 的一个重载方法，查看其源码

1
2
3
4
5
6
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

这段代码和上面一段代码十分相似，如果 LegacyMergeSort.userRequested 为 true 的话就会使用归并排序（优化过的归并排序版本，针对部分有序的集合表现更好），可以通过下面代码设置为 true

1
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

若为 false 则会使用 ComparableTimSort 方法，而 ComparableTimSort 方法和 TimSort方法类似，具体解析参考 https://blog.csdn.net/yangzhongblog/article/details/8184707

同时，我们发现 Arrays.sort 存在多个重载版本，若直接传入一个数组，则采用 DualPivotQuicksort 方法（即双轴快速排序），具体可参考 http://www.cnblogs.com/nullzx/p/5880191.html

查看 DualPivotQuicksort 源码

1
2
3
4
5
6
// Use Quicksort on small arrays
// 此处 QUICKSORT_THRESHOLD 等于 286
if (right - left < QUICKSORT_THRESHOLD) {
    sort(a, left, right, true);
    return;
}

若数组的长度大于 286，则判断该数组的有序程度高低，若高则采用快速排序，若低则采用归并排序

进入此处的 sort 函数源码

1
2
// 此处 INSERTION_SORT_THRESHOLD 等于 47
if (length < INSERTION_SORT_THRESHOLD)

若数组长度小于 47，则采用插入排序，若大于 47 则采用快速排序

Collections 工具类

Collections 类内部存在许多内部私有类，粗略地阅读其源码认为其作用可能是将传入的某个集合具体实现类的对象包装成另一种类的对象，对原有对象的某些特性加以限制或简单的修改

1
2
3
4
5
6
7
8
9
// 若集合实现了随机访问，则低于此阈值的均采用随机访问，大于等于此阈值则采用迭代器访问
private static final int BINARYSEARCH_THRESHOLD   = 5000;
private static final int REVERSE_THRESHOLD        =   18;
private static final int SHUFFLE_THRESHOLD        =    5;
private static final int FILL_THRESHOLD           =   25;
private static final int ROTATE_THRESHOLD         =  100;
private static final int COPY_THRESHOLD           =   10;
private static final int REPLACEALL_THRESHOLD     =   11;
private static final int INDEXOFSUBLIST_THRESHOLD =   35;

sort

源码如下

1
2
3
public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

并没有什么新奇的东西，内部调用 List 类本身的 sort 方法，而 List 内的 sort 方法本质是通过 Arrays.sort 方法实现的

binarySearch

源码如下

1
2
3
4
5
6
7
8
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
	    // 普通的二分查找
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
    int low = 0;
    int high = l.size()-1;
    ListIterator<? extends T> i = l.listIterator();

    while (low <= high) {
        int mid = (low + high) >>> 1;
        T midVal = get(i, mid);
        int cmp = c.compare(midVal, key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}

对 list 的要求必须是按升序（升序的规则由 compareTo 方法确定）排序的，当要找的 key 在 list 中有多个元素匹配时，无法确定返回的是哪一个

当在 list 找不到匹配的元素时，返回的 index 代表了 -（插入位置 - 1），插入位置相当于 list 中刚好比 key 大的元素的位置，如果 key 比 list 中的所有元素都大，则返回 list.size()

若传入的 list 支持随机访问，则此方法的复杂度为 O(log n)，若不支持，则此方法需进行 O(n) 次迭代（仍需遍历整个 list）和 O（log n）次元素比较

从 iteratorBinarySearch 方法源码可以看出，当 key 位于 list 前半部分时，效果不一定比直接遍历好，尤其是 key 十分接近 list 头部时，唯一的优势应该就在于减少了比较的次数。从下文的测试程序也可以看到区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SortTest {
	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
		LinkedList<Integer> linkedList = new LinkedList<>(list);
		ArrayList<Integer> arrayList = new ArrayList<>(list);
		long startTime = System.nanoTime();
		Integer i = new Integer(10);
		System.out.println(linkedList.indexOf(i));
		long endTime = System.nanoTime();
		System.out.println(endTime - startTime);
		
		startTime = System.nanoTime();
		System.out.println(Collections.binarySearch(linkedList, i));
		endTime = System.nanoTime();
		System.out.println(endTime - startTime);
		
		startTime = System.nanoTime();
		System.out.println(Collections.binarySearch(arrayList, i));
		endTime = System.nanoTime();
		System.out.println(endTime - startTime);
	}
}

输出结果为

1
2
3
4
5
6
0
142436
0
198577
0
16040

当 key 位于后半部分时，发现依旧是 iteratorBinarySearch 方法最慢，具体原因暂不明，猜测可能和 iteratorBinarySearch 方法中调用关系更复杂有关

list(Enumeration< T > e) : ArrayList< T >

将一个枚举类中的所有元素依次存入一个新的 ArrayList 中，刚好与 Vector 中的 element 方法相反

reverse(List<?> list)

将传入的 List 对象逆序排列，通过一个头指针和一个尾指针将 List 对象中的元素进行交换，然后头指针往后移，尾指针往前移。当两个指针碰面时，整个 List 即逆序完成

rotate

源码如下

1
2
3
4
5
6
public static void rotate(List<?> list, int distance) {
    if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
        rotate1(list, distance);
    else
        rotate2(list, distance);
}

应用此方法后，原先在 i 位置的元素将放在 (i - distance) % list.size() 上。同时，此方法可以用于 list 的 subList 上，效果是原 list 上不在 subList 中的元素顺序保持原样，而 subList 进行旋转

rotate1 方法的源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static <T> void rotate1(List<T> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    distance = distance % size;
    if (distance < 0)
        distance += size;
    if (distance == 0)
        return;
	// 将 i 位置上的元素依次往后移 distance 个位置，最后一个元素移至相对应的第一个元素之前的位置
    for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
        T displaced = list.get(cycleStart);
        int i = cycleStart;
        do {
            i += distance;
            if (i >= size)
                i -= size;
            displaced = list.set(i, displaced);
            nMoved ++;
        } while (i != cycleStart);
    }
}

for 循环一次的效果如图所示，针对本例子 for 循环执行两次即可完成 rotate 操作

rotate2 方法的源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static void rotate2(List<?> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    int mid =  -distance % size;
    if (mid < 0)
        mid += size;
    if (mid == 0)
        return;

    reverse(list.subList(0, mid));
    reverse(list.subList(mid, size));
    reverse(list);
}

rotate2 方法设计的很巧妙，先将 list 前一部分和后一部分元素分别逆序，然后将整个 list 逆序即可完成 rotate 操作

shuffle

shuffle 方法用于将 list 内的元素随机排列，底层实现是从后往前遍历整个 list，将 i 位置上的元素与 i 位置及其之前位置的随机一个元素进行交换。对于不支持随机访问的 list，通过 list.toArray 方法转换为数组，然后对数组进行随机排列，再通过一一映射回原 list 即可

补充

Collections 还有一些其他比较实用的方法，如 copy、max、min、replaceAll 、swap 等方法，由于源码比较简单，故不做介绍。

需要注意的是，使用 swap 交换数组的两个元素时需要一个临时变量来存储其中的一个元素的值，但交换 List 元素时不一定需要，因为 List 类的 set 方法会返回旧值

List 接口

具体参考 Java List 解析

Set 接口

具体参考 Java Set 解析