「浅谈HashMap」

来自 gpt 的摘要： HashMap 是一种基于数组和链表（或红黑树）的数据结构，用于存储键值对。在插入元素时，通过键的 hashCode() 方法计算哈希值

来自 gpt 的摘要： HashMap 是一种基于数组和链表（或红黑树）的数据结构，用于存储键值对。在插入元素时，通过键的 hashCode() 方法计算哈希值，并经过扰动函数确定元素在数组中的位置。Java 8 之前，HashMap 通过链表解决哈希碰撞问题，而在 Java 8 之后，当链表长度超过 8 时，链表会转换为红黑树，以提升效率。当 HashMap 的元素数量达到其容量的 75% 时，触发扩容，容量通常增加为原来的两倍。 HashMap 和 HashSet 的主要区别在于前者存储键值对，而后者仅存储对象。HashSet 的底层依赖于 HashMap，通过 HashMap 的键来存储对象。相比之下，HashMap 是非线程安全的，而 Hashtable 是线程安全的，但性能较低。此外，HashMap 允许 null 键和值，而 Hashtable 不允许。 HashMap 在多线程环境下可能不安全，尤其在插入和扩容操作时，可能导致数据不一致或死循环。要解决这个问题，可以使用 ConcurrentHashMap，它通过细粒度锁和 CAS（Compare-And-Swap）机制保证并发环境下的安全性。

HashMap 底层原理？HashMap 底层是数组和链表（Java 8 之前）或红黑树（Java 8 之后）的结合体。插入时通过 hashCode() 计算哈希值，经过扰动函数处理后确定存放位置。如果发生哈希碰撞，Java 8 之前通过链表解决，Java 8 之后当链表长度超过 8 时且数组容量超过 64 时转换为红黑树以提高效率。此外，HashMap 的默认负载因子是 0.75，当元素数量达到容量的 75% 时会触发扩容操作。

HashMap 和 HashSet 的区别？HashMap 存储键值对，HashSet 仅存储对象。

HashSet 底层基于 HashMap，插入元素时，HashSet 使用 HashMap 的键来存储对象。

HashMap 和 Hashtable 的区别？HashMap 是非线程安全的，Hashtable 是线程安全的，但性能较低。

HashMap 允许存储 null 键和值，Hashtable 不允许。

Java 8 之后 HashMap 在链表长度大于 8 时会转换为红黑树，而 Hashtable 没有这种机制。

HashMap 的负载因子？负载因子决定了何时扩容，默认是 0.75。较低的负载因子减少碰撞，但会浪费空间，较高的负载因子减少空间占用，但可能增加哈希碰撞的概率。

达到负载因子的阈值后，HashMap 具体扩容的倍数？当 HashMap 达到负载因子的阈值时，会进行扩容，容量一般是当前容量的两倍。扩容时，HashMap 会创建一个新数组，并将旧数组中的元素重新哈希到新数组中。

从红黑树转回链表为什么阈值是 6？在 HashMap 中，链表长度超过 8 时会转为红黑树，当长度减少到 6 时会转回链表。这是为了平衡空间和时间的复杂度。红黑树的操作虽然更快（O (log n)），但维护成本和内存占用比链表高，因此当节点较少时，转回链表能提高效率。

HashMap 时间复杂度？插入操作（put）：平均 O (1)，最坏 O (n)（当发生大量碰撞时）。

查找操作（get）：平均 O (1)，最坏 O (n)，使用红黑树后最坏情况为 O (log n)。

删除操作（remove）：平均 O (1)，最坏 O (n)，使用红黑树时为 O (log n)。

遍历操作：O (n)。

为什么 HashMap 是线程不安全的，哪个操作可能导致它线程不安全，如果仍想用你该如何解决？HashMap 是线程不安全的，尤其在多线程环境下插入和扩容操作时会出现数据不一致或死循环的风险。例如，多个线程同时对 HashMap 进行 put 操作时，可能会导致数据覆盖或丢失。此外，扩容过程中的 rehash 操作也可能引发问题。

要解决这个问题，可以使用以下方法：

Collections.synchronizedMap：将 HashMap 包装成线程安全的 Map。

ConcurrentHashMap：更高效的线程安全 Map 实现，适合高并发场景。

手动同步：通过 synchronized 关键字对共享的 HashMap 进行操作。

有哪些线程安全的 Map？ConcurrentHashMap：适用于高并发环境，采用分段锁机制。

Collections.synchronizedMap：将非线程安全的 Map 包装成线程安全的。

ConcurrentSkipListMap：线程安全的有序 Map，基于跳表结构。

Hashtable：老旧的线程安全 Map，每个方法上都使用同步，性能较低。

ConcurrentHashMap 的 put 过程？计算哈希值：对键进行哈希计算，得到哈希值。

定位桶位置：根据哈希值找到桶（bucket）的索引。

检查数组是否初始化：如果数组未初始化，执行线程安全的初始化操作。

插入操作：

如果桶为空，使用 CAS 操作插入新节点；

如果桶不为空，使用 synchronized 锁定该桶，处理链表或红黑树中的节点插入操作。

处理哈希碰撞：当冲突发生时，遍历链表或红黑树进行插入操作。链表长度超过阈值（默认 8）时转换为红黑树。

结束操作：释放锁并更新状态（如元素数量）。

通过 CAS、细粒度锁、链表转红黑树的机制，ConcurrentHashMap 高效地处理并发插入操作。

ConcurrentHashMap 如何保证线程安全？JDK 1.7 分段锁：使用 Segment 将哈希表分为多个部分，每个部分有独立锁，允许并发访问不同段的数据。

JDK 1.8 无锁+细粒度锁：抛弃 Segment，采用 Node + CAS + synchronized 机制，锁只在必要时针对某个桶，减少锁竞争，提高并发度。

CAS 操作：保证无锁下的原子性更新操作。

读操作：大多数读操作为无锁，减少性能开销。

JDK 1.8 中，ConcurrentHashMap 实现了更高效的并发控制，锁粒度更细，提高了读写性能。

HashMap 为什么使用红黑树？自平衡特性：红黑树保证了最坏情况下操作的时间复杂度为 (O (\log n))，通过着色和旋转来维持平衡。

高效的插入和删除：红黑树的旋转操作相对较少，性能优于其他平衡树（如 AVL 树）。

链表优化：链表长度超过阈值时转换为红黑树，大幅提升查找效率。

红黑树在性能和复杂度上更适合解决 HashMap 中的高冲突情况。