Java集合框架

Java集合学习

0 引言

大家都学过数据结构这门课，应该对数据的基本存储和组织方式有一定的概念了吧。我们可以把大量的数据的存储到“容器”里，这里的“容器”就是一种被封装起来的数据结构，为我们提供了很多便捷好用的接口，而将内部的实现细节给隐藏起来了。

打个比方，我们使用电饭煲做饭，可以把电饭煲看作是容器，只需要知道怎么打开电饭煲把米放进去，按哪个按钮开始做饭，怎么把盖子打开把饭盛出来，这些就是电饭煲为我们提供的接口。而我们不需要了解电饭煲内部的电路结构，使用什么电子元件，盖子的机械传动结构是什么样的，这些是被隐藏起来的实现细节。

当我们用 C 语言写链表时，会先定义一个长这样的结构体：

typedef struct Node {
    ElementType val;
    struct Node * next;
} *List;

然后在程序里各种malloc函数、next指针满天飞，跑起来就空指针野指针程序崩溃是吧。

当然我们也可以将写的链表操作封成函数，类似这样：

void insertList(List L, int idx, ElementType e);
void removeNode(List L);
List find(List L, ElementType e);

这些是我们自己写的链表函数，用函数来实现链表的功能，一是方便 debug，二是可以让程序更有条理。C 毕竟还只是面向过程的编程语言，而封装到极致就进化成了面向对象。

再比如，做编程题的时候，要写一个栈，于是你上来就开一个大小 100005 的数组，再设一个全局变量 top。真要写大工程的时候是万万不能这样搞的，尤其不能动不动就设全局变量。

在 C++ 中就友好多了，C++ 提供了很多拿来就用的容器，比如可变数组 vector、栈 stack、字典 Map等等。而到了 Java 这边，容器更要复杂而精致得多。

1 集合框架概述

集合框架的四部分：

• 数据结构
• 比较器
• 算法：Collections 和 Arrays；
• 迭代器

集合类的特点：

• 只容纳对象，基本数据类型要封装成类的对象；

---

Java 中的集合框架为我们提供了各种各样的容器类，每一种容器都有各自的性质，当然底层的实现方式也不尽相同，因此其使用方式、操作效率和安全性也不一样。

同时 Java 中的容器还具有能动态增长、高性能、提供丰富的方法等特点，很方便用户使用。

继承是面向对象语言的一大特点，而不同的容器也是有继承关系的，就好像生物学中的分类一样。Java 的所有容器都发源于 Iterable 接口，从 Iterable 接口又分出两大派系（接口），一是每个单元格存储数据本身的 Collection 接口，二是单元格需要存储键值对（<key, value>）的 Map 接口。其它的容器类或接口都是继承或实现了这两个接口。下面用一张图来说明一下 Java 容器的家族关系：

Java集合框架关系

？？？怎么这么多啊

其实很多细节我们也用不上在这篇文章也不会详细介绍，用到了就查官方文档吧。下面就一些重要的部分简单说一下：

• Collection 接口：
  • List 接口：数据被组织为线性结构，每一个元素在容器中有固定的位置，可以通过索引访问；
  • Queue 接口：队列，可以往里放元素，但是只有一个出口
    • PriorityQueue：优先队列，每次只能弹出或访问权值最大（或小）的元素；
    • Deque：双端队列，两头都可以进出元素。
  • Set 接口：每个元素无固定位置，元素不能重复，因此元素必须实现 equals() 方法
    • SortedSet：可以有序遍历的集合；
• Map：
  • HashMap：哈希实现的 <key, value> 集合，高效插入查找；
  • SortedMap：同样是 <key, value> 集合，但是内部存储从某种程度来说是有序的，方便遍历。

这些多种多样的容器跟比较器（Comparable、Comparator）、算法（Collactions、Arrays）、迭代器（Iterator）共同组成了 Java 的集合框架。

下面的内容便是对这部分的较为详细的介绍。

2 容器

2.1 泛型

Java 5 之前的容器都是放的 Object 类的对象作为元素，一旦被放进去就会被自动转型。虽然什么都能往里面放，但是拿出来的话那个对象也不是原来的对象了，就需要强制转回原来的类才能用。但是这样操作不仅麻烦，而且很容易在运行时由于转换错误抛出运行时异常。所以 Java 5 及之后的版本使用泛型来解决这个问题。

在声明一个容器的时候必须指定容器内元素的类型：

ArrayList<Integer> arrayList = new ArrayList<>();
				// 声明一个存放整数的可变数组

HashMap<String, Object> hashMap = new HashMap<>();	
				// 声明一个以 String 为键, Object 为值的哈希表

注意：

• 泛型中不能使用基本类型，但可以用其对应的类，比如 Integer 存整数，Boolean 存布尔变量；
• 声明好的容器可以存放声明类型的子类，比如声明成 Object 类就可以放任何类。
• 泛型中也可以使用接口，里面的可以存放实现该接口的子类。

2.2 Collection 接口

直接说一下这个接口里的常用方法吧：

• int size()：返回元素个数；
• boolean isEmpty()：返回是否空；
• boolean add(E e)：加入一个元素，返回是否成功；
• boolean remove(Object o)：删除一个元素，返回是否成功；
• boolean contains(Object o)：返回是否含有某个元素，调用 equals() 方法作比较；
• boolean addAll(Collection<? extends E> c)：加入 c 中的所有元素，返回是否成功；
• boolean removeAll(Collection<?> c)：删除 c 中的所有元素，返回是否有元素被删除；
• boolean containsAll(Collection<?> c)：检查是否含有 c 中的所有元素；
• Iterator<E> iterator()：返回一个迭代器；
• Object[] toArray()：返回一个数组，存放里面的元素；
• <T> T[] toArray(T[] a)：
  • 首先将集合中的元素造型为 T；
  • 若 a 的大小足以容纳集合中的元素，则将 a 中填为集合中的元素，同时返回 a 本身；
  • 否则另开一个数组填为集合中的所有元素并返回。

    Collection<Object> collection = new Collection<>();
    String[] strings = collection.toArray(new String[5]);

• default boolean removeIf(Predicate<? super E> filter)：传进一个谓词 filter，符合该条件的元素被删除，返回是否有元素被删除；
• boolean retainAll(Collection<?> c)：仅保留 c 中含有的元素，返回是否有元素被删除；
• void clear()：清除集合。

2.1.1 List

• default void replaceAll(UnaryOperator<E> operator)：传一个操作类的对象 UnaryOperator，对每一个元素施以这个操作。
• default void sort(Comparator<? super E> c)：传一个比较器，进行排序；
• E get(int index)：取得指定位置的元素；
• E set(int index, E element)：将指定位置位置的元素替换为 element；
• void add(int index, E element)：向指定位置插入一个元素；
• E remove(int index)：删除指定位置的元素；
• int indexOf(Object o)：查找第一次出现的位置；
• int lastIndexOf(Object o)：查找最后一次出现的位置；
• ListIterator<E> listIterator()：返回一个迭代器；
• ListIterator<E> listIterator(int index)：返回值定位置的迭代器。

2.1.1.1 ArrayList

动态数组，顺序存储，每次扩张容量增大 50%。

• public ArrayList(int initialCapacity)：构造函数，初始化大小；
• public ArrayList()：构造函数，默认大小为 10；
• public ArrayList(Collection<? extends E> c)：从 c 中初始化；
• public void trimToSize()：将容器占用空间收缩至长度；
• public void ensureCapacity(int minCapacity)：扩大大小至 minCapacity。
• public List<E> subList(int fromIndex, int toIndex)：返回子列。

2.1.1.2 LinkedList

链式存储，也可以快速删除首尾元素。

• public LinkedList()：构造空链表；
• public LinkedList(Collection<? extends E> c)：从 c 中初始化；
• public E getFirst()：获取头部；
• public E getLast()：获取尾部；
• public E removeFirst()：删除头部；
• public E removeLast()：删除尾部；
• public void addFirst(E e)：从头部添加；
• public void addLast(E e)：从尾部添加。

2.1.1.3 Vector

ArrayList 的线程安全版，但是效率不如 ArrayList。

2.1.2 Set

元素必须唯一，所以里面的元素必须定义 equals() 方法。不允许添加重复的元素。

方法与 Collection 相同，只是当插入失败（试图插入重复元素）时 add() 方法会返回 false。

2.1.2.1 HashSet

初始化时可以规定大小，也可以从某集合初始化，是无序的。

2.1.2.2 TreeSet

初始化时可以规定大小，也可以从某集合初始化，是有序的。

• public Iterator<E> descendingIterator()：返回一个降序的迭代器；
• public NavigableSet<E> descendingSet()：返回降序的集合；
• public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)：返回从 fromElement 到 toElement 子集合；
• public NavigableSet<E> headSet(E toElement, boolean inclusive)：返回从头到 toElement 的自集合；
• public NavigableSet<E> tailSet(E fromElement, boolean inclusive)：返回从 fromElement 到尾的子集合；
• public Comparator<? super E> comparator()：返回比较器；
• public E first()：返回首个元素；
• public E last()：返回最后一个元素；
• public E lower(E e)
• public E floor(E e)
• public E ceiling(E e)
• public E higher(E e)
• public E pollFirst()
• public E pollLast()

2.1.3 Queue

• boolean add(E e)：加入一个元素，容量满会异常；
• boolean offer(E e)：功能同 add()，插入失败会返回 false 而不会异常；
• E remove()：返回并删除队头，队列为空则异常；
• E poll()：返回并删除队头，队列为空返回 null，不会异常；
• E element()：取队首元素，队列为空则异常；
• E peek()：取队首元素，队列为空则返回 null 不会异常。

2.3 Map 接口

其含有的方法如下：

• int size()
• boolean isEmpty()
• boolean containsKey(Object key)
• boolean containsValue(Object value)
• V get(Object key)
• V put(K key, V value)
• V remove(Object key)
• void putAll(Map<? extends K, ? extends V> m)
• void clear()
• Set<K> keySet()
• Collection<V> values()
• Set<Map.Entry<K, V>> entrySet()：返回一个集合。

2.3.1 HashMap

方法基本同上。可以从一个 Map 初始化。

2.3.2 TreeMap

使用红黑树存储便于遍历。

3 比较器

Java 中要实现自动排序需要定义比较器，对于 String 和包装类有自动的比较器，但是对于其他类就需要使用我们自己定义的比较器了。要实现比较功能，可以实现 Comparable 接口或定义 Comparator 类。

3.1 Comparable 接口

自定义类可以实现 Comparable<E> 接口，其中 E 为自定义类，同时类中必须实现 compareTo 方法，例如：

class Cell implements Comparable<Cell>{
    private final int id;

    public Item(int id) {
        this.id = id;
    }


    @Override
    public int compareTo(Item o) {
        return this.id - o.id;
    }
}

3.2 Comparator 类

在使用一些容器的 sort() 方法之前，需要定义一个 Comparator 类作为参数传入，定义可以是这样：

Comparator<Cell> comparator = new Comparator<Cell>() {
    @Override
    public int compare(Cell o1, Cell o2) {
        ...;
        return o1.compareTo(o2);
    }
};
arrayList.sort(comparator);

当然可以用 lambda 表达式化简：

Comparator<Cell> comparator = (o1, o2) ->{
    ...;
    o1.compareTo(o2)
};

当只是调用到 Cell 的一个函数时，可以用方法的引用进一步化简：

Comparator<Cell> comparator = Cell::compareTo;

以至于你在使用容器的排序方法时可以：

arrayList.sort(Cell::compareTo);

4 迭代器 Iterator

迭代器是用于容器的遍历的，对于一个容器，遍历方法通常有以下三种：

• for 循环遍历：

for (int i = 0; i < array.size(); i++) {
    System.out.println(array.get(i));
}

• 增强型 for 循环：

for (Cell cell : array) {
    System.out.println(cell);
}

• 迭代器遍历

下面将要细说迭代器是怎么用的了。

4.1 初始化迭代器

调用容器的返回迭代器的方法即可获得一个迭代器，如：

Iterator<Cell> iterator = array.iterator();

4.2 迭代器的方法

• boolean hasNext()：判断迭代器是否到达末尾（此时指的是一个空元素）；
• next()：返回迭代器所指的成员，并且自身后移一位；
• default void remove()：删除迭代器所指的前一个元素，要跟在 next() 后面，且每调用一次 next() 最多只能删除一次。

示例：

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(15);
Iterator<Integer> iterator = arrayList.iterator();
while (iterator.hasNext()) {
    Integer i = iterator.next();
    if (i < 10)
        iterator.remove();
}
System.out.println(arrayList);

4.3 ListIterator

相比于一般的 Iterator，ListIterator 可以前向遍历，也可以返回所指元素的的位置，具体方法见文档。

5 算法类

Java 的集合架构提供了两个功能强大的算法库 Collections 和 Arrays，用这两个库可以在集合上进行排序、序列化等等操作。

5.1 Collections

• void sort(List<T> list)：对 list 进行排序，要求其中的元素 T 必须实现了 Comparable 接口，重写 compareTo 方法；
• void sort(List<T> list, Comparator<? super T> c)：当 list 没有实现 Comparable 接口时，可以传入一个 Comparator 进行排序操作；
• int binarySearch(List<? extends Comparable<? super T>> list, T key)：对一个实现了 Comparable 的有序 list 进行二分查找，返回第一个找到的元素的下标；
• int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)：二分查找，传入一个比较器；
• void reverse(List<?> list)：翻转 list；
• void shuffle(List<?> list)：打乱 list；
• void shuffle(List<?> list, Random rnd)：以 rnd 为种子打乱 list；
• void swap(List<?> list, int i, int j)：交换两个元素的位置；
• void fill(List<? super T> list, T obj)：将所有元素都赋为 obj；
• void copy(List<? super T> dest, List<? extends T> src)：将 src 的内容拷贝到 dest 中；
• T min(Collection<? extends T> coll)：获得最小值，coll 要实现 Comparable 接口；
• T min(Collection<? extends T> coll, Comparator<? super T> comp)：根据 comp 获得最小元素；
• T max(Collection<? extends T> coll)：获得最大元素；
• T max(Collection<? extends T> coll, Comparator<? super T> comp)：获得最大元素；
• void rotate(List<?> list, int distance)：可以理解为循环列表的整体平移操作；
• boolean replaceAll(List<T> list, T oldVal, T newVal)；
• int indexOfSubList(List<?> source, List<?> target)：查找字列；
• int lastIndexOfSubList(List<?> source, List<?> target)：找最后一个字列；

5.2 Arrays

这个类中的方法都是对数组进行操作的。

• void sort()：可以对基本类型的数组进行排序，也可以排自定义类的数组，也可以传入 Comparator，还可以指定排序的起始和终止位置；
• void parallelSort()：归并排序；
• int binarySearch()：二分查找；
• boolean equals()：判断两数组是否相等；
• void fill()：将数组用 obj 填满；
• T[] copyOf(T[] original, int newLength)：深拷贝；
• T[] copyOfRange(T[] original, int from, int to)：区间深拷贝；
• List<T> asList(T... a)：转 ArrayList；