美文网首页
ConcurrentHashMap的总结

ConcurrentHashMap的总结

作者: 北雁南飞_8854 | 来源:发表于2018-06-18 22:13 被阅读0次

HashMap的创建

指定参数时:

/**
 * 根据容量参数initialCapacity计算sizeCtrl,值为:
 *  (1.5 * initialCapacity + 1),然后向上取近的2次幂。
 * @param initialCapacity 
 * @throws IllegalArgumentException 如果initialCapacity为负时,抛出该异常;
 */
public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

不指定参数时:

public ConcurrentHashMap() {
}

数组的初始化发生在initTable()中。

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0) 
        //如果sizeCtrl<0, 则表示有其他线程正在执行初始化操作且未成功, 
       //调用Thread.yield()使其失去CPU的执行权,等待初始化的完成;
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //当sizeCtrl的值为sc时, 将sizeCtrl更新为-1;
           try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY; //如果没有指定过sizeCtrl, 则使用默认值DEFAULT_CAPACITY(16);
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                    sizeCtl = sc; //执行成功以后, 将sizeCtrl更新为原来的0.75倍.
            }
            break;
        }
    }
    return tab;
}

元素访问操作

//获取i位置的元素
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

//利用CAS算法设置i位置上的元素值(将c和v比较,如果不相同则插入v到i位置);
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

//设置i位置的值为v
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
    U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

插入操作

插入<K,V>类型的键值对<key, value>, 具体方法:

  1. 计算key的hash值,为spread(key.hashCode());
  2. 如果table为null, 则创建大小为sizeCtrl的Node<K,V>[]数组table, 并更新sizeCtrl;
  3. 根据hash值, 确定要插入的位置: (n - 1) && hash;
  4. 如果table中待插入位置为null, 则插入新创建的Node实例;
  5. 如果table待插入位置的Node实例hash值>=0, 从Node链表中找出hash和key都相等的元素; 如果找到, 则直接更新;如果没有找到,则将新的Node插入到链表末尾;
  6. 如果待插入位置的Node实例的hash值<0, 则判断是否为红黑树节点。
/**
 * @param key
 * @param value
 * @param onlyIfAbsent onlyIfAbsent为true时, 仅当table中不存在该key时, 才会进行插入操作;
 * @return
 */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    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)
            //initTable()创建大小为sizeCtrl的Node<K,V>[]数组table, 并更新sizeCtrl.
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //tab[i]为null.
            //在位置i处插入新建的Node实例.
            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) //tab[i]的Node实例hash值为MOVED(-1)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    //tab[i]的Node实例hash值>=0, 从Node链表中找出hash和key都相等的元素;
                    // 如果找到,如果没有找到,则将新的Node插入到链表末尾.
                    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;
                            }
                        }
                    } 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;
                        }
                    } 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;
}

获取操作

获取参数key所对应的Value,具体方法:

  1. 计算hash值h:spread(key.hashCode());
  2. 根据hash值确定table数组位置: (n - 1) & h;
  3. (1) 如果该位置为null, 返回null;
    (2) 如果该位置不为null, 记首节点为e; 如果e.hash == h && e.key == key,则直接返回e.val, 否则进入(3)
    (3) 如果e.hash < 0, 说明正在扩容,或者是红黑树;
    (4) 如果以上3条都不满足, 说明是链表, 按顺序进行遍历.
    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;
    }

相关文章

  • ConcurrentHashMap-JDK1.7版

    分析一下ConcurrentHashMap的成员变量: 总结:ConcurrentHashMap中包含一个segm...

  • ConcurrentHashMap的总结

    HashMap的创建 指定参数时: 不指定参数时: 数组的初始化发生在initTable()中。 元素访问操作 插...

  • ConcurrentHashMap总结

    其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言,Con...

  • ConcurrentHashMap总结

    1. 总结:如何保证线程线程安全 CAS操作数据:table数组的取值/设置值、链表的数值操作、sizeCtl修改...

  • ConcurrentHashMap 1.7总结

    一、通过Key找到在Segment[]数组中的位置: 1. 变量定义: ssize: 不小于concurrency...

  • ConcurrentHashMap详细总结

    上文详细介绍了HashMap的内容,但是由于HashMap不是线程安全的,因此使用起来会存在一定的风险。本文主要介...

  • ConcurrentHashMap并发总结

    ConcurrentHashMap(以下称为CHM)各版本JDK 5:分段锁,必要时加锁。通过Segment来分段...

  • 简单总结ConcurrentHashMap

    在并发使用到HashMap的时候,往往不建议直接用HashMap,因为HashMap在并发写数据的时候容易因为re...

  • ConcurrentHashMap源码分析(JDK8)

    导入 ConcurrentHashMap是HashMap的线程安全版本的实现版本,关于HashMap的分析总结,可...

  • ConcurrentHashMap源码阅读小结

    putVal 方法总结 说起 ConcurrentHashMap ,当然从入口开始说。该方法要点如下: 1. 不允...

网友评论

      本文标题:ConcurrentHashMap的总结

      本文链接:https://www.haomeiwen.com/subject/yocoeftx.html