Java 集合类总结

集合类是 Java 应用过程中最为核心的一部分，类似 C++ 的 STL，不仅在刷题的过程中十分常用，在日常工作生活中也常常使用。因此，我将 Java 集合类的内容进行了整理。参考内容在文末给出。

1. 集合容器概念

1.1 基本内容

什么是集合？

  • 集合框架：存储数据的容器。集合包括三个内容：接口（用于形成规范）、实现和算法。
  • 集合与数组的区别：集合用于封装对象（引用数据类型）；集合可以存放个数不确定的对象；集合可以存储不同数据类型的对象。

1.2 常用内容

常用集合类有哪些？

  • 所有集合类的父接口：Map 接口和 Collection 接口。
  • image-20210305101455639
  • image-20210305101517670

1.2.1 Collection 接口

Collection 接口：包含三种子接口 Set, List 和 Queue（注意还有一个 Queue）。

  • Set 子接口：无序，无重复，唯一性，只能插入一个 null。实现类有 HashSet, TreeSet。
  • List 子接口：有序，可重复，有索引，可以插任意个 null。实现类有 Stack, Vector, ArrayList, LinkedList。
  • Queue 子接口：队列。子接口有 BlockingQueue（普通队列） 和 Deque（双端队列）。注意，Stack 是 List 的实现类，而 Queue 是接口。

1.2.2 Map 接口

Map 接口：下面就是实现类。包含 HashMap, TreeMap, HashTable, LinkedHashMap, ConcurrentHahsMap。

  • 注意，Stack、Queue、Map 的位置。Python 中他们仨是并列的，而 Java 不是。
  • Stack 是 Collection 接口下的 List 接口的实现类；
  • Queue 是 Collection 接口的接口；
  • Map 是和 Collection 并列的接口，不属于 Collection。⭐

1.2.3 Collection 常用实现类

Set：

  • HashSet：基于 HashMap 实现。（常用）
  • LinkedHashSet：基于 LinkedHashMap 实现。可以记录插入顺序。
  • TreeSet：基于 TreeMap 实现。红黑树结构（自平衡排序二叉树）。（常用）

List：

  • ArrayList：Object 数组。（常用）
  • LinkedList：双向循环链表。（常用）
  • Vector：ArrayList 的线程安全版。
  • Stack：栈。

Queue：

  • LinkedList：队列。（常用）
  • PriorityQueue：不支持多线程的优先队列。
  • ArrayBlockingQueue：固定大小多线程阻塞式队列。
  • LinkedBlockingQueue：非固定大小多线程阻塞式队列。
  • ArrayBlockingDeque：类似 ArrayBlockingQueue 不过是双端队列。
  • LinkedBlockingDeque：类似 LinkedBlockingQueue 不过是双端队列。

1.2.4 Map 常用实现类

Map：

  • HashMap：字典。（常用）
  • LinkedHashMap：字典，可以记录插入顺序。
  • HashTable：HashMap 的线程安全版。（常用）
  • TreeMap：字典，红黑树。（常用）

1.3 面试问题

哪些集合是线程安全的？

  • 线程安全的有：Stack, HashTable, Vector（很少用，效率低）, Enumeration。

fail-fast 是啥？

  • 多线程同时改变集合时的错误检测机制。

怎么让集合不被修改？

  • Collections. unmodifiableCollection(Collection c) 创建只读集合。

2. Collection 接口

2.1 Iterator 接口

Iterator 接口是什么？

  • 定义：Iterator 接口提供了 Collection 接口的遍历。

  • List arrayListA = new ArrayList<>();
Iterator it = arrayListA.iterator();
while(it.hasNext()){
  System.out.println("Value is %d", it.next());
}

  • 特点：Iterator 只能单向遍历，但线程安全。

  • image-20210305104523056

  • Iterator 子类：ListIterator，可以双向遍历。Iterator 可以用于 Set 和 List, ListIterator 只能用于 List。

如何边遍历边删除集合内容？

  • 唯一方法：采用 Iterator 遍历，并用 Iterator.remove() 方法删除集合内容。

  • List arrayListA = new ArrayList<>();
Iterator it = arrayListA.iterator();
while(it.hasNext()){
  it.remove();
}

Collection 元素如何遍历？哪种最好？

  • 遍历方式有三种：for 循环遍历，迭代器遍历，foreach 遍历。
  • 哪种最好：Java Collection 提供了一个 RandomAccess 接口。如果实现类实现了这个接口，那么用 for 循环遍历效率也很高。否则用迭代器遍历和 foreach 遍历效率更高。

2.2 List 接口

List 通用的常用方法有哪些？

  • 常用方法：isEmpty, indexOf, contains, iterator, clear, clone, size, toArray, hashCode。

2.2.1 ArrayList 常用方法

常用方法：增删改查方法是 add, remove, set, get。⭐

  • 增：add。
  • 删：remove。
  • 改：set。
  • 查：get。

2.2.2 LinkedList 常用方法

常用方法：增删改查方法是 add, offer, push, poll, pop, remove, set, get, peek。⭐

  • 增：add, offer, push。
  • 删：poll, pop, remoe。
  • 改：set。
  • 查：get, peek。
  • 当然还有很多变种的，结尾加 First, Last 即可。

2.2.3 Stack 常用方法

常用方法：增删改查方法是 push, pop, peek, search。

  • 增：push。

  • 删：pop。

  • 改：没有（naidesu 悲）。

  • 查：peek, search。

  • Stack 就这几种方法，没有其他 List 的公用方法。还有一个判断方法 empty。

2.2.4 Array 和 List 转换

数组转换为 List：

  • // Collections.toArray() 用法：
Integer[] array = new Integer[list.size()];
list.toArray(array); // 用法1：list.toArray(目标数组)
array = list.toArray(new Integer[0]); // 用法2：a = list.toArray(new Type[0]) 利用 new Type[0] 转换 Object 类型
array = list.toArray((Integer[]) new Object(list.size)) // 用法3：a = list.toArray((Type[]) new Object(list.size())) 利用 (Type[]) 强制类型转换

List 转换为数组：

  • //Arrays.asList() 用法：
Integer[] array = {1, 2, 3}; // 源数组必须为包装类数组
List list = Arrays.asList(array); // 用法1：直接调用 Arrays.asList()
List list = new ArrayList<>(Arrays.asList(array)); // 用法2：利用 new Type<>() 修改 Arrays.asList 的类型

2.2.5 其他

多线程情况下如何使用 ArrayList？

  • 可以通过 Collections.synchronizedList 方法，将 arrayListA 转换为线程安全的 arrayListB。

  • List arrayListB = Collections.synchronizedList(arrayListB);

2.3 Set 接口

2.3.1 Set

Set 通用的常用方法有哪些？

  • 常用方法：isEmpty, contains, iterator, clear, clone, size, hashCode。
  • 特点：增删方法都是 add, remove。没有改查方法。⭐

2.3.2 TreeSet

TreeSet 就是红黑树结构的 Set。在增删改查方面是 O(log n) 的二分法复杂度。

TreeSet 是基于 HashSet 实现的，同时又是基于 TreeMap 实现的。

TreeSet 常用的方法有哪些？

  • 常用方法：floor, lower, ceiling, higher, first, last。
    • 更小一点的：floor, lower。
    • 更大一点的：ceiling, higher。
    • 头尾：first, last。

hashCode 和 equals 方法有什么关系？equals 和 == 又有什么关系？

  • equals 用于判断值是否相等。
  • == 用于判断地址是否相等。
  • hashCode。如果 equals，hashCode 一定相等。如果 hashCode 相等，不一定 equals。

2.3.3 HashSet

HashSet 是哈希结构的 Set。

HashSet 的常用方法和 TreeSet 差不多，但是没有 floor, lower, ceiling, higher, first, last。

2.4 Queue 接口

2.4.1 Queue 系列常用方法

常用方法：增删改查方法是 add, offer, push, poll, pop, remove, set, get, peek。⭐

  • 增：add, offer, push。
  • 删：poll, pop, remove。
  • 改：set。
  • 查：get, peek。
  • 当然还有很多变种的，结尾加 First, Last 即可。

poll 和 remove 有什么区别？

  • 队列为空时，poll 返回 null，remove 报错。

3. Map 接口

3.1 Map 系列常用方法

常用方法：增删改查是 put, remove, replace, get, getOrDefault, containsKey, containsValue。

  • 增：put。

  • 删：remove。

  • 改：replace。

  • 查：get, getOrDefault, containsKey, containsValue。

  • put 和 replace 效果相同，可以多用 put。

  • 其他常用方法：entrySet, keySet, values, isEmpty, contains, iterator, clear, clone, size, hashCode。

  • 遍历常用方法：entrySet, KeySet, values。

参考内容

  1. Java 集合容器面试题（2020最新版）
  2. Java Platform SE 8