Java中的多线程之线程安全的集合

引言:如果使用多线程并发修改一个数据结构,例如散列表:会很容易破坏这个数据结构,例如:一个线程可能要开始向表中插入一个新元素;假定在调整散列表各个桶之间的连接关系过程中,被剥夺了控制权,如果另外一个线程也开始遍历同一个链表,可能使用无效的来凝结并造成混乱;会抛出异常陷入死循环;
可以通过锁来保护共享的数据结构,但是选择线程安全的实现作为替代可能更容易些;阻塞队列就是线程安全的集合;
1:高效的映像,集合和队列
java.util.concurrent包下面提供了映像,有序集,队列的高效实现:
ConcurrenHashMap;ConcurrentSkipListMap;ConcurrentSkipListSet;ConcurrentLinkedQuene;
确定这样的集合大小通常是需要遍历的;集合返回弱一致性的迭代器。意味着迭代器不一定能够反映出他们呢被构造之后的所有修改;
<1>ConcurrentHashMap是Java5中新增加的一个线程安全的Map集合,可以用来替代HashTable。对于ConcurrentHashMap是如何提高其效率的,可能大多人只是知道它使用了多个锁代替HashTable中的单个锁,也就是锁分离技术(Lock Stripping)。实际上,ConcurrentHashMap对提高并发方面的优化,还有一些其它的技巧在里面(比如你是否知道在get操作的时候,它是否也使用了锁来保护?)。
ConcurrentHashMap有三个主要方法:
分别为get,put,remove;
对于hash表,java都是采用拉链法处理冲突的;而hashMap和ConcurrentHashMap也都一样;实现了同步的HashTable也一样,但是hashTable所有的线程都使用一个锁,当n个线程都在要进行get操作时,这n个线程需要串行等待;
而ConcurrentHashMap将这一种数据结构进行了一定的改进;将整个hash表根据他们的并发级别分成了若干个segment;默认情况下内部按照级别为16来进行创建;对于每一个segment默认的容量也都是16;当然并发级别和 默认容量也可自己去设定;
<2>:ConcurrentSkipListMap
A、ConcurrentSkipListMap 的key是有序的。
B、ConcurrentSkipListMap 支持更高的并发。ConcurrentSkipListMap 的存取时间是log(N),和线程数几乎无关。也就是说在数据量一定的情况下,并发的线程越多,ConcurrentSkipListMap越能体现出他的优势。
详见:http://www.educity.cn/java/498061.html
<3>:ConcurrentSkipListSet;
ConcurrentSkipListSet是线程安全的有序的集合,适用于高并发的场景。ConcurrentSkipListSet和[TreeSet]
它们虽然都是有序的集合。但是,
第一,它们的线程安全机制不同,TreeSet是非线程安全的,而ConcurrentSkipListSet是线程安全的。第二,ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的,而TreeSet是通过TreeMap实现的。
<4>:ConcurrentLinkedQueue是Queue的一个安全实现.Queue中元素按FIFO原则进行排序.采用CAS操作,来保证元素的一致性。LinkedBlockingQueue是一个线程安全的阻塞队列,它实现了BlockingQueue接口,BlockingQueue接口继承自java.util.Queue接口,并在这个接口的基础上增加了take和put方法,这两个方法正是队列操作的阻塞版本。
ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部,当我们获取一个元素时,它会返回队列头部的元素。它采用了“wait-free”算法来实现,该算法在Michael & Scott算法上进行了一些修改, Michael & Scott算法的详细信息可以参见参考资料一。
2:写数组的拷贝:
<1>:CopyOnWriteArrayList:
CopyOnWriteArrayList是ArrayList 的一个线程安全的变体,其中所有可变操作(add、set等等)都是通过对底层数组进行一次新的复制来实现的。
<2>:CopyOnWriteArraySet:
CopyOnWriteArraySet基于CopyOnWriteArrayList实现,其唯一的不同是在add时调用的是CopyOnWriteArrayList的addIfAbsent方法.adIfAbsent方法同样采用锁保护,并创建一个新的大小+1的Object数组。遍历当前Object数组,如Object数组中已有了当前元素,则直接返回,如果没有则放入Object数组的尾部,并返回。
从以上分析可见,CopyOnWriteArraySet在add时每次都要进行数组的遍历,因此其性能会低于CopyOnWriteArrayList.
3:旧的线程安全的集合:
Vector和HashTable实现了线程安全的数组和散列表;在java1.2版本中他们就已经不再使用了,取而代之是ArrayList和HashMap这些集合类不是线程安全但是他们可以通过集合库中提供的同步包装器使其变成线程安全的;

你可能感兴趣的