HashMap的工作原理及线程安全问题

题目

HashMap的工作原理及线程安全问题

信息

• 类型：问答
• 难度：⭐⭐

考点

HashMap实现原理,线程安全,ConcurrentHashMap,哈希冲突解决

快速回答

HashMap基于数组+链表/红黑树实现，通过哈希算法确定键值对存储位置。主要特点：

• 使用hashCode()和equals()确定键的唯一性
• JDK8后链表长度>8时转换为红黑树
• 默认负载因子0.75，触发扩容时容量翻倍
• 线程不安全问题：多线程扩容可能导致死循环或数据丢失
• 解决方案：使用ConcurrentHashMap或Collections.synchronizedMap()

一、HashMap核心原理

HashMap采用数组+链表/红黑树结构存储数据：

// 简化版put方法流程
final V putVal(int hash, K key, V value) {
    Node<K,V>[] tab; // 存储桶数组
    // 1. 数组为空则初始化（默认大小16）
    if ((tab = table) == null) 
        tab = resize();

    // 2. 计算桶索引: (n-1) & hash
    int i = (n - 1) & hash; 

    // 3. 处理哈希冲突
    if (tab[i] == null) 
        tab[i] = newNode(hash, key, value); // 直接插入
    else {
        // 遍历链表/红黑树
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 键已存在
        else if (p instanceof TreeNode) 
            e = ((TreeNode<K,V>)p).putTreeVal(...); // 红黑树插入
        else {
            // 链表遍历并插入
            if (binCount >= TREEIFY_THRESHOLD - 1) // 链表长度>8
                treeifyBin(tab, hash);  // 转红黑树
        }
    }

    // 4. 超过阈值则扩容
    if (++size > threshold)
        resize(); // 扩容为2倍
}

二、多线程环境下的问题

• 死循环问题：JDK7扩容时链表倒序可能形成环形链表（已修复）
• 数据丢失：多线程put时覆盖写入
• size不准确：并发更新导致计数器错误

三、线程安全解决方案

1. ConcurrentHashMap (推荐)

   Map<String, Integer> safeMap = new ConcurrentHashMap<>();

   • JDK7使用分段锁（Segment）
   • JDK8改用CAS+synchronized锁桶头节点
   • 支持高并发读写
2. Collections.synchronizedMap()

   Map<String, Integer> syncMap = 
       Collections.synchronizedMap(new HashMap<>());

   • 使用对象互斥锁，性能较低

四、最佳实践

• 键对象必须正确重写hashCode()和equals()
• 预估数据量设置初始容量避免频繁扩容：new HashMap<>(128)
• 高并发场景优先使用ConcurrentHashMap
• 避免在迭代过程中修改Map（使用Iterator.remove()）

五、常见错误

• 使用可变对象作为Key导致哈希值变化
• 多线程环境直接使用HashMap导致数据不一致
• 未重写hashCode()造成大量哈希冲突

六、扩展知识

• 负载因子：0.75是时间与空间成本的平衡值
• 红黑树转换：链表长度>8且数组长度≥64时才转换
• 哈希优化：JDK8将哈希算法简化为(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)