Java核心技术1-集合

摘要: 本文是《Java核心技术 10th》中关于集合的要点总结。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

Java 集合框架

设计人员希望让集合类库规模小且易于学习，而不希望像 C++ 的“标准模版库”那样复杂，但却又希望能够得到 STL 的“泛型算法”所具有的优点，希望将传统的类融入新的框架中。因此必须做出一些艰难的选择，以及一些独特的设计。

本节介绍 Java 集合框架的基本设计，使用方法，并解释一些颇具争议的特性背后的考虑。

集合的接口与实现分离

以队列为例，队列接口的最简单形式想下面这样：

public interface Queue<E> {
    void add(E element);
    E remove();
    int size();
}

接口并没有说明队列如何实现，通常有两种实现方式：使用循环数组、使用链表。

每个实现都是通过实现了 Queue 接口的类表示:

public class CircularArrayQueue<E> implements Queue<E> {
    private int head;
    private int tail;

    CircularArrayQueue(int capacity) {...}
    public void add(E element) {...}
    public E remove() {...}
    public int size() {...}
    private E[] elements {...}
}

public class LinkedListQueue<E> implements Queue<E> {
    private Link head;
    private Link tail;

    LinkedListQueue() {...}
    public void add(E element) {...}
    public E remove() {...}
    public int size() {...}
}

Java 类库中，如果要循环数组队列，用 ArrayQueue，如果要链表队列，用 LinkedList，这个类实现了 Queue 接口。

使用队列的是，一旦构建了集合，就不需要知道用的那种实现。只有在构建集合对象时，用具体的类才有意义，可以用接口类型存放集合的引用。

Queue<Customer> expressLane = new ArrayQueue<>(100);
expressLane.add(new Custemer("Harry"));

另外一组名字以 Abstract 开头的类，例如，AbstractQueue。这些类是为类库实现者而设计的。如果想要实现自己的队列类，扩展 AbstractQueue 类要比实现 Queue 接口中的所有方法轻松得多。

Collection 接口

集合的基本接口是 Collection 接口，有两个基本方法：

public interface Collection<E> {
    boolean add(E element);
    Iterator<E> iterator();
    ...
}

• add 方法：用于向集合中添加元素。如果添加元素确实改变了集合就返回 true，如果集合没有发生变化就返回 false。
• iterator 方法：返回一个实现了 Iterator 接口的对象。可以使用这个迭代器对象依次访问集合中的元素。

迭代器

Iterator 接口包含 4 个方法：

public interface Iterator<E> {
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemaining(Consumer<? super E> action);
}

如果到达了集合的末尾，next 方法将抛出一个 NoSuchElementException。因此调用 next 之前需要调用 hasNext 方法。

for each 循环可以与任何实现了 Iterable 接口的对象一起工作，该接口只包含一个抽象方法：

public interface Itarable<E> {
    Iterator<E> iterator();
}

Collection 接口扩展了 Iterable 接口。因此，对于标准类库中的任何集合都可以使用 “for each” 循环。

Java8 以后 iterator 有一个 forEachRemaining 方法，可以提供一个处理一个元素的 lambda 表达式，直到再没有元素为止。

itarator.forEachRemaining(element -> ...);

C++ 与 Java 关于 Iterator 的区别

在 C++ 标准模板库中，迭代器是根据数组索引建模的。

• 如果给定这样一个迭代器，就可以查看指定位置上的元素，就像知道数组索引 i 就可以查看数组元素 a[i] 一样。
• 不需要查找元素，就可以将迭代器向前移动一个位置。这与不需要执行查找操作就可以通过 i++ 将数组索引向前移动一样。

Java 查找操作与位置变更是紧密相连的。查找一个元素的唯一方法是调用 next，而在执行查找操作的同时，迭代器的位置随之向前移动。

应该将 Java 迭代器认为是位于两个元素之间。当调用 next 时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。

可以将 Iterator.next 与 InputStream.read 看作为等效的。从数据流中读取一个字节，就会自动地“消耗掉”这个字节。下一次调用 read 将会消耗并返回输入的下一个字节。用同样的方式，反复地调用 next 就可以读取集合中所有元素。

Iterator 接口的 remove 方法将会删除上次调用 next 方法时返回的元素。下面的代码是删除第一个元素的代码：

Iterator<String> it = c.iterator();
it.next();
it.remove();

调用 remove 之前必须调用 next 方法，否则抛出 IllegalStateException。

泛型实用方法

Collection 与 Iterator 泛型接口，可以编写操作任何集合类型的实用方法。

例如：检测任意集合是否包含指定元素的泛型方法

public static <E> boolean contains(Collection<E> c, Object obj) {
    for(E element: c) {
        if(element.equals(obj)) {
            return true;
        }
    }
    return false;
}

AbstractCollection

Collection 接口声明了很多方法，所有实现类都必须提供这些方法。

如果实现 Collection 接口，要实现这么多方法，有点麻烦。Java 类库提供了一个类 AbstractCollection，它将基础方法 size 和 iterator 抽象化了，但是在此提供了例行方法。

这样具体集合可以扩展 AbstractCollection。

public abstract class AbstractCollection<E> implements Collection<E> {
    ...
    public abstract Iterator<E> iterator();
    public boolean contains(Object obj) {
        for(E element: this) { // 调用 iterator 方法
            if(element.equals(obj)) {
                return true;
            }
        }
        return false;
    }
    ...
}

在 Java8 中，Collection 接口增加了很多默认方法。其中大部分与流的处理有关。此外还有个删除满足某个条件元素的方法：

default boolean removeIf(Predicate<? super E> filter)

java.util.Collection<E> API 总结

// 返回一个用于访问集合中每个元素的迭代器。
Iterator<E> iterator()

// 返回当前存储在集合中的元素个数。
int size()

// 如果集合中没有元素，返回true。
boolean isEmpty()

// 如果集合中包含了一个与obj相等的对象，返回true。
boolean contains(Object obj)

// 如果这个集合包含other集合中的所有元素，返回true。
boolean containsAll(Collection<? > other)

// 将一个元素添加到集合中。如果由于这个调用改变了集合，返回true。
boolean add(Object element)

// 将other集合中的所有元素添加到这个集合。如果由于这个调用改变了集合，返回true。
boolean addAll(Collection<? extends E> other)

// 从这个集合中删除等于obj的对象。如果有匹配的对象被删除，返回true。
boolean remove(Object obj)

// 从这个集合中删除other集合中存在的所有元素。如果由于这个调用改变了集合，返回true。
boolean removeAll(Collection<? > other)

// 从这个集合删除filter返回true的所有元素。如果由于这个调用改变了集合，则返回true。
default boolean removeIf(Predicate<? super E> filter) 

// 从这个集合中删除所有的元素。
void clear()

// 从这个集合中删除所有与other集合中的元素不同的元素。如果由于这个调用改变了集合，返回true。
boolean retainAll(Collection<? > other)

// 返回这个集合的对象数组。
Object[] toArray()

// 返回这个集合的对象数组。如果arrayToFill足够大，就将集合中的元素填入这个数组中。剩余空间填补null；否则，分配一个新数组，其成员类型与arrayToFill的成员类型相同，其长度等于集合的大小，并填充集合元素。
<T> T[] toArray(T[] arrayToFill)

java.util.Iterator<E> API 总结

// 如果存在可访问的元素，返回true。
boolean hasNext()

// 返回将要访问的下一个对象。如果已经到达了集合的尾部，将抛出一个NoSuchElement Exception。
E next()

// 删除上次访问的对象。这个方法必须紧跟在访问一个元素之后执行。如果上次访问之后，集合已经发生了变化，这个方法将抛出一个IllegalStateException。
void remove()

集合框架中的接口

Java 集合框架不同类型的接口示意图如下：

集合有两个基本接口：Collection 和 Map。

• Collection 的插入:

boolean add(E element)

• Map 的插入:

V put(K key, V value)

• Collection 的读取: 通过迭代器

E next()

• Map 的读取:

V get(K key)

• List 是有序集合。访问元素有两种方式，使用迭代器或使用整数索引(随机访问)。

void add(int index E element)
void remove(int index)
E get(int index)
E set(int index, E element)

• ListIterator 接口是 Iterable 的子接口，定义了一个方法用于在迭代器位置前面增加一个元素。

void add(E element)

• 为了避免对链表完成随机访问操作，引入了一个标记接口 RandomAccess。这个接口不包含任何方法。但可以测试特定集合是佛支持随机访问：

if (c instanceof RandomAccess) {
    // 用随机访问的算法
} else {
    // 用顺序访问的算法
}

• Set 接口。add 方法不允许增加重复的元素。equals 方法只要两个集包含同样的元素就认为是相等的。hashCode 方法的定义要保证包含相同元素的两个集会得到相同的散列码。

• SortedSet 和 SortedMap 接口会提供用于排序的比较器对象，这两个接口定义了可以得到集合子集视图的方法。TreeSet 和 TreeMap 类实现了这些接口。

---

具体的集合

Java 类库中的具体集合如下，这里省略了线程安全集合。除了以 Map 结尾的类，都实现了 Collection 接口。以 Map 结尾的类实现了 Map 接口。

集合	描述
ArrayList	可以动态增长和缩减的索引序列
LinkedList	可以在任何位置进行高效地插入和删除操作的有序序列
ArrayDeque	用循环数组实现的双端队列
HashSet	没有重复元素的无序集合
TreeSet	有序集
EnumSet	包含枚举类型值的集合
LinkedHashSet	可以记住元素插入次序的集合
PriorityQueue	允许高效删除最小元素的集合
HashMap	存储键/值关联的数据结构
TreeMap	键值有序排列的映射表
EnumMap	键值属于枚举类型的映射表
LinkedHashMap	可以记住键/值项添加次序的映射表
WeakHashMap	其值无用武之地后可以被垃圾回收器回收的映射表
IdentityHashMap	一种用 == 而不是用 equals 比较键值的映射表

链表

LinkedList 类，实现了 List 接口。有两个注意的点：

• 某个迭代器在修改集合时，另一个迭代器对其进行遍历，会出现混乱的情况。
• 可以通过 get(i) 访问元素，但是这会从头开始遍历。

java.util.List<E> API 总结

// 返回一个列表迭代器，以便用来访问列表中的元素。
ListIterator<E> listIterator() 

// 返回一个列表迭代器，以便用来访问列表中的元素，这个元素是第一次调用next返回的给定索引的元素。
ListIterator<E> listIterator(int index)

// 在给定位置添加一个元素。
void add(int i, E element)

// 将某个集合中的所有元素添加到给定位置。
void addAll(int i, Collection<? extends E> elements)

// 删除给定位置的元素并返回这个元素。
E remove(int i)

// 获取给定位置的元素。
E get(int i)

// 用新元素取代给定位置的元素，并返回原来那个元素。
E set(int i, E element)

// 返回与指定元素相等的元素在列表中第一次出现的位置，如果没有这样的元素将返回-1。
int indexOf(Object element)

// 返回与指定元素相等的元素在列表中最后一次出现的位置，如果没有这样的元素将返回-1。
int lastIndexOf(Object element)

java.util.ListIterator<E> API 总结

// 在当前位置前添加一个元素。
void add(E newElement)

// 用新元素取代next或previous上次访问的元素。如果在next或previous上次调用之后列表结构被修改了，将抛出一个IllegalStateException异常。
void set(E newElement)

// 当反向迭代列表时，还有可供访问的元素，返回true。
boolean hasPrevious()

// 返回前一个对象。如果已经到达了列表的头部，就抛出一个NoSuchElementException异常。
E previous()

// 返回下一次调用next方法时将返回的元素索引。
int nextIndex()

// 返回下一次调用previous方法时将返回的元素索引。
int previousIndex()

java.util.LinkedList<E> API 总结

// 构造一个空链表。
LinkedList()

// 构造一个链表，并将集合中所有的元素添加到这个链表中。
LinkedList(Collection<? extends E> elements)

// 将某个元素添加到列表的头部或尾部。
void addFirst(E element)
void addLast(E element)

// 返回列表头部或尾部的元素。
E getFirst()
E getLast()

// 删除并返回列表头部或尾部的元素。
E removeFirst()
E removeLast()

数组列表

List 接口用于描述一个有序集合。ArrayList 也实现了 List 接口，封装了一个动态再分配的对象数组。

散列集

自定义类元素，需要实现这个类的 hashCode 方法。且自己实现的 hashCode 方法应该与 equals 方法兼容，即 a.equals(b) 为 true 则 a, b 必须有相同的散列码。

在 Java 中，散列表用链表数组实现，每个链表数组称为桶。

要想查找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。

Java8 中，桶满的时候会从链表变为平衡二叉树。如果选择的散列函数不当，会产生很多冲突。

如果大致知道最终会有多少个元素要插入到散列表中，就可以设置桶数。通常，将桶数设置为预计元素个数的 75%～150%。

尽管还没有确凿的证据，但最好将桶数设置为一个素数，以防键的集聚。

标准类库使用的桶数是 2 的幂，默认值为 16。

初始桶数过少，如果散列表太满，就需要再散列（rehashed）。如果要对散列表再散列，就需要创建一个桶数更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。装填因子（load factor）决定何时对散列表进行再散列。例如，如果装填因子为 0.75（默认值），而表中超过 75% 的位置已经填入元素，这个表就会用双倍的桶数自动地进行再散列。对于大多数应用程序来说，装填因子为 0.75 是比较合理的。

java.util.HashSet<E> 构造器总结

// 构造一个空散列表。
HashSet()

// 构造一个散列集，并将集合中的所有元素添加到这个散列集中。
HashSet(Collection<? extends E> elements)

// 构造一个空的具有指定容量（桶数）的散列集。
HashSet(int initialCapacity)

// 构造一个具有指定容量和装填因子（一个0.0～1.0之间的数值，确定散列表填充的百分比，当大于这个百分比时，散列表进行再散列）的空散列集。
HashSet(int initialCapacity, float loadFactor)

树集

TreeSet 类实现了 NavigableSet 接口。这个接口增加了几个便于定位元素以及反向遍历的方法。

自定义类 A 作为树集的元素，需要实现 Comparable<A> 接口，或者构造树集时必须提供一个 Comparator。

java.util.TreeSet<E> 构造器总结

// 构造一个空的树集
TreeSet()
TreeSet(Comparator<? super E> comparator)

// 构造一个树集，并增加一个集合或有序集中的所有元素（对于后一种情况，要使用同样的顺序）。
TreeSet(Collection<? extends E> elements)
TreeSet(SortedSet<E> s)

java.util.SortedSet<E> API 总结

// 返回用于对元素进行排序的比较器。如果元素用Comparable接口的compareTo方法进行比较则返回null。
Comparator<? super E> comparator()

// 返回有序集中的最小元素或最大元素。
E first()
E last()

java.util.NavigableSet<E>

// 返回大于value的最小元素或小于value的最大元素，如果没有这样的元素则返回null。
E higher(E value)
E lower(E value)

// 返回大于等于value的最小元素或小于等于value的最大元素，如果没有这样的元素则返回null。
E ceiling(E value)
E floor(E value)

// 删除并返回这个集中的最大元素或最小元素，这个集为空时返回null。
E pollFirst()
E pollLast()

// 返回一个按照递减顺序遍历集中元素的迭代器。
Iterator<E> descendingIterator()

队列

ArrayDeque 和 LinkedList 类实现了 Deque 接口。

java.util.Queue<E> API 总结

// 如果队列没有满，将给定的元素添加到这个双端队列的尾部并返回true。如果队列满了，第一个方法将抛出一个IllegalStateException，而第二个方法返回false。
boolean add(E element)
boolean offer(E element)

// 假如队列不空，删除并返回这个队列头部的元素。如果队列是空的，第一个方法抛出NoSuchElementException，而第二个方法返回null。
E remove()
E poll()

// 如果队列不空，返回这个队列头部的元素，但不删除。如果队列空，第一个方法将抛出一个NoSuchElementException，而第二个方法返回null。
E element()
E peek()

java.util.Deque<E> API 总结

// 将给定的对象添加到双端队列的头部或尾部。如果队列满了，前面两个方法将抛出一个IllegalStateException，而后面两个方法返回false。
void addFirst(E element)
void addLast(E element)
boolean offerFirst(E element)
boolean offerLast(E element)

// 如果队列不空，删除并返回队列头部的元素。如果队列为空，前面两个方法将抛出一个NoSuchElementException，而后面两个方法返回null。
E removeFirst()
E removeLast()
E pollFirst()
E pollLast()

// 如果队列非空，返回队列头部的元素，但不删除。如果队列空，前面两个方法将抛出一个NoSuchElementException，而后面两个方法返回null。
E getFirst()
E getLast()
E peekFirst()
E peekLast()

java.util.ArrayDeque<E> 构造器总结

// 用初始容量16或给定的初始容量构造一个无限双端队列。
ArrayDeque()
ArrayDeque(int initialCapacity)

优先级队列

无论何时调用 remove 方法，总会获得当前优先级队列中最小的元素。

自定义类作为元素，需要实现 Comparable 接口。

java.util.PriorityQueue 构造器总结

// 构造一个用于存放Comparable对象的优先级队列。
PriorityQueue()
PriorityQueue(int initialCapacity)

// 构造一个优先级队列，并用指定的比较器对元素进行排序。
PriorityQueue(int initialCapacity, Comparator<? superE> c)

---