java集合框架概要

• Collection（单列集合）

  • Set (无序，不重复，无索引)
    • TreeSet 基于红黑树实现，元素是有序的，并且不允许重复。它的操作时间复杂度为 O(log n)。
    • HashSet 基于哈希表实现，不保证元素的顺序，查找、插入和删除操作的时间复杂度为 O(1)。
      • LinkedHashSet 继承自 HashSet，它保持元素的插入顺序（通过双向链表实现）。
  • List (有序，可重复，有索引)
    • ArrayList 基于动态数组实现，支持快速随机访问，但插入和删除操作可能比较慢，特别是在数组中间。
    • Vector 类似于 ArrayList，但它是同步的，因此线程安全；现在推荐使用 ArrayList。
    • LinkedList 基于双向链表实现，支持快速插入和删除，但随机访问较慢
    • Stack 继承自 Vector，实现了后进先出（LIFO）栈结构的方法，如 push()、pop() 等。
  • Queue (队列，先进先出)
    • LinkedList 不仅实现了 List 接口，还实现了 Queue 接口，可以作为队列使用。
    • PriorityQueue 一个基于堆实现的优先队列，不保证元素的插入顺序，而是根据元素的自然顺序或通过构造函数提供的比较器来排序。
    • ArryDeque 基于数组实现的双端队列，支持高效的头尾操作，不支持线程安全。
  • Deque (双端队列)
    • ArryDeque 可以作为双端队列使用，支持从两端插入和删除元素。
    • LinkedList 同样实现了 Deque 接口，可以作为双端队列使用。
  • 其他接口
    • CopyOnWriteArrayList 线程安全的 ArrayList 实现，适用于读多写少的场景。
    • CopyOnWriteArraySet 线程安全的 HashSet 实现，适用于读多写少的场景。

• Map（单列集合）

  • TreeMap 基于红黑树实现，按键的自然顺序或构造时指定的比较器排序，键不允许为 null。
  • HashMap 基于哈希表实现，提供快速的键值对查找、插入和删除操作。键和值均可以为 null
  • HashTable 基于哈希表实现，线程安全的 Map，不推荐使用，已被 HashMap 和 ConcurrentHashMap 替代。
  • LinkedHashMap 基于哈希表和双向链表实现，保持元素的插入顺序或访问顺序。
  • ConcurrentHashMap 线程安全的 Map 实现，适用于并发环境。

---

Java 数据结构体系思维导图

                          ┌───────────────────────────────────┐
                          │         Java 数据结构体系         │
                          └───────────────────────────────────┘
                                    │
              ┌────────────────────┼────────────────────┐
         ┌────┴────┐         ┌────┴────┐          ┌────┴────┐
      线性数据结构    非线性数据结构    映射与集合   辅助数据结构与工具类
         │                │             │                 │
   ┌─────┴─────┐    ┌────┴─────┐    ┌────┴─────┐       ┌────┴────┐
  数组与列表  队列与栈  集合（Set）  映射（Map）   树与图    特殊数据结构
       │             │             │                 │
  ┌────┴─────┐  ┌────┴─────┐  ┌────┴─────┐         ┌────┴────┐
  数组        List          Queue        Set       HashMap   特殊工具类
                           Stack           TreeMap   PriorityQueue
                                          TreeSet    LinkedHashMap

详细分类和内容说明：

1. 线性数据结构

这些数据结构的元素按顺序排列，并且通常支持按位置访问或插入/删除元素。

数组（Array）

• 固定大小，元素类型相同。
• 支持按索引快速访问。

列表（List）

• 有序集合，允许重复。
• 典型实现：ArrayList, LinkedList

ArrayList：基于数组实现，支持快速随机访问。

LinkedList：基于链表实现，支持高效的插入/删除操作。

2. 非线性数据结构

这些数据结构的元素不按顺序排列，而是根据某种层级或关系组织的。

树（Tree）

• 每个节点最多有一个父节点，但可以有多个子节点。
• 二叉树（Binary Tree）：每个节点最多有两个子节点。
• 二叉搜索树（Binary Search Tree）：左右子树的元素有大小顺序。
• 平衡二叉树：例如 AVL 树、红黑树。
• 堆（Heap）：完全二叉树，用于实现优先队列。
• Trie（字典树）：用于字符串查找。

图（Graph）

• 由节点（顶点）和连接节点的边组成。
• 无向图与有向图：边的方向决定了图的类型。
• 加权图与无权图：边可以有权重。
• 图的常见表示方式：邻接矩阵、邻接表。

3. 映射与集合

这些数据结构管理键值对（Map）或唯一的元素（Set），并提供高效的查找、插入和删除操作。

映射（Map）

存储键值对，键是唯一的。

HashMap：基于哈希表实现，时间复杂度 O(1)。

LinkedHashMap：基于哈希表并保持插入顺序。

TreeMap：基于红黑树实现，按键排序，时间复杂度 O(log n)。

WeakHashMap：弱引用实现的映射，允许垃圾回收回收键。

集合（Set）

存储唯一的元素。

HashSet：基于哈希表实现，元素无序。

LinkedHashSet：基于哈希表实现，元素有序（插入顺序）。

TreeSet：基于红黑树实现，元素自动排序。

EnumSet：用于枚举类型的集合。

4. 队列与栈

这些数据结构通常用于处理元素的顺序，遵循特定的插入/删除规则。

队列（Queue）

先进先出（FIFO）顺序。

LinkedList：支持队列操作。

ArrayDeque：双端队列，提供更高效的队列操作。

PriorityQueue：优先队列，按优先级顺序处理元素。

栈（Stack）

后进先出（LIFO）顺序。

Stack：实现栈的基本操作。

Deque：双端队列也可以实现栈。

5. 辅助数据结构与工具类

这些数据结构和工具类用于解决特定问题或提供辅助功能。

特殊数据结构

LinkedList：既可以作为队列，也可以作为栈。

PriorityQueue：优先队列，用于按优先级处理元素。

Deque：双端队列，支持从两端插入和删除。

工具类

Collections：提供对集合框架的各种操作（如排序、查找、反转等）。

Arrays：提供对数组的各种操作（如排序、搜索等）。

BitSet：用于存储位集（布尔值集合）。