AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

查漏补缺第五期(HashMap & ConcurrentHashMap)

2023-05-31 93
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
检索分析服务 Elasticsearch 版，2核4GB开发者规格 1个月
推荐场景：
数据可视化分析航班信息
简介： 前言目前正在出一个查漏补缺专题系列教程, 篇幅会较多, 喜欢的话，给个关注❤️ ~本专题主要以Java语言为主, 好了, 废话不多说直接开整吧~HashMap底层有了解过吗? 它的put原理以及扩容机制是什么HashMap是一种常用的数据结构，用于存储键值对。在理解HashMap的put原理和扩容机制之前，我们先来了解一下HashMap的基本结构。HashMap的内部是由一个数组和链表（或红黑树）组成的，数组被称为哈希表，用于存储元素。每个数组元素是一个链表的头节点（或红黑树的根节点），该链表（或红黑树）用于解决哈希冲突，即当不同的键映射到相同的数组索引时。

前言

目前正在出一个查漏补缺专题系列教程, 篇幅会较多, 喜欢的话，给个关注❤️ ~

本专题主要以Java语言为主, 好了, 废话不多说直接开整吧~

HashMap底层有了解过吗? 它的put原理以及扩容机制是什么

HashMap是一种常用的数据结构，用于存储键值对。在理解HashMap的put原理和扩容机制之前，我们先来了解一下HashMap的基本结构。

HashMap的内部是由一个数组和链表（或红黑树）组成的，数组被称为哈希表，用于存储元素。每个数组元素是一个链表的头节点（或红黑树的根节点），该链表（或红黑树）用于解决哈希冲突，即当不同的键映射到相同的数组索引时。

put原理

当我们调用HashMap的put方法插入键值对时，HashMap会执行以下操作：

  • 首先，根据键的hashCode()方法计算出哈希值。
  • 使用哈希值与数组的长度进行按位与运算，得到元素在数组中的索引位置。
  • 如果该索引位置上的链表（或红黑树）为空，表示当前位置没有冲突，直接将键值对插入到该位置。
  • 如果该索引位置上的链表（或红黑树）不为空，表示发生了哈希冲突。
  • 如果链表的长度小于等于8（默认值），则继续使用链表进行插入，将新的键值对插入链表的末尾。
  • 如果链表的长度大于8，并且当前数组的长度大于64（默认值），则将链表转换为红黑树进行插入。
  • 如果链表的长度大于8，并且当前数组的长度小于等于64，则先进行扩容，再将键值对插入到新的位置。

扩容机制

HashMap在内部有一个负载因子（load factor）的概念，默认为0.75。负载因子表示哈希表的填充程度，当填充程度超过负载因子时，就会触发扩容操作。

当HashMap的容量达到阈值（容量乘以负载因子）时，会触发扩容。扩容操作将数组的大小增加一倍，并重新计算每个元素在新数组中的索引位置。

扩容过程中，HashMap会执行以下操作：

  • 创建一个新的两倍大小的数组。
  • 遍历旧数组中的每个元素，重新计算它们在新数组中的索引位置，并将它们插入到新数组中的对应位置。
  • 完成插入后，新数组将取代旧数组成为HashMap的内部数组。

需要注意的是，扩容操作是一个相对耗时的操作，因为需要重新计算索引位置并重新插入元素。因此，尽量提前估算需要存储的元素数量，以减少扩容操作的频率。

总结：

HashMap的put原理是根据键的哈希值和数组长度计算出索引位置，解决哈希冲突采用链表（或红黑树）进行存储。扩容机制是在填充程度超过负载因子时，将数组的大小增加一倍，并重新计算元素的索引位置，完成扩容操作。这些机制使得HashMap能够高效地存储和检索键值对。

哈希冲突是如何产生的

哈希冲突是在哈希表中发生的现象，当不同的键经过哈希函数计算后得到相同的哈希值，它们就会发生哈希冲突。哈希函数将键映射到哈希表的索引位置，而哈希冲突意味着多个键被映射到了同一个索引位置。

哈希冲突可以由多种原因引起，下面是一些常见的原因：

  • 不同的键具有相同的哈希码：哈希函数将键转换为哈希码，然后根据哈希码计算索引位置。如果不同的键具有相同的哈希码，它们就会被映射到同一个索引位置，从而产生哈希冲突。
  • 哈希函数的分布性不均匀：哈希函数应该尽可能均匀地将键分布到不同的索引位置。如果哈希函数的分布性不好，即使键的哈希码不同，它们也可能被映射到相同的索引位置，导致哈希冲突的发生。
  • 哈希表容量过小：哈希表的容量决定了可以存储键值对的数量。如果哈希表的容量较小，而要存储的键值对数量较多，那么哈希冲突的概率就会增加。这是因为索引位置的数量有限，当键的数量超过索引位置的数量时，必然会有多个键被映射到同一个索引位置。

哈希冲突是哈希表中常见的情况，而设计一个好的哈希函数和合适的哈希表容量可以尽量减少哈希冲突的发生。当发生哈希冲突时，常用的解决方法是采用链表或红黑树等数据结构来处理冲突，以保证在不同的键被映射到同一个索引位置时，仍然能够正确地存储和检索键值对。

为什么HashMap要采用链表和红黑树

HashMap采用链表和红黑树的主要目的是解决哈希冲突。当不同的键映射到相同的数组索引位置时，就会发生哈希冲突。解决哈希冲突的一种常见方法是使用链表来存储具有相同索引位置的键值对。

链表解决冲突的方式简单直接，新的键值对可以直接添加到链表的末尾。然而，当链表长度过长时，查找效率会变低。为了解决这个问题，Java 8引入了红黑树作为链表的替代结构，用于存储链表长度超过一定阈值的键值对。

红黑树是一种自平衡的二叉搜索树，具有较好的查找性能。当链表长度超过阈值（默认为8）且HashMap的容量超过一定大小（默认为64）时，会将链表转换为红黑树。这样，在搜索某个键值对时，使用红黑树的查找操作可以提高效率。

采用链表和红黑树的结构可以在大部分情况下保证HashMap的操作性能良好。链表适用于较小的冲突链，而红黑树适用于较大的冲突链。这样，在不同的冲突情况下，HashMap可以根据链表长度选择合适的数据结构，从而提高了插入、查找和删除等操作的效率。

需要注意的是，Java 8之前的HashMap使用的是纯链表来解决哈希冲突，没有红黑树的优化。而Java 8及之后的版本引入了红黑树的优化，进一步提升了HashMap的性能。

下面一起看下这个过程:

HashMap
+------------------------------------+
|                                    |
|    Bucket 0    |    Bucket 1    |    ...    |    Bucket n    |
|                                    |
+------------------------------------+

  • 初始状态下，HashMap由多个Bucket组成，每个Bucket可以存储多个键值对。
HashMap
+------------------------------------+
|                                    |
|  Bucket 0:                           |
|  +----------------+                |
|  | Key 1  | Value 1 |                |
|  +----------------+                |
|                                    |
|  Bucket 1:                           |
|  +----------------+                |
|  | Key 2  | Value 2 |                |
|  +----------------+                |
|                                    |
|     ...                             |
|                                    |
|  Bucket n:                           |
|  +----------------+                |
|  | Key k  | Value k |                |
|  +----------------+                |
|                                    |
+------------------------------------+
  • 当发生哈希冲突时，新的键值对需要添加到相同的 Bucket中。

HashMap
+------------------------------------+
|                                    |
|  Bucket 0:                           |
|  +----------------+                |
|  | Key 1  | Value 1 |                |
|  +----------------+                |
|  | Key m  | Value m |  --->          |
|  +----------------+    |           |
|                        |           |
|  Bucket 1:                           |
|  +----------------+                |
|  | Key 2  | Value 2 |                |
|  +----------------+                |
|                                    |
|     ...                             |
|                                    |
|  Bucket n:                           |
|  +----------------+                |
|  | Key k  | Value k |                |
|  +----------------+                |
|                                    |
+------------------------------------+
  • 哈希冲突发生后，新的键值对以链表的形式插入到Bucket中。
HashMap
+------------------------------------+
|                                    |
|  Bucket 0:                           |
|  +----------------+                |
|  | Key 1  | Value 1 |                |
|  +----------------+                |
|  | Key m  | Value m |  --->          |
|  +----------------+    |           |
|                        |           |
|                        V           |
|                      +----------------+             +----------------+
|                      | Key x  | Value x |   --->    | Key y  | Value y |
|                      +----------------+             +----------------+
|                                    |
|  Bucket 1:                           |
|  +----------------+                |
|  | Key 2  | Value 2 |                |
|  +----------------+                |
|                                    |
|     ...                             |
|                                    |
|  Bucket n:                           |
|  +----------------+                |
|  | Key k  | Value k |                |
|  +----------------+                |
|                                    |
+------------------------------------+
  • 当链表长度超过阈值时（默认为8），链表会被转换为红黑树，以提高查找效率。
HashMap
+------------------------------------+
|                                    |
|  Bucket 0:                           |
|  +-----------------------------------+               +----------------+
|  |                                   |               | Key m  | Value m |
|  +-----------------------------------+               +----------------+
|                                |                     |
|                                V                     |
|                              +----------------+             +----------------+
|                              | Key x  | Value x |   --->    | Key y  | Value y |
|                              +----------------+             +----------------+
|                                    |
|  Bucket 1:                           |
|  +----------------+                |
|  | Key 2  | Value 2 |                |
|  +----------------+                |
|                                    |
|     ...                             |
|                                    |
|  Bucket n:                           |
|  +----------------+                |
|  | Key k  | Value k |                |
|  +----------------+                |
|                                    |
+------------------------------------+

通过链表和红黑树的结构，HashMap可以在哈希冲突发生时，将键值对存储在同一个Bucket中，并根据链表长度和容量大小来选择合适的数据结构，从而提高插入、查找和删除等操作的效率。

HashMap线程安全吗?

HashMap在默认情况下不是线程安全的。它是一种非同步（non-synchronized）的数据结构，不会对多线程并发访问进行任何同步控制。这意味着如果多个线程同时修改HashMap的状态（如插入、删除、更新等操作），可能会导致不一致的结果或抛出异常。

在并发环境下使用非线程安全的HashMap可能会出现以下问题：

  • 结果不一致：当多个线程同时对HashMap进行修改时，可能会导致数据不一致的情况。例如，一个线程正在进行插入操作，而另一个线程同时进行删除操作，可能会导致数据丢失或错误的结果。
  • 死循环：在并发环境下，如果多个线程同时进行扩容或链表转换为红黑树等操作，可能会导致死循环或无限循环的情况。

为了在多线程环境下安全地使用HashMap，可以采用以下方法之一：

  • 使用线程安全的Map实现：Java提供了线程安全的Map实现，如ConcurrentHashMap。ConcurrentHashMap使用了一些机制来确保线程安全，如分段锁（Segment Locking）和CAS操作（Compare and Swap），从而允许多个线程同时进行读操作，以及一定程度上的并发写操作。
  • 使用同步控制手段：如果需要使用普通的HashMap，但又要保证线程安全，可以通过显式地使用同步控制手段来保护HashMap的操作。例如，可以使用synchronized关键字或使用ReentrantLock来保护对HashMap的并发访问。

需要根据具体的应用场景和线程安全要求来选择合适的方案。如果需要在多线程环境中使用HashMap，并希望保证线程安全和高性能，推荐使用ConcurrentHashMap或其他线程安全的Map实现。

上文提到了ConcurrentHashMap是线程安全的，能说说它的底层实现机制吗?

ConcurrentHashMap是Java中的线程安全的哈希表实现，它是基于哈希表和链表（或红黑树）的数据结构，并使用了一些特殊的技术来实现线程安全和高并发性能。

下面是ConcurrentHashMap的底层实现要点：

  • 分段锁（Segment Locking）：ConcurrentHashMap将整个哈希表分成多个段（Segment），每个段维护着一个独立的哈希表，具有自己的锁。不同的线程可以同时访问不同的段，从而实现了一定程度的并发性。
  • Hash桶（Hash Buckets）：每个段包含多个哈希桶，每个哈希桶是一个链表或红黑树，用于解决哈希冲突。哈希桶中的节点称为Node，存储了键值对的数据。
  • CAS操作（Compare and Swap）：ConcurrentHashMap使用CAS操作来进行并发的插入、更新和删除操作。CAS操作是一种无锁的原子操作，可以在不使用锁的情况下修改共享数据。通过使用CAS操作，ConcurrentHashMap能够在并发环境下实现高效的并发更新。
  • 锁分离技术：ConcurrentHashMap在并发更新时，只需要锁定对应段（Segment），而不需要锁定整个哈希表。这样可以最大程度地减小锁的粒度，提高并发性能。
  • 自动扩容：与普通的HashMap类似，ConcurrentHashMap也支持自动扩容。当哈希表的负载因子（load factor）超过阈值时，ConcurrentHashMap`会自动进行扩容操作，以保证哈希表的性能。

通过分段锁、CAS操作和锁分离等技术，ConcurrentHashMap实现了高度的并发性能，允许多个线程同时读取并发修改哈希表的状态，而不需要显式的同步控制。这使得ConcurrentHashMap成为处理并发场景下的首选Map实现之一。

首先，让我们看一下ConcurrentHashMap的整体结构：

ConcurrentHashMap
+-----------------------------------+
|                                   |
|       Segment 0      |      Segment 1      |  ...  |    Segment n      |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|   |  Hash Bucket |   |   |  Hash Bucket |   |      |   |  Hash Bucket |   |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|          |                    |                   |                    |
|          V                    V                   V                    |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|   |    Node     |   |   |    Node     |   |  ... |   |    Node     |   |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|          |                    |                   |                    |
|          V                    V                   V                    |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|   |    Node     |   |   |    Node     |   |      |   |    Node     |   |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|          |                    |                   |                    |
|          V                    V                   V                    |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|   |    Node     |   |   |    Node     |   |      |   |    Node     |   |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|          |                    |                   |                    |
|          V                    V                   V                    |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|   |    Node     |   |   |    Node     |   |      |   |    Node     |   |
|   +-------------+   |   +-------------+   |      |   +-------------+   |
|          |                    |                   |                    |
|          V                    V                   V                    |
|         ...                  ...                 ...                  |
|                                   |
+-----------------------------------+

  • ConcurrentHashMap由多个Segment（段）组成，每个Segment维护着一个独立的哈希表，具有自己的锁。不同的线程可以同时访问不同的Segment，从而实现并发性。
  • 每个Segment包含多个哈希桶（Hash Bucket），每个哈希桶存储了键值对的数据。哈希桶可以是链表或红黑树，用于解决哈希冲突。
  • 每个哈希桶中的节点（Node）存储了键值对的数据。节点可以是链表节点或红黑树节点，具体的数据结构取决于哈希桶中的元素数量和阈值。
  • 并发插入操作
Thread 1                 Thread 2
  |                         |
  V                         V
Insert key1:value1       Insert key2:value2
  |                         |
  V                         V
  |---Hash(key1)---------->|
  |                         |
  V                         V
  |---Lock Segment 0------->|
  |                         |
  V                         V
  |---Find Hash Bucket----->|
  |                         |
  V                         V
  |---Insert into Bucket--->|
  |                         |
  V                         V
  |                         |
Insert completed         Insert completed

  • 并发删除操作
Thread 1                 Thread 2
  |                         |
  V                         V
Delete key1               Delete key2
  |                         |
  V                         V
  |---Hash(key1)---------->|
  |                         |
  V                         V
  |---Lock Segment 0------->|
  |                         |
  V                         V
  |---Find Hash Bucket----->|
  |                         |
  V                         V
  |---Delete from Bucket--->|
  |                         |
  V                         V
  |                         |
Delete completed         Delete completed

在并发更新时，ConcurrentHashMap通过锁分离的方式，只锁定对应的Segment或Hash Bucket，而不需要锁定整个哈希表。这样可以最大程度地减小锁的粒度，提高并发性能。

结束语

大家可以针对自己薄弱的地方进行复习, 然后多总结，形成自己的理解，不要去背~

本着把自己知道的都告诉大家，如果本文对您有所帮助，点赞+关注鼓励一下呗~

相关文章

项目源码(源码已更新 欢迎star⭐️)

往期设计模式相关文章

设计模式项目源码(源码已更新 欢迎star⭐️)

Kafka 专题学习

项目源码(源码已更新 欢迎star⭐️)

ElasticSearch 专题学习

项目源码(源码已更新 欢迎star⭐️)

往期并发编程内容推荐

推荐 SpringBoot & SpringCloud (源码已更新 欢迎star⭐️)

博客(阅读体验较佳)













文章标签：
云消息队列 Kafka 版
检索分析服务 Elasticsearch版
Java
容器
消息中间件
NoSQL
索引
Redis
Kafka
安全
存储
设计模式
关键词：
HashMap concurrenthashmap
程序员皮卡秋(公众号程序员皮卡秋)
目录
相关文章
海风极客
|
6月前
|
存储 安全 算法
详解Java中HashMap、HashTable、ConcurrentHashMap常见问题
详解Java中HashMap、HashTable、ConcurrentHashMap常见问题
海风极客
68 0
qhhf_地道酬勤
|
1月前
|
存储 开发者
HashMap和Hashtable的key和value可以为null吗，ConcurrentHashMap呢
HashMap的key可以为null，value也可以为null；Hashtable的key不允许为null，value也不能为null；ConcurrentHashMap的key不允许为null
qhhf_地道酬勤
58 0
土木林森
|
3月前
|
存储 Java 开发者
HashMap线程安全问题大揭秘：ConcurrentHashMap、自定义同步，一文让你彻底解锁！
【8月更文挑战第24天】HashMap是Java集合框架中不可或缺的一部分，以其高效的键值对存储和快速访问能力广受开发者欢迎。本文深入探讨了HashMap在JDK 1.8后的底层结构——数组+链表+红黑树混合模式，这种设计既利用了数组的快速定位优势，又通过链表和红黑树有效解决了哈希冲突问题。数组作为基石，每个元素包含一个Node节点，通过next指针形成链表；当链表长度过长时，采用红黑树进行优化，显著提升性能。此外，还介绍了HashMap的扩容机制，确保即使在数据量增大时也能保持高效运作。通过示例代码展示如何使用HashMap进行基本操作，帮助理解其实现原理及应用场景。
土木林森
53 1
热爱技术的小郑
|
3月前
|
安全 Java
【Java集合类面试十六】、HashMap与ConcurrentHashMap有什么区别？
HashMap是非线程安全的，而ConcurrentHashMap通过减少锁粒度来提高并发性能，检索操作无需锁，从而提供更好的线程安全性和性能。
热爱技术的小郑
48 1
土木林森
|
3月前
|
开发者 C# UED
WPF与多媒体：解锁音频视频播放新姿势——从界面设计到代码实践，全方位教你如何在WPF应用中集成流畅的多媒体功能
【8月更文挑战第31天】本文以随笔形式介绍了如何在WPF应用中集成音频和视频播放功能。通过使用MediaElement控件，开发者能轻松创建多媒体应用程序。文章详细展示了从创建WPF项目到设计UI及实现媒体控制逻辑的过程，并提供了完整的示例代码。此外，还介绍了如何添加进度条等额外功能以增强用户体验。希望本文能为WPF开发者提供实用的技术指导与灵感。
土木林森
141 0
嘟嘟嘟嘟嘟嘟
|
4月前
|
安全 Java
多线程线程安全问题之避免ThreadLocal的内存泄漏，如何解决
多线程线程安全问题之避免ThreadLocal的内存泄漏，如何解决
嘟嘟嘟嘟嘟嘟
36 0
杰哥在此
|
4月前
|
存储 安全 Java
Java面试题：请解释Java内存模型，并说明如何在多线程环境下使用synchronized关键字实现同步，阐述ConcurrentHashMap与HashMap的区别，以及它如何在并发环境中提高性能
Java面试题：请解释Java内存模型，并说明如何在多线程环境下使用synchronized关键字实现同步，阐述ConcurrentHashMap与HashMap的区别，以及它如何在并发环境中提高性能
杰哥在此
39 0
JavaBuild
|
6月前
|
存储 C++
为什么HashMap的键值可以为null，而ConcurrentHashMap不行？
为什么HashMap的键值可以为null，而ConcurrentHashMap不行？
JavaBuild
85 1
JavaBuild
|
6月前
|
安全 Java 调度
HashMap很美好，但线程不安全怎么办？ConcurrentHashMap告诉你答案！
HashMap很美好，但线程不安全怎么办？ConcurrentHashMap告诉你答案！
JavaBuild
97 1
JAVA开发大本营
|
存储 安全 Java
java学会这些，我就入门啦！（基础篇六）HashMap、Hashtable、ConcurrentHashMap的原理与区别
java学会这些，我就入门啦！（基础篇六）HashMap、Hashtable、ConcurrentHashMap的原理与区别
JAVA开发大本营
67 0