侧边栏壁纸
博主头像
晓果冻博主等级

一个热爱生活的95后精神小伙

  • 累计撰写 131 篇文章
  • 累计创建 15 个标签
  • 累计收到 67 条评论

目 录CONTENT

文章目录

ConcurrentHashMap学习

晓果冻
2022-06-05 / 0 评论 / 0 点赞 / 487 阅读 / 2,428 字
温馨提示:
本文最后更新于 2022-06-10,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

ConcurrentHashMap学习

image-20220605214144265

image-20220601155015265

属性
//最大容量 2的30次方
private static final int MAXIMUM_CAPACITY = 1 << 30;

//初始容量 
private static final int DEFAULT_CAPACITY = 16;

/** 
 * 虚拟机限制的最大数组长度,在ArrayList中有说过,jdk1.8新引入的,
 * ConcurrentHashMap的主体代码中是不使用这个的,主要用在Collection.toArray两个方法中
 */
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/** 
 *默认并行级别,主体代码中未使用此常量,为了兼容性,保留了之前的定义,
 *主要是配合同样是为了兼容性的Segment使用
 */
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

//默认加载因子
private static final float LOAD_FACTOR = 0.75f;

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

static final int MIN_TREEIFY_CAPACITY = 64;

//并发扩容时每个线程最少处理16个桶
private static final int MIN_TRANSFER_STRIDE = 16;
//扩容时使用 一个标识戳
private static int RESIZE_STAMP_BITS = 16;
//标识并发扩展的最大线程数量
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
//扩容相关
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

//表示当前节点是forwarding nodes
static final int MOVED = -1; 

//红黑树的代理结点
static final int TREEBIN = -2; 

// 临时保留的散列表
static final int RESERVED = -3;

// 0x7fffffff = 31个1  用于将一个负数变成一个正数 但不是取绝对值
static final int HASH_BITS = 0x7fffffff; 

//全局table  volatile保证可见性 例如初始化时,多个线程操作
transient volatile Node<K,V>[] table;

//扩容时的临时散列表
private transient volatile Node<K,V>[] nextTable;

private transient volatile long baseCount;

//默认 0 -1 表示其他线程已经在扩容 -2 当前有俩个线程在扩容
private transient volatile int sizeCtl;

//扩容过程中,记录当前进度
private transient volatile int transferIndex;

// 0 无锁 1 加锁
private transient volatile int cellsBusy;

private transient volatile CounterCell[] counterCells;

// views
private transient KeySetView<K,V> keySet;
private transient ValuesView<K,V> values;
private transient EntrySetView<K,V> entrySet;
构造函数
//默认无参构造函数
public ConcurrentHashMap() {
}

   
    public ConcurrentHashMap(int initialCapacity) {
    	//初始容量小于0,则抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        //判断初始容量是否大于等于2的29次方,是则取最大值2的30次方,否则
        //tableSizeFor: 返回一个比给定整数大且最接近的2的幂次方整数,如给定10,返回2的4次方16. 
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

	// 带初始集合数据参数的构造函数
    public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this.sizeCtl = DEFAULT_CAPACITY;
        putAll(m);
    }

	//指定初始容量和负载因子
    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, 1);
    }


//指定初始容量、负载因子、并发数量
    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        // 初始容量参数小于并发线程数,将初始容量参数赋值为并发线程数
        if (initialCapacity < concurrencyLevel)   
            initialCapacity = concurrencyLevel;  
        //计算容量 (需要存储的元素个数 / 负载因子) + 1
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }
实现存储的数据结构
//与HashMap的区别是volatile   
   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方法
public V put(K key, V value) {
	return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
		//不支持key或者value为空
        if (key == null || value == null) throw new NullPointerException();
        //计算hash值
        int hash = spread(key.hashCode());
        //记录链表的长度 如果大于8的情况下,则转为红黑树
        int binCount = 0;
        //自旋
        for (Node<K,V>[] tab = table;;) { 
            Node<K,V> f; int n, i, fh;
            //判断全局table
            if (tab == null || (n = tab.length) == 0)
            //初始化
                tab = initTable();
            /* 计算该key存放的index下标位置,查找该node节点 如果没发生index冲突
            *(n-1)&hash 计算当前key存放在table的哪个下标位置
            */
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //使用cas操作去修改
            //同时有多个线程同时修改 没有发生index冲突下标位置 cas修改 如果cas修改成功的
            //情况下 break 退出自旋
                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 = helpTransfer(tab, f);
            //下标发生冲突的情况下
            else {
                V oldVal = null;
                synchronized (f) {
                //自旋再查一次  
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            //链表的情况下追加元素,break跳出synchronized锁
                            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;
                            }
                        }
                    }
                }
                //转红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
initTable方法
   //初始化
   private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        //判断table是否为空  自旋:消耗cpu资源,但可以提高效率
        while ((tab = table) == null || tab.length == 0) {
        //如果发现有其他的线程正在扩容的时候,当前线程释放cpu执行权
            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) {
                    //初始化 
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        //假如此线程走到这步挂掉了,没有给table赋值,那么其他线程会一直在做自旋
                        //所以上面Thread.yield()很有用,在这种情况下最起码释放了其他线程的
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        //sc 扩容阈值
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }
private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }
        if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }
addCount方法
    private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }
        if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }
spread方法(计算Hash值)
// 当前的hash右移16位 亦或 原来的hash  & HASH_BITS 得到正数的hash值,让高16位 也参与到运算中来
static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }
tableSizeFor方法
//返回一个大于输入值 c 的2的幂
private static final int tableSizeFor(int c) {
//减一的作用是防止输入的值正好是2的幂,得到比输入值大一倍的值,例如 c = 8,如果不减1的话return 16
    int n = c - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
tabAt方法
    //获取数组指定下标位置的元素
    @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);
    }
casTabAt方法
  //用cas的方式去tab指定位置设置值
  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);
    }
setTabAt方法
 
 static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }
计算存放位置
  • JDK1.7计算俩次,第一次计算存放在哪一个Segments中,第二次计算存放在Segments中的哪个下标位置。
  • JDK1.8 一次,只需要计算在哪个下标位置。

我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=3kmaxlbket8g8

0

评论区