当前位置：首页 > article >正文

Java集合ConcurrentHashMap——针对实习面试

article 2024/11/22 23:45:23

Java集合ConcurrentHashMap

在这里插入图片描述

ConcurrentHashMap的特性是什么？

线程安全性
- 多线程并发读写安全：ConcurrentHashMap是为了在多线程环境下安全地操作哈希表而设计的。与非线程安全的HashMap不同，它允许多个线程同时对其进行读取和写入操作，而不会出现数据不一致或并发异常的情况。
- 细粒度锁机制：它采用了一种更精细的锁策略。在Java 7及以前，ConcurrentHashMap采用分段锁（Segment）的方式，将整个哈希表分成多个段（Segment），每个段就像一个独立的小哈希表，不同段之间的操作互不影响，在进行操作时只需要锁住对应的段，而不是整个哈希表。例如，假设有16个段，多个线程操作不同段中的元素时可以同时进行，这大大提高了并发性能。在Java 8之后，这种锁机制进行了优化，采用了CAS（Compare - And - Swap）操作和synchronized关键字来实现更细粒度的锁。当对某个桶（bucket）进行操作时，尽量只锁住这个桶，减少锁的范围，进一步提高并发读写的效率。
高效的并发性能
- 读操作的高并发支持：读操作在大多数情况下是无锁的。这是因为它利用了volatile关键字来保证可见性，当一个线程修改了某个桶中的元素后，其他线程能够立即看到这个修改。例如，当多个线程同时读取ConcurrentHashMap中的元素时，它们可以自由地访问而不会相互阻塞，这样在高并发读取场景下能够提供非常高的性能。
- 写操作的并发优化：对于写操作，如put和remove，虽然需要获取锁，但由于采用了细粒度的锁机制，锁的竞争范围被缩小。而且CAS操作的使用使得在一些情况下可以避免使用重量级的锁，比如在对元素进行更新时，如果没有冲突，可以通过CAS直接更新，从而减少了线程阻塞等待的时间，提高了并发写操作的效率。
数据结构与功能完整性
- 类似HashMap的功能：它基本保留了HashMap的功能特性，如存储键 - 值（key - value）对，可以通过键来获取对应的值。支持常见的操作方法，像put方法用于插入键值对，get方法用于获取指定键对应的的值，remove方法用于移除指定键的键值对。
- 动态扩容机制：ConcurrentHashMap也有自己的扩容机制，并且在扩容过程中也能保证一定程度的并发访问。在扩容时，它不会像HashMap那样完全阻塞其他操作，而是采用了一种更复杂的多阶段扩容策略，使得在扩容期间部分操作仍然可以正常进行，进一步提高了整体的可用性和性能。

HashMap和ConcurrentHashMap的区别？

线程安全性
- HashMap：
  - 不是线程安全的。在多线程环境下，如果多个线程同时对HashMap进行读写操作，可能会导致数据不一致、死循环等问题。例如，当一个线程正在对HashMap进行扩容操作，而另一个线程同时在插入新元素，可能会出现数据丢失或者链表形成环（在旧版本Java中，扩容时对链表的处理可能导致这种情况）等异常情况。
- ConcurrentHashMap：
  - 是专门为多线程环境设计的线程安全的哈希表。它采用了精细的锁机制来保证在高并发情况下数据的安全性。在Java 7及以前，使用分段锁（Segment），把哈希表分成多个段，每个段类似一个独立的小哈希表，不同段之间的操作互不干扰，只要锁住相应的段就能保证操作安全。在Java 8以后，使用CAS（Compare - And - Swap）操作和更细粒度的synchronized关键字，尽量减少锁的范围，当对某个桶（bucket）进行操作时，通常只锁住这个桶，提高了并发性能。
性能特点
- HashMap：
  - 在单线程环境下，由于没有锁的开销，性能通常比ConcurrentHashMap好。它的插入、删除和查找操作在理想情况下（没有哈希冲突）时间复杂度接近 $O (1)$ 。但是在多线程环境下，因为其非线程安全的特性，不能直接使用，否则会出现各种并发问题。
- ConcurrentHashMap：
  - 虽然在多线程环境下保证了安全性，但由于锁机制的存在，会有一定的性能开销。不过，它在高并发的读操作场景下性能表现出色，因为读操作大部分情况下是无锁的，利用了volatile关键字来保证数据的可见性。对于写操作，它通过细粒度的锁和CAS操作尽量减少锁的竞争和阻塞时间，使得在多线程环境下的性能损耗控制在一定范围内，其性能仍然可以满足高并发场景的需求。
数据结构细节
- HashMap：
  - 底层主要是由数组和链表（Java 8以后，当链表长度大于8且数组长度大于等于64时，链表转换为红黑树）组成。通过计算键（key）的哈希值来确定元素在数组中的存储位置（索引），如果发生哈希冲突，新的元素以链表（或红黑树）的形式存储在该索引对应的位置。
- ConcurrentHashMap：
  - 在Java 7中，数据结构为Segment数组和HashEntry数组，Segment本身就是一个可重入锁（ReentrantLock），它维护了一个HashEntry数组，这样就形成了分段锁的结构。在Java 8以后，结构和HashMap类似，也是数组、链表和红黑树，但在并发控制机制上做了很大的改进，采用CAS和synchronized来保证并发安全。
适用场景
- HashMap：
  - 适用于单线程环境下，对数据的插入、删除和查找操作比较频繁，并且对元素的顺序没有严格要求的场景。例如，在一个简单的本地缓存系统中，只有一个线程负责缓存数据的管理，就可以使用HashMap。
- ConcurrentHashMap：
  - 主要用于多线程并发环境下，需要频繁进行数据的读写操作的场景。比如，在一个多线程的Web服务器中，用于存储和管理用户的会话信息（键为会话ID，值为会话相关的数据），可以保证在多个线程同时访问和修改会话信息时的安全性和高效性。

说说ConcurrentHashMap的底层实现

Java 7及以前的底层实现
- 数据结构：采用了分段锁（Segment）的机制。整个ConcurrentHashMap由多个Segment组成，每个Segment相当于一个独立的小哈希表，包含一个HashEntry数组、一个负载因子（loadFactor）和一个阈值（threshold）用于控制扩容。HashEntry数组用于存储键 - 值（key - value）对，其结构和普通的HashMap中的节点类似，包含了键、值、下一个节点的引用等信息。
- 锁机制：Segment本身是一个可重入锁（ReentrantLock）。在进行操作时，例如put或remove操作，只需要锁定对应的Segment，而不是整个ConcurrentHashMap。这样不同Segment之间的操作可以并发进行。例如，假设有两个不同的Segment，线程A对Segment1进行操作，线程B对Segment2进行操作，这两个操作可以同时执行，大大提高了并发性能。
- 操作过程：
  - put操作：首先根据键的哈希值确定它所在的Segment。然后获取该Segment的锁，在锁定的Segment内，按照类似于普通HashMap的方式查找键是否已经存在。如果存在，则更新值；如果不存在，则在合适的位置插入新的HashEntry。最后释放Segment的锁。
  - get操作：计算键所在的Segment，然后在该Segment内查找键对应的value。由于get操作不需要修改数据结构，在大多数情况下，它不需要获取锁，只是简单地遍历HashEntry数组和链表来查找键，这利用了volatile关键字保证了共享变量的可见性，使得在多线程环境下读取数据是安全的。
Java 8及以后的底层实现
- 数据结构：放弃了分段锁的设计，整体结构和普通的HashMap更加相似，主要由数组、链表（当链表长度大于8且数组长度大于等于64时转换为红黑树）组成。数组中的每个元素（桶）可以存储一个或多个键值对。这种结构的改变使得在单线程操作时性能和普通HashMap更接近。
- 锁机制：采用了CAS（Compare - And - Swap）操作和更细粒度的synchronized关键字来保证并发安全。
  - CAS操作：在一些操作中，例如在更新节点的引用（如在链表中插入新节点或者将链表转换为红黑树时更新节点之间的引用），会使用CAS操作。CAS操作是一种乐观锁机制，它会比较当前内存中的值和期望的值，如果相同，则将新的值更新到内存中。通过这种方式，在没有冲突的情况下可以避免使用重量级的锁，提高并发性能。
  - synchronized关键字：当需要对某个桶（bucket）进行操作，如插入、删除或修改节点时，会使用synchronized关键字来锁住这个桶。由于锁的范围缩小到了单个桶，相比于Java 7中的分段锁，进一步提高了并发性能，特别是在高并发的读写场景下。
- 操作过程：
  - put操作：首先计算键的哈希值和在数组中的索引。如果索引位置为空，则通过CAS操作尝试插入新的键值对。如果索引位置已经有元素（发生哈希冲突），则使用synchronized关键字锁住这个桶，然后按照和普通HashMap类似的方式处理，如查找键是否存在，更新值或者插入新的键值对。如果链表长度达到转换红黑树的条件，还需要进行链表到红黑树的转换操作。
  - get操作：和普通HashMap类似，先计算键的哈希值和索引，然后在索引位置查找键对应的value。在查找过程中，如果是链表则逐个遍历节点，如果是红黑树则使用红黑树的查找算法。由于数据结构中的元素（如节点的引用）使用了volatile关键字来保证可见性，所以在多线程环境下读取操作是安全的，并且在大多数情况下不需要获取锁。