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

浅析hashmap

news 2025/6/13 10:05:49

hashmap底层

底层结构是数组 + 链表 + 红黑树。

数组：也被叫做哈希桶，每个元素是一个链表或红黑树的头节点。数组的每个位置被称作一个桶（bucket），通过哈希值确定元素存于哪个桶。
链表：当多个键的哈希值相同（哈希冲突）时，这些键值对会以链表形式存储在同一个桶中。
红黑树：当链表长度达到一定阈值（默认为 8），且数组长度达到 64 时，链表会转化为红黑树，以此提升查找效率。

工作原理

存储键值对

当调用 put(key, value) 方法时：

计算 key 的哈希值：借助 hash() 方法算出 key 的哈希值。
确定桶的位置：用哈希值对数组长度取模，得到存储的桶索引。
处理哈希冲突：
- 若桶为空，直接创建新节点存入。
- 若桶已有节点，遍历链表或红黑树：
  - 若 key 已存在，更新对应的值。
  - 若 key 不存在，添加新节点。若链表长度达到 8 且数组长度达到 64，将链表转换为红黑树。

获取键值对

调用 get(key) 方法时：

计算 key 的哈希值：使用相同的 hash() 方法。
确定桶的位置：通过哈希值对数组长度取模。
查找元素：在对应的桶的链表或红黑树中查找 key，若找到则返回对应的值，否则返回 null。

扩容机制

触发条件：元素数量超过阈值（容量 × 负载因子）时触发。
扩容动作：容量翻倍，重新计算元素位置并迁移。
JDK 1.8 优化：通过位运算快速定位新索引，避免全量哈希计算，提升扩容效率

假设旧数组长度为 16，负载因子 0.75，阈值为 12：

插入第 13 个元素时触发扩容。
新容量为 32，新阈值为 24（32×0.75）。
遍历旧数组每个桶：
- 对于桶中元素，计算hash & 16
  
  oldCapacity
  - 若结果为 0，元素留在原索引位置。
  - 若结果为 16，元素移至 原索引 + 16 的位置

线程安全性相关问题

hashMap在多线程环境下是不安全的，多个线程操作同一个节点，会造成链表结构的被破坏或数据的丢失

线程安全的替代类

1. Hashtable

import java.util.Hashtable;Hashtable<String, Integer> table = new Hashtable<>();
table.put("key", 1); // 所有方法都加 synchronized

特性：
- 所有方法都用 synchronized 修饰，保证线程安全。
- 不允许 null 键或值（否则抛出 NullPointerException）。
缺点：
- 锁粒度太大（整个 Hashtable 对象），多线程并发性能差。
- 已被 ConcurrentHashMap 替代

2. Collections.synchronizedMap

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
syncMap.put("key", 1); // 所有操作通过同步包装器实现

特性：
- 基于普通 HashMap，通过包装器对所有方法加 synchronized。
- 允许 null 键和值（前提是底层 HashMap 支持）。
缺点：
- 锁粒度仍为整个 Map，并发性能不如 ConcurrentHashMap

3. ConcurrentHashMap（推荐）

import java.util.concurrent.ConcurrentHashMap;ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put("key", 1); // 高效并发操作

特性：
- 分段锁（JDK 7）：将 Map 分为多个 Segment，不同 Segment 可并发访问。
  
  JDK 7 实现：分段锁（Segment）
  
  1. 核心结构
  - 分段锁（Segment）：继承自 ReentrantLock，将整个 Map 分为 16 个（默认）独立的 Segment，每个 Segment 维护一个小的哈希表。
  - 锁粒度：每个 Segment 独立加锁，不同 Segment 可并发访问，提升并发度
  CAS + synchronized（JDK 8+）
  
  使用 CAS（Compare-And-Swap）和对单个桶（链表的头结点或者红黑树的头结点）加锁，锁粒度更小。
  
  CAS 是一种原子操作，包含三个参数：内存位置（V）、预期原值（A）和新值（B）。当且仅当 V 处的值等于 A 时，CAS 才会通过原子方式将 V 的值更新为 B；否则不执行任何操作
- 支持高并发读写，读操作几乎无锁（volatile 变量保证可见性）。
- 不允许 null 键或值（避免歧义，如 get(key) 返回 null 可能表示值为 null 或键不存在）。
一、传统锁（如 synchronized）的性能瓶颈
- 锁竞争流程：
  1. 线程 A 获得锁，执行临界区代码。
  2. 线程 B 尝试获取锁失败，被挂起（进入阻塞状态），操作系统将其从运行队列移除。
  3. 线程 A 释放锁后，操作系统唤醒线程 B，将其重新加入运行队列。
- 上下文切换代：
  - 需要保存当前线程的执行上下文（如寄存器值、程序计数器），并恢复另一个线程的上下文。
  - 涉及用户态与内核态的切换，通常需要几十到几百微秒，远超 CPU 指令执行时间。
二、CAS 无锁化设置
1. 线程读取变量的当前值 A。
2. 计算新值 B。
3. 通过 CAS 尝试将变量从 A 更新为 B：
  - 若成功，操作完成。
  - 若失败（说明其他线程已修改该变量），则重试步骤 1-3（自旋）。
关键优势： 避免线程阻塞
对比传统锁：
- 当 CAS 失败时，线程不会被挂起，而是继续重试（自旋），避免了上下文切换的开销。
- 若锁竞争不激烈，多数情况下 CAS 能在几次重试内成功，性能远高于线程阻塞