栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【Java并发编程】ConcurrentHashMap

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【Java并发编程】ConcurrentHashMap

重要属性和内部类
// 默认为 0
// 当初始化时, 为 -1
// 当扩容时, 为 -(1 + 扩容线程数)
// 当初始化或扩容完成后,为 下一次的扩容的阈值大小
private transient volatile int sizeCtl;
// 整个 ConcurrentHashMap 就是一个 Node[]
static class Node implements Map.Entry {}
// hash 表
transient volatile Node[] table;//Node包括键,值,哈希码和Next
// 扩容时的 新 hash 表
private transient volatile Node[] nextTable;
// 扩容时如果某个 bin 迁移完毕, 用 ForwardingNode 作为旧 table bin 的头结点
static final class ForwardingNode extends Node {}
// 用在 compute 以及 computeIfAbsent 时, 用来占位, 计算完成后替换为普通 Node
static final class ReservationNode extends Node {}
// 作为 treebin 的头节点, 存储 root 和 first
static final class TreeBin extends Node {}
// 作为 treebin 的节点, 存储 parent, left, right
static final class TreeNode extends Node {}

 ForwardingNode用于扩容时会从后往前一个一个处理,当处理完后就会在该桶下标处加一个头节点fnode,其他线程也来处理时看到fnode就知道该节点已经被处理过了,就不会继续处理了,相当于一个标记作用,如下图所示。另外,当扩容的过程中有其他线程get(key),这个时候有fnode,就会在新的table去get。

 重要方法
// 获取 Node[] 中第 i 个 Node
static final  Node tabAt(Node[] tab, int i)
 
// cas 修改 Node[] 中第 i 个 Node 的值, c 为旧值, v 为新值
static final  boolean casTabAt(Node[] tab, int i, Node c, Node v)
 
// 直接修改 Node[] 中第 i 个 Node 的值, v 为新值
static final  void setTabAt(Node[] tab, int i, Node v)
构造器分析

构造器三个参数分别是:初始容量,负载因子0.75,并发度。

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
 if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
 throw new IllegalArgumentException();
 if (initialCapacity < concurrencyLevel) // Use at least as many bins
 initialCapacity = concurrencyLevel; // as estimated threads
 long size = (long)(1.0 + (long)initialCapacity / loadFactor);
 // tableSizeFor 仍然是保证计算的大小是 2^n, 即 16,32,64 ... 
 int cap = (size >= (long)MAXIMUM_CAPACITY) ?
 MAXIMUM_CAPACITY : tableSizeFor((int)size);
 this.sizeCtl = cap;
}
  1. 如果初始容量小于并发度,那么会将初始容量改为并发度
  2. 实现了懒惰初始化,在构造方法中仅仅计算了 table 的大小,以后在第一次使用时才会真正创建 
 get流程
public V get(Object key) {
 Node[] tab; Node e, p; int n, eh; K ek;
 // spread 方法能确保返回结果是正数
 int h = spread(key.hashCode());
 if ((tab = table) != null && (n = tab.length) > 0 &&
 (e = tabAt(tab, (n - 1) & h)) != null) {
 // 如果头结点已经是要查找的 key
 if ((eh = e.hash) == h) {
 if ((ek = e.key) == key || (ek != null && key.equals(ek)))
 return e.val;
 }
 // hash 为负数表示该 bin 在扩容中或是 treebin, 这时调用 find 方法来查找
 else if (eh < 0)
 return (p = e.find(h, key)) != null ? p.val : null;
 // 正常遍历链表, 用 equals 比较
 while ((e = e.next) != null) {
 if (e.hash == h &&
 ((ek = e.key) == key || (ek != null && key.equals(ek))))
 return e.val;
 }
 }
 return null;

全程未加锁,并发度高

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

    
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        // 其中 spread 方法会综合高位低位, 具有更好的 hash 性
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node[] tab = table;;) {
         // f 是链表头节点
         // fh 是链表头结点的 hash
         // i 是链表在 table 中的下标
            Node f; int n, i, fh; K fk; V fv;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null, new Node(hash, key, value)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else if (onlyIfAbsent && fh == hash &&  // check first node
                     ((fk = f.key) == key || fk != null && key.equals(fk)) &&
                     (fv = f.val) != null)
                return fv;
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node(hash, key, value);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node p;
                            binCount = 2;
                            if ((p = ((TreeBin)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                        else if (f instanceof ReservationNode)
                            throw new IllegalStateException("Recursive update");
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
  1. 调用putVal方法,除了键值对以外还有个布尔值,取值为真表示,只有第一次put才会将这个键值对放入map,后面put相同的key不做操作,这里false说明每次都会用新值覆盖掉旧值
  2. 如果key或者value为null,抛出空指针异常(hashmap允许空key和空value)
  3. 遍历table,判断是否需要初始化,如果tab为null或长度为0,调用initTable()创建(cas)
  4. f 即为当前 key 定位出的 Node,如果为空表示当前位置可以写入数据,利用 CAS 尝试写入,失败则自旋保证成功。
  5. 帮忙扩容,如果当前位置的 hashcode == MOVED == -1,则说明有线程正在进行扩容,这个时候该线程也不会闲着,而是帮忙扩容
  6. 进入最后一个else,此时发生了桶下标冲突,此时就要进行加锁,锁住链表头节点。遍历该 链表,如果不为空则判断传入的 key 和当前遍历的 key 是否相等,相等则覆盖旧的 value。遍历到最后时,就新建一个节点添加到链表尾部。
  7. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
 7 VS 8

JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言, ConcurrentHashMap只是增加了同步的操作来控制并发,从JDK1.7版本的 ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑 树。

  • 1.数据结构:取消了Segment分段锁的数据结构,取而代之的是数组+链表+红黑树的结构。
  • 2.保证线程安全机制:JDK1.7采用segment的分段锁机制实现线程安全,其中segment继承自 ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
  • 3.锁的粒度:原来是对需要进行数据操作的Segment加锁,现调整为对每个数组元素加锁 (Node)。
  • 4.链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数 量大于8时,会将链表转化为红黑树进行存储。
  • 5.查询时间复杂度:从原来的遍历链表O(n),变成遍历红黑树O(logN)。

来自:全面深入学习java并发编程_哔哩哔哩_bilibili

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/963184.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号