ConcurrentHashMap的原理

背景

我们知道hashmap是一个线程不安全的数据结构,在多线程编程的时候,多个线程同时向hashmap中put元素的时候,会发生数据丢失。多线程put操作后,再get操作导致死循环。
多线程put非NULL元素后,get操作得到NULL值。

使用

为了保证并发安全,我们使用hashmap的时候,建议是使用ConcurrentHashMap。

底层原理

1.7的时候,底层数据结构是大数组Segment(容量为16)和小数组HashEntry。默认是16个Segmement,每个HashEntry会存放一些键值对或者链表。
Segment继承了可重入锁,有加锁和释放锁的操作,这样就能保证多个线程访问ConcurrentHashMap的时候,同一时间只能有一个线程能够操作相应的节点,保证了线程安全。


性能相对于hashtable而言,效率提高了16倍。即当线程访问一个Segment 的时候,只对这一个Segment加锁,对于其他段的Segment,则可以继续被其他线程访问,不会有冲突。
1.8的时候,底层数据结构更新为数组+链表+红黑树。1.8不再有分段锁的设计,而是采用CAS和synchrionzed来保证并发安全。
CAS主要是用于put的过程中进行初始化,synchronzied主要是用于往map中插入元素的时候保证线程安全。
采用CAS自旋重试的方式进行初始化,是为了保证只有一个线程完成map的初始化问题,因为多个线程同时初始化,会产生数据丢失的问题。这边使用CAS原子操作,通过修改sizeCtl变量成功与否来代表是否抢占到了锁。如果抢占到了,由该线程完成map的初始化工作;
如果没抢占到,那就进行While循环,自旋重试,直到该map初始化成功,循环自动退出,自旋也随之结束。
初始化结束以后,对于一个put(key, val)操作,首先计算出该key的哈希值,从而得到该key在数组中的插入位置。
首先使用CAS的方式插入key-val, 先判断该位置是否为null, 为null, CAS插入元素。如果成功,则该key-val成功插入;
如果不为null,说明发生了碰撞,改用synchronized关键字,对头节点加锁,然后将key-val插入链表或者红黑树。
插入前,判断是链表还是红黑树,不同的结构处理方式不同;
如果是链表,那么从链表的头节点开始向下遍历,遍历的每个节点:
使用equlas判断key相等否,相等,则修改该key 的value; 否则,把当前的key value插入链表的最后一个节点。
如果是红黑树,那么putTreeVal完成值的存储。
要说明的是,这种锁控制在单个数据节点上,16位的数组可以支持16个线程并发写入数据。

源码

public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        //1、数据检查
        if (key == null || value == null) throw new NullPointerException();
        
        //2、求key哈希
        int hash = spread(key.hashCode());
        int binCount = 0;  //记录遍历的节点数,可以用于判断是否要链表转化为红黑树
        
        for (Node<K,V>[] tab = table;;) {  //死循环
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)  //检查 table 是否初始化
                tab = initTable();
            //使用哈希值计算索引 i 并检查该位置是否为空。如果为空,使用 CAS 操作插入新节点,并跳出循环。
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED) // MOVEDd标志用于判断是否已经节点迁移
                //当一个桶(bin)中的所有节点都被迁移到新的数组中后,原来的位置上会放置一个特殊的转发节点,表示这个桶已经处理完毕。此时,转发节点的 hash 字段会被设置为 MOVED(即 -1)。
                tab = helpTransfer(tab, f);//协助迁移
            else {   //如果碰撞了  需要使用synchronized,放弃cas,f是table那个碰撞节点
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) { // 经典的双重检查,防止当前线程获取table锁之前,tabAt(tab, i)被其它线程改变了
                        if (fh >= 0) {// 哈希值>=0代表是链表,<0代表是红黑树
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {  // 三比较,hashcode==hashcode,key==key,key.equals(key)
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) { // 红黑树
                            Node<K,V> p;
                            binCount = 2;  //binCount 被初始化为 2,因为红黑树中的节点数计算方式不同于链表。 具体原因我不知道
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {   // 判断是否要扩容 TREEIFY_THRESHOLD=8
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);  //计数 里面通过cas维护元素个数。
        return null;
    }

热门相关:美漫大幻想   甜蜜婚令:首长的影后娇妻   世界第一校长   福晋有喜:四爷,宠上天!   末日乐园