学习笔记
小谈Java的HashMap和ConcurrentHashMap
2023-09-16
JAVA
0

目录

HashMap结构
HashMap扩容、树化和退化过程
红黑树详解
ConcurrentHashMap实现原理

HashMap结构

Java 8中的HashMap是Java集合框架中的一种数据结构，用于存储键值对，并提供了快速的查找、插入和删除操作。在Java 8之前，HashMap的内部实现是基于数组和链表的，但在Java 8中引入了一些重要的改进，主要是为了提高性能。

下面详细讲解Java 8中的HashMap：

  1. 内部数据结构：

    • Java 8中的HashMap依然基于数组，但不再使用纯链表。相反，它引入了红黑树（Red-Black Tree）来优化链表的性能。这种数据结构称为"桶"（buckets），每个桶存储一个链表或红黑树。

  2. 哈希算法：

    • HashMap仍然使用哈希算法来确定键值对的存储位置。哈希码由键的hashCode()方法生成。
    • Java 8引入了一种称为“树化”（treeify）的机制，当某个桶中的链表长度达到一定阈值时，会将链表转换为红黑树，以提高查找性能。这样可以防止链表过长时性能急剧下降的问题。

  3. 负载因子和扩容：

    • 负载因子（load factor）是一个影响HashMap性能和空间利用率的重要参数。默认负载因子是0.75，表示当桶的填充程度达到75%时，HashMap会自动扩容，将桶的数量翻倍。
    • 扩容涉及将所有键值对重新分配到新的桶中，这个过程可能会消耗一些时间，但确保了性能的可控性。

  4. 并发性：

    • HashMap不是线程安全的，因此在多线程环境中需要采取额外的同步措施，或者使用ConcurrentHashMap来替代。
    • Java 8中的ConcurrentHashMap也进行了改进，引入了分段锁（segmented locking）来提高并发性能。

  5. 迭代顺序：

    • 在Java 8之前，HashMap的迭代顺序是不确定的。在Java 8中，HashMap保持了键值对的插入顺序，即它是有序的。
    • 若要按照键值对的插入顺序迭代HashMap，可以使用LinkedHashMap。

  6. null键和null值：

    • HashMap允许一个键为null，多个值为null的情况。
    • 如果将多个键的哈希码映射到同一个桶，它们将以链表或红黑树的形式存储。

  7. API增强：

    • Java 8引入了一些新的方法，如forEach和compute系列方法，以便更方便地进行键值对的处理和修改。

HashMap扩容、树化和退化过程

HashMap在Java中是一种常用的散列表数据结构，它用于存储键值对，并提供快速的查找、插入和删除操作。为了维持性能和内存利用的平衡，HashMap在不同的情况下会执行扩容、树化和退化操作。

扩容过程：

  1. 初始状态：HashMap在创建时会有一个初始容量，通常为16，并且有一个扩容因子，通常为0.75。哈希表包含一些桶，每个桶可以存储多个键值对。

  2. 插入操作：当执行插入操作时，HashMap会根据键的哈希值计算出应该存储在哪个桶中。如果插入操作导致某个桶中的键值对数量超过了扩容因子乘以容量（16 * 0.75 = 12，这是默认值），就会触发扩容操作。

  3. 扩容：扩容包括以下步骤：

    • 创建一个新的桶数组，通常是当前容量的两倍，即32。
    • 遍历原始桶数组中的每个桶，将其中的键值对重新分配到新的桶数组中。
    • 更新HashMap的引用，指向新的桶数组。

  4. 继续插入：之后的插入操作会根据新的桶数组进行插入，直到再次触发扩容。

注意

上面提到通常是32，是默认情况，如果手动设置了初始值为12，那么在容量为10的时候会触发扩容，并且此时的容量大小为20，也就是说扩容两倍不是固定的值而是和初始容量设置有关

树化过程：

  1. 扩容操作：当某个桶中的链表长度超过了一定阈值（默认为8），并且哈希表的容量大于等于64，HashMap会考虑将链表转换为红黑树（树化操作）。

  2. 树化：树化操作包括以下步骤：

    • 创建一个新的红黑树。
    • 将链表中的所有键值对按照哈希值插入到新的红黑树中，以保持树的平衡性。
    • 更新原始桶中的引用，指向新的红黑树。

  3. 继续插入：之后的插入操作会根据新的红黑树进行插入，提高了查找性能。

退化过程：

  1. 删除操作或扩容操作：当某个桶中的红黑树的元素数量低于一定阈值（默认为6），HashMap会考虑将红黑树转换回链表（退化操作）。这通常发生在删除操作或扩容操作后。

  2. 退化：退化操作包括以下步骤：

    • 遍历红黑树中的所有键值对，并按照它们在树中的顺序，重新构建成一个链表。
    • 更新原始桶中的引用，指向新创建的链表。

  3. 继续插入：之后的插入操作会根据新的链表进行插入，减少了内存消耗。

总之，HashMap通过扩容、树化和退化操作来维持性能和内存利用率的平衡。这些操作都是自动进行的，无需用户干预。它们确保了HashMap在不同负载下都能提供高效的插入、查找和删除操作。

红黑树详解

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，通常用于实现动态集合或映射（如C++中的std::map或Java中的TreeMap）。红黑树具有以下特性：

  1. 节点颜色：每个节点都有一个颜色，通常是红色或黑色。

  2. 根节点：根节点是黑色的。

  3. 叶子节点（NIL节点）：叶子节点是特殊的黑色节点，通常表示为NIL或null。叶子节点不存储数据，用于简化算法。

  4. 颜色规则：

    • 每个节点要么是红色，要么是黑色。
    • 红色节点的子节点必须是黑色的（没有两个相邻的红色节点）。
    • 从根节点到叶子节点的每条路径上，黑色节点数量必须相同。这个特性确保了树的高度近似平衡，最多不会超过两倍于最短路径的高度。

这些特性保证了红黑树的高度是近似平衡的，因此各种基本操作（插入、删除、查找）的时间复杂度都是 O(log n)，其中 n 是树中节点的数量。

红黑树的基本操作：

  1. 插入操作：插入新节点后，可能会破坏红黑树的特性。为了维持这些特性，需要通过一系列的旋转和重新着色操作来修复。

  2. 删除操作：删除节点后，也可能会破坏红黑树的特性，需要通过旋转和重新着色操作来修复。

  3. 查找操作：从根节点开始，根据比较键值来导航树，以查找目标节点。

红黑树的自平衡性质使得在插入和删除操作后需要进行一些修复操作，但这些修复操作的成本是有限的，因此红黑树在实际应用中表现出色。它常用于实现各种数据结构，包括集合、映射、优先队列等，以及数据库索引。

红黑树的一个重要应用是在数据库中用于实现索引结构，例如在某些数据库管理系统中用于支持高效的查询操作。红黑树的自平衡性质确保了数据库索引的高性能和稳定性。

在这个示例中，每个节点包含一个键和颜色。节点的颜色用括号中的字母表示，"Black"表示黑色，"Red"表示红色。根节点为 7（黑色），并且遵循红黑树的性质：

  1. 根节点是黑色的。
  2. 所有叶子节点（NIL节点）是黑色的。
  3. 红色节点的子节点必须是黑色的。
  4. 从根节点到叶子节点的每条路径上，黑色节点数量必须相同。

请注意，这只是一个小型示例，实际的红黑树可能包含大量节点，但它的结构和性质与此示例类似。根据红黑树的性质，这种树的高度是平衡的，因此各种操作（插入、删除、查找）的时间复杂度都是 O(log n)，其中 n 是树中节点的数量。

以下是一个简单的红黑树示例，包含一些节点以及它们的颜色和键值。这是一个小型示例，以便更容易理解红黑树的结构和性质（1、3、5、7、18、19、22）。

image.png

  • 构造过程 要构造一个红黑树，需要按照一定规则逐步插入每个数字，确保红黑树的性质得以满足。下面是基于给定的一组数字{1, 3, 5, 7, 18, 19, 22}构造红黑树的过程：

  1. 插入 1：

    • 插入第一个数字 1，作为根节点，涂为黑色。

      image.png

  2. 插入 3：

    • 插入数字 3，由于是第二个节点，将其涂为红色。

    • 红黑树的性质要求红节点的子节点必须是黑色，所以这里不会违反性质。

      image.png

  3. 插入 5：

    • 插入数字 5，由于是第三个节点，将其涂为红色。

    • 红黑树的性质要求红节点的子节点必须是黑色，因此需要进行修复。

    • 通过左旋转，将 3 提升为根节点，同时将 1 和 5 放置在正确的位置，并将它们涂为黑色。

      image.png

  4. 插入 7：

    • 插入数字 7，由于是第四个节点，将其涂为红色。

    • 红黑树的性质要求红节点的子节点必须是黑色，因此需要进行修复。

    • 通过右旋转，将 3 作为根节点，将 1 和 5 放置在正确的位置，同时将 7 涂为黑色。

      image.png

  5. 插入 18：

    • 插入数字 18，由于是第五个节点，将其涂为红色。

    • 红黑树的性质要求红节点的子节点必须是黑色，因此需要进行修复。

    • 通过左旋转，将 5 提升为根节点，同时将 3 和 7 放置在正确的位置，同时将 18 涂为黑色。

      image.png

  6. 插入 19：

    • 插入数字 19，由于是第六个节点，将其涂为红色。

    • 红黑树的性质要求红节点的子节点必须是黑色，因此需要进行修复。

    • 通过右旋转，将 7 提升为根节点，同时将 5 和 18 放置在正确的位置，同时将 19 涂为黑色。

      image.png

  7. 插入 22：

    • 插入数字 22，由于是最后一个节点，将其涂为红色。

    • 红黑树的性质要求红节点的子节点必须是黑色，因此需要进行修复。

    • 通过左旋转，将 18 提升为根节点，同时将 7 和 19 放置在正确的位置，同时将 22 涂为黑色。

      image.png

现在，我们已经成功构造了一个满足红黑树性质的红黑树，每个路径上的黑色节点数量相同，符合红黑树的性质。这个红黑树可以用于高效地进行查找、插入和删除操作。请注意，红黑树的构建过程是按照一定规则进行的，以确保满足红黑

注意

红黑树的最终结构可能会因输入数据的顺序不同而产生差异。虽然红黑树的自平衡性质确保了在插入或删除操作后树的高度大致平衡，但具体的节点排列和颜色分布仍然取决于数据的插入顺序。

Java 8中的HashMap在性能和功能上进行了改进，通过红黑树的引入来优化查找性能，保持了键值对的插入顺序，同时提供了一些新的API方法。但请注意，HashMap仍然不是线程安全的，如果在多线程环境中使用，需要额外的同步措施。如果需要线程安全的散列表，可以考虑使用ConcurrentHashMap。

ConcurrentHashMap实现原理

Java 8 中的 ConcurrentHashMap 实现了一些重要的改进，其实现原理基本上仍然采用分段锁机制，但具体实现细节和性能有所优化。下面是 Java 8 中 ConcurrentHashMap 的详细实现原理：

  1. 分段锁：Java 8 中的 ConcurrentHashMap 与旧版不同，Java 8 中的 ConcurrentHashMap 使用了基于 CAS（Compare-And-Swap）的锁和操作，而不再依赖传统的锁机制。这意味着更多的读取操作可以并行进行，而不仅仅是写入操作。

  2. Buckets 和 Nodes：ConcurrentHashMap 内部的数据结构是一组桶（Buckets），每个桶包含多个节点（Nodes）。每个节点可以包含一个键值对。在 Java 8 中，桶和节点都是通过 CAS 操作来管理的，而不是使用传统的锁。

  3. 扩容机制：当插入操作需要进行扩容时，Java 8 的 ConcurrentHashMap 使用了一种更高效的分割策略，而不是像旧版那样逐个段地扩容。这可以减少扩容操作的争用，提高了性能。

  4. 红黑树：Java 8 中的 ConcurrentHashMap 引入了红黑树来优化处理大量哈希冲突的情况。当一个桶中的节点数量超过一定阈值时，会将节点存储在一个红黑树中，而不是简单的链表。这使得在大规模数据集上，ConcurrentHashMap 的性能得到了显著提升。

  5. CAS 操作：Java 8 中的 ConcurrentHashMap 大量使用了 CAS 操作，这是一种非阻塞算法，用于实现并发访问。CAS 操作允许多个线程尝试同时更新数据，而只有一个线程能够成功，其他线程会自旋重试。这降低了锁的粒度，提高了并发性能。

  6. 读取操作：在 Java 8 的 ConcurrentHashMap 中，读取操作通常是非阻塞的，多个线程可以同时读取不同部分的数据，因此读取性能非常高。

总的来说，Java 8 中的 ConcurrentHashMap 通过引入红黑树、改进的分段扩容策略和 CAS 操作等技术，提供了更高的并发性能和更好的扩展性。这使得它成为一个非常强大且高效的线程安全哈希表实现，特别适用于高并发的应用程序。