高清图解28个高并发之数据结构/数据结构场景匹配技巧分析(高并发精通篇三)

标签：插入 元素 28 链表 并发 键值 哈希 数据结构 节点

Java中的Map家族包括基于哈希表的HashMap，维护插入顺序的LinkedHashMap，基于红黑树的TreeMap，线程安全的Hashtable和ConcurrentHashMap，以及基于身份比较的IdentityHashMap和基于弱引用的WeakHashMap。Queue家族则涵盖了Vector、Stack、Properties以及多种List和Deque实现，适用于不同的数据管理和并发处理场景。

肖哥弹架构 跟大家“弹弹” 高并发锁， 关注公号回复 ‘mvcc’ 获得手写数据库事务代码

欢迎 点赞，关注，评论。

关注公号Solomon肖哥弹架构获取更多精彩内容

历史热点文章

• 解锁大语言模型参数：零基础掌握大型语言模型参数奥秘与实践指南
• 高性能连接池之HikariCP框架分析：高性能逐条分解(架构师篇)
• 缓存雪崩/穿透/击穿/失效原理图/14种缓存数据特征+10种数据一致性方案
• Java 8函数式编程全攻略：43种函数式业务代码实战案例解析(收藏版)
• 一个项目代码讲清楚DO/PO/BO/AO/E/DTO/DAO/ POJO/VO
• 17个Mybatis Plugs注解：Mybatis Plugs插件架构设计与注解案例(必须收藏)

0、本章范围

1、JDK集合数据结构范围

1.5. 映射（Map）

• HashMap: 基于哈希表，存储键值对。
• LinkedHashMap: 哈希表加链表，维护插入顺序。
• TreeMap: 基于红黑树，键处于排序状态。
• Hashtable: 古老的 Map 实现，线程安全。
• ConcurrentHashMap: 线程安全的 HashMap 实现。
• ConcurrentSkipListMap: 线程安全的 TreeMap 实现。
• IdentityHashMap: 使用 == 比较键的身份，而不是使用 equals() 方法。
• WeakHashMap: 键是弱引用，适合缓存使用。

选择范围

Map 类型	键值对顺序	键值对排序	线程安全	内存占用	适用场景
HashMap	无	无	否	较低	非线程安全的哈希表，需要快速查找的场景
LinkedHashMap	维护插入顺序	无	否	稍高	需要维护插入顺序的场景
TreeMap	无	按键排序	否	较高	需要按键排序的场景
Hashtable	无	无	是	较高	需要线程安全的古老实现
ConcurrentHashMap	无	无	是	较高	需要线程安全的 HashMap 类型的场景
ConcurrentSkipListMap	无	按键排序	是	较高	需要线程安全的 TreeMap 类型的场景
IdentityHashMap	无	无	否	较低	键的身份比较（==）比 equals() 更频繁的场景
WeakHashMap	无	无	否	较低	键适合作为缓存，可以被垃圾回收的场景

1.6. 其他

• Vector: 古老的动态数组实现，线程安全。
• Stack: 古老的栈实现，可以使用 Vector 或 Deque 实现。
• Properties: 用于处理配置文件的集合类。

选择范围

集合类	线程安全	动态数组	适用场景
Vector	是	是	需要线程安全的动态数组场景，如早期的Java版本
Stack	否	否	需要栈结构的场景，可以使用 Vector 或 Deque 实现
Properties	否	是	处理配置文件，如属性或偏好设置

2、集合数据结构设计与分析

2.1 HashMap

HashMap 是 Java 中的一个关键数据结构，用于存储键值对。

设计思考：

1. 需求场景：
   • 在各种编程任务中，经常需要将键与值关联起来，以实现快速的数据检索。例如，在数据库应用中，需要根据键（如用户名）快速查找用户信息。
   • 适用于需要快速查找、插入和删除键值对的场景，如缓存实现、查找表等。
2. 现有技术局限性：
   • 数组或链表等线性数据结构在查找特定元素时需要遍历整个结构，导致效率低下。
   • 早期的 Hashtable 类虽然提供了键值对的存储，但它是线程安全的，使用 synchronized 方法或块，这限制了并发性能。
3. 技术融合：
   • HashMap 结合了数组和链表的特点，使用哈希表来存储键值对，并通过哈希函数将键映射到数组的特定位置，从而实现快速的查找。
4. 设计理念：
   • HashMap 旨在提供一个高效的键值对存储结构，它允许快速的插入、删除和查找操作，时间复杂度接近 O(1)。
   • 它不保证映射的顺序，而是根据键的哈希码来存储和检索数据。
5. 实现方式：
   • HashMap 内部使用一个数组来存储桶（bucket），每个桶可以包含一个或多个通过链表或红黑树（Java 8 及以后版本）链接的节点（Node）。
   • 当插入一个新的键值对时，HashMap 会根据键的哈希码来确定它应该存储在哪个桶中，如果发生哈希冲突，则会将新的节点添加到链表或红黑树的末尾。

2.1.1 数据结构

图说明：

• HashMap：
  • 表示 HashMap 类的实例，是一个基于哈希表的 Map 实现。
• 数组（桶数组） ：
  • HashMap 使用一个数组来存储桶（Buckets）。
• 桶：
  • 每个桶可以包含多个节点（Node），这些节点存储实际的键值对。
• 链表节点（Node） ：
  • 节点存储键值对，并且每个节点都有一个 next 引用，指向同一桶中的下一个节点。
• 红黑树节点（Tree Node） ：
  • 当链表长度超过一定阈值时，链表会被转换成红黑树，树节点用于维护具有相同哈希值的节点顺序。
• 键（Key） ：
  • 节点中存储的键。
• 值（Value） ：
  • 节点中存储的值。
• 下一个节点（Next） ：
  • 节点中的引用，指向链表中的下一个节点，用于处理哈希冲突。
• 左子树（Left） ：
  • 红黑树节点的左子树引用。
• 右子树（Right） ：
  • 红黑树节点的右子树引用。
• 父节点（Parent） ：
  • 红黑树节点的父节点引用。
• 负载因子阈值：
  • 加载因子阈值，用于决定何时将链表转换为红黑树。

2.1.2 执行流程

图说明：

• 创建 HashMap 实例：初始化 HashMap 对象。
• 插入元素(put) ：执行将键值对插入到 HashMap 的操作。
• 计算键的哈希码：计算插入键的哈希码以确定其在桶数组中的位置。
• 检查是否需要扩容：检查 HashMap 是否需要扩容（即桶数组的大小是否需要增加）。
• 确定桶索引：根据哈希码和桶数组的大小确定桶索引。
• 处理哈希冲突：如果桶中已有元素，则处理哈希冲突，可能是通过链表或红黑树。
• 插入节点：将新节点插入到桶中。
• 查找元素(get) ：执行根据键查找值的操作。
• 遍历桶：遍历桶中的链表或红黑树以查找节点。
• 找到节点：找到包含指定键的节点。
• 返回值：返回找到节点的值。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 找到节点并删除：找到包含指定键的节点并从桶中删除。
• 更新链表或红黑树：删除节点后，更新链表或红黑树的状态。

2.2 LinkedHashMap

LinkedHashMap 是 Java 中的一个 Map 实现，它继承自 HashMap 并添加了一个链表来维护元素的插入顺序或者访问顺序。

设计思考：

1. 需求场景：
   • 在许多应用中，不仅需要快速的查找性能，还需要保持元素的插入顺序或访问顺序。例如，实现一个 LRU（Least Recently Used）缓存，需要在元素被访问时更新其位置。
   • 适用于需要按插入顺序或访问顺序遍历键值对的场景，如会话管理、历史记录等。
2. 现有技术局限性：
   • HashMap 提供了快速的查找性能，但它不保证元素的顺序，即元素的迭代顺序是不确定的。
   • LinkedHashMap 的前身 LinkedHashMap（Java 1.4 之前）基于链表实现，虽然可以保持插入顺序，但查找性能较差，为 O(n)。
3. 技术融合：
   • LinkedHashMap 结合了 HashMap 的快速查找特性和链表的顺序保持功能，使用一个哈希表来存储键值对，同时使用一个双向链表来维护元素的插入或访问顺序。
4. 设计理念：
   • LinkedHashMap 旨在提供一个既能快速查找又能保持元素顺序的映射结构。它可以被配置为保持插入顺序或访问顺序。
5. 实现方式：
   • LinkedHashMap 内部使用一个哈希表来存储键值对，同时使用一个双向链表来维护元素的顺序。每个桶中的元素不再是单独的节点，而是包含在链表节点中的映射条目。
   • 当插入或访问元素时，可以根据需要更新链表，以保持插入顺序或访问顺序。

2.2.1 数据结构

图说明：

• LinkedHashMap：
  • 表示 LinkedHashMap 类的实例，是一个基于哈希表的 Map 实现，同时维护了元素的插入顺序或访问顺序。
• Hash Table：
  • LinkedHashMap 内部使用一个哈希表来存储键值对。
• Buckets Array：
  • 哈希表由一个桶数组组成，每个桶可以包含一个或多个节点（Node）。
• Node1 & Node2：
  • 表示桶中的两个具体节点，每个节点都包含键值对信息，并通过链表连接以维护顺序。
• Key1 & Key2：
  • 节点中存储的键。
• Value1 & Value2：
  • 节点中存储的值。
• Next Node：
  • 节点中的引用，指向链表中的下一个节点。
• Prev Node：
  • 节点中的引用，指向链表中的前一个节点，用于实现双向链表。
• Head：
  • 头指针，指向链表的第一个节点，即 LinkedHashMap 中的第一个元素。
• Tail：
  • 尾指针，指向链表的最后一个节点，即 LinkedHashMap 中的最后一个元素。

2.2.2 执行流程

图说明：

• 创建 LinkedHashMap 实例：初始化 LinkedHashMap 对象。
• 插入元素(put) ：执行将键值对插入到 LinkedHashMap 的操作。
• 计算键的哈希码：计算插入键的哈希码以确定其在桶数组中的位置。
• 检查是否需要扩容：检查 LinkedHashMap 是否需要扩容（即桶数组的大小是否需要增加）。
• 确定桶索引：根据哈希码和桶数组的大小确定桶索引。
• 处理哈希冲突：如果桶中已有元素，则处理哈希冲突，可能是通过链表或红黑树。
• 插入节点：将新节点插入到桶中。
• 节点插入链表：将节点插入到链表的适当位置，以维护插入顺序。
• 查找元素(get) ：执行根据键查找值的操作。
• 遍历桶：遍历桶中的链表或红黑树以查找节点。
• 找到节点：找到包含指定键的节点。
• 返回值：返回找到节点的值。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 找到节点并删除：找到包含指定键的节点并从桶和链表中删除。
• 更新链表：删除节点后，更新链表的链接。

2.3 TreeMap

设计思考：

1. 需求场景：
   • 在许多应用中，需要根据键的自然顺序或自定义顺序来存储和检索键值对。例如，需要实现有序的查找表、索引表或执行范围查询等。
   • 适用于需要有序遍历键值对的场景，如字典、词典、电话簿等。
2. 现有技术局限性：
   • HashMap 和 Hashtable 提供了快速的查找性能，但它们不维护键的任何顺序。
   • 其他线性数据结构，如 ArrayList 或 LinkedList，虽然可以保持元素顺序，但查找性能为 O(n)。
3. 技术融合：
   • TreeMap 结合了哈希表的快速查找特性和二叉搜索树的有序性，使用红黑树（一种自平衡的二叉搜索树）来维护键的排序。
4. 设计理念：
   • TreeMap 提供了一个能够根据键的自然顺序或指定的 Comparator 来维护键的顺序的映射结构，同时保持了快速的查找性能。
5. 实现方式：
   • TreeMap 内部使用一个红黑树来存储键值对，每个节点包含键、值以及指向父节点、左子节点、右子节点的引用。
   • 插入、删除和查找操作都通过维护红黑树的平衡来保证 O(log n) 的时间复杂度。

2.3.1 数据结构

图说明：

• TreeMap：
  • 表示 TreeMap 类的实例，是一个基于红黑树的有序键值对集合。
• RedBlackTree：
  • TreeMap 内部使用一个红黑树来存储键值对，确保元素处于排序状态。
• Root：
  • 根节点，是红黑树的入口点，树中所有节点的父节点都是根节点。
• Node：
  • 红黑树中的节点，包含键值对和指向左右子节点以及父节点的引用。
• Key：
  • 节点中存储的键。
• Value：
  • 节点中存储的值。
• Left Child & Right Child：
  • 节点的左子节点和右子节点，用于维护树的结构和顺序。
• Parent：
  • 节点的父节点，用于维护树的父子关系。
• Color：
  • 节点的颜色，红黑树中的节点颜色可以是红色或黑色，用于维护树的平衡。

2.3.2 执行流程

图说明：

• 创建 TreeMap 实例：初始化 TreeMap 对象。
• 插入元素(put) ：执行将键值对插入到 TreeMap 的操作。
• 计算键的哈希码：计算插入键的哈希码以确定其在树中的位置。
• 确定节点位置：根据哈希码确定节点在树中的大致位置。
• 处理哈希冲突：如果存在哈希冲突，将节点插入到相应的链表中。
• 插入节点：将节点插入到树中，并维护红黑树的性质。
• 查找元素(get) ：执行根据键查找值的操作。
• 遍历树节点：从根节点开始遍历树，直到找到对应的键。
• 找到节点：找到包含指定键的节点。
• 返回值：返回找到节点的值。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 找到节点：找到包含指定键的节点。
• 删除节点：从树中删除节点，并维护红黑树的性质。
• 重新平衡树：删除节点后，可能需要对树进行重新平衡。

2.4 Hashtable

Hashtable 是 Java 中一个古老的键值对集合类，它继承自 Dictionary 类并且实现了 Map 接口。Hashtable 是线程安全的，因为它的所有公共方法都是同步的。

设计思考：

1. 需求场景：
   • 在早期的 Java 应用中，需要一种方式来存储和检索键值对数据，同时保证在多线程环境下数据的一致性和完整性。
   • 适用于需要同步访问和修改键值对的场景，如全局配置信息、用户会话信息等。
2. 现有技术局限性：
   • 在 Java 5 之前，集合框架中缺乏线程安全的 Map 实现，导致开发者需要手动同步 Map 操作，这增加了编程复杂性并可能引入死锁等问题。
3. 技术融合：
   • Hashtable 结合了哈希表的快速查找特性和同步机制，提供了一个线程安全的 Map 实现。
4. 设计理念：
   • Hashtable 旨在提供一个线程安全的 Map，它通过全局锁（synchronized 方法或块）来确保在多线程环境下的线程安全。
5. 实现方式：
   • Hashtable 内部使用一个哈希表来存储键值对，所有公有方法都是同步的，以确保在多线程环境下的线程安全。

2.4.1 数据结构

图说明：

• 创建 Hashtable 实例：初始化 Hashtable 对象。
• 插入元素(put) ：执行将键值对插入到 Hashtable 的操作。
• 计算键的哈希码：计算插入键的哈希码以确定其在桶数组中的位置。
• 确定桶索引：根据哈希码确定桶在数组中的索引。
• 处理哈希冲突：如果存在哈希冲突，即多个键哈希到同一个桶，将它们链接在同一个桶的链表中。
• 插入桶中的链表：将节点插入到对应桶的链表中。
• 查找元素(get) ：执行根据键查找值的操作。
• 遍历桶中的链表：在对应桶的链表中查找具有指定键的节点。
• 找到节点：找到包含指定键的节点。
• 返回值：返回找到节点的值。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 找到节点：找到包含指定键的节点。
• 删除节点：从链表中删除节点。
• 处理链表：删除节点后，可能需要对链表进行处理，如重新计算负载因子以决定是否需要缩容。

2.4.2 执行流程

图说明：

• 创建 Hashtable 实例：初始化 Hashtable 对象。
• 插入元素(put) ：执行将键值对插入到 Hashtable 的操作。
• 计算键的哈希码：计算插入键的哈希码以确定其在桶数组中的位置。
• 确定桶索引：根据哈希码确定桶在数组中的索引。
• 处理哈希冲突：如果存在哈希冲突，即多个键哈希到同一个桶，将它们链接在同一个桶的链表中。
• 插入桶中的链表：将节点插入到对应桶的链表中。
• 查找元素(get) ：执行根据键查找值的操作。
• 遍历桶中的链表：在对应桶的链表中查找具有指定键的节点。
• 找到节点：找到包含指定键的节点。
• 返回值：返回找到节点的值。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 找到节点：找到包含指定键的节点。
• 删除节点：从链表中删除节点。
• 处理链表：删除节点后，可能需要对链表进行处理，如重新计算负载因子以决定是否需要缩容。

2.5 ConcurrentHashMap

设计思考：

1. 需求场景：
   • 在多线程应用中，需要快速地进行键值对的插入、删除和查找操作，同时保证线程安全。例如，在缓存系统、任务分配、实时数据处理等场景中，这些操作非常常见。
   • 适用于需要高并发访问和更新键值对的场景，如高并发网站后端、大数据处理等。
2. 现有技术局限性：
   • Hashtable 提供了线程安全的 Map 实现，但它使用全局锁来同步所有操作，这在高并发环境下会导致性能瓶颈。
   • HashMap 提供了非线程安全的快速查找性能，但需要额外的同步措施来保证线程安全，这同样会影响并发性能。
3. 技术融合：
   • ConcurrentHashMap 结合了 HashMap 的快速查找特性和线程安全的机制，使用分段锁（Segmentation）或 CAS（Compare-And-Swap）操作来实现高效的并发控制。
4. 设计理念：
   • ConcurrentHashMap 旨在提供一个线程安全的 Map，它通过减少锁的粒度或避免使用锁来提高并发性能，允许多个线程同时执行操作而不会相互阻塞。
5. 实现方式：
   • 在 Java 7 及之前版本中，ConcurrentHashMap 使用分段锁机制，将 Map 分成多个段（Segment），每个段有自己的锁，从而允许在不同段上并发执行操作。
   • 在 Java 8 及以后版本中，ConcurrentHashMap 使用 CAS 操作和 synchronized 关键字来实现无锁或细粒度锁定的并发控制，同时使用了红黑树来优化长链表的性能。

2.5.1 数据结构

图说明：

• ConcurrentHashMap：表示 ConcurrentHashMap 类的实例，是一个线程安全的 Map 实现。
• Segment Array：ConcurrentHashMap 内部使用一个段数组来存储数据，每个段是一个独立的哈希表。
• Segment 1 & Segment 2：每个段都是一个独立的哈希表，相当于将整个哈希表分成多个小的片段，不同的段可以由不同的线程独立操作。
• Hash Array：每个段包含一个哈希数组，用于存储桶（Buckets）。
• Bucket 1 & Bucket 2：哈希数组中的每个桶可以包含一个或多个节点（Node），在 Java 8 及以后的版本中，当链表长度超过一定阈值时，链表会转换为红黑树。
• Node：每个桶包含多个节点，这些节点存储实际的键值对，并且通过链表连接以维护顺序。
• Key & Value：节点中存储的键和值。
• Next Node：节点中的引用，指向链表中的下一个节点。
• Null：链表的末尾节点的 Next Node 指向 Null。
• Load Factor：加载因子，用于决定何时需要扩容哈希表。

2.5.2 执行流程

图说明

• 创建 ConcurrentHashMap 实例：初始化 ConcurrentHashMap 对象。
• 插入元素(put) ：执行将键值对插入到 ConcurrentHashMap 的操作。
• 计算键的哈希码：计算插入键的哈希码以确定其在桶数组中的位置。
• 确定段和桶位置：根据哈希码确定段和桶的位置。
• 尝试插入节点：尝试在桶中插入节点，如果需要同步，则获取段锁。
• 获取段锁：获取对应段的锁。
• 插入或更新节点：在桶中插入新节点或更新现有节点。
• 释放段锁：释放段锁。
• 查找元素(get) ：执行根据键查找值的操作。
• 读取节点：读取对应桶中的节点。
• 返回节点值：返回节点的值。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 删除节点：从桶中删除节点。
• 重新平衡树：删除节点后，可能需要对树进行重新平衡。

2.6 ConcurrentSkipListMap

设计思考：

1. 需求场景：
   • 在多线程环境中，需要一个高效的数据结构来维护有序的键值对集合，同时支持快速的插入、删除和查找操作。
   • 适用于需要有序数据且高并发访问的场景，如实时数据索引、多维数据范围查询等。
2. 现有技术局限性：
   • TreeMap 提供了有序的键值对存储，但它不是线程安全的，需要额外的同步措施来保证线程安全，这会影响并发性能。
   • ConcurrentHashMap 提供了高效的并发性能，但它不维护元素的顺序。
3. 技术融合：
   • ConcurrentSkipListMap 结合了跳表的有序性和其他并发控制技术，以提供线程安全的有序映射。
4. 设计理念：
   • ConcurrentSkipListMap 旨在提供一个线程安全的有序映射，它允许多个线程高效地执行插入、删除和查找操作，同时保持元素的排序。
5. 实现方式：
   • ConcurrentSkipListMap 内部使用跳表来存储键值对，跳表是一种通过多级索引来提高查找效率的有序数据结构。
   • 它使用了多种并发控制技术，包括分段锁和 CAS（Compare-And-Swap）操作，以实现高效的并发访问。

2.6.1 数据结构

图说明：

• ConcurrentSkipListMap：这是整个跳表的根结构，表示一个线程安全的有序映射结构。
• HeadIndex：这是跳表的头部索引节点，它不存储数据，而是作为多层索引结构的起点。
• Level 3 Index：这是跳表的第三层索引节点，用于快速定位到第二层索引节点。
• Level 2 Index：这是跳表的第二层索引节点，用于快速定位到第一层索引节点。
• Level 1 Index：这是跳表的第一层索引节点，直接指向数据节点。
• Node A, Node B, Node C：这些是数据节点，每个节点包含一个键（Key）和一个值（Value），并形成链表结构。
• Key A, Key B, Key C：这些是数据节点中的键。
• Value A, Value B, Value C：这些是数据节点中的值。
• Null：表示链表的末尾，没有更多的节点。

2.6.2 执行流程

图说明：

• 创建 ConcurrentHashMap 实例：初始化 ConcurrentHashMap 对象。
• 执行操作：决定要执行的操作类型，可以是插入、查找或删除。
• 插入元素(put) ：执行将键值对插入到 ConcurrentHashMap 的操作。
• 查找元素(get) ：执行根据键查找值的操作。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 计算键的哈希码：计算操作键的哈希码以确定其在跳表中的位置。
• 确定节点索引：根据哈希码确定节点在跳表中的索引位置。
• 遍历索引节点：从高层索引开始，逐层向下遍历到底层数据节点。
• 找到节点：在数据层找到包含指定键的节点。
• 更新节点值：在找到的节点上执行更新操作，插入或覆盖值。
• 返回节点值：返回找到节点的值。
• 删除节点：从跳表中删除指定的节点。
• 重新平衡索引：删除节点后，可能需要对索引进行重新平衡以维持跳表的性能。

2.7 IdentityHashMap

IdentityHashMap 是 Java 中的一个 Map 实现，它使用对象的 identity（即它们的内存地址）来比较键，而不是使用 equals() 方法。这意味着即使两个对象相等，如果它们不是同一个实例，IdentityHashMap 也会将它们视为不同的键。

设计思考：

1. 需求场景：
   • 在某些特定的应用场景中，需要根据对象的引用身份（而不是对象的内容）来存储和检索键值对。例如，需要快速确定对象是否已经存在集合中，或者需要快速地将对象映射到另一个对象上。
2. 现有技术局限性：
   • 标准的 HashMap 和 TreeMap 使用对象的 equals() 和 hashCode() 方法来确定键的相等性，这在比较对象时可能会引入额外的性能开销，特别是当对象重写了这些方法以提供内容比较时。
3. 技术融合：
   • IdentityHashMap 结合了哈希表的快速查找特性和基于引用相等性的键比较机制，提供了一种快速且轻量级的键值对存储方式。
4. 设计理念：
   • IdentityHashMap 旨在提供一个简单的键值对映射，它使用 == 操作符来比较键的相等性，而不是使用 equals() 方法。这意味着只有当两个键引用完全相同时，它们才被视为相等。
5. 实现方式：
   • IdentityHashMap 内部使用一个数组来存储桶（bucket），每个桶可以包含一个或多个通过链表链接的节点（Node）。当插入一个新的键值对时，IdentityHashMap 会使用键的系统哈希码来确定它应该存储在哪个桶中。

2.7.1 数据结构

图说明：

• IdentityHashMap：表示 IdentityHashMap 类的实例，它使用对象的身份（内存地址）来比较键。
• Hash Array：IdentityHashMap 使用一个哈希数组来存储桶（Buckets）。
• Bucket 1 & Bucket 2：哈希数组中的每个桶可以包含一个或多个节点（Node），这些节点存储实际的键值对。
• Node：每个桶包含多个节点，这些节点存储键值对，并且通过链表连接。
• Key (Object Reference) ：节点中存储的键是对象的引用，IdentityHashMap 通过这些引用来比较键。
• Value：节点中存储的值。
• Next Node：节点中的引用，指向链表中的下一个节点。
• Null：链表的末尾节点的 Next Node 指向 Null。

2.7.2 执行流程

图说明：

• 创建 IdentityHashMap 实例：初始化 IdentityHashMap 对象。
• 执行操作：决定要执行的操作类型，可以是插入、查找或删除。
• 插入元素(put) ：执行将键值对插入到 IdentityHashMap 的操作。
• 查找元素(get) ：执行根据键查找值的操作。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 计算键的哈希码：计算操作键的哈希码以确定其在哈希表中的位置。
• 确定桶索引：根据哈希码确定键在哈希表中的桶索引。
• 遍历桶中的链表：在确定的桶中遍历链表以查找键值对。
• 找到节点：在链表中找到包含指定键的节点。
• 插入节点：在哈希表中插入新的键值对。
• 返回节点值：返回找到节点的值。
• 删除节点：从哈希表中删除指定的节点。

2.8 WeakHashMap

WeakHashMap 是 Java 中的一种哈希表实现，它使用弱引用来存储键。这意味着当键不再被其他强引用引用时，它们可以被垃圾回收器回收，即使WeakHashMap中还包含这些键的引用。这种特性使得WeakHashMap常用于缓存实现，其中键的生命周期不需要超过对键的最后一次引用。

设计思考：

1. 需求场景：
   • 在某些应用中，需要一种映射结构，其中的键是弱引用的，这意味着这些键不会阻止它们所引用的对象被垃圾回收器回收。这在缓存实现或临时映射中非常有用，特别是当希望映射表在不再被外部引用时能够自动释放资源时。
2. 现有技术局限性：
   • 标准的 HashMap 和 TreeMap 使用强引用存储键，这意味着只要键存在于映射中，即使没有其他引用，对象也不会被垃圾回收，这可能导致内存泄漏。
3. 技术融合：
   • WeakHashMap 结合了哈希表的快速查找特性和弱引用机制，允许键被垃圾回收器自动回收，而不需要显式的删除操作。
4. 设计理念：
   • WeakHashMap 旨在提供一个映射，其中的键是弱引用的，这意味着如果一个键不再被其他强引用引用，那么它将被垃圾回收器回收，即使它仍然存在于 WeakHashMap 中。
5. 实现方式：
   • WeakHashMap 内部使用一个数组来存储桶（bucket），每个桶可以包含一个或多个通过链表链接的节点（Entry）。键是弱引用，而值是强引用。当垃圾回收器运行时，它会清除所有没有被强引用的键。

2.8.1 数据结构

图说明：

• WeakHashMap：表示 WeakHashMap 类的实例，它使用弱引用来存储键。
• Hash Array：WeakHashMap 使用一个哈希数组来存储桶（Buckets）。
• Bucket 1 & Bucket 2：哈希数组中的每个桶可以包含一个或多个节点（Node），这些节点存储实际的键值对。
• Node：每个桶包含多个节点，这些节点存储键值对，并且通过链表连接。
• Weak Reference to Key：节点中存储的键是弱引用，这意味着如果这些键没有被其他强引用引用，它们可以被垃圾回收器回收。
• Value：节点中存储的值。
• Next Node：节点中的引用，指向链表中的下一个节点。
• Null：链表的末尾节点的 Next Node 指向 Null。

2.8.2 执行流程

图说明：

• 创建 WeakHashMap 实例：初始化 WeakHashMap 对象。
• 插入元素(put) ：执行将键值对插入到 WeakHashMap 的操作。
• 查找元素(get) ：执行根据键查找值的操作。
• 删除元素(remove) ：执行根据键删除键值对的操作。
• 计算键的哈希码：计算操作键的哈希码以确定其在哈希表中的位置。
• 确定桶索引：根据哈希码确定键在哈希表中的桶索引。
• 检查键是否被回收：检查键是否已被垃圾回收器回收。
• 插入或更新节点：如果桶中没有找到相同的键（基于引用相等性），则在桶的链表中插入新的节点；如果找到，则更新节点的值。
• 遍历桶中的链表：在确定的桶中遍历链表以查找键值对。
• 返回节点值：返回找到节点的值。
• 删除节点：从桶的链表中删除指定的节点。
• 清理被回收的键值对：清理所有被垃圾回收器回收的键值对。

2.9 Vector

Vector 是 Java 中的一个同步的动态数组类，它继承自 AbstractList 并实现了 List 接口。Vector 可以动态地调整大小，以容纳任意数量的元素。由于 Vector 是同步的，所以它是线程安全的，但这也意味着它的性能可能不如 ArrayList，特别是在单线程环境中。

设计思考：

1. 需求场景：
   • 在早期的 Java 编程中，需要一种动态数组结构来存储和管理元素集合，尤其是当元素数量未知或变化时。
   • 适用于需要动态大小调整的数组，如实现动态列表、堆栈、队列等数据结构。
2. 现有技术局限性：
   • Java 的基本数组类型长度固定，一旦创建，其大小不能改变，这限制了其在需要动态大小管理时的使用。
   • 需要一种数据结构能够在运行时动态调整大小，以适应不断变化的元素数量。
3. 技术融合：
   • Vector 结合了动态数组的概念和早期 Java 对线程安全的需求，提供了一个可以动态增长和收缩的数组结构。
4. 设计理念：
   • Vector 提供了一个可以动态调整大小的数组，同时为了保证线程安全，它的所有公共方法都是同步的。
5. 实现方式：
   • Vector 内部使用一个数组来存储元素，当添加元素导致数组容量不足时，Vector 会自动创建一个更大的新数组，并将旧数组中的元素复制到新数组中。

2.9.1 数据结构

图说明：

• Vector：表示 Vector 类的实例，是一个线程安全的动态数组。
• Element Array：Vector 使用一个动态数组来存储元素。
• Element 0, Element 1, …, Element N：数组中的每个位置存储一个元素，这些元素可以是任意类型的对象。
• Null：在数组的末尾，表示数组的当前大小。

2.9.2 执行流程

图说明：

• 创建 Vector 实例：初始化 Vector 对象。
• 插入元素(add) ：执行将元素添加到 Vector 的操作。
• 计算索引：计算插入元素的索引位置。
• 检查同步锁：检查是否有线程正在对 Vector 进行操作，如果有，则等待。
• 插入元素：将元素添加到 Vector 中。
• 查找元素(get) ：执行根据索引查找元素的操作。
• 返回元素：返回查找到的元素。
• 删除元素(remove) ：执行根据索引删除元素的操作。
• 删除并通知：删除元素并通知其他等待的线程。

2.10 Stack

Stack 是一个后进先出（LIFO）的数据结构，通常使用数组或链表来实现。在 Java 中，Stack 类继承自 Vector，因此它是线程安全的。

设计思考：

1. 需求场景：
   • 在编程中，经常需要一种数据结构来支持后进先出（LIFO）的操作，例如在算法实现中，如深度优先搜索、递归算法、函数调用栈等。
   • 适用于需要跟踪最近添加的元素，或者需要撤销操作的场景，如文本编辑器的撤销功能。
2. 现有技术局限性：
   • 基本数组或固定大小的数据结构不支持 LIFO 操作，或者在进行这类操作时效率不高。
   • 需要一种数据结构能够快速地从一端添加和移除元素，同时能够轻松地检查栈顶元素。
3. 技术融合：
   • Stack 融合了动态数组的概念和 LIFO 操作的特性，提供了一个可以动态增长和收缩的栈结构。
4. 设计理念：
   • Stack 设计为一个简单的数据结构，它提供了一系列方法来支持 LIFO 操作，如 push（入栈）、pop（出栈）、peek（查看栈顶元素）和 isEmpty（检查栈是否为空）。
5. 实现方式：
   • Stack 内部使用 Vector 来存储元素，由于 Vector 是同步的，Stack 也是线程安全的。Stack 定义了一系列方法来操作 Vector 的顶部元素，从而实现栈的操作。

2.10.1 数据结构

图说明：

• Stack：表示 Stack 类的实例，是一个后进先出的数据结构。
• Element Array：Stack 使用一个数组来存储栈中的元素。
• Top Marker：表示栈顶的位置，指向数组中的最后一个元素，即栈顶元素。
• Element 0, Element 1, …, Element N-1：数组中的每个位置存储一个元素，这些元素可以是任意类型的对象。
• Null：在数组的末尾，表示数组的当前大小。

2.10.2 执行流程

图说明：

• 创建 Stack 实例：初始化 Stack 对象。
• 执行操作：决定要执行的操作类型，可以是入栈（push）、出栈（pop）或查看栈顶元素（peek）。
• 入栈操作(push) ：执行将元素添加到栈顶的操作。
• 检查栈满：检查栈是否已满，如果已满则不能执行入栈操作。
• 将元素压入栈顶：将元素添加到栈顶。
• 出栈操作(pop) ：执行移除栈顶元素的操作。
• 检查栈空：检查栈是否为空，如果为空则不能执行出栈操作。
• 移除栈顶元素：从栈中移除栈顶元素。
• 返回被移除的元素：返回被移除的栈顶元素。
• 查看栈顶元素(peek) ：执行查看但不移除栈顶元素的操作。
• 获取栈顶元素：获取栈顶元素的引用。
• 返回栈顶元素：返回栈顶元素的值。

2.11 Properties

Properties 是 Java 中的一个类，用于处理属性文件。属性文件是一种将键值对以特定的格式存储在文件中的简单数据存储方式。Properties 类继承自 Hashtable，因此它本质上是一个线程安全的哈希表，其键和值都是字符串。

设计思考：

1. 需求场景：s
   • 在软件开发中，经常需要将程序的配置信息与代码分离，以便在不同环境中使用不同的配置，而无需修改代码。
   • 适用于需要读取和写入配置文件的场景，如应用程序设置、用户偏好设置等。
2. 现有技术局限性：
   • 在 Properties 类出现之前，配置信息可能以硬编码的形式存在于代码中，或者以非结构化的文本文件存储，这使得配置管理变得困难。
3. 技术融合：
   • Properties 类融合了键值对存储和文件读写的功能，提供了一种简单且标准化的方式来处理配置信息。
4. 设计理念：
   • Properties 类旨在提供一个简单的键值对集合，用于存储和检索属性。它使用标准化的格式读取和写入属性文件，通常以 .properties 为文件扩展名。
5. 实现方式：
   • Properties 类使用一个 Hashtable（在 Java 9 之前）或 HashMap（从 Java 9 开始）来存储键值对。它提供了方法来加载、保存和处理属性文件，这些文件通常以等号（=）分隔键和值，并且支持特定格式的注释。

2.11.1 数据结构

图说明：

• Properties：表示 Properties 类的实例，用于处理属性文件。
• Hash Array：Properties 使用一个哈希数组来存储桶（Buckets）。
• Bucket 1 & Bucket 2：哈希数组中的每个桶可以包含一个或多个节点（Node），这些节点存储实际的键值对。
• Node：每个桶包含多个节点，这些节点存储键值对，并且通过链表连接。
• Key String：节点中存储的键，是一个字符串。
• Value String：节点中存储的值，也是一个字符串。
• Next Node：节点中的引用，指向链表中的下一个节点。
• Null：链表的末尾节点的 Next Node 指向 Null。

2.11.2 执行流程

图说明：

• 创建 Properties 实例：初始化 Properties 对象。
• 加载属性文件(load) ：从文件系统中加载属性文件到 Properties 对象。
• 读取文件：读取属性文件的内容。
• 解析键值对：解析文件内容中的键值对。
• 存储到 HashMap：将解析的键值对存储到 Properties 内部的 HashMap 中。
• 保存属性文件(store) ：将 Properties 对象中的属性保存到文件系统。
• 写入文件：打开文件并准备写入。
• 格式化键值对：将 Properties 对象中的键值对格式化为字符串。
• 获取属性(getProperty) ：根据键获取属性值。
• 查找键值对：在 Properties 内部的 HashMap 中查找键值对。
• 返回属性值：返回查找到的属性值。

标签：插入,元素,28,链表,并发,键值,哈希,数据结构,节点
From： https://blog.csdn.net/alises1314/article/details/143058574