problem
(1) Is the CopyOnWriteArraySet implemented with Map?
(2) Is the CopyOnWriteArray Set orderly?
(3) Is the CopyOnWriteArraySet concurrently secure?
(4) How does CopyOnWriteArraySet ensure that elements are not duplicated?
(5) How to compare whether the elements in the two Set s are identical?
brief introduction
CopyOnWriteArraySet uses CopyOnWriteArrayList to store elements, so it does not use Map to store elements.
However, we know that the bottom of CopyOnWriteArrayList is an array, which allows elements to repeat. How can we use it to implement CopyOnWriteArraySet to ensure that elements do not repeat?
Copy On Write Array List Review click[ Source Code Analysis of CopyOnWriteArrayList of Dead java Sets].
Source code analysis
Set class source code is generally relatively short, so let's paste the source code line by line analysis.
Set and other simple source code suitable for extensive reading, mainly to grasp some unusual usage, to say in my heart, a car ride in three or five minutes may be finished.
Longer ones like Concurrent HashMap and Concurrent SkipListMap still tend to analyze the main methods, which are suitable for intensive reading, mainly to grasp the implementation principles and some good ideas. It may take an hour or two to finish the whole article.
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
implements java.io.Serializable {
private static final long serialVersionUID = 5457747651344034263L;
// Internally store elements using CopyOnWriteArrayList
private final CopyOnWriteArrayList<E> al;
// Construction method
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
// Initialize elements in set c into CopyOnWriteArraySet
public CopyOnWriteArraySet(Collection<? extends E> c) {
if (c.getClass() == CopyOnWriteArraySet.class) {
// If c is a CopyOnWriteArraySet type, there is no duplicate element.
// Initialization of the construction method of calling CopyOnWriteArrayList directly
@SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
(CopyOnWriteArraySet<E>)c;
al = new CopyOnWriteArrayList<E>(cc.al);
}
else {
// If c is not CopyOnWriteArraySet type, there are duplicate elements
// Initialization by calling the addAllAbsent() method of CopyOnWriteArrayList
// It excludes repetitive elements.
al = new CopyOnWriteArrayList<E>();
al.addAllAbsent(c);
}
}
// Get the number of elements
public int size() {
return al.size();
}
// Check whether the collection is empty
public boolean isEmpty() {
return al.isEmpty();
}
// Check whether an element is included
public boolean contains(Object o) {
return al.contains(o);
}
// Set Rotation Array
public Object[] toArray() {
return al.toArray();
}
// Collection rotation arrays, where there may be bug s, are analyzed in ArrayList
public <T> T[] toArray(T[] a) {
return al.toArray(a);
}
// Empty all elements
public void clear() {
al.clear();
}
// Delete elements
public boolean remove(Object o) {
return al.remove(o);
}
// Additive elements
// Here is the addIfAbsent() method that calls CopyOnWriteArrayList
// It detects elements that do not exist before adding them.
// Do you remember this method? It was suggested that CopyOnWriteArrayList be taken out and looked at again.
public boolean add(E e) {
return al.addIfAbsent(e);
}
// Does it contain all the elements in c?
public boolean containsAll(Collection<?> c) {
return al.containsAll(c);
}
// Union
public boolean addAll(Collection<? extends E> c) {
return al.addAllAbsent(c) > 0;
}
// Unidirectional difference set
public boolean removeAll(Collection<?> c) {
return al.removeAll(c);
}
// intersection
public boolean retainAll(Collection<?> c) {
return al.retainAll(c);
}
// iterator
public Iterator<E> iterator() {
return al.iterator();
}
// equals() method
public boolean equals(Object o) {
// If both are the same object, return true
if (o == this)
return true;
// If o is not a Set object, return false
if (!(o instanceof Set))
return false;
Set<?> set = (Set<?>)(o);
Iterator<?> it = set.iterator();
// A snapshot of an array of collection elements
Object[] elements = al.getArray();
int len = elements.length;
// I don't think the design here is very good.
// First of all, the elements in the Set are not duplicated, so you don't need to use a matched [] array to record whether or not they have ever appeared.
// Secondly, if the number of elements in two sets is not equal, it must not be equal. Should this be checked as the first element?
boolean[] matched = new boolean[len];
int k = 0;
// Traverse from the set o
outer: while (it.hasNext()) {
// If k > len, there are more elements in o.
if (++k > len)
return false;
// Value
Object x = it.next();
// Traversal checks whether or not in the current collection
for (int i = 0; i < len; ++i) {
if (!matched[i] && eq(x, elements[i])) {
matched[i] = true;
continue outer;
}
}
// If not in the current collection, return false
return false;
}
return k == len;
}
// Remove elements that satisfy filtering conditions
public boolean removeIf(Predicate<? super E> filter) {
return al.removeIf(filter);
}
// Traversal element
public void forEach(Consumer<? super E> action) {
al.forEach(action);
}
// Partitioned Iterator
public Spliterator<E> spliterator() {
return Spliterators.spliterator
(al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);
}
// Compare the equality of two elements
private static boolean eq(Object o1, Object o2) {
return (o1 == null) ? o2 == null : o1.equals(o2);
}
}As you can see, the addIfAbsent() method of CopyOnWriteArrayList is called to ensure that the elements are not duplicated when adding elements.
Do you remember how this method works? Click through[ Source Code Analysis of CopyOnWriteArrayList of Dead java Sets].
summary
(1) CopyOnWriteArraySet is implemented with CopyOnWriteArrayList;
(2) CopyOnWriteArraySet is ordered, because the bottom layer is actually an array, is the array ordered?!?
(3) CopyOnWriteArraySet is concurrently secure and achieves read-write separation.
(4) CopyOnWriteArraySet ensures that elements are not duplicated by calling addIfAbsent() of CopyOnWriteArrayList;
Egg
(1) How to compare whether the elements in the two Set s are completely equal?
Suppose there are two sets, one is A and the other is B.
The simplest way is to determine whether the elements in A are all in B, and whether the elements in B are all in A, that is, two-level loops.
In fact, it is not necessary.
Because the elements in the Set are not repeated, it is necessary to compare the number of elements in the two Sets first, and then make a two-tier cycle, which requires careful consideration. The code is as follows:
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 is equivalent to a layer for loop
if (!set2.contains(t)) {
return false;
}
}
return true;
}
}(2) So, how do you compare the two lists to see if the elements are exactly equal?
We know that elements in a List are repeatable. Is that a two-tier loop?
In fact, there is no need to do two-tier traversal, one can also be done, set up an array of tags, mark whether the elements of a location have been found, please carefully taste. The code is as follows:
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;
}
// Mark whether an element has been found to prevent duplication
boolean matched[] = new boolean[list2.size()];
outer: for (T t : list1) {
for (int i = 0; i < list2.size(); i++) {
// i This position was not found before the size was compared.
if (!matched[i] && list2.get(i).equals(t)) {
matched[i] = true;
continue outer;
}
}
return false;
}
return true;
}
}Is the design clever? ^ ^
Welcome to pay attention to my public number "Tong Ge Reads Source Code". Check out more articles about source code series and enjoy the sea of source code with Tong Ge.
