之前看过 ConcurrentHashMap 的分析, 感觉也了解的七七八八了但昨晚接到了面试, 让我把所知道的 ConcurrentHashMap 全部说出来
然后我结结巴巴, 然后应该毫无意外的话就 G 了, 今天下定决心好好分析一下, 这个万能的并发包, ConcurrentHashMap
分一下几个方面分析 ConcurrentHashMap:
put 方法
remove 方法
get 方法
(一)put 方法
- public V put(K key, V value) {
- return putVal(key, value, false);
- }
调用了 putVal 方法, 传入三个参数第一个为 key, 第二个为 val, 第三个为 onlyIfAbsent(意思为: 如果为 true, 当插入的 key 相同时, 不替换 val 值, 默认是为 false, 替换最新的 val 值)
putVal 方法比较多, 我们分两个部分讲:
- // 第一部分
- final V putVal(K key, V value, boolean onlyIfAbsent) {
- // 对传入的参数进行合法性判断
- if (key == null || value == null) throw new NullPointerException();
- // 计算键所对应的 hash 值
- 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) tab = initTable();
- // 根据键的 hash 值找到哈希数组相应的索引位置
- // 如果为空, 那么以 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;
- }
我们看到第四行, 如果 key 和 val 都为 null, 直接抛出异常, 所以不能传入 key 和 val 都不能为 null
第二个注意点是 散列这个函数
- static final int spread(int h) {
- return (h ^ (h >>> 16)) & HASH_BITS;
- }
我在 HashMap 里面有介绍, 我就不详细说了, 反正很重要
第三个注意点就是初始化 table 这个函数 initTable
- private final Node < K,
- V > [] initTable() {
- Node < K,
- V > [] tab;
- int sc;
- // 如果表为空才进行初始化操作
- while ((tab = table) == null || tab.length == 0) {
- //sizeCtl 小于零说明已经有线程正在进行初始化操作
- // 当前线程应该放弃 CPU 的使用
- 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) {
- //sc 大于零说明容量已经初始化了, 否则使用默认容量
- int n = (sc > 0) ? sc: DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
- // 根据容量构建数组
- Node < K,
- V > [] nt = (Node < K, V > []) new Node < ?,
- ?>[n];
- table = tab = nt;
- // 计算阈值, 等效于 n*0.75
- sc = n - (n >>> 2);
- }
- } finally {
- // 设置阈值
- sizeCtl = sc;
- }
- break;
- }
- }
- return tab;
- }
我们看到第 7,8 行如果有线程在初始化, 那么那就等待, 让出 cpu
初始化只允许一个线程对表进行初始化, 如果不巧有其他线程进来了, 那么会让其他线程交出 CPU 等待下次系统调度这样, 保证了表同时只会被一个线程初始化
默认初始化为大小为 16, 阕值为 0.75
我们重新回到 putVal 这个方法中去
- // 检测到桶结点是 ForwardingNode 类型, 协助扩容
- else if ((fh = f.hash) == MOVED)
- tab = helpTransfer(tab, f);
- // 桶结点是普通的结点, 锁住该桶头结点并试图在该链表的尾部添加一个节点
- else {
- V oldVal = null;
- synchronized (f) {
- if (tabAt(tab, i) == f) {
- // 向普通的链表中添加元素, 无需赘述
- if (fh >= 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)))) {
- 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;
- }
- }
- }
- // 向红黑树中添加元素, TreeBin 结点的 hash 值为 TREEBIN(-2)
- else if (f instanceof TreeBin) {
- Node<K,V> p;
- binCount = 2;
- if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
- oldVal = p.val;
- if (!onlyIfAbsent)
- p.val = value;
- }
- }
- }
- }
- //binCount != 0 说明向链表或者红黑树中添加或修改一个节点成功
- //binCount == 0 说明 put 操作将一个新节点添加成为某个桶的首节点
- if (binCount != 0) {
- // 链表深度超过 8 转换为红黑树
- if (binCount >= TREEIFY_THRESHOLD)
- treeifyBin(tab, i);
- //oldVal != null 说明此次操作是修改操作
- // 直接返回旧值即可, 无需做下面的扩容边界检查
- if (oldVal != null)
- return oldVal;
- break;
- }
- }
- }
- //CAS 式更新 baseCount, 并判断是否需要扩容
- addCount(1L, binCount);
- // 程序走到这一步说明此次 put 操作是一个添加操作, 否则早就 return 返回了
- return null;
我们看到第三行, 如果 f 的 hash 是 MOVED, 那么就帮助他扩容 (说明至少有一个线程在扩容)
这个方法说实话我看的不太懂, 我就在网上查了点资料:
首先, 每个线程进来会先领取自己的任务区间, 然后开始 --i 来遍历自己的任务区间, 对每个桶进行处理如果遇到桶的头结点是空的, 那么使用 ForwardingNode 标识该桶已经被处理完成了如果遇到已经处理完成的桶, 直接跳过进行下一个桶的处理如果是正常的桶, 对桶首节点加锁, 正常的迁移即可, 迁移结束后依然会将原表的该位置标识位已经处理
当 i < 0, 说明本线程处理速度够快的, 整张表的最后一部分已经被它处理完了, 现在需要看看是否还有其他线程在自己的区间段还在迁移中
putVal 后面的代码就比较清楚了如果是链表, 就找到尾节点, 插入即可如果是红黑树, 童谣插入即可
至此, 对于 put 方法的源码分析已经完全结束了, 感觉真的很复杂至此我感觉我都没有完全理解每一行代码是什么意思
(二)remove 方法
- public V remove(Object key) {
- return replaceNode(key, null, null);
- }
三个参数, 第一个为 key, 第二个为 val, 删除直接置为 null, 让 gc 来回收第三个是 Object cv, 含义还不是很清楚先继续看吧
我们还是分为两部分:
- // 第一部分
- final V replaceNode(Object key, V value, Object cv) {
- // 先找到 key 的位置 hash 散列
- int hash = spread(key.hashCode());
- for (Node < K, V > [] tab = table;;) {
- Node < K,
- V > f;
- int n,
- i,
- fh;
- // 如果表为空, 直接返回 null
- if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null) break;
- // 如果有在扩容的线程, 帮助他扩容
- else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f);
首先遍历整张表的桶结点, 如果表还未初始化或者无法根据参数的 hash 值定位到桶结点, 那么将返回 null
如果定位到的桶结点类型是 ForwardingNode 结点, 调用 helpTransfer 协助扩容
- else {
- V oldVal = null;
- boolean validated = false;
- synchronized (f) {
- if (tabAt(tab, i) == f) {
- if (fh >= 0) {
- validated = true;
- for (Node<K,V> e = f, pred = null;;) {
- K ek;
- if (e.hash == hash &&
- ((ek = e.key) == key ||
- (ek != null && key.equals(ek)))) {
- V ev = e.val;
- if (cv == null || cv == ev ||
- (ev != null && cv.equals(ev))) {
- oldVal = ev;
- if (value != null)
- e.val = value;
- else if (pred != null)
- pred.next = e.next;
- else
- setTabAt(tab, i, e.next);
- }
- break;
- }
- pred = e;
- if ((e = e.next) == null)
- break;
- }
- }
- else if (f instanceof TreeBin) {
- validated = true;
- TreeBin<K,V> t = (TreeBin<K,V>)f;
- TreeNode<K,V> r, p;
- if ((r = t.root) != null &&
- (p = r.findTreeNode(hash, key, null)) != null) {
- V pv = p.val;
- if (cv == null || cv == pv ||
- (pv != null && cv.equals(pv))) {
- oldVal = pv;
- if (value != null)
- p.val = value;
- else if (t.removeTreeNode(p))
- setTabAt(tab, i, untreeify(t.first));
- }
- }
- }
- }
- }
- if (validated) {
- if (oldVal != null) {
- if (value == null)
- addCount(-1L, -1);
- return oldVal;
- }
- break;
- }
- }
代码很多, 但我觉得思路不难就是找到那个桶以后, 直接加锁判断是链表还是树, 然后删除即可
(三)get 方法
- public V get(Object key) {
- Node < K,
- V > [] tab;
- Node < K,
- V > e,
- p;
- int n,
- eh;
- K ek;
- int h = spread(key.hashCode());
- if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {
- if ((eh = e.hash) == h) {
- if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val;
- } else if (eh < 0) return (p = e.find(h, key)) != null ? p.val: null;
- while ((e = e.next) != null) {
- if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val;
- }
- }
- return null;
- }
和 HashMap 的 get 方法大同小异没有涉及到并发操作直接取到 key 的 hash 值, 如果是第一个节点, 直接返回否则 while 循环查找
来源: https://www.cnblogs.com/wenbochang/p/8484779.html