Java多线程系列--“JUC集合”06之 ConcurrentSkipListSet

时间:2021-11-10 01:33:31

概要

本章对Java.util.concurrent包中的ConcurrentSkipListSet类进行详细的介绍。内容包括:
ConcurrentSkipListSet介绍ConcurrentSkipListSet原理和数据结构
ConcurrentSkipListSet函数列表
ConcurrentSkipListSet源码(JDK1.7.0_40版本)
ConcurrentSkipListSet示例

转载请注明出处:http://www.cnblogs.com/skywang12345/p/3498634.html

ConcurrentSkipListSet介绍

ConcurrentSkipListSet是线程安全的有序的集合,适用于高并发的场景。
ConcurrentSkipListSet和TreeSet,它们虽然都是有序的集合。但是,第一,它们的线程安全机制不同,TreeSet是非线程安全的,而ConcurrentSkipListSet是线程安全的。第二,ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的,而TreeSet是通过TreeMap实现的。

ConcurrentSkipListSet原理和数据结构

ConcurrentSkipListSet的数据结构,如下图所示:

Java多线程系列--“JUC集合”06之 ConcurrentSkipListSet

说明
(01) ConcurrentSkipListSet继承于AbstractSet。因此,它本质上是一个集合。
(02) ConcurrentSkipListSet实现了NavigableSet接口。因此,ConcurrentSkipListSet是一个有序的集合。
(03) ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的。它包含一个ConcurrentNavigableMap对象m,而m对象实际上是ConcurrentNavigableMap的实现类ConcurrentSkipListMap的实例。ConcurrentSkipListMap中的元素是key-value键值对;而ConcurrentSkipListSet是集合,它只用到了ConcurrentSkipListMap中的key!

ConcurrentSkipListSet函数列表

// 构造一个新的空 set,该 set 按照元素的自然顺序对其进行排序。
ConcurrentSkipListSet()
// 构造一个包含指定 collection 中元素的新 set,这个新 set 按照元素的自然顺序对其进行排序。
ConcurrentSkipListSet(Collection<? extends E> c)
// 构造一个新的空 set,该 set 按照指定的比较器对其元素进行排序。
ConcurrentSkipListSet(Comparator<? super E> comparator)
// 构造一个新 set,该 set 所包含的元素与指定的有序 set 包含的元素相同,使用的顺序也相同。
ConcurrentSkipListSet(SortedSet<E> s) // 如果此 set 中不包含指定元素,则添加指定元素。
boolean add(E e)
// 返回此 set 中大于等于给定元素的最小元素;如果不存在这样的元素,则返回 null。
E ceiling(E e)
// 从此 set 中移除所有元素。
void clear()
// 返回此 ConcurrentSkipListSet 实例的浅表副本。
ConcurrentSkipListSet<E> clone()
// 返回对此 set 中的元素进行排序的比较器;如果此 set 使用其元素的自然顺序,则返回 null。
Comparator<? super E> comparator()
// 如果此 set 包含指定的元素,则返回 true。
boolean contains(Object o)
// 返回在此 set 的元素上以降序进行迭代的迭代器。
Iterator<E> descendingIterator()
// 返回此 set 中所包含元素的逆序视图。
NavigableSet<E> descendingSet()
// 比较指定对象与此 set 的相等性。
boolean equals(Object o)
// 返回此 set 中当前第一个(最低)元素。
E first()
// 返回此 set 中小于等于给定元素的最大元素;如果不存在这样的元素,则返回 null。
E floor(E e)
// 返回此 set 的部分视图,其元素严格小于 toElement。
NavigableSet<E> headSet(E toElement)
// 返回此 set 的部分视图,其元素小于(或等于,如果 inclusive 为 true)toElement。
NavigableSet<E> headSet(E toElement, boolean inclusive)
// 返回此 set 中严格大于给定元素的最小元素;如果不存在这样的元素,则返回 null。
E higher(E e)
// 如果此 set 不包含任何元素,则返回 true。
boolean isEmpty()
// 返回在此 set 的元素上以升序进行迭代的迭代器。
Iterator<E> iterator()
// 返回此 set 中当前最后一个(最高)元素。
E last()
// 返回此 set 中严格小于给定元素的最大元素;如果不存在这样的元素,则返回 null。
E lower(E e)
// 获取并移除第一个(最低)元素;如果此 set 为空,则返回 null。
E pollFirst()
// 获取并移除最后一个(最高)元素;如果此 set 为空,则返回 null。
E pollLast()
// 如果此 set 中存在指定的元素,则将其移除。
boolean remove(Object o)
// 从此 set 中移除包含在指定 collection 中的所有元素。
boolean removeAll(Collection<?> c)
// 返回此 set 中的元素数目。
int size()
// 返回此 set 的部分视图,其元素范围从 fromElement 到 toElement。
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
// 返回此 set 的部分视图,其元素从 fromElement(包括)到 toElement(不包括)。
NavigableSet<E> subSet(E fromElement, E toElement)
// 返回此 set 的部分视图,其元素大于等于 fromElement。
NavigableSet<E> tailSet(E fromElement)
// 返回此 set 的部分视图,其元素大于(或等于,如果 inclusive 为 true)fromElement。
NavigableSet<E> tailSet(E fromElement, boolean inclusive)

ConcurrentSkipListSet源码(JDK1.7.0_40版本)

ConcurrentSkipListSet.java的完整源码如下:

 /*
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/ /*
*
*
*
*
*
* Written by Doug Lea with assistance from members of JCP JSR-166
* Expert Group and released to the public domain, as explained at
* http://creativecommons.org/publicdomain/zero/1.0/
*/ package java.util.concurrent;
import java.util.*;
import sun.misc.Unsafe; /**
* A scalable concurrent {@link NavigableSet} implementation based on
* a {@link ConcurrentSkipListMap}. The elements of the set are kept
* sorted according to their {@linkplain Comparable natural ordering},
* or by a {@link Comparator} provided at set creation time, depending
* on which constructor is used.
*
* <p>This implementation provides expected average <i>log(n)</i> time
* cost for the <tt>contains</tt>, <tt>add</tt>, and <tt>remove</tt>
* operations and their variants. Insertion, removal, and access
* operations safely execute concurrently by multiple threads.
* Iterators are <i>weakly consistent</i>, returning elements
* reflecting the state of the set at some point at or since the
* creation of the iterator. They do <em>not</em> throw {@link
* ConcurrentModificationException}, and may proceed concurrently with
* other operations. Ascending ordered views and their iterators are
* faster than descending ones.
*
* <p>Beware that, unlike in most collections, the <tt>size</tt>
* method is <em>not</em> a constant-time operation. Because of the
* asynchronous nature of these sets, determining the current number
* of elements requires a traversal of the elements, and so may report
* inaccurate results if this collection is modified during traversal.
* Additionally, the bulk operations <tt>addAll</tt>,
* <tt>removeAll</tt>, <tt>retainAll</tt>, <tt>containsAll</tt>,
* <tt>equals</tt>, and <tt>toArray</tt> are <em>not</em> guaranteed
* to be performed atomically. For example, an iterator operating
* concurrently with an <tt>addAll</tt> operation might view only some
* of the added elements.
*
* <p>This class and its iterators implement all of the
* <em>optional</em> methods of the {@link Set} and {@link Iterator}
* interfaces. Like most other concurrent collection implementations,
* this class does not permit the use of <tt>null</tt> elements,
* because <tt>null</tt> arguments and return values cannot be reliably
* distinguished from the absence of elements.
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @author Doug Lea
* @param <E> the type of elements maintained by this set
* @since 1.6
*/
public class ConcurrentSkipListSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2479143111061671589L; /**
* The underlying map. Uses Boolean.TRUE as value for each
* element. This field is declared final for the sake of thread
* safety, which entails some ugliness in clone()
*/
private final ConcurrentNavigableMap<E,Object> m; /**
* Constructs a new, empty set that orders its elements according to
* their {@linkplain Comparable natural ordering}.
*/
public ConcurrentSkipListSet() {
m = new ConcurrentSkipListMap<E,Object>();
} /**
* Constructs a new, empty set that orders its elements according to
* the specified comparator.
*
* @param comparator the comparator that will be used to order this set.
* If <tt>null</tt>, the {@linkplain Comparable natural
* ordering} of the elements will be used.
*/
public ConcurrentSkipListSet(Comparator<? super E> comparator) {
m = new ConcurrentSkipListMap<E,Object>(comparator);
} /**
* Constructs a new set containing the elements in the specified
* collection, that orders its elements according to their
* {@linkplain Comparable natural ordering}.
*
* @param c The elements that will comprise the new set
* @throws ClassCastException if the elements in <tt>c</tt> are
* not {@link Comparable}, or are not mutually comparable
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
public ConcurrentSkipListSet(Collection<? extends E> c) {
m = new ConcurrentSkipListMap<E,Object>();
addAll(c);
} /**
* Constructs a new set containing the same elements and using the
* same ordering as the specified sorted set.
*
* @param s sorted set whose elements will comprise the new set
* @throws NullPointerException if the specified sorted set or any
* of its elements are null
*/
public ConcurrentSkipListSet(SortedSet<E> s) {
m = new ConcurrentSkipListMap<E,Object>(s.comparator());
addAll(s);
} /**
* For use by submaps
*/
ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
this.m = m;
} /**
* Returns a shallow copy of this <tt>ConcurrentSkipListSet</tt>
* instance. (The elements themselves are not cloned.)
*
* @return a shallow copy of this set
*/
public ConcurrentSkipListSet<E> clone() {
ConcurrentSkipListSet<E> clone = null;
try {
clone = (ConcurrentSkipListSet<E>) super.clone();
clone.setMap(new ConcurrentSkipListMap(m));
} catch (CloneNotSupportedException e) {
throw new InternalError();
} return clone;
} /* ---------------- Set operations -------------- */ /**
* Returns the number of elements in this set. If this set
* contains more than <tt>Integer.MAX_VALUE</tt> elements, it
* returns <tt>Integer.MAX_VALUE</tt>.
*
* <p>Beware that, unlike in most collections, this method is
* <em>NOT</em> a constant-time operation. Because of the
* asynchronous nature of these sets, determining the current
* number of elements requires traversing them all to count them.
* Additionally, it is possible for the size to change during
* execution of this method, in which case the returned result
* will be inaccurate. Thus, this method is typically not very
* useful in concurrent applications.
*
* @return the number of elements in this set
*/
public int size() {
return m.size();
} /**
* Returns <tt>true</tt> if this set contains no elements.
* @return <tt>true</tt> if this set contains no elements
*/
public boolean isEmpty() {
return m.isEmpty();
} /**
* Returns <tt>true</tt> if this set contains the specified element.
* More formally, returns <tt>true</tt> if and only if this set
* contains an element <tt>e</tt> such that <tt>o.equals(e)</tt>.
*
* @param o object to be checked for containment in this set
* @return <tt>true</tt> if this set contains the specified element
* @throws ClassCastException if the specified element cannot be
* compared with the elements currently in this set
* @throws NullPointerException if the specified element is null
*/
public boolean contains(Object o) {
return m.containsKey(o);
} /**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element <tt>e</tt> to this set if
* the set contains no element <tt>e2</tt> such that <tt>e.equals(e2)</tt>.
* If this set already contains the element, the call leaves the set
* unchanged and returns <tt>false</tt>.
*
* @param e element to be added to this set
* @return <tt>true</tt> if this set did not already contain the
* specified element
* @throws ClassCastException if <tt>e</tt> cannot be compared
* with the elements currently in this set
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
return m.putIfAbsent(e, Boolean.TRUE) == null;
} /**
* Removes the specified element from this set if it is present.
* More formally, removes an element <tt>e</tt> such that
* <tt>o.equals(e)</tt>, if this set contains such an element.
* Returns <tt>true</tt> if this set contained the element (or
* equivalently, if this set changed as a result of the call).
* (This set will not contain the element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return <tt>true</tt> if this set contained the specified element
* @throws ClassCastException if <tt>o</tt> cannot be compared
* with the elements currently in this set
* @throws NullPointerException if the specified element is null
*/
public boolean remove(Object o) {
return m.remove(o, Boolean.TRUE);
} /**
* Removes all of the elements from this set.
*/
public void clear() {
m.clear();
} /**
* Returns an iterator over the elements in this set in ascending order.
*
* @return an iterator over the elements in this set in ascending order
*/
public Iterator<E> iterator() {
return m.navigableKeySet().iterator();
} /**
* Returns an iterator over the elements in this set in descending order.
*
* @return an iterator over the elements in this set in descending order
*/
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
} /* ---------------- AbstractSet Overrides -------------- */ /**
* Compares the specified object with this set for equality. Returns
* <tt>true</tt> if the specified object is also a set, the two sets
* have the same size, and every member of the specified set is
* contained in this set (or equivalently, every member of this set is
* contained in the specified set). This definition ensures that the
* equals method works properly across different implementations of the
* set interface.
*
* @param o the object to be compared for equality with this set
* @return <tt>true</tt> if the specified object is equal to this set
*/
public boolean equals(Object o) {
// Override AbstractSet version to avoid calling size()
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection<?> c = (Collection<?>) o;
try {
return containsAll(c) && c.containsAll(this);
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
} /**
* Removes from this set all of its elements that are contained in
* the specified collection. If the specified collection is also
* a set, this operation effectively modifies this set so that its
* value is the <i>asymmetric set difference</i> of the two sets.
*
* @param c collection containing elements to be removed from this set
* @return <tt>true</tt> if this set changed as a result of the call
* @throws ClassCastException if the types of one or more elements in this
* set are incompatible with the specified collection
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
public boolean removeAll(Collection<?> c) {
// Override AbstractSet version to avoid unnecessary call to size()
boolean modified = false;
for (Iterator<?> i = c.iterator(); i.hasNext(); )
if (remove(i.next()))
modified = true;
return modified;
} /* ---------------- Relational operations -------------- */ /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if the specified element is null
*/
public E lower(E e) {
return m.lowerKey(e);
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if the specified element is null
*/
public E floor(E e) {
return m.floorKey(e);
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if the specified element is null
*/
public E ceiling(E e) {
return m.ceilingKey(e);
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if the specified element is null
*/
public E higher(E e) {
return m.higherKey(e);
} public E pollFirst() {
Map.Entry<E,Object> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
} public E pollLast() {
Map.Entry<E,Object> e = m.pollLastEntry();
return (e == null) ? null : e.getKey();
} /* ---------------- SortedSet operations -------------- */ public Comparator<? super E> comparator() {
return m.comparator();
} /**
* @throws NoSuchElementException {@inheritDoc}
*/
public E first() {
return m.firstKey();
} /**
* @throws NoSuchElementException {@inheritDoc}
*/
public E last() {
return m.lastKey();
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if {@code fromElement} or
* {@code toElement} is null
* @throws IllegalArgumentException {@inheritDoc}
*/
public NavigableSet<E> subSet(E fromElement,
boolean fromInclusive,
E toElement,
boolean toInclusive) {
return new ConcurrentSkipListSet<E>
(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if {@code toElement} is null
* @throws IllegalArgumentException {@inheritDoc}
*/
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if {@code fromElement} is null
* @throws IllegalArgumentException {@inheritDoc}
*/
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if {@code fromElement} or
* {@code toElement} is null
* @throws IllegalArgumentException {@inheritDoc}
*/
public NavigableSet<E> subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if {@code toElement} is null
* @throws IllegalArgumentException {@inheritDoc}
*/
public NavigableSet<E> headSet(E toElement) {
return headSet(toElement, false);
} /**
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if {@code fromElement} is null
* @throws IllegalArgumentException {@inheritDoc}
*/
public NavigableSet<E> tailSet(E fromElement) {
return tailSet(fromElement, true);
} /**
* Returns a reverse order view of the elements contained in this set.
* The descending set is backed by this set, so changes to the set are
* reflected in the descending set, and vice-versa.
*
* <p>The returned set has an ordering equivalent to
* <tt>{@link Collections#reverseOrder(Comparator) Collections.reverseOrder}(comparator())</tt>.
* The expression {@code s.descendingSet().descendingSet()} returns a
* view of {@code s} essentially equivalent to {@code s}.
*
* @return a reverse order view of this set
*/
public NavigableSet<E> descendingSet() {
return new ConcurrentSkipListSet(m.descendingMap());
} // Support for resetting map in clone
private void setMap(ConcurrentNavigableMap<E,Object> map) {
UNSAFE.putObjectVolatile(this, mapOffset, map);
} private static final sun.misc.Unsafe UNSAFE;
private static final long mapOffset;
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
Class k = ConcurrentSkipListSet.class;
mapOffset = UNSAFE.objectFieldOffset
(k.getDeclaredField("m"));
} catch (Exception e) {
throw new Error(e);
}
}
}

ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的,它的接口基本上都是通过调用ConcurrentSkipListMap接口来实现的。这里就不再对它的源码进行分析了。

ConcurrentSkipListSet示例

 import java.util.*;
import java.util.concurrent.*; /*
* ConcurrentSkipListSet是“线程安全”的集合,而TreeSet是非线程安全的。
*
* 下面是“多个线程同时操作并且遍历集合set”的示例
* (01) 当set是ConcurrentSkipListSet对象时,程序能正常运行。
* (02) 当set是TreeSet对象时,程序会产生ConcurrentModificationException异常。
*
* @author skywang
*/
public class ConcurrentSkipListSetDemo1 { // TODO: set是TreeSet对象时,程序会出错。
//private static Set<String> set = new TreeSet<String>();
private static Set<String> set = new ConcurrentSkipListSet<String>();
public static void main(String[] args) { // 同时启动两个线程对set进行操作!
new MyThread("a").start();
new MyThread("b").start();
} private static void printAll() {
String value = null;
Iterator iter = set.iterator();
while(iter.hasNext()) {
value = (String)iter.next();
System.out.print(value+", ");
}
System.out.println();
} private static class MyThread extends Thread {
MyThread(String name) {
super(name);
}
@Override
public void run() {
int i = 0;
while (i++ < 10) {
// “线程名” + "序号"
String val = Thread.currentThread().getName() + (i%6);
set.add(val);
// 通过“Iterator”遍历set。
printAll();
}
}
}
}

(某一次)运行结果

a1, b1,
a1, a1, a2, b1,
b1, a1, a2, a3, b1, a1, a2, a3, a1, a4, b1, b2,
a2, a1, a2, a3, a4, a5, b1, b2,
a3, a0, a4, a5, a1, b1, a2, b2,
a3, a0, a4, a1, a5, a2, b1, a3, b2, a4, b3,
a5, a0, b1, a1, b2, a2, b3,
a3, a0, a4, a1, a5, a2, b1, a3, b2, a4, b3, a5, b4,
b1, a0, b2, a1, b3, a2, b4,
a3, a0, a4, a1, a5, a2, b1, a3, b2, a4, b3, a5, b4, b1, b5,
b2, a0, a1, a2, a3, a4, a5, b3, b1, b4, b2, b5,
b3, a0, b4, a1, b5,
a2, a0, a3, a1, a4, a2, a5, a3, b0, a4, b1, a5, b2, b0, b3, b1, b4, b2, b5, b3,
b4, a0, b5,
a1, a2, a3, a4, a5, b0, b1, b2, b3, b4, b5,
a0, a1, a2, a3, a4, a5, b0, b1, b2, b3, b4, b5,
a0, a1, a2, a3, a4, a5, b0, b1, b2, b3, b4, b5,
a0, a1, a2, a3, a4, a5, b0, b1, b2, b3, b4, b5,

结果说明
示例程序中,启动两个线程(线程a和线程b)分别对ConcurrentSkipListSet进行操作。以线程a而言,它会先获取“线程名”+“序号”,然后将该字符串添加到ConcurrentSkipListSet集合中;接着,遍历并输出集合中的全部元素。 线程b的操作和线程a一样,只不过线程b的名字和线程a的名字不同。
当set是ConcurrentSkipListSet对象时,程序能正常运行。如果将set改为TreeSet时,程序会产生ConcurrentModificationException异常。


更多内容

1. Java多线程系列--“JUC集合”01之 框架

2. Java多线程系列目录(共xx篇)