ConcurrentHashMap

素颜马尾好姑娘i 2023-01-01 02:58 202阅读 0赞

ConcurrentHashMap

数组 + 链表 +红黑树 的简单梳理

初始化数组长度默认长度16，初始化有指定长度，就会返回指定长度（n）的数组

  1. private final Node<K,V>[] initTable() { 
  2.         Node<K,V>[] tab; int sc;
  3.         while ((tab = table) == null || tab.length == 0) { 
  4.             if ((sc = sizeCtl) < 0)
  5.                 Thread.yield(); // lost initialization race; just spin
  6.             else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { 
  7.                 try { 
  8.                     if ((tab = table) == null || tab.length == 0) { 
  9.                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
  10.                         @SuppressWarnings("unchecked")
  11.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
  12.                         table = tab = nt;
  13.                         sc = n - (n >>> 2);
  14.                     }
  15.                 } finally { 
  16.                     sizeCtl = sc;
  17.                 }
  18.                 break;
  19.             }
  20.         }
  21.         return tab;
  22.     }

指定长度数组的计算规则

比指定长度initialCapacity大的最小的2的n次方

  1. tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1))

计算Key的Hash值

  1. int hash = spread(key.hashCode());

添加一个Node节点

i=(n - 1) & hash 数组长度和hash值 转成二进制后进行运算 同为1 就是1，否则为0
如果 数组 i 为空那么就会创建一个Node节点 无锁添加
如果 数组 i 不为空 那么就会为当前Node节点添加子节点 加锁添加

  1. if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
  2.      if (casTabAt(tab, i, null,new ConcurrentHashMap.Node<K,V>(hash, key,value, null)))
  3.          break;
  4.     }

添加一个Node链表的子节点

1、key的去重判断

  1. if (e.hash == hash &&
  2.       ((ek = e.key) == key || (ek != null && key.equals(ek)))) { 
  3.         oldVal = e.val;
  4.         if (!onlyIfAbsent)
  5.              e.val = value;
  6.                break;
  7.   }

2、声明一个Node pred将他指向原先存在的Node 对象

  1. ConcurrentHashMap.Node<K,V> pred = e;

3、 找到该Node链表节点下最后一个节点

  1. if ((e = e.next) == null)

4、最后添加链表节点

  1. pred.next = new ConcurrentHashMap.Node<K,V>(hash, key,value, null);

红黑二叉树添加

  1. if (f instanceof ConcurrentHashMap.TreeBin) { 
  2.     ConcurrentHashMap.Node<K,V> p;
  3.     binCount = 2;
  4.     if ((p = ((ConcurrentHashMap.TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) { 
  5.          oldVal = p.val;
  6.          if (!onlyIfAbsent)
  7.              p.val = value;
  8.          }
  9.     }

转换成红黑二叉树

如果一个链表下的节点大于等于8 转换成红黑二叉树

  1. if (binCount >= TREEIFY_THRESHOLD)
  2.     treeifyBin(tab, i);
  3.       if (oldVal != null)
  4.           return oldVal;
  5.       break;
  6.    }

发表评论

表情：
评论列表 （有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

    相关 ConcurrentHashMap

    这个能看懂的都是大佬了 反正我是看懂了一部分，但是对于一些跳出循环呀，跳出if判断的还是很模糊，不过不影响对于hash表整体的理解 有完全搞明白的大佬可以指点一波

    快来打我*快来打我*/ 0 赞/ 169 阅读

    相关 ConcurrentHashMap

    HashMap在多线程的情况下，HashMap是不安全的，但Hashtable因为操作的时候会锁住整个table，这就意味着所有的对象在争一把锁，效率极低，在这种情况下推出了C

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 226 阅读