HashMap底层原理与线程安全分析

HashMap的底层原理

数据结构

HashMap的底层数据结构是数组+链表/红黑树。在JDK 1.8之前，HashMap采用数组+链表的方式解决哈希冲突；从JDK 1.8开始，当链表长度超过8（且数组长度超过64）时，链表会转换为红黑树，以提高查询效率。

// JDK 1.8 HashMap部分源码
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    // ...
}

put()方法的执行流程

当调用put(key, value)方法时，HashMap会执行以下步骤：

1. 计算key的hashCode值，然后通过哈希函数处理得到哈希值
2. 通过(n - 1) & hash计算数组下标（n为数组长度）
3. 判断该位置是否为空：
   • 如果为空，直接创建新Node插入
   • 如果不为空，发生哈希冲突，进行下一步处理
4. 判断该位置是链表还是红黑树：
   • 如果是链表，遍历链表，如果找到相同的key，则替换value；否则在链表尾部插入新节点
   • 如果是红黑树，按照红黑树的规则插入节点
5. 判断是否需要扩容：如果元素数量超过阈值（容量*负载因子），则进行扩容

get()方法的执行流程

当调用get(key)方法时，HashMap会执行以下步骤：

1. 计算key的hashCode值，然后通过哈希函数处理得到哈希值
2. 通过(n - 1) & hash计算数组下标
3. 判断该位置是否为空：
   • 如果为空，返回null
   • 如果不为空，进行下一步处理
4. 判断该位置是链表还是红黑树：
   • 如果是链表，遍历链表，通过equals()方法查找key
   • 如果是红黑树，在红黑树中查找key
5. 找到则返回对应的value，否则返回null

扩容机制

HashMap的扩容机制是其核心功能之一，当元素数量超过阈值（容量*负载因子）时，HashMap会进行扩容。扩容过程如下：

1. 创建一个新的数组，长度为原数组的2倍
2. 将原数组中的元素重新计算哈希值并放入新数组中
3. 在JDK 1.8中，扩容时采用了优化算法，利用(e.hash & oldCap) == 0判断元素在新数组中的位置是否需要改变，避免了重新计算哈希值

哈希冲突解决方法

哈希冲突是指不同的key通过哈希函数计算得到相同的哈希值。HashMap解决哈希冲突的方法是链地址法（Separate Chaining），即将哈希值相同的元素放在同一个链表（或红黑树）中。

在JDK 1.8中，当链表长度超过8（且数组长度超过64）时，链表会转换为红黑树，以提高查询效率。当红黑树中的节点数量减少到6时，红黑树会重新转换为链表。

HashMap的线程安全性

HashMap是非线程安全的，如果在多线程环境下使用HashMap，可能会导致以下问题：

多线程环境下的问题

1. 死循环（JDK 1.7及之前）

   • 在JDK 1.7及之前，HashMap在扩容时可能会导致死循环
   • 原因是多个线程同时进行扩容操作，可能导致链表形成环形结构
   • 在JDK 1.8中，通过改进扩容算法解决了这个问题

2. 数据覆盖

   • 多个线程同时执行put操作，如果计算出的索引位置相同，可能导致一个线程的插入操作被另一个线程覆盖
   • 例如：线程A和线程B同时put一个key，可能导致只有一个value被保存

3. size不准确

   • HashMap的size操作不是原子性的
   • 在多线程环境下，一个线程正在修改HashMap（如put操作），另一个线程执行size操作，可能得到不准确的结果

4. get操作可能获取到null

   • 在多线程环境下，一个线程正在执行put操作（可能导致扩容），另一个线程执行get操作，可能获取到null值

线程安全的替代方案

在多线程环境下，如果需要使用Map，可以考虑以下几种线程安全的替代方案：

1. Hashtable

Hashtable是Java早期提供的线程安全的Map实现，它通过在所有公共方法上使用synchronized关键字来保证线程安全。

优点：

• 实现简单，所有操作都是线程安全的
• 兼容性较好，是Java早期版本中唯一的线程安全Map

缺点：

• 性能较差，所有操作都使用同一个锁，并发度低
• 不允许null键和null值

public synchronized V put(K key, V value) {
    // ...
}

public synchronized V get(Object key) {
    // ...
}

2. Collections.synchronizedMap()

Collections.synchronizedMap()是一个包装方法，可以将任何Map包装成线程安全的Map。

优点：

• 可以将任何Map实现转换为线程安全的Map
• 使用简单，只需要调用一个静态方法

缺点：

• 性能较差，所有操作都使用同一个锁，并发度低
• 需要手动同步复合操作

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

3. ConcurrentHashMap

ConcurrentHashMap是Java并发包中提供的线程安全的Map实现，它通过更精细的锁机制来提高并发性能。

优点：

• 并发性能好，支持高并发读写
• 允许null值，但不允许null键
• 在迭代时不需要加锁，不会抛出ConcurrentModificationException

缺点：

• 实现复杂，理解起来有一定难度
• 某些复合操作需要手动同步

ConcurrentHashMap的线程安全实现

ConcurrentHashMap是Java并发包中提供的线程安全的Map实现，它在不同版本中有不同的实现方式。

JDK 1.7的实现：分段锁

在JDK 1.7中，ConcurrentHashMap采用**分段锁（Segment）**的设计来保证线程安全。

核心思想：

• 将整个Map分为多个段（Segment），每个段类似于一个小型的Hashtable
• 每个段有自己的锁，不同段的操作可以并行执行
• 默认分为16个段，支持最多16个线程同时写入

数据结构：

• ConcurrentHashMap包含一个Segment数组
• 每个Segment包含一个HashEntry数组
• 每个HashEntry是一个链表节点

// JDK 1.7 ConcurrentHashMap部分源码
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {
    // Segment数组
    final Segment<K,V>[] segments;
    
    // Segment类
    static final class Segment<K,V> extends ReentrantLock implements Serializable {
        transient volatile HashEntry<K,V>[] table;
        // ...
    }
    
    // HashEntry类
    static final class HashEntry<K,V> {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry<K,V> next;
        // ...
    }
}

put()方法的执行流程：

1. 计算key的hashCode值，然后通过哈希函数处理得到哈希值
2. 通过哈希值找到对应的Segment
3. 获取Segment的锁（如果获取不到则进入等待状态）
4. 在Segment中执行put操作（类似于HashMap的put操作）
5. 释放Segment的锁

get()方法的执行流程：

1. 计算key的hashCode值，然后通过哈希函数处理得到哈希值
2. 通过哈希值找到对应的Segment
3. 在Segment中执行get操作（不需要获取锁，因为value使用了volatile修饰）

JDK 1.8的实现：CAS+synchronized

在JDK 1.8中，ConcurrentHashMap放弃了分段锁的设计，改用CAS（Compare And Swap）操作和synchronized关键字来保证线程安全。

核心思想：

• 使用CAS操作进行无锁尝试，如果失败则使用synchronized锁
• 锁的粒度更细，只锁住需要修改的桶（数组中的某个位置）
• 使用volatile变量保证可见性

数据结构：

• 与HashMap类似，采用数组+链表/红黑树的结构
• 使用Node类表示链表节点，TreeNode类表示红黑树节点
• 使用sun.misc.Unsafe类的CAS操作

// JDK 1.8 ConcurrentHashMap部分源码
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    
    // Node数组
    transient volatile Node<K,V>[] table;
    
    // Node类
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        // ...
    }
    
    // TreeNode类
    static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        // ...
    }
}

put()方法的执行流程：

1. 计算key的hashCode值，然后通过哈希函数处理得到哈希值
2. 通过(n - 1) & hash计算数组下标
3. 使用CAS操作尝试在该位置插入新节点：
   • 如果该位置为空，使用CAS操作直接插入
   • 如果该位置不为空，使用synchronized锁住该位置，然后进行插入操作
4. 判断是否需要扩容：如果元素数量超过阈值，则进行扩容

get()方法的执行流程：

1. 计算key的hashCode值，然后通过哈希函数处理得到哈希值
2. 通过(n - 1) & hash计算数组下标
3. 在该位置查找key：
   • 如果该位置为空，返回null
   • 如果该位置不为空，根据是链表还是红黑树进行查找
4. 找到则返回对应的value，否则返回null

size()方法的实现：

• 在JDK 1.8中，ConcurrentHashMap的size()方法不再像JDK 1.7那样直接统计所有Segment的元素数量
• 而是使用一个计数器（baseCount）和多个计数器数组（counterCells）来统计元素数量
• 通过CAS操作更新计数器，避免了锁竞争

JDK 1.7与JDK 1.8实现对比