Java 集合框架总览

总览图

以下是 Java 集合框架的uml类图：

实现类介绍

以下是 Java 集合框架中一些常见实现类的特点和实现原理：

1. ArrayList

• 特点
  • 动态数组：它是基于动态数组实现的，支持随机访问，通过索引可以快速定位元素，时间复杂度为 。
  • 可扩容：当数组空间不足时，会自动进行扩容操作，一般是扩容为原来容量的 1.5 倍。
  • 有序性：元素按照插入顺序排列。
  • 允许重复元素和 null 值。
• 实现原理
  • 内部维护一个 Object 类型的数组，当添加元素时，如果数组容量不足，会创建一个新的更大的数组，并将原数组中的元素复制到新数组中。
  • 随机访问时，直接根据索引访问数组对应位置的元素。

2. LinkedList

• 特点
  • 双向链表：基于双向链表实现，插入和删除操作效率较高，特别是在链表头部和尾部进行操作，时间复杂度为 。
  • 不支持随机访问：随机访问元素时，需要从头或尾开始遍历链表，时间复杂度为 。
  • 有序性：元素按照插入顺序排列。
  • 允许重复元素和 null 值。
• 实现原理
  • 内部维护了一个双向链表，每个节点包含数据、指向前一个节点的引用和指向后一个节点的引用。
  • 插入和删除操作只需要修改相邻节点的引用关系。

3. Vector

• 特点
  • 动态数组：和 ArrayList 类似，也是基于动态数组实现的。
  • 线程安全：它的大部分方法都使用了 synchronized 关键字进行同步，保证在多线程环境下的线程安全，但这也导致了性能开销较大。
  • 可扩容：当数组空间不足时，会自动进行扩容操作，默认扩容为原来容量的 2 倍。
  • 有序性：元素按照插入顺序排列。
  • 允许重复元素和 null 值。
• 实现原理
  • 内部维护一个 Object 类型的数组，和 ArrayList 扩容机制类似，但扩容倍数不同。
  • 方法使用 synchronized 进行同步，保证线程安全。

4. Stack

• 特点
  • 后进先出（LIFO）：继承自 Vector，遵循后进先出的原则，支持 push（入栈）、pop（出栈）、peek（查看栈顶元素）等操作。
  • 线程安全：由于继承自 Vector，所以也是线程安全的。
• 实现原理
  • 基于 Vector 实现，通过调用 Vector 的方法来实现栈的操作，例如 push 方法调用 addElement 方法，pop 方法调用 removeElementAt 方法。

5. HashSet

• 特点
  • 无序性：不保证元素的插入顺序，元素的存储顺序是由哈希值决定的。
  • 唯一性：不允许存储重复元素，通过元素的 hashCode() 和 equals() 方法来判断元素是否重复。
  • 允许 null 值：但只能有一个 null 值。
• 实现原理
  • 内部基于 HashMap 实现，HashSet 中的元素实际上是存储在 HashMap 的键中，HashMap 的值统一为一个静态的 Object 对象。
  • 插入元素时，先计算元素的哈希值，根据哈希值找到对应的桶位置，如果桶为空，则直接插入；如果桶不为空，则通过 equals() 方法比较元素是否重复，不重复则插入。

6. TreeSet

• 特点
  • 有序性：根据元素的自然顺序或指定的比较器进行排序，元素会按照排序后的顺序存储。
  • 唯一性：不允许存储重复元素，通过元素的比较结果来判断元素是否重复。
  • 不允许 null 值：因为需要对元素进行比较排序。
• 实现原理
  • 内部基于 TreeMap 实现，TreeSet 中的元素实际上是存储在 TreeMap 的键中，TreeMap 的值统一为一个静态的 Object 对象。
  • TreeMap 基于红黑树实现，插入元素时，会根据元素的比较结果将元素插入到红黑树的合适位置，保证树的平衡和有序性。

7. LinkedHashSet

• 特点
  • 有序性：保证元素的插入顺序，即元素按照插入的先后顺序存储。
  • 唯一性：不允许存储重复元素，通过元素的 hashCode() 和 equals() 方法来判断元素是否重复。
  • 允许 null 值：但只能有一个 null 值。
• 实现原理
  • 内部基于 LinkedHashMap 实现，LinkedHashSet 中的元素实际上是存储在 LinkedHashMap 的键中，LinkedHashMap 的值统一为一个静态的 Object 对象。
  • LinkedHashMap 维护了一个双向链表，用于记录元素的插入顺序。

8. HashMap

• 特点
  • 键值对存储：以键值对（key - value）的形式存储数据，每个键是唯一的。
  • 无序性：不保证元素的插入顺序，元素的存储顺序是由键的哈希值决定的。
  • 允许 null 键和 null 值：但 null 键只能有一个。
• 实现原理
  • 内部基于哈希表实现，哈希表是一个数组，数组的每个元素是一个链表或红黑树（当链表长度超过 8 且数组长度大于 64 时，链表会转换为红黑树）。
  • 插入元素时，先计算键的哈希值，根据哈希值找到对应的桶位置，如果桶为空，则直接插入；如果桶不为空，则遍历链表或红黑树，通过 equals() 方法比较键是否重复，不重复则插入。

9. TreeMap

• 特点
  • 键值对存储：以键值对（key - value）的形式存储数据，每个键是唯一的。
  • 有序性：根据键的自然顺序或指定的比较器进行排序，键会按照排序后的顺序存储。
  • 不允许 null 键：因为需要对键进行比较排序。
• 实现原理
  • 内部基于红黑树实现，红黑树是一种自平衡的二叉搜索树。
  • 插入元素时，根据键的比较结果将元素插入到红黑树的合适位置，保证树的平衡和有序性。

10. LinkedHashMap

• 特点
  • 键值对存储：以键值对（key - value）的形式存储数据，每个键是唯一的。
  • 有序性：可以保持插入顺序或访问顺序，当 accessOrder 为 false 时，按照插入顺序；为 true 时，按照访问顺序（每次访问元素后，该元素会被移动到链表尾部）。
  • 允许 null 键和 null 值：但 null 键只能有一个。
• 实现原理
  • 内部基于哈希表和双向链表实现，哈希表用于快速查找键值对，双向链表用于记录元素的顺序。
  • 插入元素时，先计算键的哈希值，根据哈希值找到对应的桶位置，如果桶为空，则直接插入；如果桶不为空，则遍历链表或红黑树，通过 equals() 方法比较键是否重复，不重复则插入，并更新双向链表的顺序。

11. Hashtable

• 特点
  • 键值对存储：以键值对（key - value）的形式存储数据，每个键是唯一的。
  • 线程安全：它的大部分方法都使用了 synchronized 关键字进行同步，保证在多线程环境下的线程安全，但这也导致了性能开销较大。
  • 不允许 null 键和 null 值。
• 实现原理
  • 内部基于哈希表实现，和 HashMap 类似，但方法使用 synchronized 进行同步，保证线程安全。

12. WeakHashMap

• 特点
  • 键值对存储：以键值对（key - value）的形式存储数据，每个键是唯一的。
  • 弱引用键：键是使用弱引用存储的，当键所引用的对象被垃圾回收时，对应的键值对会自动从 WeakHashMap 中移除。
  • 允许 null 键和 null 值：但 null 键只能有一个。
• 实现原理
  • 内部基于哈希表实现，键使用 WeakReference 进行包装，当键所引用的对象被垃圾回收时，WeakReference 会被加入到引用队列中，WeakHashMap 会定期检查引用队列，将对应的键值对从哈希表中移除。

13. Properties

• 特点
  • 键值对存储：继承自 Hashtable，以键值对（key - value）的形式存储数据，键和值都是 String 类型。
  • 常用于配置文件：可以方便地从文件中加载配置信息，也可以将配置信息保存到文件中。
• 实现原理
  • 基于 Hashtable 实现，提供了一些方便的方法来处理 String 类型的键和值，例如 load 方法用于从文件中加载配置信息，store 方法用于将配置信息保存到文件中。