死磕 java集合之CopyOnWriteArraySet原始碼分析——內含巧妙設計
問題
（1）CopyOnWriteArraySet是用Map實現的嗎？
（2）CopyOnWriteArraySet是有序的嗎？
（3）CopyOnWriteArraySet是併發安全的嗎？
（4）CopyOnWriteArraySet以何種方式保證元素不重複？
（5）如何比較兩個Set中的元素是否完全一致？
簡介
CopyOnWriteArraySet底層是使用CopyOnWriteArrayList儲存元素的，所以它並不是使用Map來儲存元素的。
但是，我們知道CopyOnWriteArrayList底層其實是一個數組，它是允許元素重複的，那麼用它來實現CopyOnWriteArraySet怎麼保證元素不重複呢？
CopyOnWriteArrayList回顧請點選【死磕 java集合之CopyOnWriteArrayList原始碼分析 】。
原始碼分析
Set類的原始碼一般都比較短，所以我們直接貼原始碼上來一行一行分析吧。
Set之類的簡單原始碼適合泛讀，主要是掌握一些不常見的用法，做到心裡有說，坐個車三五分鐘可能就看完了。
像ConcurrentHashMap、ConcurrentSkipListMap之類的比較長的我們還是傾向分析主要的方法，適合精讀，主要是掌握實現原理以及一些不錯的思想，可能需要一兩個小時才能看完一整篇文章。
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) {
// 如果兩者是同一個物件，返回true
if (o == this)
return true;
// 如果o不是Set物件，返回false
if (!(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;
}
}
// 如果不在當前集合中，返回false
return 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);
}
}
可以看到，在新增元素時呼叫了CopyOnWriteArrayList的addIfAbsent()方法來保證元素不重複。
還記得這個方法的實現原理嗎？點選直達【死磕 java集合之CopyOnWriteArrayList原始碼分析 】。
總結
（1）CopyOnWriteArraySet是用CopyOnWriteArrayList實現的；
（2）CopyOnWriteArraySet是有序的，因為底層其實是陣列，陣列是不是有序的？！
（3）CopyOnWriteArraySet是併發安全的，而且實現了讀寫分離；
（4）CopyOnWriteArraySet通過呼叫CopyOnWriteArrayList的addIfAbsent()方法來保證元素不重複；
彩蛋
（1）如何比較兩個Set中的元素是否完全相等？
假設有兩個Set，一個是A，一個是B。
最簡單的方式就是判斷是否A中的元素都在B中，B中的元素是否都在A中，也就是兩次兩層迴圈。
其實，並不需要。
因為Set中的元素並不重複，所以只要先比較兩個Set的元素個數是否相等，再作一次兩層迴圈就可以了，需要仔細體味。程式碼如下：
public class CopyOnWriteArraySetTest {
public static void main(String[] args) {
Set<Integer> set1 = new CopyOnWriteArraySet<>();
set1.add(1);
set1.add(5);
set1.add(2);
set1.add(7);
//set1.add(3);
set1.add(4);
Set<Integer> set2 = new HashSet<>();
set2.add(1);
set2.add(5);
set2.add(2);
set2.add(7);
set2.add(3);
System.out.println(eq(set1, set2));
System.out.println(eq(set2, set1));
}
private static <T> boolean eq(Set<T> set1, Set<T> set2) {
if (set1.size() != set2.size()) {
return false;
}
for (T t : set1) {
// contains相當於一層for迴圈
if (!set2.contains(t)) {
return false;
}
}
return true;
}
}
（2）那麼，如何比較兩個List中的元素是否完全相等呢？
我們知道，List中元素是可以重複的，那是不是要做兩次兩層迴圈呢？
其實，也不需要做兩次兩層遍歷，一次也可以搞定，設定一個標記陣列，標記某個位置的元素是否找到過，請仔細體味。程式碼如下：
public class ListEqTest {
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<>();
list1.add(1);
list1.add(3);
list1.add(6);
list1.add(3);
list1.add(8);
list1.add(5);
List<Integer> list2 = new ArrayList<>();
list2.add(3);
list2.add(1);
list2.add(3);
list2.add(8);
list2.add(5);
list2.add(6);
System.out.println(eq(list1, list2));
System.out.println(eq(list2, list1));
}
private static <T> boolean eq(List<T> list1, List<T> list2) {
if (list1.size() != list2.size()) {
return false;
}
// 標記某個元素是否找到過，防止重複
boolean matched[] = new boolean[list2.size()];
outer: for (T t : list1) {
for (int i = 0; i < list2.size(); i++) {
// i這個位置沒找到過才比較大小
if (!matched[i] && list2.get(i).equals(t)) {
matched[i] = true;
continue outer;
}
}
return false;
}
return true;
}
}
這種設計是不是很巧妙？^^
歡迎關注我的公眾號“彤哥讀原始碼”，檢視更多原始碼系列文章, 與彤哥一起暢遊原始碼的海洋。
