Java 集合 (15) -- CopyOnWriteArraySet 类 ConcurrentSkipListSet 类

1. CopyOnWriteArraySet 类

1. 简介

public class CopyOnWriteArraySet<E> extends AbstractSet<E>implements java.io.Serializable {
    }

CopyOnWriteArraySet 底层是使用 CopyOnWriteArrayList 存储元素的，也就是说它并不是使用 Map 来存储元素的。

它的底层是数组，所以是有序的，并且是线程安全的，实现了读写分离；它通过调用 CopyOnWriteArrayList 的 addIfAbsent() 方法来保证元素不重复。

2. 继承体系

3. 源码

public class CopyOnWriteArraySet<E> extends AbstractSet<E>implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;// 内部使用CopyOnWriteArrayList存储元素private final CopyOnWriteArrayList<E> al;// 构造方法public CopyOnWriteArraySet() {
    al = new CopyOnWriteArrayList<E>();}// 将集合c中的元素初始化到CopyOnWriteArraySet中public CopyOnWriteArraySet(Collection<? extends E> c) {
    if (c.getClass() == CopyOnWriteArraySet.class) {
    // 如果c是CopyOnWriteArraySet类型，说明没有重复元素，// 直接调用CopyOnWriteArrayList的构造方法初始化@SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =(CopyOnWriteArraySet<E>)c;al = new CopyOnWriteArrayList<E>(cc.al);}else {
    // 如果c不是CopyOnWriteArraySet类型，说明有重复元素// 调用CopyOnWriteArrayList的addAllAbsent()方法初始化// 它会把重复元素排除掉al = new CopyOnWriteArrayList<E>();al.addAllAbsent(c);}}// 获取元素个数public int size() {
    return al.size();}// 检查集合是否为空public boolean isEmpty() {
    return al.isEmpty();}// 检查是否包含某个元素public boolean contains(Object o) {
    return al.contains(o);}// 集合转数组public Object[] toArray() {
    return al.toArray();}// 集合转数组，这里是可能有bug的，详情见ArrayList中分析public <T> T[] toArray(T[] a) {
    return al.toArray(a);}// 清空所有元素public void clear() {
    al.clear();}// 删除元素public boolean remove(Object o) {
    return al.remove(o);}// 添加元素// 这里是调用CopyOnWriteArrayList的addIfAbsent()方法// 它会检测元素不存在的时候才添加// 还记得这个方法吗？当时有分析过的，建议把CopyOnWriteArrayList拿出来再看看public boolean add(E e) {
    return al.addIfAbsent(e);}// 是否包含c中的所有元素public boolean containsAll(Collection<?> c) {
    return al.containsAll(c);}// 并集public boolean addAll(Collection<? extends E> c) {
    return al.addAllAbsent(c) > 0;}// 单方向差集public boolean removeAll(Collection<?> c) {
    return al.removeAll(c);}// 交集public boolean retainAll(Collection<?> c) {
    return al.retainAll(c);}// 迭代器public Iterator<E> iterator() {
    return al.iterator();}// equals()方法public boolean equals(Object o) {
    // 如果两者是同一个对象，返回trueif (o == this)return true;// 如果o不是Set对象，返回falseif (!(o instanceof Set))return false;Set<?> set = (Set<?>)(o);Iterator<?> it = set.iterator();// 集合元素数组的快照Object[] elements = al.getArray();int len = elements.length;// 我觉得这里的设计不太好// 首先，Set中的元素本来就是不重复的，所以不需要再用个matched[]数组记录有没有出现过// 其次，两个集合的元素个数如果不相等，那肯定不相等了，这个是不是应该作为第一要素先检查boolean[] matched = new boolean[len];int k = 0;// 从o这个集合开始遍历outer: while (it.hasNext()) {
    // 如果k>len了，说明o中元素多了if (++k > len)return false;// 取值Object x = it.next();// 遍历检查是否在当前集合中for (int i = 0; i < len; ++i) {
    if (!matched[i] && eq(x, elements[i])) {
    matched[i] = true;continue outer;}}// 如果不在当前集合中，返回falsereturn false;}return k == len;}// 移除满足过滤条件的元素public boolean removeIf(Predicate<? super E> filter) {
    return al.removeIf(filter);}// 遍历元素public void forEach(Consumer<? super E> action) {
    al.forEach(action);}// 分割的迭代器public Spliterator<E> spliterator() {
    return Spliterators.spliterator(al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);}// 比较两个元素是否相等private static boolean eq(Object o1, Object o2) {
    return (o1 == null) ? o2 == null : o1.equals(o2);}
}

2. ConcurrentSkipListSet 类

1. 简介

public class ConcurrentSkipListSet<E>extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable {
    }

ConcurrentSkipListSet 底层是通过 ConcurrentNavigableMap 来实现的，它是一个有序的，基于元素的自然排序或者通过比较器确定的顺序，并且线程安全；ConcurrentNavigableMap 的实现类是 ConcurrentSkipListMap，ConcurrentSkipListMap 的 key 存储着 ConcurrentSkipListSet 元素。

2. 继承体系

3. 源码

// 实现了NavigableSet接口，并没有所谓的ConcurrentNavigableSet接口
public class ConcurrentSkipListSet<E>extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = -2479143111061671589L;// 存储使用的mapprivate final ConcurrentNavigableMap<E,Object> m;// 初始化public ConcurrentSkipListSet() {
    m = new ConcurrentSkipListMap<E,Object>();}// 传入比较器public ConcurrentSkipListSet(Comparator<? super E> comparator) {
    m = new ConcurrentSkipListMap<E,Object>(comparator);}// 使用ConcurrentSkipListMap初始化map// 并将集合c中所有元素放入到map中public ConcurrentSkipListSet(Collection<? extends E> c) {
    m = new ConcurrentSkipListMap<E,Object>();addAll(c);}// 使用ConcurrentSkipListMap初始化map// 并将有序Set中所有元素放入到map中public ConcurrentSkipListSet(SortedSet<E> s) {
    m = new ConcurrentSkipListMap<E,Object>(s.comparator());addAll(s);}// ConcurrentSkipListSet类内部返回子set时使用的ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) {
    this.m = m;}// 克隆方法public ConcurrentSkipListSet<E> clone() {
    try {
    @SuppressWarnings("unchecked")ConcurrentSkipListSet<E> clone =(ConcurrentSkipListSet<E>) super.clone();clone.setMap(new ConcurrentSkipListMap<E,Object>(m));return clone;} catch (CloneNotSupportedException e) {
    throw new InternalError();}}/* ---------------- Set operations -------------- */// 返回元素个数public int size() {
    return m.size();}// 检查是否为空public boolean isEmpty() {
    return m.isEmpty();}// 检查是否包含某个元素public boolean contains(Object o) {
    return m.containsKey(o);}// 添加一个元素// 调用map的putIfAbsent()方法public boolean add(E e) {
    return m.putIfAbsent(e, Boolean.TRUE) == null;}// 移除一个元素public boolean remove(Object o) {
    return m.remove(o, Boolean.TRUE);}// 清空所有元素public void clear() {
    m.clear();}// 迭代器public Iterator<E> iterator() {
    return m.navigableKeySet().iterator();}// 降序迭代器public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();}/* ---------------- AbstractSet Overrides -------------- */// 比较相等方法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 {
    // 这里是通过两次两层for循环来比较// 这里是有很大优化空间的，参考上篇文章CopyOnWriteArraySet中的彩蛋return containsAll(c) && c.containsAll(this);} catch (ClassCastException unused) {
    return false;} catch (NullPointerException unused) {
    return false;}}// 移除集合c中所有元素public boolean removeAll(Collection<?> c) {
    // Override AbstractSet version to avoid unnecessary call to size()boolean modified = false;for (Object e : c)if (remove(e))modified = true;return modified;}/* ---------------- Relational operations -------------- */// 小于e的最大元素public E lower(E e) {
    return m.lowerKey(e);}// 小于等于e的最大元素public E floor(E e) {
    return m.floorKey(e);}// 大于等于e的最小元素public E ceiling(E e) {
    return m.ceilingKey(e);}// 大于e的最小元素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();}// 最小的元素public E first() {
    return m.firstKey();}// 最大的元素public E last() {
    return m.lastKey();}// 取两个元素之间的子setpublic NavigableSet<E> subSet(E fromElement,boolean fromInclusive,E toElement,boolean toInclusive) {
    return new ConcurrentSkipListSet<E>(m.subMap(fromElement, fromInclusive,toElement,   toInclusive));}// 取头子setpublic NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive));}// 取尾子setpublic NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive));}// 取子set，包含from，不包含topublic NavigableSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElement, true, toElement, false);}// 取头子set，不包含topublic NavigableSet<E> headSet(E toElement) {
    return headSet(toElement, false);}// 取尾子set，包含frompublic NavigableSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);}// 降序setpublic NavigableSet<E> descendingSet() {
    return new ConcurrentSkipListSet<E>(m.descendingMap());}// 可分割的迭代器@SuppressWarnings("unchecked")public Spliterator<E> spliterator() {
    if (m instanceof ConcurrentSkipListMap)return ((ConcurrentSkipListMap<E,?>)m).keySpliterator();elsereturn (Spliterator<E>)((ConcurrentSkipListMap.SubMap<E,?>)m).keyIterator();}// 原子更新map，给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);}}
}