hashmap循环链表（hashmap循环链表是如何产生的）

## HashMap 中的循环链表### 简介HashMap 作为一种常用的数据结构，其内部通常采用数组 + 链表（或红黑树）的方式来解决哈希冲突。在 Java 1.7 及之前的版本中，HashMap 使用了

头插法

来构建链表，这在某些情况下会导致链表过长，形成近似线性结构，从而影响 HashMap 的性能。为了解决这个问题，Java 1.8 引入了

尾插法

构建链表，并在链表长度超过一定阈值时，将链表转换为红黑树，以优化查询效率。然而，在并发场景下，无论是头插法还是尾插法都可能导致

循环链表

的问题，本文将详细介绍 HashMap 中循环链表的产生原因、影响以及解决方案。### 循环链表的产生#### 1. 并发扩容与头插法在 Java 1.7 及之前的版本中，HashMap 采用头插法插入新节点，并在扩容时会进行链表的迁移。由于扩容操作涉及到链表节点的重新定位，如果在多线程环境下，两个线程同时进行扩容操作，就可能导致循环链表的产生。假设有两个线程 A 和 B，同时对 HashMap 进行扩容，此时链表结构如下：``` Thread A: ... -> Node1 -> Node2 -> null Thread B: ... -> Node1 -> Node2 -> null ```两个线程都需要将 `Node1` 和 `Node2` 迁移到新的数组位置，如果执行顺序如下：1. 线程 A 将 `Node1` 的 `next` 指针指向新的 `Node2` 位置。 2. 线程 B 将 `Node2` 的 `next` 指针指向新的 `Node1` 位置。 3. 线程 A 将 `Node2` 的 `next` 指针指向新的 `Node1` 位置。最终会导致 `Node1` 和 `Node2` 形成循环链表。#### 2. 并发扩容与尾插法尽管 Java 1.8 及以后的版本采用了尾插法来缓解循环链表的问题，但在并发场景下，仍然有可能出现循环链表。这是因为，虽然尾插法避免了在迁移链表时修改节点的 `next` 指针，但在扩容过程中，仍然需要修改链表的头节点。如果多个线程同时尝试修改头节点，就可能导致链表断裂，从而形成循环链表。### 循环链表的影响循环链表的存在会对 HashMap 造成以下影响：1.

死循环

: 当出现循环链表时，如果调用 `get()` 方法查找对应 key 对应的 value，就会陷入死循环，导致 CPU 占用率飙升，程序无法正常运行。 2.

数据丢失

: 循环链表会导致部分节点无法被访问到，从而造成数据丢失。### 解决方案为了避免循环链表的产生，可以采取以下措施：1.

使用 ConcurrentHashMap

: ConcurrentHashMap 是线程安全的 HashMap 实现，它通过锁分段技术和 CAS 操作来保证线程安全，避免了循环链表的产生。 2.

使用其他数据结构

: 如果不需要线程安全，可以考虑使用 TreeMap 或 LinkedHashMap 等其他数据结构来替代 HashMap。 3.

避免并发操作

: 尽量避免在多线程环境下对 HashMap 进行并发操作，例如可以使用 Collections.synchronizedMap() 方法将 HashMap 包装成线程安全的 Map。### 总结循环链表是 HashMap 在并发场景下可能出现的一种异常情况，它会导致死循环和数据丢失等问题。为了避免循环链表的产生，建议使用线程安全的 ConcurrentHashMap，或采取其他措施来保证线程安全。

HashMap 中的循环链表

简介HashMap 作为一种常用的数据结构，其内部通常采用数组 + 链表（或红黑树）的方式来解决哈希冲突。在 Java 1.7 及之前的版本中，HashMap 使用了**头插法**来构建链表，这在某些情况下会导致链表过长，形成近似线性结构，从而影响 HashMap 的性能。为了解决这个问题，Java 1.8 引入了**尾插法**构建链表，并在链表长度超过一定阈值时，将链表转换为红黑树，以优化查询效率。然而，在并发场景下，无论是头插法还是尾插法都可能导致**循环链表**的问题，本文将详细介绍 HashMap 中循环链表的产生原因、影响以及解决方案。

循环链表的产生

1. 并发扩容与头插法在 Java 1.7 及之前的版本中，HashMap 采用头插法插入新节点，并在扩容时会进行链表的迁移。由于扩容操作涉及到链表节点的重新定位，如果在多线程环境下，两个线程同时进行扩容操作，就可能导致循环链表的产生。假设有两个线程 A 和 B，同时对 HashMap 进行扩容，此时链表结构如下：``` Thread A: ... -> Node1 -> Node2 -> null Thread B: ... -> Node1 -> Node2 -> null ```两个线程都需要将 `Node1` 和 `Node2` 迁移到新的数组位置，如果执行顺序如下：1. 线程 A 将 `Node1` 的 `next` 指针指向新的 `Node2` 位置。 2. 线程 B 将 `Node2` 的 `next` 指针指向新的 `Node1` 位置。 3. 线程 A 将 `Node2` 的 `next` 指针指向新的 `Node1` 位置。最终会导致 `Node1` 和 `Node2` 形成循环链表。

2. 并发扩容与尾插法尽管 Java 1.8 及以后的版本采用了尾插法来缓解循环链表的问题，但在并发场景下，仍然有可能出现循环链表。这是因为，虽然尾插法避免了在迁移链表时修改节点的 `next` 指针，但在扩容过程中，仍然需要修改链表的头节点。如果多个线程同时尝试修改头节点，就可能导致链表断裂，从而形成循环链表。

循环链表的影响循环链表的存在会对 HashMap 造成以下影响：1. **死循环**: 当出现循环链表时，如果调用 `get()` 方法查找对应 key 对应的 value，就会陷入死循环，导致 CPU 占用率飙升，程序无法正常运行。 2. **数据丢失**: 循环链表会导致部分节点无法被访问到，从而造成数据丢失。

解决方案为了避免循环链表的产生，可以采取以下措施：1. **使用 ConcurrentHashMap**: ConcurrentHashMap 是线程安全的 HashMap 实现，它通过锁分段技术和 CAS 操作来保证线程安全，避免了循环链表的产生。 2. **使用其他数据结构**: 如果不需要线程安全，可以考虑使用 TreeMap 或 LinkedHashMap 等其他数据结构来替代 HashMap。 3. **避免并发操作**: 尽量避免在多线程环境下对 HashMap 进行并发操作，例如可以使用 Collections.synchronizedMap() 方法将 HashMap 包装成线程安全的 Map。

总结循环链表是 HashMap 在并发场景下可能出现的一种异常情况，它会导致死循环和数据丢失等问题。为了避免循环链表的产生，建议使用线程安全的 ConcurrentHashMap，或采取其他措施来保证线程安全。