20分钟了解Java容器

介绍

上一篇讲完了Java基础的核心思想，这一篇主要介绍Java容器的概念，和主要容器的实现方式与其数据结构。

Java容器

Java 容器是 Java 集合框架（Java Collections Framework，简称 JCF）的核心组成部分，用于存储和操作一组数据对象。Java 容器提供了灵活的接口和实现类，支持各种数据结构，如列表、集合、映射、队列等。容器通常分为两类：Collection 容器和 Map 容器。

Collection容器

Collection 是 Java 容器的基础接口，表示一组对象的集合。Collection 容器包括三个主要子接口：List、Set 和 Queue。

List 接口

List 是一种有序的集合，允许重复元素。List 维护元素的插入顺序，支持基于索引的访问和操作。常见的实现类有：

• ArrayList：基于动态数组实现，支持快速随机访问，适合频繁读取和少量插入删除的场景。
• LinkedList：基于双向链表实现，适合频繁插入和删除操作的场景。
• Vector：类似于 ArrayList，但是线程安全的，已较少使用。

数据结构原理

1. ArrayList的动态数组

ArrayList的动态数组机制使得它在不确定集合大小的场景时非常适用，但扩展时会有额外的性能开销，因此初始化时预估合适的容量可以提高性能。

• 动态扩展机制
  • 检查容量 : 添加元素前，若空间足够则直接添加，若空间不足，则扩容。
  • 扩容 : 一般扩大1.5倍后，将现有元素复制到新数组中，通过System.arraycopy()实现。若新容量仍然不足以容纳即将添加的元素，则将其设置为所需的最小容量。
• 动态收缩机制
  • ArrayList不会自动收缩，可调用trimToSize()方法减小数组的占用空间。
• 时间复杂度
  • 添加单个元素的平均时间复杂度：O(1)
  • 扩容时的时间复杂度：O(n)

• 优化 : 每次扩容涉及大量的内存分配和数据复制操作，若能够预估存储的数据量，可以在初始化时指定初始容量来减少扩容次数。

• 场景示例
  • 存储和管理学生成绩，例如学校管理系统中，可能需要存储和管理大量学生的成绩。由于学生数量可能不固定，而且需要频繁地按照学生索引访问他们的成绩。
  • 实现简单的队列功能，例如在一些简单场景中，可以使用 ArrayList 实现一个基本的 FIFO（先进先出）队列。
  • 用作缓存，在缓存大小有限时，可以通过 remove 和 add 方法来维护缓存的最近使用状态。这种用法在需要对数据进行快速访问且能够容忍简单淘汰策略的场景中非常有效。

2. LinkedList的双向链表

链表数据结构，其中每个节点都包含对前一个节点和后一个节点的引用。这种结构允许我们从任意一个节点开始，既可以向前遍历链表，也可以向后遍历链表，它在需要多方向操作的应用中非常有用。

• 基本结构
  • 数据部分（data/item）：存储节点的实际数据。
  • 前驱指针（prev）：指向链表中前一个节点。
  • 后继指针（next）：指向链表中后一个节点。
• 实现原理(头结点/尾结点)
  • 头节点（first）：链表中的第一个节点，它的 prev 指针为 null。
  • 尾节点（last）：链表中的最后一个节点，它的 next 指针为 null。
• 场景示例
  • 浏览器的前进和后退功能，例如浏览器的历史记录管理，每个节点代表一个浏览历史中的页面，当前页面用一个指针（current）来表示。

3. Vector

与 ArrayList 类似，也是基于动态数组的实现，但有几个关键的区别和特点，使得它在某些场景中具有不同的使用价值。由于 Vector 是线程安全的，它适用于多线程环境下需要频繁修改和访问集合的场景。但是同步开销不小，所以适用于大多数单线程或读多写少的场景中。如果确实需要线程安全的集合，通常建议使用更灵活的同步策略，如 Collections.synchronizedList 或 CopyOnWriteArrayList。

• 特点
  • 同步 : Vector 的所有方法都是同步的synchronized，多个线程可以安全地同时访问和修改 Vector 对象，而不需要额外的同步控制。
  • 动态数组 : 与 ArrayList 的区别在于扩容两倍，并且可以控制扩容幅度，也就是指定增量大小。
  • API一致性 : Vector 类实现了 List 接口，因此它具有 List 的所有功能，如索引访问、遍历等。它也实现了 RandomAccess 接口，这意味着它支持快速随机访问元素。
• 场景示例
  • 多线程日志记录，例如在一个多线程应用中，多个线程可能会同时记录日志信息。如果所有线程都往一个共享的日志列表中添加日志记录，使用 Vector 能确保每条日志记录都能正确地添加到列表中。

Set 接口

Set 是一种不允许重复元素的集合，通常用于存储无序且唯一的对象。常见的实现类有：

• HashSet：基于哈希表实现，支持快速查找，可去重，但不保证顺序。
• LinkedHashSet：继承自 HashSet，维护元素的插入顺序。
• TreeSet：基于红黑树实现，元素按照自然顺序或指定的比较器排序。

数据结构原理

1. HashSet的哈希表

哈希表 是一种数据结构，用于根据键值对（key-value pairs）来存储数据。哈希表通过哈希函数将键映射到表中的一个位置(桶或槽)，如果该位置上存在元素，则表示发生冲突，解决冲突的办法例如找下一个空位，或者这个位置是一个链表，可以置于链表末端等等。使用场景通常包括需要唯一元素的集合、集合操作、去重等。

• 概念解释
  • 桶（Bucket）: 桶是哈希表中的一个存储位置，每个桶通常可以存放一个或多个数据项，具体取决于处理碰撞的策略。例如在链地址法中，每个桶会存储一个链表或其他数据结构（如平衡树）。在开放地址法中，每个桶直接存储数据。
  • 槽（Slot）: 槽通常指的是哈希表中的一个具体存储位置。
  • 链地址法（chaining）: 一种通过在哈希表的每个槽（slot）中存储一个链表来处理碰撞的方法。
  • 开放地址法（Open Addressing）: 通过在哈希表中寻找空桶来处理碰撞的方法。
• 哈希表原理
  • 哈希函数 : 将输入的键转换为一个哈希值，通常是一个整数，这个哈希值决定了数据存储的位置（索引）。理想的哈希函数能均匀的分布输入的键，以避免哈希冲突。
  • 哈希冲突 : 多个键映射到相同的位置。处理冲突的常见方法有“链地址法”（chaining）和“开放地址法”（open addressing）。
• 时间复杂度
  • 哈希表可以在 O(1) 时间内完成查找、插入和删除操作
• 场景示例
  • 日志系统，存储唯一的日志事件，以避免重复记录。
  • 数据清洗，在数据导入或处理过程中去除重复数据。
  • 跟踪唯一访问者，在网站分析中，需要跟踪唯一的访问者。例如，计算网站的独立访问用户数。

2. LinkedHashSet

实现了Set接口，并结合了HashSet和LinkedList的特点。与 HashSet 相比，LinkedHashSet 保留了元素的插入顺序。

• 特点
  • 使用双向链表维护元素顺序
  • 其余特性与HashSet一致

3. TreeSet的红黑树

红黑树是一种自平衡的二叉搜索树，它保证了在最坏情况下的操作时间复杂度为 O(log n)。

合法红黑树样例

• 性质
  1. 节点颜色 : 红色或黑色。
  2. 根节点 : 根节点是黑色。
  3. 叶子节点 : 所有叶子都是黑色的空节点。
  4. 红色节点 : 每个红色节点必须有两个黑色的子节点。(或者说从每个叶子到根的所有路径上不能有两个连续的红色节点) (或者说不存在两个相邻的红色节点，相邻指两个节点是父子关系) (或者说红色节点的父节点和子节点均是黑色的)
  5. 黑色高度 : 从任意节点到其所有叶子节点的路径中，必须包含相同数量的黑色节点。
• 自平衡原理 : 一般新增和删除的操作比较复杂，但时间复杂度也能保持在O(log n)
  1. 重新着色 :
     • 新增节点 : 需要查看父节点和叔叔节点(父节点的兄弟节点)的颜色，若两个都为红色，则重新着色
     • 将父节点和叔叔节点都改为黑色。
     • 将祖父节点改为红色。
     • 递归地对祖父节点进行修正（即将祖父节点作为新插入的节点来处理）。 - 删除节点 : 若其子节点是黑色（或树的黑色高度被破坏）时，通常需要通过重新着色和旋转操作来恢复树的性质。
  2. 旋转

左旋是指将一个节点的右子节点上升为其父节点的位置，而将原节点降到右子节点的左子节点位置。示例 : 假设我们要对节点 x 进行左旋。

    x
     \
      y
     / \
    T2  T3

左旋后：

    y
   / \
  x   T3
   \
    T2

右旋是指将一个节点的左子节点上升为其父节点的位置，而将原节点降到左子节点的右子节点位置。示例 : 假设我们要对节点 y 进行右旋。

    y
   /
  x
   \
    T2

右旋后：

    x
     \
      y
     /
    T2

• 红黑树有多种情况，具体操作新开一篇文章。

Queue 接口

Queue 是一种先进先出（FIFO）的集合，用于表示一组等待处理的元素。常见的实现类有：

• LinkedList：既是 List 的实现类，也是 Queue 的实现类，适合双端队列操作。
• PriorityQueue：基于优先级堆实现，元素按优先级排序，适合优先级队列的场景。

数据结构原理

1. LinkedList的双端队列

LinkedList 类不仅实现了 List 接口，还实现了 Deque 接口，因此它可以用作双端队列（Deque）。双端队列是一种可以在两端（即前端和后端）插入和删除元素的数据结构。它适用于需要双端访问功能的场景，比如实现队列和栈的混合功能，或在数据处理时需要在两端进行操作的情况。

• 特性
  • FIFO（First-In-First-Out）：当你从队列的一端插入元素，并从另一端删除元素时，表现为队列（Queue）的特性。
  • LIFO（Last-In-First-Out）：当你从同一端插入和删除元素时，表现为栈（Stack）的特性。
• 场景示例
  • 双端队列常用于缓存实现，尤其是最近最少使用（LRU）缓存。LRU 缓存使用双端队列来保持缓存的访问顺序：当访问某个缓存项时，将其移到队列的前端。当缓存满时，移除队列后端的最旧项。
  • 在任务调度系统中，双端队列可以用来实现优先级队列或工作队列。任务可以根据优先级被插入到队列的前端，而低优先级任务则被插入到后端。通过双端访问，可以高效地管理任务调度和执行。

2. PriorityQueue的优先级堆

PriorityQueue 通常使用 最小堆（min-heap）作为其底层数据结构。这意味着，堆的根节点总是具有最小的优先级值（对于自然排序的元素）或最高的优先级（对于自定义的比较器），从而使得每次访问或删除操作都能处理优先级最高的元素。

• 特性
  • 元素排序：PriorityQueue 内部使用堆（通常是最小堆）来实现优先级队列。在最小堆中，每个节点的值都小于或等于其子节点的值。这使得堆的根节点总是具有最小的值。
  • 无容量限制：PriorityQueue 的容量是动态调整的，只有在元素被插入时才分配内存。
  • 非线程安全：PriorityQueue 是非线程安全的。如果多个线程并发地访问同一个 PriorityQueue，并且至少有一个线程修改了队列，则需要进行外部同步。
• 场景示例
  • 图算法：如 Dijkstra 算法和 A* 算法中，优先队列用于处理图中的最短路径计算。
  • 事件处理：在事件驱动系统中，根据事件的优先级处理事件。
  • 带权排序：根据不同的权重（如任务的重要性、截止日期等）对元素进行排序。

Collection容器总结

接口	说明	常见实现类
List	有序的集合，允许重复元素。List 维护元素的插入顺序，支持基于索引的访问和操作	ArrayList(动态数组)、LinkedList(双向链表)、Vector(线程安全)
Set	不允许重复元素的集合，通常用于存储无序且唯一的对象	HashSet(哈希表)、LinkedHashSet(维护顺序)、TreeSet(红黑树)
Queue	先进先出（FIFO）的集合，用于表示一组等待处理的元素	LinkedList(双端队列)、PriorityQueue(优先级堆)

Map容器

Map 容器不属于 Collection 子接口。常见的实现类有：

• HashMap：基于哈希表实现，提供快速查找和插入，不保证顺序。场景示例如计数器、评率统计。
• LinkedHashMap：继承自 HashMap，维护元素的插入顺序或访问顺序。场景示例如序列化和反序列化(JSON 序列化)、数据库结果集处理、命令行参数解析。
• TreeMap：基于红黑树实现，键按自然顺序或指定的比较器排序。场景示例如数据库索引、词频统计、排序功能、范围查询。
• Hashtable：类似于 HashMap，但线程安全，性能较低，已较少使用。场景示例如线程安全的缓存、线程安全的配置管理。
• ConcurrentHashMap：线程安全的 HashMap，实现高效的并发访问。场景示例如并发任务调度(线程池的任务状态)、实时统计、高并发缓存、会话管理。

在Collection容器中介绍过相关数据结构原理，在此不重复介绍了。

容器的高级特性

• 迭代器：Java 容器支持使用迭代器（Iterator）进行遍历，提供安全的遍历操作。fail-fast 机制会在遍历过程中检测到集合被修改时抛出 ConcurrentModificationException。
• 泛型：Java 集合框架广泛使用泛型，提供类型安全的容器操作，减少类型转换的风险。
• 排序与搜索：Collections 工具类提供了对容器进行排序和搜索的静态方法，如 sort()、binarySearch() 等。

Map容器总结

实现类	说明	场景示例
HashMap	基于哈希表实现，提供快速查找和插入，不保证顺序	计数器、评率统计
LinkedHashMap	继承自 HashMap，维护元素的插入顺序或访问顺序	序列化和反序列化(JSON 序列化)、数据库结果集处理、命令行参数解析
TreeMap	基于红黑树实现，键按自然顺序或指定的比较器排序	数据库索引、词频统计、排序功能、范围查询
Hashtable	类似于 HashMap，但线程安全，性能较低，已较少使用	线程安全的缓存、线程安全的配置管理
ConcurrentHashMap	线程安全的 HashMap，实现高效的并发访问	并发任务调度(线程池的任务状态)、实时统计、高并发缓存、会话管理