查漏补缺第五期(HashMap & ConcurrentHashMap)
前言
目前正在出一个查漏补缺专题系列教程, 篇幅会较多, 喜欢的话，给个关注❤️ ~
本专题主要以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 专题学习
- 一起来学kafka之Kafka集群搭建
- 一起来学kafka之整合SpringBoot基本使用
- 一起来学kafka之整合SpringBoot深入使用(一)
- 一起来学kafka之整合SpringBoot深入使用(二)
- 一起来学kafka之整合SpringBoot深入使用(三)
项目源码(源码已更新 欢迎star⭐️)
ElasticSearch 专题学习
项目源码(源码已更新 欢迎star⭐️)
往期并发编程内容推荐
- Java多线程专题之线程与进程概述
- Java多线程专题之线程类和接口入门
- Java多线程专题之进阶学习Thread(含源码分析)
- Java多线程专题之Callable、Future与FutureTask(含源码分析)
- 面试官: 有了解过线程组和线程优先级吗
- 面试官: 说一下线程的生命周期过程
- 面试官: 说一下线程间的通信
- 面试官: 说一下Java的共享内存模型
- 面试官: 有了解过指令重排吗，什么是happens-before
- 面试官: 有了解过volatile关键字吗 说说看
- 面试官: 有了解过Synchronized吗 说说看
- Java多线程专题之Lock锁的使用
- 面试官: 有了解过ReentrantLock的底层实现吗？说说看
- 面试官: 有了解过CAS和原子操作吗？说说看
- Java多线程专题之线程池的基本使用
- 面试官: 有了解过线程池的工作原理吗？说说看
- 面试官: 线程池是如何做到线程复用的？有了解过吗，说说看
- 面试官: 阻塞队列有了解过吗?说说看
- 面试官: 阻塞队列的底层实现有了解过吗? 说说看
- 面试官: 同步容器和并发容器有用过吗? 说说看
- 面试官: CopyOnWrite容器有了解过吗? 说说看
- 面试官: Semaphore在项目中有使用过吗？说说看(源码剖析)
- 面试官: Exchanger在项目中有使用过吗？说说看(源码剖析)
- 面试官: CountDownLatch有了解过吗？说说看(源码剖析)
- 面试官: CyclicBarrier有了解过吗？说说看(源码剖析)
- 面试官: Phaser有了解过吗？说说看
- 面试官: Fork/Join 有了解过吗？说说看（含源码分析）
- 面试官: Stream并行流有了解过吗？说说看