看图学源码之 CopyOnWriteArraySet源码分析

基本介绍

使用内部CopyOnWriteArrayList进行所有操作的Set

特点

1. 它最适合以下应用程序：集合大小通常较小、只读操作的数量远远多于可变操作，并且您需要在遍历期间防止线程之间的干扰。
2. 它是线程安全的。
3. 突变操作（ add 、 set 、 remove等）的成本很高，因为它们通常需要复制整个底层数组。
4. 迭代器不支持变异remove操作。
5. 通过迭代器进行遍历速度很快，并且不会遇到其他线程的干扰。迭代器依赖于构造迭代器时数组的不变快照。

源码分析

public class CopyOnWriteArraySet<E> extends AbstractSet<E>implements java.io.Serializable {private static final long serialVersionUID = 5457747651344034263L;private final CopyOnWriteArrayList<E> al;/*** Creates an empty set.*/public CopyOnWriteArraySet() {al = new CopyOnWriteArrayList<E>();}//创建一个包含指定集合的所有元素的集合public CopyOnWriteArraySet(Collection<? extends E> c) {if (c.getClass() == CopyOnWriteArraySet.class) {@SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =(CopyOnWriteArraySet<E>)c;al = new CopyOnWriteArrayList<E>(cc.al);}else {al = new CopyOnWriteArrayList<E>();al.addAllAbsent(c);}}//返回该集合中的元素数量public int size() {return al.size();}// 判断集合是不是为空public boolean isEmpty() {return al.isEmpty();}//返回一个包含该集合中所有元素的数组。如果此集合对其迭代器返回其元素的顺序做出任何保证，则此方法必须以相同的顺序返回元素。返回的数组将是“安全的”，因为该集合不维护对它的引用。 （换句话说，即使该集合由数组支持，此方法也必须分配一个新数组）。因此，调用者可以自由修改返回的数组。public Object[] toArray() {return al.toArray();}//返回一个包含该集合中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。如果该集合适合指定的数组，则将其返回其中。否则，将使用指定数组的运行时类型和该集合的大小分配一个新数组。//如果该集合适合指定的数组，并且有空闲空间（即该数组的元素多于该集合），则数组中紧随该集合末尾的元素将设置为null 。 （仅当调用者知道该集合不包含任何空元素时，这对于确定该集合的长度很有用。）//如果此集合对其迭代器返回其元素的顺序做出任何保证，则此方法必须以相同的顺序返回元素。public <T> T[] toArray(T[] a) {return al.toArray(a);}//仅保留此集中包含在指定集合中的元素。换句话说，从该集合中删除所有未包含在指定集合中的元素。如果指定的集合也是一个集合，则此操作会有效地修改该集合，使其值是两个集合的交集。public boolean retainAll(Collection<?> c) {return al.retainAll(c);}//按添加这些元素的顺序返回此集合中包含的元素的迭代器。//返回的迭代器提供了构造迭代器时集合状态的快照。遍历迭代器时不需要同步。迭代器不支持remove方法。public Iterator<E> iterator() {return al.iterator();}// 比较指定对象与该集合是否相等。如果指定的对象与此对象是同一对象，或者它也是Set ，并且指定集合上的迭代器返回的元素与此集合上的迭代器返回的元素相同，则返回true 。更正式地说，如果两个迭代器返回相同数量的元素，则认为它们返回相同的元素，并且对于迭代器在指定集合上返回的每个元素e1 ，迭代器在该集合上返回一个元素e2 ，使得(e1==null ? e2==null : e1.equals(e2)) public boolean equals(Object o) {if (o == this)return true;if (!(o instanceof Set))return false;Set<?> set = (Set<?>)(o);Iterator<?> it = set.iterator();// 使用仅适用于小集合的 O(n^2) 算法，CopyOnWriteArraySets 应该是这样的。// 使用底层阵列的单个快照Object[] elements = al.getArray();int len = elements.length;// Mark matched elements to avoid re-checkingboolean[] matched = new boolean[len];int k = 0;outer: while (it.hasNext()) {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;}}return false;}return k == len;}public void forEach(Consumer<? super E> action) {al.forEach(action);}//按照添加这些元素的顺序返回此集合中元素的Spliterator public Spliterator<E> spliterator() {// 返回该集合中元素的Spliteratorreturn Spliterators.spliterator (al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);}//试相等性，处理空值。private static boolean eq(Object o1, Object o2) {return (o1 == null) ? o2 == null : o1.equals(o2);}
}

读

contains

contains(Object o)

如果此集合包含指定元素，则返回true 。更正式地说，当且仅当该集合包含满足(onull ? enull : o.equals(e)) 的元素e时，才返回true 。

public boolean contains(Object o) {return al.contains(o);
}

containsAll(Collection<?> c)

如果此集合包含指定集合的所有元素，则返回true 。如果指定的集合也是一个集合，并且它是该集合的子集，则此方法返回true

public boolean containsAll(Collection<?> c) {return al.containsAll(c);
}

写

add

add(E e)

如果指定元素尚不存在，则将其添加到该集合中。更正式地说，如果集合不包含满足(e==null ? e2==null : e.equals(e2)) 的元素e2 ，则将指定元素e添加到此集合中。如果该集合已包含该元素，则调用将保持该集合不变并返回false

public boolean add(E e) {return al.addIfAbsent(e);
} 

addAll(Collection<? extends E> c)

将指定集合中的所有元素添加到该集合中（如果它们尚不存在）。如果指定的集合也是一个集合，则addAll操作会有效地修改此集合，使其值是两个集合的并集。如果在操作进行过程中修改了指定的集合，则该操作的行为是未定义的

public boolean addAll(Collection<? extends E> c) {return al.addAllAbsent(c) > 0;
}

remove

remove(Object o)

从此集合中删除指定元素（如果存在）。更正式地说，如果该集合包含这样的e ，则删除(o==null ? e==null : o.equals(e))的元素 e 。如果此集合包含该元素（或者等效地，如果此集合因调用而发生更改），则返回true 。 （一旦调用返回，该集合将不再包含该元素。）

public boolean remove(Object o) {return al.remove(o);
}

removeIf(Predicate<? super E> filter)

调用 CopyOnWriteArrayList 中的removeIf(filter)

public boolean removeIf(Predicate<? super E> filter) {return al.removeIf(filter);
}

removeAll(Collection<?> c)

从此集合中删除指定集合中包含的所有元素。如果指定的集合也是一个集合，则此操作有效地修改该集合，使其值为两个集合的非对称集合差。

public boolean removeAll(Collection<?> c) {return al.removeAll(c);
}

clear

clear()

删除该集合中的所有元素。该调用返回后该集合将为空。

public void clear() {al.clear();
}

总结

所有的方法都是调用 CopyOnWriteArrayList 对应的方法，所以其原理和实现可以观看上一章内容。

CopyOnWriteArraySet 和CopyOnWriteArrayList 的关系

CopyOnWriteArraySet 是 Set 接口的实现类，它内部使用了 CopyOnWriteArrayList 来存储元素，CopyOnWriteArraySet的底层数据结构是一个 CopyOnWriteArrayList 对象。 每次进行写操作时都会创建一个新的数组副本，并在副本上进行修改，而不是直接在原始数组上进行修改。这样可以保证读操作的线程安全性，因为读操作可以在不加锁的情况下进行。

CopyOnWriteArrayList 也是一个线程安全的集合类，它实现了 List 接口。它的原理和 CopyOnWriteArraySet 类似，通过"写时复制"的机制来实现线程安全。每次进行写操作时，都会创建一个新的数组副本，并在副本上进行修改，从而保证读操作的线程安全性。

因此，可以说 CopyOnWriteArraySet 是在 CopyOnWriteArrayList 的基础上实现的，它在 CopyOnWriteArrayList 的基础上提供了 Set 接口的特性，即 元素不能重复。

去重的逻辑

去重的逻辑来源于：CopyOnWriteArraySet的add 方法会调用 CopyOnWriteArrayList中的addIfAbsent 方法，在 CopyOnWriteArrayList 中的addIfAbsent 会调用 indexOf(Object o, Object[] elements, int index, int fence) 来进行判断是不是存在，不存在再调用 addIfAbsent(e, snapshot)来进行添加元素。