The problem
(1) Is CopyOnWriteArraySet implemented with Map?
(2) Is CopyOnWriteArraySet ordered?
(3) Is CopyOnWriteArraySet concurrency safe?
(4) In what way does CopyOnWriteArraySet guarantee that elements are not duplicated?
(5) How to compare whether the elements in two sets are exactly the same?
Introduction to the
CopyOnWriteArraySet uses CopyOnWriteArrayList to store elements, so it doesn’t use a Map to store elements.
However, we know that CopyOnWriteArrayList is actually an array, and it allows elements to be repeated, so how can we implement CopyOnWriteArraySet without repeating elements?
CopyOnWriteArrayList review please click on “Deadpan Java collection of CopyOnWriteArrayList source analysis”.
Source code analysis
The source code of the Set class is generally short, so let’s paste the source code up line by line analysis.
Set and other simple source code for extensive reading, mainly to master some uncommon usage, do have said in the heart, take a car three or five minutes may be finished.
Like ConcurrentHashMap, ConcurrentSkipListMap and other relatively long we still tend to analyze the main method, suitable for intensive reading, mainly to grasp the implementation principle and some good ideas, may need one or two hours to read the whole article.
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
implements java.io.Serializable {
private static final long serialVersionUID = 5457747651344034263L;
// Use CopyOnWriteArrayList internally to store elements
private final CopyOnWriteArrayList<E> al;
// constructor
public CopyOnWriteArraySet(a) {
al = new CopyOnWriteArrayList<E>();
}
// Initialize the elements in collection C to CopyOnWriteArraySet
public CopyOnWriteArraySet(Collection<? extends E> c) {
if (c.getClass() == CopyOnWriteArraySet.class) {
// If c is CopyOnWriteArraySet, there are no duplicate elements.
// Call the constructor of CopyOnWriteArrayList directly to initialize
@SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
(CopyOnWriteArraySet<E>)c;
al = new CopyOnWriteArrayList<E>(cc.al);
}
else {
// If c is not CopyOnWriteArraySet, there are duplicate elements
// Call CopyOnWriteArrayList's addAllAbsent() method to initialize
// It excludes duplicate elements
al = newCopyOnWriteArrayList<E>(); al.addAllAbsent(c); }}// Get the number of elements
public int size(a) {
return al.size();
}
// Check if the set is empty
public boolean isEmpty(a) {
return al.isEmpty();
}
// Check whether an element is included
public boolean contains(Object o) {
return al.contains(o);
}
// Set to array
public Object[] toArray() {
return al.toArray();
}
// Set to array, this is possible bug, see ArrayList for details
public <T> T[] toArray(T[] a) {
return al.toArray(a);
}
// Clear all elements
public void clear(a) {
al.clear();
}
// Delete elements
public boolean remove(Object o) {
return al.remove(o);
}
// Add elements
// Here is the addIfAbsent() method calling CopyOnWriteArrayList
// It checks if the element does not exist before adding it
// Remember this method? At that time there was analysis, I suggest to take CopyOnWriteArrayList out and have a look
public boolean add(E e) {
return al.addIfAbsent(e);
}
// Whether to include all elements in c
public boolean containsAll(Collection
c) {
return al.containsAll(c);
}
/ / and set
public boolean addAll(Collection<? extends E> c) {
return al.addAllAbsent(c) > 0;
}
// Single direction difference set
public boolean removeAll(Collection
c) {
return al.removeAll(c);
}
/ / intersection
public boolean retainAll(Collection
c) {
return al.retainAll(c);
}
/ / the iterator
public Iterator<E> iterator(a) {
return al.iterator();
}
/ / the equals () method
public boolean equals(Object o) {
// If both are the same object, return true
if (o == this)
return true;
// If o is not Set, return false
if(! (oinstanceof Set))
return false; Set<? > set = (Set<? >)(o); Iterator<? > it = set.iterator();// A snapshot of the 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 Set are not duplicated, so there is no need to use the matched[] array to record whether or not it appears
// If the number of elements in two sets is not equal, it is definitely not equal. Should this be checked as the first element
boolean[] matched = new boolean[len];
int k = 0;
// start with o
outer: while (it.hasNext()) {
// If k>len, there are more elements in o
if (++k > len)
return false;
/ / value
Object x = it.next();
// Iterate to check if it is in the current collection
for (int i = 0; i < len; ++i) {
if(! matched[i] && eq(x, elements[i])) { matched[i] =true;
continueouter; }}If not in the current collection, return false
return false;
}
return k == len;
}
// Remove elements that meet the filter criteria
public boolean removeIf(Predicate<? super E> filter) {
return al.removeIf(filter);
}
// Iterate over the elements
public void forEach(Consumer<? super E> action) {
al.forEach(action);
}
// Split iterator
public Spliterator<E> spliterator(a) {
return Spliterators.spliterator
(al.getArray(), Spliterator.IMMUTABLE | Spliterator.DISTINCT);
}
// Compare whether two elements are equal
private static boolean eq(Object o1, Object o2) {
return (o1 == null)? o2 ==null: o1.equals(o2); }}Copy the codeAs you can see, the addIfAbsent() method of CopyOnWriteArrayList is called when the element is added to ensure that the element is not duplicated.
Remember how this works? Click direct [deadknock Java collection CopyOnWriteArrayList source code analysis].
conclusion
(1) CopyOnWriteArraySet is implemented with CopyOnWriteArrayList;
(2) CopyOnWriteArraySet is ordered, because the underlying layer is actually an array, array is not ordered? !
(3) CopyOnWriteArraySet is concurrency safe, and achieve read and write separation;
(4) CopyOnWriteArraySet ensures that elements are not duplicated by calling addIfAbsent() of CopyOnWriteArrayList;
eggs
(1) How to compare whether elements in two sets are exactly equal?
Let’s say I have two sets, one is A and one is B.
And the easiest way to do that is to determine if everything in A is in B, and everything in B is in A, which is A two-layer loop twice.
Well, not necessarily.
Since the elements in a Set are not duplicated, it is only necessary to compare the number of elements in the two sets to see if they are the same. 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 contains a layer for loop
if(! set2.contains(t)) {return false; }}return true; }}Copy the code(2) How do you compare elements in two lists that are exactly equal?
We know that the elements in the List can be repeated, so do we do a two-level loop twice?
In fact, you don’t need to do two layers of traversal, you can also do it once, set an array of tags, to mark the location of the element found, please feel carefully. 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;
}
// Marks whether an element was found to prevent duplication
boolean matched[] = new boolean[list2.size()];
outer: for (T t : list1) {
for (int i = 0; i < list2.size(); i++) {
// select * from 'I'
if(! matched[i] && list2.get(i).equals(t)) { matched[i] =true;
continueouter; }}return false;
}
return true; }}Copy the codeIsn’t that clever? ^ ^
Welcome to pay attention to my public number “Tong Elder brother read source code”, view more source code series articles, with Tong elder brother tour the ocean of source code.
