从源码了解HashMap和ConcurrentHashMap的基本实现(下)

面试题1:谈谈ConcurrentHashMap的线程安全性?

ConcurrentHashMap基本数据结构和HashMap一致,读方法没有使用同步机制,和HashMap也基本是一致,写方法通过使用synchronized关键字和Unsafe的CAS机制,保证其线程安全性和高效性。

面试题2:简单谈谈Java的CAS机制?

CAS的全称是Compare and Swap, 翻译成比较并交换,java.util.concurrent包完全建立在CAS之上的,很多concurrent的基础类都用到了CAS机制,包括atomic相关的基本数据容器,reentrant lock,ConcurrentHashMap等,CAS是一种自旋乐观锁。

CAS机制当中使用了3个基本操作数:内存地址V,旧的预期值A,要修改的新值B,更新一个变量的时候,只有当变量的预期值A和内存地址V当中的实际值相同时,才会将内存地址V对应的值修改为B。

CAS机制优点:低并发时效率高,且锁灵活。

CAS机制确定:高并发时cpu开销大,无法保证代码块的线程安全,ABA问题(可优化)。

源码解析:该源码基于jdk1.8,且接上文,有些源码与HashMap类似部分在上文中已给出。

2.ConcurrentHashMap

(1)类定义

 

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable


ConcurrentHashMa实现了Serializable(序列化接口)

其主要继承和实现关系如下:

ConcurrentHashMap-->AbstractMap-->Map

ConcurrentHashMap-->ConcurrentMap-->Map

前面的线为Map优化线

后面的线为Map基本定义线

(2)主要变量

transient volatile Node<K,V>[] table;
private transient volatile Node<K,V>[] nextTable;
private transient volatile long baseCount;
private transient volatile int sizeCtl;
private transient volatile int transferIndex;
private transient volatile int cellsBusy;
private transient volatile CounterCell[] counterCells;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}


相对于HashMap,添加了不少辅助量,其中新增sizeCtl作为控制值,来控制初始化,扩容进度,最大容量等,且基本类型均为volatile类型,但是基本数据类型还是Node类型的数组,Node类型数值和向后指针引用也改成了volatile类型。

(3)主要构造方法

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)     
        throw new IllegalArgumentException();  
    if (initialCapacity < concurrencyLevel)      
        initialCapacity = concurrencyLevel;  
    long size = (long)(1.0 + (long)initialCapacity / loadFactor);  
    int cap = (size >= (long)MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : tableSizeFor((int)size);  
    this.sizeCtl = cap;
}

该方法中concurrencyLevel表示预估的并发更新的线程数,并且通过tableSizeFor方法保证最大容量一定是2的n次方。

(4)主要方法

初始化

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

 

和HashMap类似,第一次put,且对象为空时会有一步操作,HashMap的操作是执行一次扩容resize,ConcurrentHashMap执行的是初始化initTable,通过CAS机制保证初始化线程的安全性,当有线程在初始化时sizeCtl值为-1,其余线程会执行Thread.yield(),简单谈下CAS机制的优劣势,在低中冲突时效率比锁高,在高并发时效率比锁低,且占用空间比较大,也就是随着硬件功能的提升,硬件指令集的支持使得该机制使用越来越广泛。

扩容

扩容的主要方法是transfer方法,由于源码过长,只做原理解析。

1.设置步长,表示每个线程最少处理的长度,默认最低16,代表如果数组长度为16时,最多一个线程处理。

2.设置扩容后的长度,和HashMap一致,大小翻倍,限制只有一个扩容的线程会设置扩容后的长度。

3.ForwardingNode的创建,该节点是一个特殊的Node节点,hash值为-1,其中存储nextTable的引用,只有在table发生扩容的时候,ForwardingNode才会发挥作用。

4.循环遍历和线程安全移动。

put方法

基本流程和HashMap一致,只是在大部分情况下都有加锁,不需要加锁的情况主要两种,1.该Hash冲突对应的值为空时,采用CAS机制赋值,2.put操作在有其他线程在扩容时调用helpTransfer方法辅助扩容

helpTransfer

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

 

1.判断tab是否为空,判断是否是转移节点。判断nextTable是否更改了。
2.获取到扩容后的大小值。
3.判断是否并发修改了,判断是否还在扩容。
4.如果还在扩容,判断标识符是否变化,判断扩容是否结束,判断是否达到最大线程数,判断扩容转移下标是否在调整(扩容结束),如果满足任意条件,结束循环。
5.如果不满足,执行扩容方法。

get方法

get方法基本和HashMap是一致的,没有采用同步机制,也是较为简单,请参考上文。

(5)线程安全性和高效性分析

读主要分析get方法,在get操作中,没有使用同步机制,也没有使用unsafe方法,所以读操作是支持并发操作的。

写主要分析put方法和扩容,put方法主要是通过Unsafe的CAS机制,该机制在低冲突并发时主要在硬件层面的操作,效率非常高,但是如果是高冲突并发,空间浪费和时间效率都比较低,扩容是CAS机制和通过Synchronized的同步机制来保证现程安全。

原文地址:https://www.cnblogs.com/hxlr/p/11535150.html