集合类

类似数学中的集合概念，集合类表示一组对象，每个对象都可以称为元素，不同的集合性质不同，比如一些允许元素重复一些不允许，一些有序其他无序。

集合类其实就是为了更好地组织、管理和操作数据而存在的，包括列表、集合、队列、映射等。

集合根接口

Java已经把常用的集合类型都实现好了，只需要用就可以了。所有的集合类最终都是实现自集合跟接口的，比如ArrayList类就是实现Collection接口的：

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public interface Collection<E> extends Iterable<E> {
    //-------这些是查询相关的操作----------

   	//获取当前集合中的元素数量
    int size();

    //查看当前集合是否为空
    boolean isEmpty();

    //查询当前集合中是否包含某个元素
    boolean contains(Object o);

    //返回当前集合的迭代器，我们会在后面介绍
    Iterator<E> iterator();

    //将集合转换为数组的形式
    Object[] toArray();

    //支持泛型的数组转换，同上
    <T> T[] toArray(T[] a);

    //-------这些是修改相关的操作----------

    //向集合中添加元素，不同的集合类具体实现可能会对插入的元素有要求，
  	//这个操作并不是一定会添加成功，所以添加成功返回true，否则返回false
    boolean add(E e);

    //从集合中移除某个元素，同样的，移除成功返回true，否则false
    boolean remove(Object o);


    //-------这些是批量执行的操作----------

    //查询当前集合是否包含给定集合中所有的元素
  	//从数学角度来说，就是看给定集合是不是当前集合的子集
    boolean containsAll(Collection<?> c);

    //添加给定集合中所有的元素
  	//从数学角度来说，就是将当前集合变成当前集合与给定集合的并集
  	//添加成功返回true，否则返回false
    boolean addAll(Collection<? extends E> c);

    //移除给定集合中出现的所有元素，如果某个元素在当前集合中不存在，那么忽略这个元素
  	//从数学角度来说，就是求当前集合与给定集合的差集
  	//移除成功返回true，否则false
    boolean removeAll(Collection<?> c);

    //Java8新增方法，根据给定的Predicate条件进行元素移除操作
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();   //这里用到了迭代器，我们会在后面进行介绍
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }

    //只保留当前集合中在给定集合中出现的元素，其他元素一律移除
  	//从数学角度来说，就是求当前集合与给定集合的交集
  	//移除成功返回true，否则false
    boolean retainAll(Collection<?> c);

    //清空整个集合，删除所有元素
    void clear();


    //-------这些是比较以及哈希计算相关的操作----------

    //判断两个集合是否相等
    boolean equals(Object o);

    //计算当前整个集合对象的哈希值
    int hashCode();

    //与迭代器作用相同，但是是并行执行的，我们会在下一章多线程部分中进行介绍
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }

    //生成当前集合的流，我们会在后面进行讲解
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }

    //生成当前集合的并行流，我们会在下一章多线程部分中进行介绍
    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

在这个接口中，与操作集合类相关的功能都定义的比较完备，那么来看实现类。

List列表

List列表即线性表。线性表支持随机访问，相比之前的Collection接口功能更完善。

List是集合类型的一个分支，主要特性有：

  • 是一个有序的集合，插入元素默认插入尾部，按顺序从前往后存放，每个元素都有自己的特定的下标位置。
  • 列表中允许有重复元素。

在List接口中，定义了列表类型需要支持的全部操作，List直接继承自前面介绍的Collection接口，其中很多方法在List接口中被重新定义了一次，为了更加明确方法的具体功能。

List接口的定义：

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
public interface List<E> extends Collection<E> {
    ...
   	
    //将给定集合中所有元素插入到当前结合的给定位置上（后面的元素就被挤到后面去了，跟我们之前顺序表的插入是一样的）
    boolean addAll(int index, Collection<? extends E> c);

    ...

   	//Java 8新增方法，可以对列表中每个元素都进行处理，并将元素替换为处理之后的结果
    default void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final ListIterator<E> li = this.listIterator();  //这里同样用到了迭代器
        while (li.hasNext()) {
            li.set(operator.apply(li.next()));
        }
    }

    //对当前集合按照给定的规则进行排序操作，这里同样只需要一个Comparator就行了
    @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);
        }
    }

    ...

    //-------- 这些是List中独特的位置直接访问操作 --------

   	//获取对应下标位置上的元素
    E get(int index);

    //直接将对应位置上的元素替换为给定元素
    E set(int index, E element);

    //在指定位置上插入元素，就跟我们之前的顺序表插入是一样的
    void add(int index, E element);

    //移除指定位置上的元素
    E remove(int index);


    //------- 这些是List中独特的搜索操作 -------

    //查询某个元素在当前列表中的第一次出现的下标位置
    int indexOf(Object o);

    //查询某个元素在当前列表中的最后一次出现的下标位置
    int lastIndexOf(Object o);


    //------- 这些是List的专用迭代器 -------

    //迭代器我们会在下一个部分讲解
    ListIterator<E> listIterator();

    //迭代器我们会在下一个部分讲解
    ListIterator<E> listIterator(int index);

    //------- 这些是List的特殊转换 -------

    //返回当前集合在指定范围内的子集
    List<E> subList(int fromIndex, int toIndex);

    ...
}

在List接口中扩展了大量列表支持的操作，比如直接根据下标位置进行的CRUD操作。

ArrayList顺序表

当我们使用数组作为底层来实现这个List接口，我们就得到了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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
		
    //默认的数组容量
    private static final int DEFAULT_CAPACITY = 10;

    ...

    //存放数据的底层数组，这里的transient关键字我们会在后面I/O中介绍用途
    transient Object[] elementData;

    //记录当前数组元素数的
    private int size;

   	//这是ArrayList的其中一个构造方法
    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);
        }
    }
  
  	...
      
   	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 这里会判断容量是否充足，不充足需要扩容
        elementData[size++] = e;
        return true;
    }
  	
  	...
    
    //默认的列表最大长度为Integer.MAX_VALUE - 8
    //JVM都C++实现中，在数组的对象头中有一个_length字段，用于记录数组的长
    //度，所以这个8就是存了数组_length字段（这个只做了解就行）
		private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  	
  	private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);   //扩容规则跟我们之前的是一样的，也是1.5倍
        if (newCapacity - minCapacity < 0)    //要是扩容之后的大小还没最小的大小大，那么直接扩容到最小的大小
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)   //要是扩容之后比最大的大小还大，需要进行大小限制
            newCapacity = hugeCapacity(minCapacity);  //调整为限制的大小
        elementData = Arrays.copyOf(elementData, newCapacity);   //使用copyOf快速将内容拷贝到扩容后的新数组中并设定为新的elementData底层数组
    }
}

一般地，我们要使用一个集合类，会使用接口的引用，而不是直接使用具体实现类的引用：

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("darling");
        list.add("in");

        System.out.println(list);
    }
}

这是Java的面向对象编程中的多态的一种应用，在这里List是一个接口，而ArrayList是List接口的一种实现类。通过使用List接口的引用，我们可以灵活地切换到其他实现了List接口的类比如LinkedList等，只需要简单修改实例化的部分List<String> list = new ArrayList<>();。此外，使用接口类型的引用还有一个好处，因为我们只关心集合类应该提供哪些由接口定义功能而不是如何实现的。

在使用Integer时要注意传参问题：

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(10);
        list.remove((Integer) 10);

        System.out.println(list);
    }
}

在这种情况下使用list.remove的时候，我们要删除刚刚添加的10这个值，就必须注明要删除的是Integer类的10，否则list.remove会默认删除下标为10的元素。在这里如果不加就会出现警告：

如果我们这样写：

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(new Integer(10));    //会提示不必要的装箱，为了对比这样写
        list.remove(new Integer(10));

        System.out.println(list);
    }
}

输出

1
[]

发现会删除成功。因为集合类在删除元素时，只会调用equals方法进行判断是否为指定元素而不是进行等号判断，所以需要注意，如果两个对象使用equals方法相等，那么集合中就是相等的两个对象。这个功能在ArrayList源码中是这样定义的：

1
2
3
4
5
6
7
8
9
10
11
12
public boolean remove(Object o) {
    if (o == null) {
        ...
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {   //只是对两个对象进行equals判断
                fastRemove(index);
                return true;  //只要判断成功，直接认为就是要删除的对象，删除就完事
            }
    }
    return false;
}

列表中允许存在相同元素，所以我们可以添加两个一样的元素：

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("darling");
        list.add("darling");

        System.out.println(list);
    }
}
1
[darling, darling]

那如果我们要删除呢，是一起删除还是只删一个呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("darling");
        list.add("x");
        list.add("darling");

        String str = "darling";
        list.remove(str);

        System.out.println(list);
    }
}

输出

1
[x, darling]

可以发现在这种情况下，只会删除排在前面的第一个元素。

集合类支持嵌套使用，一个集合中可以存放多个集合：

1
2
3
4
5
6
7
8
9
10
11
import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<List<String>> list = new LinkedList<>();
        list.add(new LinkedList<>());

        System.out.println(list.get(0).isEmpty());
    }
}

在Arrays工具类中，可以快速生成一个只读的List：

1
2
3
4
5
6
public class Main {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("A", "B", "C");
        System.out.println(list);
    }
}

使用Arrays.List生成的List是只读的，不能进行修改操作，只能使用获取内容相关的方法，否则会抛出UnsupportedOperationException异常：

1
2
3
4
5
6
7
public class Main {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("A", "B", "C");

        list.add("D");
    }
}

报错：

如果要生成可以正常使用的，可以将这个只读的列表作为参数传入：

1
2
3
4
5
6
7
public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
        list.add("D");
        System.out.println(list);
    }
}

输出

1
[A, B, C, D]

也可以使用静态代码块：

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    List<String> list = new ArrayList<String>() {{   //使用匿名内部类
            add("A");
            add("B");
            add("C");
    }};
    System.out.println(list);
}

LinkedList链表

另一个List列表的实现类是LinkedList链表，只不过相比于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
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    //引用首结点
    transient Node<E> first;

    //引用尾结点
    transient Node<E> last;

    //构造方法，很简单，直接创建就行了
    public LinkedList() {
    }
  
  	...
      
    private static class Node<E> {   //内部使用的结点类
        E item;
        Node<E> next;   //不仅保存指向下一个结点的引用，还保存指向上一个结点的引用
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
  
    ...
}

LinkedList的使用和ArrayList使用几乎相同，只不过LinkedList不仅可以当作List来使用，也可以作为双端队列使用，对于二者的选择需要根据具体场景的需求。

迭代器

集合类都支持使用foreach语法：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("A", "B", "C");
        for (String str : list) {
            System.out.println(str);
        }
    }
}

输出：

1
2
3
A
B
C

编译之后可以发现使用了一个名为Iterator的迭代器：

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");
    Iterator var2 = list.iterator();   //使用List的迭代器在进行遍历操作

    while(var2.hasNext()) {
        String s = (String)var2.next();
        System.out.println(s);
    }

}

那么迭代器是什么呢：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("A", "B", "C");
        Iterator<String> iterator = list.iterator();
        //通过调用iterator方法快速获取当前集合的迭代器
  	    //Iterator迭代器本身也是一个接口，由具体的集合实现类来根据情况实现
    }
}

通过使用迭代器，就可以实现对集合中元素的遍历。

运行机制

迭代器的机制大致如下， 一个迭代器首先有一个默认指向集合中第一个元素的指针：


每一次next操作，都会将指针后移一位，直到完成每个元素的遍历，此时再调用next就不会再得到下一个元素。因为集合类的实现方案有很多，可能是链式存储，也有可能是数组存储，不同的实现有着不同的遍历方式，而迭代器则可以将多种多样不同的集合类遍历方式进行统一，只需要各个集合类根据自己的情况进行对应实现就行了。

接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public interface Iterator<E> {
    //查看是否还有下一个元素
    boolean hasNext();

    //遍历当前元素，并将下一个元素作为待遍历元素
    E next();

    //移除上一个被遍历的元素（某些集合不支持这种操作）
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    //对剩下的元素进行自定义遍历操作
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

在ArrayList和LinkedList中，迭代器的实现也不同。

比如ArrayList就是直接按下标访问：

1
2
3
4
5
public E next() {
    ...
    cursor = i + 1;   //移动指针
    return (E) elementData[lastRet = i];  //直接返回指针所指元素
}

而LinkedList就是不断向后寻找结点：

1
2
3
4
5
6
public E next() {
    ...
    next = next.next;   //向后继续寻找结点
    nextIndex++;
    return lastReturned.item;  //返回结点内部存放的元素
}

虽然这两种列表的实现不同，遍历方式也不同，但是都是按照迭代器的标准进行了实现。所以想要遍历集合中所有元素就可以直接使用迭代器完成而不需要关心集合类是如何实现的：

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("A", "B", "C");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {                //循环的判断条件是迭代器还有后继
            System.out.println(iterator.next());    //如果有就继续获取下个元素
        }
    }
}

需要注意的是，迭代器的使用是一次性的，如果需要再次进行遍历操作，就需要重新生成一个迭代器对象。

为了简便，我们可以使用foreach语法来快速遍历集合类，效果是相同的：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("A", "B", "C");
        for (String str : list) {
            System.out.println(str);
        }
    }
}

Java8提供了一个支持lambda表达式的forEach方法，这个方法接受一个Consumer也就是对每个遍历的元素进行的操作：

1
2
3
4
public static void main(String[] args) {
    List<String> list = Arrays.asList("A", "B", "C");
    list.forEach(System.out::println);
}

效果也是完全相同的，因为forEach方法内部本质上也是迭代器在处理，这个方法是在Iterable接口中定义的：

1
2
3
4
5
6
default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {   //foreach语法遍历每一个元素
        action.accept(t);   //调用Consumer的accept来对每一个元素进行消费
    }
}

Iterable接口

Iterable接口实际上是集合类Collection的父接口，也就是最顶层的接口，定义了迭代器生成相关的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//集合接口的父接口
public interface Iterable<T> {
    //生成当前集合的迭代器，在Collection接口中重复定义了一次
    Iterator<T> iterator();

    //Java8新增方法，因为是在顶层接口中定义的，因此所有的集合类都有这个方法
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

得益于Iterable提供的迭代器生成方法，实际上只要是实现了迭代器接口的类（包括自定义的）都可以使用foreach语法：

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
package org.example;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Test test = new Test();
        for (String str : test) {
            System.out.println(str);
        }
    }
}

class Test implements Iterable<String> {
    @Override
    public Iterator<String> iterator() {
        return new Iterator<String>() {
            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public String next() {
                return "TEST";
            }
        };
    }
}

我们自己编写了一个类，实现了Iterable接口，生成了一个Iterator对象，直接返回true实际上是一个无限循环，每次访问都返回一个字符串TEST。虽然这个Test是我们自己定义的类，并不是集合类。

ListIterator

ListIterator是针对List的强化版本，增加了更方便的操作，因为List是有序集合，所以ListInterator支持两种方向的遍历操作，不仅能从前向后，也能从后向前：

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
public interface ListIterator<E> extends Iterator<E> {
    //原本就有的
    boolean hasNext();

    //原本就有的
    E next();

    //查看前面是否有已经遍历的元素
    boolean hasPrevious();

    //跟next相反，这里是倒着往回遍历
    E previous();

    //返回下一个待遍历元素的下标
    int nextIndex();

    //返回上一个已遍历元素的下标
    int previousIndex();

    //原本就有的
    void remove();

    //将上一个已遍历元素修改为新的元素
    void set(E e);

    //在遍历过程中，插入新的元素到当前待遍历元素之前
    void 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
public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));

        //设置元素
        ListIterator<String> iterator = list.listIterator();
        iterator.next();
        iterator.set("X");
        System.out.println(list);

        //正向遍历
        while(iterator.hasNext()) {
            String str = iterator.next();
            System.out.println(str);
        }

        //反向遍历
        while(iterator.hasPrevious()) {
            String str = iterator.previous();
            System.out.println(str);
        }
    }
}

输出：

1
2
3
4
5
6
[X, B, C]
B
C
C
B
X

因为ListIterator至此双向遍历，所以可以反复使用。

Queue和Deque

在前面LinkedList的接口定义中：

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

还实现了一个Deque接口。Deque接口继承自Queue接口。

Queue队列

Queue队列接口扩展了队列的相关操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public interface Queue<E> extends Collection<E> {
    //队列的添加操作，是在队尾进行插入
  	//如果插入失败，会直接抛出异常
    boolean add(E e);

    //同样是添加操作，但是插入失败不会抛出异常
    boolean offer(E e);

    //移除队首元素，但是如果队列已经为空，那么会抛出异常
    E remove();

   	//移除队首元素并返回值，但是如果队列为空，会返回null
    E poll();

    //仅获取队首元素，不进行出队操作，但是如果队列已经为空，那么会抛出异常
    E element();

    //同样是仅获取队首元素，但是如果队列为空，会返回null
    E peek();
}

可以直接将一个LinkedList当作一个队列使用：

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("darling");
        queue.add("in");
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}

输出：

1
2
darling
in

Deque双端队列

普通的队列是：

而双端队列允许在队列的两端进行入队和出队操作：

利用这种特性，双端队列既可以当作普通队列使用，也可以当作栈来使用，Java中关于Deque双端队列接口的定义：

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
//在双端队列中，所有的操作都有分别对应队首和队尾的
public interface Deque<E> extends Queue<E> {

    //添加元素，失败抛出异常
    void addFirst(E e);
    void addLast(E e);

    //添加元素，失败不抛出异常
    boolean offerFirst(E e);
    boolean offerLast(E e);

    //移除元素，若已为空则抛出异常
    E removeFirst();
    E removeLast();

    //移除元素并返回值，若为空则返回null
    E pollFirst();
    E pollLast();

    //获取元素
    E getFirst();
    E getLast();

    //获取元素，若为空返回null
    E peekFirst();
    E peekLast();

    //从队列中删除第一个出现的指定元素
    boolean removeFirstOccurrence(Object o);

    //从队列中删除最后一个出现的指定元素
    boolean removeLastOccurrence(Object o);

    // *** 队列中继承下来的方法操作是一样的 ***

    ...

    // *** 栈相关操作也有定义 ***

    //将元素推向栈顶
    void push(E e);

    //将元素从栈顶出栈
    E pop();


    // *** 集合类中继承的方法 ***

    ...

    //生成反向迭代器，这个迭代器也是单向的，但是是next方法是从后往前进行遍历的
    Iterator<E> descendingIterator();
}

可以直接把双端队列当作栈来使用：

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.push("A");
        deque.push("B");
        System.out.println(deque.pop());
        System.out.println(deque.pop());
    }
}

输出：

1
2
B
A

可以发现Deque双端队列实现了先入后出的操作。

使用反向迭代器和正向迭代器：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.addLast("A");
        deque.addLast("B");
        
        Iterator<String> descendingIterator = deque.descendingIterator();
        System.out.println(descendingIterator.next());
        
        Iterator<String> iterator = deque.iterator();
        System.out.println(iterator.next());
    }
}

输出：

1
2
B
A

除了LinkedList实现队列以外，还有其他的实现类，但是并不常用，比如：

1
2
3
4
public static void main(String[] args) {
    Deque<String> deque = new ArrayDeque<>();   //数组实现的栈和队列
    Queue<String> queue = new PriorityQueue<>();  //优先级队列
}

优先级队列

优先级队列可以根据每个元素的优先级，对出队顺序进行调整，默认情况下按照自然顺序：

1
2
3
4
5
6
7
8
9
10
11
public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>();
        queue.offer(10);
        queue.offer(4);
        queue.offer(5);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}

输出

1
2
3
4
5
10

虽然我们插入的顺序是10、4、5，但是出队顺序是按照优先级进行的。

也可以自定义比较规则，需要给一个Comparator的实现：

1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);    //按照从大到小出队
        queue.offer(10);
        queue.offer(4);
        queue.offer(5);
        System.out.println(queue);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}

输出：

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

可以看到，优先级队列并不是队列中所有元素都按照优先级排列的，优先级队列只是保证出队顺序是按照优先级进行的。

Set

Set集合比较特殊，先看定义：

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
public interface Set<E> extends Collection<E> {
    // Set集合中基本都是从Collection直接继承过来的方法，只不过对这些方法有更加特殊的定义
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);

    //添加元素只有在当前Set集合中不存在此元素时才会成功，如果插入重复元素，那么会失败
    boolean add(E e);

    //这个同样是删除指定元素
    boolean remove(Object o);

    boolean containsAll(Collection<?> c);

    //同样是只能插入那些不重复的元素
    boolean addAll(Collection<? extends E> c);
  
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();

    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
}

可以发现，Set接口中定义的方法都是从Collection中直接继承的，因此Set支持的功能和Collection中定义的差不多，只不过Set中：

  • 不允许出现重复元素
  • 不支持随机访问即无法使用下标访问

HashSet

HashSet底层是使用哈希表实现的。可以非常高效地从HashSet中存取元素：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        System.out.println(set.add("AAA"));
        System.out.println(set.add("AAA"));
        System.out.println(set);
    }
}

输出：

1
2
3
true
false
[AAA]

在Set接口中并没有定义支持下标位置访问的添加和删除操作，只能简单地删除Set中的某个对象：

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        System.out.println(set.add("A"));
        System.out.println(set.add("B"));
        System.out.println(set.remove("A"));
        System.out.println(set);
    }
}
1
2
3
4
true
true
true
[B]

由于底层采用哈希表实现，所以Set无法维持插入元素的顺序：

1
2
3
4
5
6
7
public class Main {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.addAll(Arrays.asList("darling", "in", "the", "franxx"));
        System.out.println(set);
    }
}
1
[the, darling, in, franxx]

LinkedHashSet

如果想要使用维持顺序的Set集合，可以使用LinkedHashSet，底层维护的是一个LinkedHashMap，可以在插入数据时利用链表自动维护顺序，因此这样就能保证插入顺序和最后的迭代顺序一致：

1
2
3
4
5
6
7
public class Main {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>();
        set.addAll(Arrays.asList("darling", "in", "the", "franxx"));
        System.out.println(set);
    }
}
1
[darling, in, the, franxx]

TreeSet

还有一种Set叫做TreeSet，可以在元素插入时进行排序：

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>();
        set.add(3);
        set.add(1);
        set.add(2);
        System.out.println(set);
    }
}

输出：

1
[1, 2, 3]

可以看到，不是按照插入顺序，而是按照数字的大小进行排序。

当然我们也可以自定义排序规则：

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>((a, b) -> b - a);
        set.add(3);
        set.add(1);
        set.add(2);
        System.out.println(set);
    }
}

输出：

1
[3, 2, 1]

Set更重要的是性质与使用方法。

Map映射

Map通过保存键值对的形式来存储映射关系，可以轻松地通过键找到对应的映射值。Map并不是Collection体系下的接口，而是单独的一个体系，因为操作特殊。

Map接口的定义：

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
//需要填写两个泛型
public interface Map<K,V> {
    //-------- 查询相关操作 --------
  
  	//获取当前存储的键值对数量
    int size();

    //是否为空
    boolean isEmpty();

    //查看Map中是否包含指定的键
    boolean containsKey(Object key);

    //查看Map中是否包含指定的值
    boolean containsValue(Object value);

    //通过给定的键，返回其映射的值
    V get(Object key);

    //-------- 修改相关操作 --------

    //向Map中添加新的映射关系，也就是新的键值对
    V put(K key, V value);

    //根据给定的键，移除其映射关系，也就是移除对应的键值对
    V remove(Object key);


    //-------- 批量操作 --------

    //将另一个Map中的所有键值对添加到当前Map中
    void putAll(Map<? extends K, ? extends V> m);

    //清空整个Map
    void clear();


    //-------- 其他视图操作 --------

    //返回Map中存放的所有键，以Set形式返回
    Set<K> keySet();

    //返回Map中存放的所有值
    Collection<V> values();

    //返回所有的键值对，这里用的是内部类Entry在表示
    Set<Map.Entry<K, V>> entrySet();

    //这个是内部接口Entry，表示一个键值对
    interface Entry<K,V> {
        //获取键值对的键
        K getKey();

        //获取键值对的值
        V getValue();

        //修改键值对的值
        V setValue(V value);

        //判断两个键值对是否相等
        boolean equals(Object o);

        //返回当前键值对的哈希值
        int hashCode();

        ...
    }

    ...
}

尝试使用HashMap：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Keith");
        map.put(2, "Flick");
        System.out.println(map.get(2));
    }
}

输出：

1
Flick

Map中无法添加相同的键，如果出现相同的键，那么第二次出现的值会覆盖掉之前的：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Keith");
        map.put(2, "Flick");
        System.out.println(map.get(2));
    }
}

输出：

1
Flick

为了防止意外将之前的键值对覆盖掉，可以使用putIfAbsent()方法，：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Keith");
        map.putIfAbsent(1, "Flick");
        System.out.println(map.get(1));
    }
}

输出：

1
Keith

如果使用get获取一个不存在的映射，那么会返回null作为结果：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Keith");
        map.putIfAbsent(1, "Flick");
        System.out.println(map.get(2));
    }
}

输出：

1
null

也可以为这种情况添加一个预备方案，当Map中不存在时可以使用getOrDefault返回一个备选的返回值：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Keith");
        map.putIfAbsent(2, "Flick");
        System.out.println(map.getOrDefault(3, "Genie"));
    }
}

输出：

1
Genie

与Set类似，因为HashMap底层通过哈希表实现，所以不维护顺序，我们在获取所有键和值时可能是乱序的（根据Java版本有所不同）：

1
2
3
4
5
6
7
8
9
10
11
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "Keith");
        map.put(2, "Flick");
        map.put(3, "Genie");
        System.out.println(map);
        System.out.println(map.keySet());
        System.out.println(map.values());
    }
}

想维护顺序可以使用LinkedHashMap。

HashMap

从最简单的HashMap开始，底层采用的是哈希表（哈希表参考之前的笔记）。哈希表可能出现哈希冲突，这样保存到元素数量就会存在限制，而可以通过链地址法解决这种问题，如下图：

实际上这个表就是一个存放头结点的数组+若干结点，而HashMap也是一样的：

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 class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
  
  	...
    
  	static class Node<K,V> implements Map.Entry<K,V> {   //内部使用结点，实际上就是存放的映射关系
        final int hash;
        final K key;   //之前一个结点只有键，而这里的结点既存放键也存放值，当然计算哈希还是使用键
        V value;
        Node<K,V> next;
				...
    }
  	
  	...
  
  	transient Node<K,V>[] table;   //哈希表本体了，跟之前的写法是一样的，也是头结点数组，只不过HashMap中没有设计头结点（相当于没有头结点的链表）
  
  	final float loadFactor;   //负载因子，决定了HashMap的扩容效果
  
  	public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; //当我们创建对象时，会使用默认的负载因子，值为0.75
    }
  
  	...     
}

可以看到，HashMap底层结构和之前的哈希表差不多只不过多了一些东西：

  • HashMap支持自动扩容。
  • HashMap不只使用链地址法，当链表长度达到一定限制时会自动转变为效率更高的红黑树结构。

HashMap中的put方法的定义：

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
public V put(K key, V value) {
  	//这里计算完键的哈希值之后，调用的另一个方法进行映射关系存放
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)  //如果底层哈希表没初始化，先初始化
        n = (tab = resize()).length;   //通过resize方法初始化底层哈希表，初始容量为16，后续会根据情况扩容，底层哈希表的长度永远是2的n次方
  	//因为传入的哈希值可能会很大，这里同样是进行取余操作
  	//(n - 1) & hash 等价于 hash % n 这里的i就是最终得到的下标位置了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);   //如果这个位置上什么都没有，那就直接放一个新的结点
    else {   //这种情况就是哈希冲突了
        Node<K,V> e; K k;
        if (p.hash == hash &&   //如果上来第一个结点的键的哈希值跟当前插入的键的哈希值相同，键也相同，说明已经存放了相同键的键值对了，那就执行覆盖操作
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;   //这里直接将待插入结点等于原本冲突的结点，一会直接覆盖
        else if (p instanceof TreeNode)   //如果第一个结点是TreeNode类型的，说明这个链表已经升级为红黑树了
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  //在红黑树中插入新的结点
        else {
            for (int binCount = 0; ; ++binCount) {  //普通链表就直接在链表尾部插入
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);  //找到尾部，直接创建新的结点连在后面
                    if (binCount >= TREEIFY_THRESHOLD - 1) //如果当前链表的长度已经很长了，达到了阈值
                        treeifyBin(tab, hash);			//那么就转换为红黑树来存放
                    break;   //直接结束
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))  //同样的，如果在向下找的过程中发现已经存在相同键的键值对了，直接结束，让p等于e一会覆盖就行了
                    break;
                p = e;
            }
        }
        if (e != null) { // 如果e不为空，只有可能是前面出现了相同键的情况，其他情况e都是null，所有直接覆盖就行
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;   //覆盖之后，会返回原本的被覆盖值
        }
    }
    ++modCount;
    if (++size > threshold)   //键值对size计数自增，如果超过阈值，会对底层哈希表数组进行扩容
        resize();   //调用resize进行扩容
    afterNodeInsertion(evict);
    return null;  //正常插入键值对返回值为null
}

根据这段put的代码可知，当我们成功插入一个键值对时会得到一个null返回值，而如果插入冲突则会得到一个被覆盖的值：

1
2
3
4
5
6
7
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        System.out.println(map.put(0, "darling"));
        System.out.println(map.put(0, "in"));
    }
}

输出：

1
2
null
darling

当HashMap的一个链表长度过大时会自动转换为红黑树：

但是这种方法治标不治本，受限制的一直是底层哈希表的长度，我们还需要进一步对底层的这个哈希表进行扩容才能从根本上解决问题，这时需要用到resize()方法：

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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;   //保存现有哈希表
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;  //新的容量和扩容阈值
    if (oldCap > 0) {  //如果旧容量大于0，那么就开始扩容
        if (oldCap >= MAXIMUM_CAPACITY) {  //如果旧的容量已经大于最大限制了，那么直接给到 Integer.MAX_VALUE
            threshold = Integer.MAX_VALUE;
            return oldTab;  //这种情况不用扩了
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)   //新的容量等于旧容量的2倍，同样不能超过最大值
            newThr = oldThr << 1; //新的阈值也提升到原来的两倍
    }
    else if (oldThr > 0) // 旧容量不大于0只可能是还没初始化，这个时候如果阈值大于0，直接将新的容量变成旧的阈值
        newCap = oldThr;
    else {               // 默认情况下阈值也是0，也就是我们刚刚无参new出来的时候
        newCap = DEFAULT_INITIAL_CAPACITY;   //新的容量直接等于默认容量16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //阈值为负载因子乘以默认容量，负载因子默认为0.75，也就是说只要整个哈希表用了75%的容量，那么就进行扩容。
    }
    ...
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;   //将底层数组变成新的扩容之后的数组
    if (oldTab != null) {  //如果旧的数组不为空，那么还需要将旧的数组中所有元素全部搬到新的里面去
      	...
    }
}

LinkedHashMap

LinkedHashMap直接继承自HashMap，具有HashMap的全部性质，同时保留了插入顺序。这样在遍历LinkedHashMap时顺序就和插入循序一致。当然也可以使用访问顺序，也就是刚访问过的元素会被排在最后一位。

TreeMap

一种比较特殊的Map，就像名字TreeMap一样，内部直接维护了一个没有哈希表的红黑树。因为它会将我们插入的结点按照规则进行排序，所以说我们可以自定义比较规则：

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        Map<Integer, String> map = new TreeMap<>((a, b) -> b - a);
        map.put(1, "darling");
        map.put(3, "in");
        map.put(0, "the");
        System.out.println(map);
    }
}

输出：

1
{3=in, 1=darling, 0=the}

Set与Map

回头来看上个章节的HashSet的底层实现：

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
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{

    private transient HashMap<E,Object> map;   //HashSet底层直接用map来做事

    // 因为Set只需要存储Key就行了，所以说这个对象当做每一个键值对的共享Value
    private static final Object PRESENT = new Object();

    //直接构造一个默认大小为16负载因子0.75的HashMap
    public HashSet() {
        map = new HashMap<>();
    }
		
  	...
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }
}

可以发现，虽然外壳是HashSet，但实际上内部维护的时一个共享值的HashMap。所以HashSet使用了HashMap的数据结构实现了Set定义的功能。

再看TreeSet，实际上用的就是TreeMap：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    //底层需要一个NavigableMap，就是自动排序的Map
    private transient NavigableMap<E,Object> m;

    //共享值
    private static final Object PRESENT = new Object();

    ...

    //直接使用TreeMap
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
		
  	...
}

Map提供的方法

  • compute、computeIfPresent、computeIfAbsent方法的用法如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "A");
        map.put(2, "B");
        map.compute(1, (k, v) -> {   //compute会将指定Key的值进行重新计算，若Key不存在，v会返回null
            return v + "M";     //这里返回原来的value+M
        });

      	map.computeIfPresent(2, (k, v) -> {   //当Key存在时存在则计算并赋予新的值
          return v + "M";     //这里返回原来的value+M
        });

        map.computeIfAbsent(3, (k) -> {   //若不存在则计算并插入新的值
            return "M";     //返回M
        });

        System.out.println(map);
    }

    输出：

    1
    {1=AM, 2=BM, 3=M}

  • merge方法用于处理数据：

    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
    public static void main(String[] args) {
        List<Student> students = Arrays.asList(
                new Student("yoni", "English", 80),
                new Student("yoni", "Chiness", 98),
                new Student("yoni", "Math", 95),
                new Student("taohai.wang", "English", 50),
                new Student("taohai.wang", "Chiness", 72),
                new Student("taohai.wang", "Math", 41),
                new Student("Seely", "English", 88),
                new Student("Seely", "Chiness", 89),
                new Student("Seely", "Math", 92)
        );
        Map<String, Integer> scoreMap = new HashMap<>();
      	//merge方法可以对重复键的值进行特殊操作，比如我们想计算某个学生的所有科目分数之后，那么就可以像这样：
        students.forEach(student -> scoreMap.merge(student.getName(), student.getScore(), Integer::sum));
        scoreMap.forEach((k, v) -> System.out.println("key:" + k + "总分" + "value:" + v));
    }

    static class Student {
        private final String name;
        private final String type;
        private final int score;

        public Student(String name, String type, int score) {
            this.name = name;
            this.type = type;
            this.score = score;
        }

        public String getName() {
            return name;
        }

        public int getScore() {
            return score;
        }

        public String getType() {
            return type;
        }
    }

  • replace方法可以快速替换某个映射的值：

    1
    2
    3
    4
    5
    6
    7
    8
    public class Main {
        public static void main(String[] args) {
            Map<Integer, String> map = new HashMap<>();
            map.put(0, "AAA");
            map.replace(0, "BBB");
            System.out.println(map);
        }
    }

    输出：

    1
    {0=BBB}

  • replace也可以实现精确匹配的替换，当且仅当键和值都相等的收才进行替换：

    1
    2
    3
    4
    5
    6
    7
    8
    public class Main {
        public static void main(String[] args) {
            Map<Integer, String> map = new HashMap<>();
            map.put(0, "AAA");
            map.replace(0, "AAA", "BBB");
            System.out.println(map);
        }
    }

    输出：

    1
    {0=BBB}

  • remove方法也支持键值对同时匹配：

    1
    2
    3
    4
    5
    6
    7
    8
    public class Main {
        public static void main(String[] args) {
            Map<Integer, String> map = new HashMap<>();
            map.put(0, "AAA");
            map.remove(0, "AAA");
            System.out.println(map);
        }
    }

    输出：

    1
    {}

Stream 流

Java8 添加了一个新的抽象称为流Stream。Stream使用一种类似用 SQL 语句从数据库查询数据的直观方式来提供一种对 Java 集合运算和表达的高阶抽象。

将要处理的元素集合看作一种流，流在管道里传输，并且可以在管道的节点上进行处理，比如筛选、排序、聚合等。元素流在管道中经过中间操作的处理，最后由最终操作得到前面处理的结果：

正常来说，我们要创建一个列表，把A、B、C放进去，然后再删除B，可以这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        //移除B
        Iterator iterator = list.iterator();
        while(iterator.hasNext()) {
            if (iterator.next().equals("B"))
                    iterator.remove();
        }

        System.out.println(list);
    }
}

输出：

1
[A, C]

如果使用stream流：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        //移除B
        list = list                                 //链式调用
                .stream()                           //获取流
                .filter(e -> !e.equals("B"))        //filter只允许值不等于B的元素通过
                .collect(Collectors.toList());      //将流水线中的元素收集起来转换回List

        System.out.println(list);
    }
}

输出：

1
[A, C]

换一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(3);

        list = list
                .stream()                           //转换成Stream流
                .distinct()                         //去重
                .sorted((a, b) -> b -a)             //从大到小排列
                .map(e -> e + 1)                    //各元素加一
                .limit(2)                   //设置列表大小限制，只放行前两个元素
                .collect(Collectors.toList());

        System.out.println(list);
    }
}

输出：

1
[4, 3]

当遇到大量操作时可以使用Stream流快速实现要求。

需要注意的是，在整个语句中可能不是依次执行的。实际上Stream会先记录每一步操作而不是直接开始执行内容，当整个链式调用完成后才会依次进行。

可以使用Stream流来生成符合条件的随机数：

1
2
3
4
5
6
7
8
9
10
11
public class Main {
    public static void main(String[] args) {
        Random random = new Random();                                   //Random支持直接生成随机数的流
        random
                .ints(-100, 100)      //生成-100到10之间的随机整型数字
                .limit(10)                                      //只获取前10个数字（不限制的话就是无限的流）
                .filter(i -> i < 0)                                     //只保留小于0的数
                .sorted()                                               //默认从小到大排序
                .forEach(System.out :: println);                        //依次打印
    }
}

输出：

1
2
-35
-28

我们可以生成一个统计实例来帮助我们快速进行统计：

1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
    public static void main(String[] args) {
        Random random = new Random();
        IntSummaryStatistics statistics = random
                .ints(0, 100)
                .limit(100)
                .summaryStatistics();                               //获取语法统计实例
        System.out.println(statistics.getMax());                    //快速获取最大值
        System.out.println(statistics.getCount());                  //获取数量
        System.out.println(statistics.getAverage());                //获取平均值
    }
}

输出：

1
2
3
99
100
53.81

普通的List只需要一个方法就可以转换为更加方便的IntStream：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(1);
        
        list.stream()
                .mapToInt(i -> 1)       //将每一个元素映射为Integer类型
                .summaryStatistics();
    }
}

还可以通过flat对整个流进行进一步的细分：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A, B");
        list.add("C, D");
        list.add("E, F");
        list = list
                .stream()
                .flatMap(e -> Arrays.stream(e.split(", ")))
                .collect(Collectors.toList());
        System.out.println(list);
    }
}

输出：

1
[A, B, C, D, E, F]

也可以只通过Stream完成所有数字的和，使用reduce方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        int sum = list
                .stream()
                .reduce((a, b) -> a + b)
                .get();
        System.out.println(sum);
    }
}

输出：

1
6

Collections工具类

JDK实现的Collection类是专门用于集合的工具类。

如果想快速求得List中的最大值和最小值：

1
2
3
4
5
6
7
8
9
10
11
public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        System.out.println(Collections.max(list));
        System.out.println(Collections.min(list));
    }
}

输出：

1
2
3
1

可以对一个实现Comparable接口的集合类进行二分搜索：

1
2
3
4
public static void main(String[] args) {
    List<Integer> list = Arrays.asList(2, 3, 8, 9, 10, 13);
    System.out.println(Collections.binarySearch(list, 8));
}

输出：

1
2

可以对集合的元素进行快速填充，需要注意的是这个填充是对集合中已有的元素进行覆盖：

1
2
3
4
5
6
7
public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5));
        Collections.fill(list, 6);
        System.out.println(list);
    }
}

输出：

1
[6, 6, 6, 6, 6]

如果集合中本身没有元素则fill方法不会生效。

有时我们需要生成一个空的集合类返回，可以使用emptyList等快速生成一个只读的空集合：

1
2
3
4
5
6
7
public class Main {
    public static void main(String[] args) {
        List<Integer> list = Collections.emptyList();
        //Collections.singletonList() 会生成一个只有一个元素的List
        list.add(10);   //不支持，会直接抛出异常
    }
}

可以寻找子集合的位置：

1
2
3
4
5
6
public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5));
        System.out.println(Collections.indexOfSubList(list, Arrays.asList(4, 5)));
    }
}

输出：

1
3

得益于泛型的类型擦除机制，实际上最后只要是Object的实现类都可以保存到集合类中，那么就会出现这种情况：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        //使用原始类型接收一个Integer类型的ArrayList
        List list = new ArrayList<>(Arrays.asList(1,2,3,4,5));
        list.add("aaa");   //存字符串进去
        System.out.println(list);
    }
}

输出：

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

由于泛型机制上的一些漏洞，实际上对应类型的集合类有可能会存放其他类型的值，泛型的类型检查只存在于编译阶段，只要我们绕过这个阶段，在实际运行时，并不会真的进行类型检查，要解决这种问题很简单，就是在运行时进行类型检查：

1
2
3
4
5
6
7
8
public class Main {
    public static void main(String[] args) {
        List list = new ArrayList<>(Arrays.asList(1,2,3,4,5));
        list = Collections.checkedList(list, Integer.class);   //这里的.class关键字表示Integer这个类型
        list.add("aaa");
        System.out.println(list);
    }
}

checkedList等可以将给定集合类进行包装，在运行时同样会进行类型检查，如果通过上面的漏洞插入一个本不应该是当前类型集合支持的类型，那么会直接抛出类型转换异常：