由于传统的HashMap在多线程环境下存在线程不安全的情况,为了解决这个问题Java中还提供了新的操作来解决这个问题:

HashTable<K,V>

为整个hashtable的数组加了一把锁,只能允许同时有一个线程访问,虽然解决了线程安全的问题,但是会降低并发环境下的执行效率

Collections.synchronizedMap(Map<K,V> m)

将传入的HashMap的所有方法都用一个同步的方法包裹起来,实现线程安全

ConcurrentHashMap<K,V>

解决了上面两种方案的效率问题

ConcurrentHashMap实现方式:

jdk1.7和1.8的实现方式有所不同

jdk1.7中使用Segment<K,V>数组实现

Segment数组默长度为16

Segment<K,V>中存放的是HashEntry<K,V>数组

HashEntry<K,V>结构

1
2
3
4
5
6
static final class HashEntry<K,V> {
    final K key; // key
    final int hash; // 当前key的hash值
    volatile V value; // 当前节点中key的值 用volatile修饰 保证多线程下数据的可见性
    volatile HashEntry<K,V> next; // 用volatile修饰 保证多线程下数据的可见性
}

由于Segment继承了ReentrantLock,所以Segment是一种可重入锁,也就是说每个Segment都是加锁的,而Segment数组的默认长度为16,也就是最多可允许16个线程同时操作,解决了并发访问的效率问题

put方法执行逻辑

先定位到Segment,然后再进行put操作:

1
2
3
4
5
6
7
//这是put方法的第一句
//先尝试获取锁,如果拿到锁就继续执行,没有拿到则尝试自选获取锁
//如果重试次数达到MAX_SCAN_RETRIES则改为阻塞式获取锁,直到获取成功
HashEntry<K,V> node=tryLock() ? null : scanAndLockForPut(key,hash,value);
// scanAndLockForPut(key,hash,value);
// 暂时找不到这个方法的实现源码(我懒得下载jdk1.7)
//但是看里面的参数肯定是再执行一些操作后再次进入put方法尝试获取锁

1.8使用Node<K,V>+链表+红黑树实现,结构上和HashMap基本相同,锁的实现上采用了比1.7更细粒度的方式,使用CAS+synchronized,给node数组中的每个hash桶中的节点加上锁,如果这个位置是链表,就给链表的头节点加锁,如果是红黑树,就给红黑树的根节点(?)加锁

put方法执行逻辑:

先根据key计算出hash值

再判断hash表(node数组)是不是需要初始化

根据hash值定位到node数组中的位置,拿到节点f,f可能是链表头节点,也可能是红黑树的根节点(?)

判断节点f:

—如果为null,则表示当前节点不存在,通过CAS[1]的方式添加

—如果f.hash==MOVED(常量,值为 -1),表示其他线程正在进行扩容,当前线程帮助进行数据转移

—else 锁住节点f,判断是红黑树还是链表,执行插入操作

[1]CAS(Compare And Swap):

意思就是比较并替换

CAS机制中使用了3个基本操作数:内存地址V,旧的预期值A,要修改的新值B。

更新一个变量的时候,只有当变量的预期值A和内存地址V当中的实际值相同时,才会将内存地址V对应的值修改为B。

如果实际值于预期值A不同,则不进行更新,重新计算预期值,并进行下一次尝试,这个过程被称为自旋