并发容器

由 笔尖 发布

HashMap

  • java1.7:数组+链表
  • java1.8:数组+链表+红黑树
  1. 创建数组时按照2的幂次进行创建,方便bucket_index计算和扩容时的高低位指针移动。
  2. &运算而不是%运算,使得计算效率提升。
  3. 扩容的阈值为0.75,即如果容量为16,达到12时进行扩容,*2,0.75综合了时间、空间效率。
  4. 扩容时,1.7采用头插法,多线程环境下易造成链表循环,无法跳出。1.8改为高低位指针,避免了死循环的同时,也没有执行index的二次计算,前提是扩容倍数为2。
  5. 另外,链表长度达到8时,不论扩容阈值是否达到,一定会考虑扩容,只有总数>64时才会转变为红黑树。

高低位指针扩容

image-20210912110650840

假设右边链表长度达到阈值,且需要进行扩容,那么扩容时会用高低位指针分别指向两个不同的链表。由于容量的大小是2的幂次的关系,因此,只需要考察高一位的二进制是否为1,即可区分出不同的节点,如果为0,则是低位,扩容后index位置保持不变,如果为1,则是高位,扩容后index位置+2^n^次幂,避免了循环问题,也减小了计算量。

image-20210912110641687

ConcurrentHashMap

基本数据结构类似,区别在于写操作是加锁执行,读操作不用考虑同步,扩容时并发协助扩容。

  • java1.7:采用分段锁保证线程安全,segment数组每个元素对应一个hashTable,当两个线程在同一个segment执行写操作时会竞争。
  • java1.8:采用分段锁(锁力度更小)+CAS保证线程安全,当node结点第一次插入时执行CAS逻辑。
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)//如果还没初始化,则初始化表
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果插入的第一个节点为空,则通过cas实现插入操作
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                  
        }
        else if ((fh = f.hash) == MOVED)//判断是否为转移节点,如果是,则协助扩容
            tab = helpTransfer(tab, f);
        else {//其他情况,需要获取该bucket的锁,之后执行插入操作。
            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;
                            }
                        }
                    }
                    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;
}

ConcurrentHashMap提供了一些组合原子操作,因为有的时候原子操作put、get组合在一起时会变得不安全,例如先读取再修改,而replace(key,oldvalue,newvalue)和putIfAbsent(key,value)提供了相应CAS操作,使得多步操作在一起时变得安全。如果依然采用之前的synchronized代码块的形式保护,反而又降低了ConcurrentHashMap的性能。

public void op() {
    int score = concurrentHashMap.get("jack");
    while (!concurrentHashMap.replace("jack", score, score + 1)){
        score = concurrentHashMap.get("jack");
    }
}

总结,HashMap非线程安全、Hashtable synchronized同步方法修饰,Collection.synchronizedMap同步代码块修饰。

ArrayList

非线程安全数组,多线程场景下,因为有failfast快速机制,导致在读的过程中,如果有写线程在工作,就会发生空指针异常、不一致等问题。可以采用加锁lock的方式,但会降低并发性能,升级为读写锁ReadWriteLock可以适用于读多写多的场景,读读并行,读写互斥,写写互斥。

CopyOnWriteList

核心思想是读写分离,空间换时间,保证并发安全的同时,也能提高并发效率。

  • 适用于读多写少,最大程度提高读的效率。
  • 只保证最终一致性,读的过程中可能已发生数据修改,新旧副本数据不相同。
  • 内部属性Object[]使用volatile修饰,保证数据可见性,写线程一旦修改完毕,读线程在写线程之后读取,一定是最新的值。
  • 写写互斥,多个线程写使用lock加锁。
  • 写多的场景,频繁的创建新数组将导致GC。

image-20210912110705469

/*
 *   添加元素api
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); //复制一个array副本
        newElements[len] = e; //往副本里写入
        setArray(newElements); //副本替换原本,成为新的原本
        return true;
    } finally {
        lock.unlock();
    }
}
//读api
public E get(int index) {
    return get(getArray(), index); //无锁,读线程读取时使用的是旧有数组。
}

总结,ArrayList非线程安全,Vector synchronized同步方法修饰,Collection.synchronizedList同步代码块修饰。


暂无评论

发表评论