线程安全的容器小结

线程安全的容器

列表

线程安全的列表有 Vector , CopyOnWriteArrayList 两种,区别则主要在实现方式上,对锁的优化上; 后者主要采用的是 copy-on-write 思路,修改时,拷贝一份出来,修改完成之后替换

1. Vector 实现

vector 保证线程安全的原理比较简单粗暴,直接在方法上加锁

get 方法

public synchronized E get(int index) {
   if (index >= elementCount)
       throw new ArrayIndexOutOfBoundsException(index);

   return elementData(index);
}

set 方法

public synchronized E set(int index, E element) {
   if (index >= elementCount)
       throw new ArrayIndexOutOfBoundsException(index);

   E oldValue = elementData(index);
   elementData[index] = element;
   return oldValue;
}

add方法

 public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

size方法

public synchronized int size() {
   return elementCount;
}

从上面几个最最常见的几个方法,就可以看出,这个实现非常的简单粗暴,全部上锁,肯定是线程安全的问题了;相应的问题也很明显,效率妥妥的够了,即便全是读操作,都会有阻塞竞争,基本上完全是没法忍的

2. CopyOnWriteArrayList 实现

使用了 copyOnWrite 机制,一句话,读时直接读,在修改时,先拷贝一份出来,在拷贝上进行修改,完成之后替换掉之前的引用

下面主要看一下几个最常见的方法,是如何实现的,以此来研究下这套机制的玩法

size 方法

public int size() {
   return getArray().length;
}

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

/**
* Gets the array.  Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
final Object[] getArray() {
   return array;
}

对比一下 ArrayList 的获取size方法,有一个size属性记录的是链表的长度,直接返回的这个值;而CopyOnWriteArrayList 则是每次都去实时查数组的长度

/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
    
public int size() {
        return size;
}

为什么这么做 ?

get方法

/**
* {@inheritDoc}
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
   return get(getArray(), index);
}

private E get(Object[] a, int index) {
   return (E) a[index];
}
// ArrayList 
public E get(int index) {
   rangeCheck(index);

   return elementData(index);
}

E elementData(int index) {
   return (E) elementData[index];
}

和上面相同,同样是先调用 getArray() 方法,然后在进行相应的操作,如果不这么做,直接如 ArrayList 一样的调用方式时(如下)

  • 假设数组长度为 3, 现在获取index=2(即最后一个)的元素值
  • rangeCheck 方法确认通过,elementData执行之前
  • 现在一个线程,删除了一个元素,此时上面这个线程获取时,就会出现数组越界

如果是上面的执行逻辑,则不会如此,因为操作的依然是老的那个数组对应的引用;当发生修改时,是在新的数组上进行的

add 方法

接下来则看一下具体的修改方法,是不是确实在新的数组上进行的操作,源码如下:

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);
       newElements[len] = e;
       setArray(newElements);
       return true;
   } finally {
       lock.unlock();
   }
}

关注几点:

  • 上锁: 这里表明,每次修改都只能有一个线程在执行
  • 修改过程:
    • 拷贝原来内容到新的的数组上
    • 将元素添加在新的数组上
    • 更新列表中数组的引用,指向新的数组

set 方法

修改内容的值时,同样是先加锁,再修改,确保每次修改都是串行进行的;需要注意的一点是

  • 若设置的value和原来的内容相等,则不需要修改引用
  • 一定得确保释放锁
public E set(int index, E element) {
   final ReentrantLock lock = this.lock;
   lock.lock();
   try {
       Object[] elements = getArray();
       E oldValue = get(elements, index);

       if (oldValue != element) {
           int len = elements.length;
           Object[] newElements = Arrays.copyOf(elements, len);
           newElements[index] = element;
           setArray(newElements);
       } else {
           // Not quite a no-op; ensures volatile write semantics
           setArray(elements);
       }
       return oldValue;
   } finally {
       lock.unlock();
   }
}

小结

  1. Vector: 无论读写,全部加上了同步锁,导致多线程访问or修改时,锁的竞争,效率较低
  2. CopyOnWriteArrayList : 读不加锁,在修改时,加锁保证每次只有一个线程在修改列表;且修改的逻辑都是先拷贝一个副本出来,然后在副本上进行修改,最后在替换列表中数组的引用
  3. CopyOnWriteArraySet : 内部数组其实就是一个 CopyOnWriteArrayList, 相关方法也是直接来自 CopyOnWriteArrayList

Map

线程安全的Map则主要是 HashTable ConcurrentHashMap, 后者采用了分段锁机制来提高并发访问的性能

在便利时,操作Map的几种场景分析

  1. 在遍历时,修改Map的引用(即用一个新的map替换这个值)
    • 仍旧遍历老的Map
  2. 在遍历时,修改Map中的元素值
    • 会读取到修改后的值
  3. 在遍历时,新增or删除元素
    • HashMap 会抛异常; ConcurrentHashMap 可正常执行

1. HashTable

同 Vector 一样,通过对所有的方法添加 synchronized 关键字来确保的线程安全;缺点也很明显,效率低,具体的几个方法源码如下,不多加说明了

public synchronized int size() {
   return count;
}

public synchronized Enumeration<K> keys() {
   return this.<K>getEnumeration(KEYS);
}

 public synchronized Enumeration<V> elements() {
   return this.<V>getEnumeration(VALUES);
}

public synchronized V get(Object key) {
   Entry<?,?> tab[] = table;
   int hash = key.hashCode();
   int index = (hash & 0x7FFFFFFF) % tab.length;
   for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
       if ((e.hash == hash) && e.key.equals(key)) {
           return (V)e.value;
       }
   }
   return null;
}


public synchronized V put(K key, V value) {
   // Make sure the value is not null
   if (value == null) {
       throw new NullPointerException();
   }

   // Makes sure the key is not already in the hashtable.
   Entry<?,?> tab[] = table;
   int hash = key.hashCode();
   int index = (hash & 0x7FFFFFFF) % tab.length;
   @SuppressWarnings("unchecked")
   Entry<K,V> entry = (Entry<K,V>)tab[index];
   for(; entry != null ; entry = entry.next) {
       if ((entry.hash == hash) && entry.key.equals(key)) {
           V old = entry.value;
           entry.value = value;
           return old;
       }
   }

   addEntry(hash, key, value, index);
   return null;
}

2. ConcurrentHashMap

一个ConcurrentHashMap由多个segment组成,每一个segment都包含了一个HashEntry数组的hashtable, 每一个segment包含了对自己的hashtable的操作,比如get,put,replace等操作,这些操作发生的时候,对自己的hashtable进行锁定。由于每一个segment写操作只锁定自己的hashtable,所以可能存在多个线程同时写的情况,性能无疑好于只有一个hashtable锁定的情况

简单来讲,就是每个 segment 的操作都是加锁的;而多个 segment 的操作可以是并发的

详解可以参考: Java集合---ConcurrentHashMap原理分析

更多可以参考个人网站: 一灰的个人博客网站之Java之线程安全的容器

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

Java 日期时间处理

java.util.Date对象表示一个精确到毫秒的瞬间; 但由于Date从JDK1.0起就开始存在了,历史悠久,而且功能强大(既包含日期,也包含时间),所以他...

3322
来自专栏Janti

springboot之使用redistemplate优雅地操作redis

2.6K3
来自专栏jeremy的技术点滴

Java开发小技巧_02

4254
来自专栏算法与数据结构

数据结构 重点详解

线性数据结构 线性表-顺序表 代码实现: #include <bits/stdc++.h> #define TRUE 1 #define FALSE 0...

2766
来自专栏Phoenix的Android之旅

Java面试基础之ArrayList操作

ArrayList应该是Java开发中经常见到的数据结构了。 曾经在一个面试中遇到这么个问题,

962
来自专栏决胜机器学习

PHP数据结构(一)——顺序结构线性表

PHP数据结构(一)——顺序结构线性表 (原创内容,转载请注明来源,谢谢) 线性表的要求:存在唯一的“第一个”元素与“最后一个”元素,每个元素最多一个前驱和一个...

5289
来自专栏ACM小冰成长之路

HDU-1512-Monkey King

ACM模版 描述 ? 题解 典型的左偏树! 问题的核心是当两个猴子帮派中的大佬斗争之后,这两个大佬要强壮值减半并且两个帮派进行合并。那么涉及到的操作有优先队列的...

2006
来自专栏小白鼠

Java面试题事务隔离级别JVM调优equals和hashCodesynchronized与LockMapSetListThreadLocal死锁多线程最佳实践扩容缓存消息队列应用拆分高可用

如果只重写了equals方法而没有重写hashCode方法的话,则会违反约定的第二条:相等的对象必须具有相等的散列码(hashCode)

1932
来自专栏程序生活

Leetcode-Easy 101. Symmetric Tree

101. Symmetric Tree 描述: 判断一个颗二叉树是否左右对称 ? 思路: 将二叉树的左右节点对放在的队列里,然后出队,判断节...

3457
来自专栏尾尾部落

[剑指offer] 最小的K个数

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。

2862

扫码关注云+社区

领取腾讯云代金券