【Java 并发笔记】ConcurrentHashMap(1.8) 相关整理

作者 : 开心源码 本文共15431个字,预计阅读时间需要39分钟 发布时间: 2022-05-12 共193人阅读

文前说明

作为码农中的一员,需要不断的学习,我工作之余将少量分析总结和学习笔记写成博客与大家一起交流,也希望采用这种方式记录自己的学习之旅。

本文仅供学习交流使用,侵权必删。
不用于商业目的,转载请注明出处。

1. ConcurrentHashMap

  • 接上一篇 【Java 并发笔记】ConcurrentHashMap(1.7) 相关整理

1.1 HaspMap(JDK 1.8)

JDK 1.8 HashMap

  • JDK 1.8 对 HashMap 进行了修改,最大的不同就是利用了红黑树,其由数组+链表+红黑树组成
    • JDK 1.7 中,查找元素时,根据 hash 值能够快速定位到数组的具体下标,但之后需要顺着链表依次比较才能查找到需要的元素,时间复杂度取决于链表的长度,为 O(N)
    • 为了降低这部分的开销,在 JDK 1.8 中,当链表中的元素超过 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)
  • JDK 1.8 使用 Node(1.7 为 Entry) 作为链表的数据结点,依然包含 key,value,hash 和 next 四个属性。
    • 红黑树的情况使用的是 TreeNode。
  • 根据数组元素中,第一个结点数据类型是 Node 还是 TreeNode 可以判断该位置下是链表还是红黑树。
  • 核心成员变量于 1.7 相似,添加了核心变量,如下表。
属性说明
TREEIFY_THRESHOLD用于判断能否需要将链表转换为红黑树的阈值,默认为 8。

put 方法过程

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);} // onlyIfAbsent 假如是 true,那么只有在不存在该 key 时才会进行 put 操作。final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    // 第一次 put 值的时候,会触发下面的 resize(),相似 java7 的第一次 put 也要初始化数组长度    // 第一次 resize 和后续的扩容有些不一样,由于这次是数组从 null 初始化到默认的 16 或者自己设置的初始容量    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // 找到具体的数组下标,假如此位置没有值,那么直接初始化一下 Node 并放置在这个位置即可以了    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);     else {// 数组该位置有数据        Node<K,V> e; K k;        // 首先,判断该位置的第一个数据和我们要插入的数据,key 是不是"相等",假如是,取出这个结点        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;        // 假如该结点是代表红黑树的结点,调用红黑树的插值方法,本文不开展说红黑树        else if (p instanceof TreeNode)            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        else {            // 到这里,说明数组该位置上是一个链表            for (int binCount = 0; ; ++binCount) {                // 插入到链表的最后面(Java7 是插入到链表的最前面)                if ((e = p.next) == null) {                    p.next = newNode(hash, key, value, null);                    // TREEIFY_THRESHOLD 为 8,所以,假如新插入的值是链表中的第 9 个                    // 会触发下面的 treeifyBin,也就是将链表转换为红黑树                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                // 假如在该链表中找到了"相等"的 key(== 或者 equals)                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    // 此时 break,那么 e 为链表中[与要插入的新值的 key "相等"]的 node                    break;                p = e;            }        }        // e!=null 说明存在旧值的key与要插入的key"相等"        // 对于我们分析的put操作,下面这个 if 其实就是进行 "值覆盖",而后返回旧值        if (e != null) {            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null)                e.value = value;            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;    // 假如 HashMap 因为新插入这个值导致 size 已经超过了阈值,需要进行扩容    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}
  • put 方法的流程。
  1. 判断当前桶能否为空,空的就需要初始化(resize 中会判断能否进行初始化)。
  2. 根据当前 key 的 hashcode 定位到具体的桶中并判断能否为空,为空表明没有 hash 冲突直接在当前位置创立一个新桶。
  3. 假如当前桶有值( hash 冲突),比较当前桶中的 key 和 key 的 hashcode 与写入的 key 能否相等,相等赋值给 e,在第 8 步的时候统一进行赋值及返回。
  4. 假如当前桶为红黑树,就按照红黑树的方式写入数据。
  5. 假如是链表,将当前的 key、value 封装成一个 新结点写入到当前桶的后面(形成链表)。
  6. 判断当前链表的大小能否大于预设的阈值(TREEIFY_THRESHOLD),大于时转换为红黑树。
  7. 假如在遍历过程中找到 key 相同时直接退出遍历。
  8. 假如 e != null 说明存在相同的 key,将值覆盖。
  9. 判断能否需要进行扩容。

数组扩容

  • resize() 方法用于初始化数组或者数组扩容,每次扩容后,容量为原来的 2 倍,并进行数据迁移。
final Node<K,V>[] resize() {    Node<K,V>[] oldTab = table;    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    if (oldCap > 0) { // 对应数组扩容        if (oldCap >= MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return oldTab;        }        // 将数组大小扩大一倍        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)            // 将阈值扩大一倍            newThr = oldThr << 1; // double threshold    }    else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后,第一次 put 的时候        newCap = oldThr;    else {// 对应使用 new HashMap() 初始化后,第一次 put 的时候        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }     if (newThr == 0) {        float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    threshold = newThr;     // 用新的数组大小初始化新的数组    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];    table = newTab; // 假如是初始化数组,到这里就结束了,返回 newTab 就可     if (oldTab != null) {        // 开始遍历原数组,进行数据迁移。        for (int j = 0; j < oldCap; ++j) {            Node<K,V> e;            if ((e = oldTab[j]) != null) {                oldTab[j] = null;                // 假如该数组位置上只有单个元素,迁移这个元素即可以了                if (e.next == null)                    newTab[e.hash & (newCap - 1)] = e;                // 假如是红黑树的解决                else if (e instanceof TreeNode)                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                else {                     // 这块是解决链表的情况,                    // 需要将此链表拆成两个链表,放到新的数组中,并且保留原来的先后顺序                    // loHead、loTail 对应一条链表,hiHead、hiTail 对应另一条链表                    Node<K,V> loHead = null, loTail = null;                    Node<K,V> hiHead = null, hiTail = null;                    Node<K,V> next;                    do {                        next = e.next;                        if ((e.hash & oldCap) == 0) {                            if (loTail == null)                                loHead = e;                            else                                loTail.next = e;                            loTail = e;                        }                        else {                            if (hiTail == null)                                hiHead = e;                            else                                hiTail.next = e;                            hiTail = e;                        }                    } while ((e = next) != null);                    if (loTail != null) {                        loTail.next = null;                        // 第一条链表                        newTab[j] = loHead;                    }                    if (hiTail != null) {                        hiTail.next = null;                        // 第二条链表的新的位置是 j + oldCap                        newTab[j + oldCap] = hiHead;                    }                }            }        }    }    return newTab;}

get 方法过程

  1. 计算 key 的 hash 值,根据 hash 值找到对应数组下标 hash & (length-1)。
  2. 判断数组该位置处的元素能否恰好就是需要的元素,假如不是,则走第 3 步。
  3. 判断该元素类型能否是 TreeNode,假如是,用红黑树的方法取数据,假如不是,走第 4 步。
  4. 遍历链表,直到找到相等(== 或者 equals)的 key。
  • 1.8 中对链表做了优化,修改为红黑树之后查询效率直接提高到了 O(logN),但是 HashMap 原有的死循环问题还是存在。
    • HashMap 扩容的时候会调用 resize() 方法,这里的并发操作容易在一个桶上形成环形链表,这样当获取一个不存在的 key 时,计算出的 index 正好是环形链表的下标就会出现死循环。
public V get(Object key) {    Node<K,V> e;    return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node<K,V> getNode(int hash, Object key) {    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {        // 判断第一个结点是不是需要的        if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k))))            return first;        if ((e = first.next) != null) {            // 判断能否是红黑树            if (first instanceof TreeNode)                return ((TreeNode<K,V>)first).getTreeNode(hash, key);             // 链表遍历            do {                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;            } while ((e = e.next) != null);        }    }    return null;}

1.2 ConcurrentHashMap(JDK 1.8)

JDK 1.8 ConcurrentHashMap

  • 抛弃了 JDK 1.7 中原有的 Segment 分段锁,而采用了 CAS + synchronized 来保证并发安全性。
  • 将 JDK 1.7 中存放数据的 HashEntry 改为 Node,但作用是相同的。
属性说明
table默认为 null,初始化发生在第一次插入操作,默认大小为 16 的数组,用来存储 Node 节点数据,扩容时大小总是 2 的幂次方。
nextTable默认为 null,扩容时新生成的数组,其大小为原数组的两倍。
sizeCtl默认为 0,用来控制 table 的初始化和扩容操作。-1 代表 table 正在初始化;-N 表示有 N-1 个线程正在进行扩容操作。
ForwardingNode一个特殊的 Node 节点,hash 值为 -1,其中存储 nextTable 的引用。有 table 发生扩容的时候,ForwardingNode 发挥作用,作为一个占位符放在 table 中表示当前节点为 null 或者者已经被移动。
static class Node<K,V> implements Map.Entry<K,V> {        final int hash;        final K key;        volatile V val;        volatile Node<K,V> next;        Node(int hash, K key, V val, Node<K,V> next) {            this.hash = hash;            this.key = key;            this.val = val;            this.next = next;        }        public final K getKey()       { return key; }        public final V getValue()     { return val; }        public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }        public final String toString(){ return key + "=" + val; }        public final V setValue(V value) {            throw new UnsupportedOperationException();        }        public final boolean equals(Object o) {            Object k, v, u; Map.Entry<?,?> e;            return ((o instanceof Map.Entry) &&                    (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&                    (v = e.getValue()) != null &&                    (k == key || k.equals(key)) &&                    (v == (u = val) || v.equals(u)));        }        /**         * Virtualized support for map.get(); overridden in subclasses.         */        Node<K,V> find(int h, Object k) {            Node<K,V> e = this;            if (k != null) {                do {                    K ek;                    if (e.hash == h &&                        ((ek = e.key) == k || (ek != null && k.equals(ek))))                        return e;                } while ((e = e.next) != null);            }            return null;        }}

put 方法过程

final V putVal(K key, V value, boolean onlyIfAbsent) {        if (key == null || value == null) throw new NullPointerException(); // 键或者值为空,抛出异常        // 键的hash值经过计算取得hash值,这里的 hash 计算多了一步 & HASH_BITS,HASH_BITS 是 0x7fffffff,该步是为了消除最高位上的负符号 hash的负在ConcurrentHashMap中有特殊意义表示在扩容或者者是树节点        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) // 表为空或者者表的长度为0                // 初始化表                tab = initTable();            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 表不为空并且表的长度大于0,并且该桶不为空                if (casTabAt(tab, i, null,                             new Node<K,V>(hash, key, value, null))) // 比较并且交换值,如tab的第i项为空则用新生成的node替换                    break;                   // no lock when adding to empty bin            }            else if ((fh = f.hash) == MOVED) // 该结点的hash值为MOVED                // 进行结点的转移(在扩容的过程中)                tab = helpTransfer(tab, f);            else {                V oldVal = null;                synchronized (f) { // 加锁同步                    if (tabAt(tab, i) == f) { // 找到table表下标为i的节点                        if (fh >= 0) { // 该table表中该结点的hash值大于0                            // binCount赋值为1                            binCount = 1;                            for (Node<K,V> e = f;; ++binCount) { // 无限循环                                K ek;                                if (e.hash == hash &&                                    ((ek = e.key) == key ||                                     (ek != null && key.equals(ek)))) { // 结点的hash值相等并且key也相等                                    // 保存该结点的val值                                    oldVal = e.val;                                    if (!onlyIfAbsent) // 进行判断                                        // 将指定的value保存至结点,即进行了结点值的升级                                        e.val = value;                                    break;                                }                                // 保存当前结点                                Node<K,V> pred = e;                                if ((e = e.next) == null) { // 当前结点的下一个结点为空,即为最后一个结点                                    // 新生一个结点并且赋值给next域                                    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) { // 将hash、key、value放入红黑树                                // 保存结点的val                                oldVal = p.val;                                if (!onlyIfAbsent) // 判断                                    // 赋值结点value值                                    p.val = value;                            }                        }                    }                }                if (binCount != 0) { // binCount不为0                    if (binCount >= TREEIFY_THRESHOLD) // 假如binCount大于等于转化为红黑树的阈值                        // 进行转化                        treeifyBin(tab, i);                    if (oldVal != null) // 旧值不为空                        // 返回旧值                        return oldVal;                    break;                }            }        }        // 添加binCount的数量        addCount(1L, binCount);        return null;}
  1. 判断存储的 key、value 能否为空,若为空,则抛出异常,否则,进入步骤 2。
  2. 计算 key 的 hash 值,随后进入自旋,该自旋可以确保成功插入数据,若 table 表为空或者者长度为 0,则初始化 table 表,否则,进入步骤 3。
  3. 根据 key 的 hash 值取出 table 表中的结点元素,若取出的结点为空(该桶为空),则使用 CAS 将 key、value、hash 值生成的结点放入桶中。否则,进入步骤 4。
  4. 若该结点的的 hash 值为 MOVED(-1),则对该桶中的结点进行转移,否则,进入步骤 5。
  5. 对桶中的第一个结点(即 table 表中的结点)进行加锁,对该桶进行遍历,桶中的结点的 hash 值与 key 值与给定的 hash 值和 key 值相等,则根据标识选择能否进行升级操作(用给定的 value 值替换该结点的 value 值),若遍历完桶仍没有找到 hash 值与 key 值和指定的 hash 值与 key 值相等的结点,则直接新生一个结点并赋值为之前最后一个结点的下一个结点。进入步骤 6。
  6. 若 binCount 值达到红黑树转化的阈值,则将桶中的结构转化为红黑树存储,最后,添加 binCount 的值。
  • 假如桶中的第一个元素的 hash 值大于 0,说明是链表结构,则对链表插入或者者升级。
  • 假如桶中的第一个元素是 TreeBin,说明是红黑树结构,则按照红黑树的方式进行插入或者者升级。
  • 在锁的保护下,插入或者者升级完毕后,假如是链表结构,需要判断链表中元素的数量能否超过 8(默认),一旦超过,就需要考虑进行数组扩容,或者者是链表转红黑树。

初始化数组

  • 初始化方法中的并发问题是通过对 sizeCtl 进行一个 CAS 操作来控制的。
    • 只有第一次使用才初始化,为了防止初始化后的初次操作就需要扩容(比方 putAll ),从而影响效率。
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        // CAS 一下,将 sizeCtl 设置为 -1,代表抢到了锁        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {            try {                if ((tab = table) == null || tab.length == 0) {                    // DEFAULT_CAPACITY 默认初始容量是 16                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;                    // 初始化数组,长度为 16 或者初始化时提供的长度                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];                    // 将这个数组赋值给 table,table 是 volatile 的                    table = tab = nt;                    // 假如 n 为 16 的话,那么这里 sc = 12                    // 其实就是 0.75 * n                    sc = n - (n >>> 2);                }            } finally {                // 设置 sizeCtl 为 sc                sizeCtl = sc;            }            break;        }    }    return tab;}

链表转红黑树

  • treeifyBin 不肯定就会进行红黑树转换,也可能是仅仅做数组扩容。
private final void treeifyBin(Node<K,V>[] tab, int index) {        Node<K,V> b; int n, sc;        if (tab != null) { // 表不为空            if ((n = tab.length) < MIN_TREEIFY_CAPACITY) // table表的长度小于最小的长度                // 进行扩容,调整某个桶中结点数量过多的问题(因为某个桶中结点数量超出了阈值,则触发treeifyBin)                tryPresize(n << 1);            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { // 桶中存在结点并且结点的hash值大于等于0                synchronized (b) { // 对桶中第一个结点进行加锁                    if (tabAt(tab, index) == b) { // 第一个结点没有变化                        TreeNode<K,V> hd = null, tl = null;                        for (Node<K,V> e = b; e != null; e = e.next) { // 遍历桶中所有结点                            // 新生一个TreeNode结点                            TreeNode<K,V> p =                                new TreeNode<K,V>(e.hash, e.key, e.val,                                                  null, null);                            if ((p.prev = tl) == null) // 该结点前驱为空                                // 设置p为头结点                                hd = p;                            else                                // 尾节点的next域赋值为p                                tl.next = p;                            // 尾节点赋值为p                            tl = p;                        }                        // 设置table表中下标为index的值为hd                        setTabAt(tab, index, new TreeBin<K,V>(hd));                    }                }            }        }}

数组扩容

  • 扩容后数组容量为原来的 2 倍。
// 参数 size 传进来的时候就已经翻倍(例如 16)private final void tryPresize(int size) {    // c:size 的 1.5 倍,再加 1,再往上取最近的 2 的 n 次方。    // 16 + 8 + 1 -> 32 -> 2^8    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :        tableSizeFor(size + (size >>> 1) + 1);    int sc;    while ((sc = sizeCtl) >= 0) {        Node<K,V>[] tab = table; int n;         // 这个 if 分支和之前说的初始化数组的代码基本上是一样的,在这里,我们可以不用管这块代码        if (tab == null || (n = tab.length) == 0) {            n = (sc > c) ? sc : c;            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {                try {                    if (table == tab) {                        @SuppressWarnings("unchecked")                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];                        table = nt;                        sc = n - (n >>> 2); // 0.75 * n                    }                } finally {                    sizeCtl = sc;                }            }        }        else if (c <= sc || n >= MAXIMUM_CAPACITY)            break;        else if (tab == table) {            int rs = resizeStamp(n);             if (sc < 0) {                Node<K,V>[] nt;                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||                    transferIndex <= 0)                    break;                // 2. 用 CAS 将 sizeCtl 加 1,而后执行 transfer 方法                //    此时 nextTab 不为 null                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))                    transfer(tab, nt);            }            // 1. 将 sizeCtl 设置为 (rs << RESIZE_STAMP_SHIFT) + 2)            //  调用 transfer 方法,此时 nextTab 参数为 null            else if (U.compareAndSwapInt(this, SIZECTL, sc,                                         (rs << RESIZE_STAMP_SHIFT) + 2))                transfer(tab, null);        }    }}

数据迁移

  • 此方法支持多线程执行,外围调用此方法的时候,会保证第一个发起数据迁移的线程,nextTab 参数为 null,之后再调用此方法的时候,nextTab 不会为 null。
    • 了解为有 n 个迁移任务,让每个线程每次负责一个小任务,每做完一个任务再检测能否有其余没做完的任务。
  • Doug Lea 使用了一个 stride(步长),每个线程每次负责迁移其中的一部分,如每次迁移 16 个小任务。所以需要一个全局的调度者来安排哪个线程执行哪几个任务,这个就是属性 transferIndex 的作用。
  • transfer 这个方法并没有实现所有的迁移任务,每次调用这个方法只实现了 transferIndex 往前 stride 个位置的迁移工作,其余的需要由外围来控制。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {        int n = tab.length, stride;        //根据cpu个数找出扩容时的数组跨度大小即最小分组 16 32 64增长        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)            stride = MIN_TRANSFER_STRIDE; // subdivide range        //普通扩容nextTab为空,竞争帮助扩容时有值,n<<1说明扩容2倍        if (nextTab == null) {            // initiating            try {                @SuppressWarnings("unchecked")                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];                nextTab = nt;            } catch (Throwable ex) {      // try to cope with OOME                sizeCtl = Integer.MAX_VALUE;                return;            }            nextTable = nextTab;            //当前转移的位置,说明是逆序迁移            transferIndex = n;        }        int nextn = nextTab.length;        //创立扩容的连接节点,节点hash是-1        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);        boolean advance = true;        boolean finishing = false; // to ensure sweep before committing nextTab        for (int i = 0, bound = 0;;) {//死循环检查            Node<K,V> f; int fh;            while (advance) {                int nextIndex, nextBound;                if (--i >= bound || finishing)//当前分组未转移完||扩容一律完成  --i完成数组逆序迁移                    advance = false;                else if ((nextIndex = transferIndex) <= 0) {//TRANSFERINDEX为0表示无下一个分组了                    i = -1;                    advance = false;                }                else if (U.compareAndSwapInt                         (this, TRANSFERINDEX, nextIndex,                          nextBound = (nextIndex > stride ?                                       nextIndex - stride : 0))) {//CAS TRANSFERINDEX 多线程时,advance死循环会找到不同的分组,以一个分组一个线程负责来进行扩容                    bound = nextBound;//迁移时本分组的下界                    i = nextIndex - 1;//上界                    advance = false;                }            }            if (i < 0 || i >= n || i + n >= nextn) {//一律迁移完或者无分组                int sc;                if (finishing) {//扩容完成                    nextTable = null;                    table = nextTab;                    sizeCtl = (n << 1) - (n >>> 1);//0.75                    return;                }                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {//减少一个扩容线程                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)//根据前面addCount的+2这里就有-2  判断能否是最后一个正在扩容的线程                        return;                    finishing = advance = true;//准备结束                    i = n; // recheck before commit 赋值n让其进入本if进行能否结束的检查                }            }            else if ((f = tabAt(tab, i)) == null)//原数组i位置无节点                advance = casTabAt(tab, i, null, fwd);//cas插入扩容节点 多线程插入失败就循环重新检查            else if ((fh = f.hash) == MOVED)//实际是检查上一步为null时CAS能否成功                advance = true; // already processed  之后在上面的while中变更i后继续            else {                synchronized (f) {//首节点上锁                    if (tabAt(tab, i) == f) {//节点此时没本remove等干掉                        Node<K,V> ln, hn;                        if (fh >= 0) {//不是树节点                            //下面这段是在拆分本位置的链表 一拆为二(一链表正向一链表反向,0或者非0谁在最后连续那它就是正向,另一个反向) map大小n是2的倍数 与计算只会有0和n本身 好想法                            int runBit = fh & n;                            Node<K,V> lastRun = f;                            for (Node<K,V> p = f.next; p != null; p = p.next) {                                int b = p.hash & n;                                if (b != runBit) {                                    runBit = b;                                    lastRun = p;                                }                            }                            if (runBit == 0) {                                ln = lastRun;                                hn = null;                            }                            else {                                hn = lastRun;                                ln = null;                            }                            for (Node<K,V> p = f; p != lastRun; p = p.next) {                                int ph = p.hash; K pk = p.key; V pv = p.val;                                if ((ph & n) == 0)                                    ln = new Node<K,V>(ph, pk, pv, ln);                                else                                    hn = new Node<K,V>(ph, pk, pv, hn);                            }                            setTabAt(nextTab, i, ln);//拆后的链表1放在新数组i位置                            setTabAt(nextTab, i + n, hn);//链表2放i+n位置                            setTabAt(tab, i, fwd);//原数组i位置放扩容节点                            advance = true;//i位置索引迁移完成                        }                        else if (f instanceof TreeBin) {                            TreeBin<K,V> t = (TreeBin<K,V>)f;                            TreeNode<K,V> lo = null, loTail = null;                            TreeNode<K,V> hi = null, hiTail = null;                            int lc = 0, hc = 0;                            for (Node<K,V> e = t.first; e != null; e = e.next) {                                int h = e.hash;                                TreeNode<K,V> p = new TreeNode<K,V>                                    (h, e.key, e.val, null, null);                                if ((h & n) == 0) {                                    if ((p.prev = loTail) == null)                                        lo = p;                                    else                                        loTail.next = p;                                    loTail = p;                                    ++lc;                                }                                else {                                    if ((p.prev = hiTail) == null)                                        hi = p;                                    else                                        hiTail.next = p;                                    hiTail = p;                                    ++hc;                                }                            }                            //扩容后数量太少降为链表 不用树                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :                                (hc != 0) ? new TreeBin<K,V>(lo) : t;                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :                                (lc != 0) ? new TreeBin<K,V>(hi) : t;                            setTabAt(nextTab, i, ln);                            setTabAt(nextTab, i + n, hn);                            setTabAt(tab, i, fwd);                            advance = true;                        }                    }                }            }        }}

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;        }        // 假如头结点的 hash 小于 0,说明 正在扩容,或者者该位置是红黑树        else if (eh < 0)            // 参考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)            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;}
  1. 计算 hash 值。
  2. 根据 hash 值找到数组对应位置: (n – 1) & h。
  3. 根据该位置处结点性质进行相应查找。
  • 假如该位置为 null,那么直接返回 null。
  • 假如该位置处的节点恰好就是需要的,返回该节点的值就可。
  • 假如该位置节点的 hash 值小于 0,说明正在扩容,或者者是红黑树。
  • 假如以上 3 条都不满足,那就是链表,进行遍历比对就可。

参考资源

http://www.importnew.com/28263.html
https://baijiahao.baidu.com/s?id=1607561719049934113&wfr=spider&for=pc
https://www.cnblogs.com/ITtangtang/p/3948786.html
https://blog.csdn.net/wo2niliye/article/details/69396812
https://blog.csdn.net/justloveyou_/article/details/72783008
https://blog.csdn.net/justloveyou_/article/details/62893086
https://www.cnblogs.com/dolphin0520/p/3932905.html
http://www.importnew.com/26049.html
https://blog.csdn.net/lin20044140410/article/details/79320587
http://ifeve.com/concurrenthashmap/

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 【Java 并发笔记】ConcurrentHashMap(1.8) 相关整理

发表回复