Java 集合 - 集合框架概述

Java 集合框架Java Collections Framework是 Java 标准类库中的一个重要组成部分用于存储、操作和管理数据。它提供了一系列的接口、抽象类和实现类用于表示和操作不同类型的集合数据结构。

集合和数组既然都是容器它们有什么区别呢

• 数组的长度是固定的集合的长度是可变的
• 数组中可以存储基本数据类型值也可以存储对象而集合中只能存储对象。

1.集合框架体系结构

先来看看一个简单的集合框架类图

可见Java 集合框架定义了两个顶层的接口 Collection存储对象的集合 和 Map存储键值对也成为映射关系用于表示不同类型的集合。

2.Collection 接口

Collection 接口是 Java 集合框架的根接口它代表了一组对象的集合这些对象也称为 collection 的元素。一些 collection 允许有重复的元素而另一些则不允许。一些 collection 是有序的而另一些则是无序的。JDK 不提供此接口的任何直接实现它只负责定义常见的集合操作如添加元素、删除元素、遍历元素等。

该接口源码如下

public interface Collection<E> extends Iterable<E> {
    // Query Operations查询操作

    /**
     * 返回此集合中的元素数。
     * 说明如果此集合包含的元素多于 Integer.MAX_VALUE则返回 Integer.MAX_VALUE。
     */
    int size();

    /**
     * 返回true如果此集合不包含元素。
     */
    boolean isEmpty();

    /**
     * 返回true如果此集合包含指定的元素。
     */
    boolean contains(Object o);

    /**
     * 返回此集合中的元素上的迭代器。没有关于元素返回的顺序的保证除非此集合是某个类的实例该类提供保证。
     */
    Iterator<E> iterator();

    /**
     * 返回包含此集合中所有元素的数组。
     * 说明
     * 1.如果此集合对其元素由其迭代器返回的顺序有任何保证则此方法必须以相同的顺序返回元素。返回的数组的运行时组件类型为Object。
     * 2.返回的数组将是“安全的”因为此集合不维护对它的任何引用。换句话说即使此集合由数组支持此方法也必须分配一个新数组。
     */
    Object[] toArray();

    /**
     * 返回包含此集合中所有元素的数组返回数组的运行时类型是指定数组的类型。
     * 说明
     * 1.如果此集合适合指定的数组则返回该数组。否则将使用指定数组的运行时类型和此集合的大小分配新数组。
     * 2.如果此集合适合指定的数组并有剩余空间即数组中的元素多于此集合则紧接此集合结束的数组中的元素将设置为null。
     * 3.如果此集合对其元素由其迭代器返回的顺序有任何保证则此方法必须以相同的顺序返回元素。
     */
    <T> T[] toArray(T[] a);

    /**
     * 返回包含此集合中所有元素的数组使用提供的生成器函数来分配返回的数组。
     * 说明
     * 1.如果此集合对其元素由其迭代器返回的顺序有任何保证则此方法必须以相同的顺序返回元素。
     * 2.返回的数组的运行时组件类型是由提供的生成器函数的返回类型确定的。
     * 3.像{@link #toArray()}一样此方法充当基于数组和基于集合的API之间的桥梁。
     */
    default <T> T[] toArray(IntFunction<T[]> generator) {
        return toArray(generator.apply(0));
    }

    // Modification Operations修改操作

    /**
     * 向此集合中添加指定的元素。
     * 说明
     * 1.如果此集合因调用而更改则返回true。
     * 2.如果此集合不允许重复并且已经包含指定的元素则返回false。
     * 3.如果此集合由于其容量而拒绝添加指定的元素则抛出 IllegalStateException。
     */
    boolean add(E e);

    /**
     * 移除此集合中的单个实例指定的元素如果存在。
     * 说明
     * 1.如果此集合包含指定的元素则返回true或者等效地如果此集合因调用而更改。
     * 2.如果此集合包含多个指定的元素则仅删除第一个。
     */
    boolean remove(Object o);


    // Bulk Operations批量操作

    /**
     * 返回true如果此集合包含指定集合中的所有元素。
     */
    boolean containsAll(Collection<?> c);

    /**
     * 添加指定集合中的所有元素到此集合。即 this = this ∪ c
     */
    boolean addAll(Collection<? extends E> c);

    /**
     * 移除此集合中包含在指定集合中的所有元素。
     */
    boolean removeAll(Collection<?> c);

    /**
     * 移除此集合中满足给定谓词的所有元素。迭代或谓词抛出的错误或运行时异常被中继给调用者。
     */
    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;
    }

    /**
     * 从此集合中移除未包含在指定集合中的所有元素。
     */
    boolean retainAll(Collection<?> c);

    /**
     * 移除此集合中的所有元素。此方法返回后集合将为空。
     */
    void clear();


    // Comparison and hashing比较和哈希

    /**
     * 比较指定的对象与此集合是否相等。
     * 说明当且仅当指定的对象也是一个集合并且两个集合中包含相同的元素时返回true。
     */
    boolean equals(Object o);

    /**
     * {@code c1.hashCode()==c2.hashCode()}.
     * 返回此集合的哈希码值。
     * 说明
     * 虽然Collection接口对Object.hashCode方法没有添加规定但是程序员应该注意
     * 任何重写Object.equals方法的类也必须重写Object.hashCode方法以满足Object.hashCode方法的一般合同。
     */
    int hashCode();

    /**
     * 创建此集合中元素的Spliterator。
     */
    @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);
    }
}

2.1 Iterator

2.1.1 使用迭代器遍历集合

迭代是一种通用的获取集合元素的方式。在获取元素之前需要先判断集合中是否有元素。如果有就取出这个元素并继续判断是否还有元素。如果有就继续取出。重复这个过程直到集合中的所有元素都被取出。

想要遍历 Collection 集合那么就要获取该集合迭代器完成迭代操作在上面的源码中提供有一个 Iterator<E> iterator() 方法专门用来获取集合对应的迭代器用来遍历集合中的元素。

java.util.Iterator 接口的源码如下

public interface Iterator<E> {
    /**
     * 如果迭代器还有元素返回true
     */
    boolean hasNext();

    /**
     * 返回迭代器的下一个元素
     */
    E next();

    /**
     * 移除迭代器最后一个元素
     * 说明
     * 1. 这个方法是可选的不是所有的迭代器都支持这个方法
     * 2. 这个方法只能在next方法之后调用一次如果再次调用会抛出IllegalStateException异常
     * 3. 如果在调用next方法之前调用remove方法也会抛出IllegalStateException异常
     * 4. 如果在调用remove方法之后再次调用remove方法也会抛出IllegalStateException异常
     */
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    /**
     * 对剩余的每个元素执行给定的操作直到所有元素都被处理或操作抛出异常。
     * 说明如果指定了顺序操作将按迭代顺序执行。
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

下面通过一个案例来演示迭代器的使用方式

public class IteratorTest {
    public static void main(String[] args) {
        // 创建集合
        Collection<String> collection = new ArrayList<>();

        // 添加元素
        collection.add("张三");
        collection.add("李四");
        collection.add("王五");

        // 从集合中获取迭代器
        Iterator<String> iterator = collection.iterator();
        // 遍历集合,条件为迭代器中还有元素
        while (iterator.hasNext()) {
            // 获取迭代器中的下一个元素
            String next = iterator.next();
            // 输出元素
            System.out.println(next);
        }
    }
}

程序执行结果如下

张三
李四
王五

其底层迭代原理是通过一个指针或称游标来指向当前遍历到的元素每次调用 next() 方法时指针向后移动一位并返回当前指向的元素。当指针遍历到集合末尾时hasNext() 方法返回 false表示遍历结束。

例如ArrayList 的迭代器实现中指针指向当前元素的下标每次调用 next() 方法时返回当前下标对应的元素并将下标加一。而 LinkedList 的迭代器实现中则需要保存一个指向当前节点的引用每次调用 next() 方法时返回当前节点的值并将指针指向下一个节点。

2.1.2 使用迭代器删除集合元素

java.util.Iterator 中还提供了一个 void remove() 方法既然 Collection 已经有 remove(Object o) 方法了为什么 Iterator 迭代器还要提供删除方法呢这是因为因为在 JDK1.8 之前 Collection 接口没有 removeIf(Predicate<? super E> filter) 方法即无法根据条件进行删除。

例如要删除以下集合元素中的偶数

public class IteratorTest02 {
    public static void main(String[] args) {
        // 创建集合
        Collection<Integer> collection = new ArrayList<>();

        // 添加元素
        collection.add(1);
        collection.add(2);
        collection.add(3);
        collection.add(4);

        // collection.remove(?) JDK 1.8 以前没有 removeIf 方法,没办法删除集合中的 “偶数” 元素

        // 方式一通过迭代器删除集合中的偶数元素
        Iterator<Integer> iterator = collection.iterator();
        while (iterator.hasNext()) {
            // 获取迭代器中的下一个元素
            Integer next = iterator.next();
            // 判断元素是否为偶数
            if (next % 2 == 0) {
                // 删除偶数元素
                iterator.remove();
            }
        }
        
        // 方式二通过增强for循环删除集合中的偶数元素(底层还是迭代器)
        for (Integer integer : collection) {
            if (integer % 2 == 0) {
                collection.remove(integer);
            }
        }
        
        // 方式三通过 removeIf 方法删除集合中的偶数元素
        collection.removeIf(integer -> integer % 2 == 0);
    }
}

2.1.3 Iterator 迭代器的 fail-fast 机制

“fail-fast” 是 Java 集合框架中迭代器的一个特性。它主要指的是当多个线程同时修改一个集合时如果一个线程正在通过迭代器遍历集合而另一个线程修改了集合如添加、删除或修改元素那么正在遍历的线程会立即抛出 ConcurrentModificationException 异常。

这种机制的设计原因是为了防止在遍历过程中由于集合的结构发生改变导致结果的不可预见性。对于 fail-fast 系统如果有错误发生系统会立即对错误进行响应而不是尝试在错误的状态下继续运行。这有助于避免在运行时发生更严重的错误也更容易找出问题的原因。

要注意的是fail-fast 机制并不能保证在所有情况下都能发现并防止并发修改它只能在迭代过程中尽可能地检测出错误。另外Java 的并发包 java.util.concurrent 中的一些集合类如 CopyOnWriteArrayList 和 ConcurrentHashMap则提供了 fail-safe 的迭代器这种迭代器在遍历时不会抛出 ConcurrentModificationException 异常因为它们在迭代时工作在集合的一个副本上而不是直接在集合上。

下面基于 ArrayList 分析实现原理可暂时跳过有基础的可以直接继续阅读。

迭代器如何实现快速失败机制以 ArrayList 为例它继承了一个变量 protected transient int modCount = 0; 用于记录集合的结构修改次数。当进行新增、删除等操作时modCount++ 将记录数量加1。在使用 Iterator 迭代器遍历集合时创建集合迭代器的对象时记录当前集合的 modCount例如int expectedModCount = modCount;。之后每次使用迭代器的 next() 方法迭代元素时都要检查 expectedModCount 是否等于当前的 modCount如果不相等则说明集合结构被修改了可能是在使用迭代器的同时使用了集合的 add、remove 等方法导致 modCount++最终会抛出 ConcurrentModificationException 异常。

下面来看一看 ArrayList 中的 Itr 迭代器的具体实现

/**
* 返回一个迭代器按照正确的顺序遍历此列表中的元素。
*/
public Iterator<E> iterator() {
return new Itr();
}

/**
* 一个优化版本的AbstractList.Itr
*/
private class Itr implements Iterator<E> {
// 下一个元素的索引
int cursor;
// 最后一个元素的索引如果没有则为-1
int lastRet = -1;
// 期望的修改次数modCount 继承自 AbstractList,创建迭代器时记录
int expectedModCount = modCount;

// prevent creating a synthetic constructor
Itr() {
}

// 判断是否有下一个元素
public boolean hasNext() {
    // cursor < size 表示还有元素
    return cursor != size;
}

// 获取下一个元素
@SuppressWarnings("unchecked")
public E next() {
    // 检查是否有并发修改即modCount是否等于expectedModCount
    checkForComodification();
    // 获取下一个元素的索引
    int i = cursor;
    // 如果下一个元素的索引大于等于元素的个数抛出异常(因为没有元素了)
    if (i >= size)
        throw new NoSuchElementException();
    // 获取ArrayList的数组
    Object[] elementData = ArrayList.this.elementData;
    // 如果下一个元素的索引大于等于数组的长度抛出异常(因为容量不够了)
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    // 将下一个元素的索引加1
    cursor = i + 1;
    // 返回下一个元素其实就是elementData[i]
    return (E) elementData[lastRet = i];
}

::: warning

迭代器的快速失败行为不能得到保证。通常在存在不同步的并发修改时不可能对其进行坚决的保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException 异常。因此将依赖于此异常的程序编写是错误的。正确的方法是使用迭代器的快速失败行为来检测 bug而不应将其用于其他用途。

:::

2.2 Iterable

通过该接口的声名我们也看到了 Collection 接口继承了 java.lang.Iterable 接口因此它的实现类可以使用 for-each 循环进行遍历。

该接口源码如下

/**
 * {@code for} statement (sometimes called the "for-each loop" statement).
 * 实现此接口允许对象成为增强的{@code for}语句有时称为“for-each循环”语句的目标。
 */
public interface Iterable<T> {
    /**
     * 返回一个迭代器用于遍历此集合中的元素。
     */
    Iterator<T> iterator();

    /**
     * 对于{@code Iterable}的每个元素执行给定的操作直到处理完所有元素或操作抛出异常。
     *
     * @param action 要对每个元素执行的操作
     * @throws NullPointerException 如果指定的操作为 null
     */
    default void forEach(Consumer<? super T> action) {
        // 进行非空判断
        Objects.requireNonNull(action);
        // 遍历集合
        for (T t : this) {
            // 对每个元素执行给定的操作
            action.accept(t);
        }
    }

    /**
     * 创建一个{@link Spliterator}用于遍历此{@code Iterable}描述的元素。
     * 说明
     * 1. Spliterator是Java 8中新增的接口它是支持并行遍历的迭代器。
     * 2. Spliterator是splitable iterator的简称它是可分割迭代器。
     */
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

可见其中的 Iterator<T> iterator() 方法就是上一节中所讲的内容从源码中也不难看出其实 for-each 循环底层其实就是使用 Iterator 迭代器来完成元素的遍历的。

下面是一个简单案例

public class IterableTest {
    public static void main(String[] args) {
        // 创建集合
        Collection<String> collection = new ArrayList<>();

        // 添加元素
        collection.add("张三");
        collection.add("李四");
        collection.add("王五");
        
        // 使用增强for循环遍历集合
        for (String s : collection) {
            System.out.println(s);
        }
    }
}

通过查看编译后的 class 文件我们便能证实上述结论

2.3 List 集合

List 接口继承自 Collection 接口它表示一个有序的集合可以包含重复的元素。List 接口定义了一些与索引相关的操作如按索引访问元素、按索引插入元素、按索引删除元素等。

下面是一个简单的总结表格

特性	ArrayList	Vector	LinkedList	Stack
元素的顺序	插入顺序	插入顺序	插入顺序	LIFO先进后出
允许 null	是	是	是	是
线程安全	否	是	否	是
性能	高	中等	高	中等
基于	动态数组	动态数组	双链表	Vector
特殊功能	无	无	双端操作	出栈入栈

2.4 Set 集合

Set 接口继承自 Collection 接口它表示一个不允许包含重复元素的集合。Set 接口定义了一些与集合操作相关的方法如判断元素是否存在、添加元素、删除元素等。

下面是一个简单的总结表格

特性	HashSet	LinkedHashSet	TreeSet
元素的顺序	无序	插入顺序	有序
允许 null	是	是	是
性能	高	中等	较低
基于	HashMap	LinkedHashMap	TreeMap
特殊功能	无	记录插入顺序	排序

2.5 Queue

Queue 接口是 Java 中表示队列的一种抽象数据类型它遵循**先进先出FIFO**的原则提供了在队尾插入元素、在队头删除元素以及查看队头元素等操作常用于实现消息传递、任务调度等场景。

下面是一个简单的总结表格

特性 / 类型	LinkedList	ArrayDeque	PriorityQueue
底层数据结构	双向链表	动态数组环形	堆Heap
顺序	FIFOFirst-In-First-Out	FIFOFirst-In-First-Out	按照自然排序或比较器排序
允许null元素	是	否	否
多线程安全	否	否	否
主要功能	队列操作、栈操作、列表操作	队列操作、栈操作	优先级队列操作

3.Map 集合

Map 接口表示一组键值对的集合每个键对应一个值。Map 接口中的键是唯一的但值可以重复。Map 接口定义了一些与键值对操作相关的方法如根据键获取值、添加键值对、删除键值对等。

下面是一个简单的总结表格

特性	HashMap	Hashtable	LinkedHashMap	TreeMap	Properties
Key 的顺序	无序	无序	插入顺序或访问顺序	有序自然排序、定制排序	无序
允许 null 值	是	否	是	是	是
线程安全	否	是	否	否	是
性能	高	低	较高	低	中等
基于	Hash表	Hash表	Hash表+链表	红黑树	Hash表
特殊功能	无	无	记录插入顺序	排序	存储字符串