The Collections utility class
We can try using this utility class when we need to perform special operations on the collection, but the collection itself does not provide such operations for us
This article focuses on the common approaches to Collections, For example, Collections.sort(), collections.shuffle (), collections.reverse (), collections.addall (), collections.copy (), collections.binar YSearch (), the Collections. SynchronizedXXX ()
And for the Collections. The copy () way to interpretation of the Source, to avoid IndexOutOfBoundsException: Source does not fit in dest
Sort sort
@Test
public void sort(a){
// Creating an array list
ArrayList<Integer> numbers = new ArrayList<>();
// Add elements
numbers.add(4);
numbers.add(2);
numbers.add(3);
System.out.println("Unsorted ArrayList: " + numbers);
// Using the sort() method
Collections.sort(numbers);
System.out.println("Sorted ArrayList: " + numbers);
}
// Output the result
Unsorted ArrayList: [4.2.3]
Sorted ArrayList: [2.3.4]
Copy the codeBreak up the shuffle
Shuffle is a very common operation in big data components, but it is rare in other contexts. You can think of it as shuffling, sort of random
@Test
public void shuffle(a) {
// Creating an array list
ArrayList<Integer> numbers = new ArrayList<>();
// Add elements
numbers.add(1);
numbers.add(2);
numbers.add(3);
System.out.println("Sorted ArrayList: " + numbers);
// Using the shuffle() method
Collections.shuffle(numbers);
System.out.println("ArrayList using shuffle: " + numbers);
}
// Output result (first time)
Sorted ArrayList: [1.2.3]
ArrayList using shuffle: [3.2.1]
// Output the result (a second, possibly multiple runs)
Sorted ArrayList: [1.2.3]
ArrayList using shuffle: [1.3.2]
Copy the codeYou can see that shuffle is changing all the time
Inversion of reverse
@Test
public void reverse(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
// Using reverse()
Collections.reverse(numbers);
System.out.println("Reversed ArrayList1: " + numbers);
}
// Output the result
ArrayList1: [1.2]
Reversed ArrayList1: [2.1]
Copy the codeFill in the fill
@Test
public void fill(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
// Using fill()
Collections.fill(numbers, 0);
System.out.println("ArrayList1 using fill(): " + numbers);
}
// Output the result
ArrayList1: [1.2]
ArrayList1 using fill(a): [0, 0]
Copy the codeAdd the collection addAll
Add an element from one list to another. This is a pretty straightforward method, but it works pretty well and doesn’t cause any problems. Unlike the copy method, which throws exceptions, we didn’t use the collections.addall method directly. We use the addAll method of the collection directly, because the second argument takes a mutable argument rather than a collection, but most of the time we use the real collection more often
But let’s take a look at the source code for the collections.addall method
public static <T> boolean addAll(Collection<? super T> c, T... elements) {
boolean result = false;
for (T element : elements)
result |= c.add(element);
return result;
}
Copy the codeIt’s just iterating and adding
@Test
public void addAll(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
ArrayList<Integer> newNumbers = new ArrayList<>();
// Using addAll
Collections.
newNumbers.addAll(numbers);
System.out.println("ArrayList2 using addAll(): " + newNumbers);
}
// Output the result
ArrayList1: [1.2]
ArrayList2 using addAll(a): [1, 2]
Copy the codeNotice, of course, that addAll() adds elements to the end of the collection
@Test
public void addAll(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
ArrayList<Integer> newNumbers = new ArrayList<>();
newNumbers.add(4);
newNumbers.addAll(numbers);
System.out.println("ArrayList2 using addAll(): " + newNumbers);
}
// the following output [1,2] is added to the end of 4
ArrayList1: [1.2]
ArrayList2 using addAll(a): [4, 1, 2]
Copy the codeSo when the target set (the set that calls addAll) is an empty set, we can think of it as a copy operation
Copy the copy
@Test
public void copy(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
ArrayList<Integer> newNumbers = new ArrayList<>();
// Using copy()
Collections.copy(newNumbers, numbers);
System.out.println("ArrayList2 using copy(): " + newNumbers);
}
Copy the codeRun the result as follows, error, since error, then look at the source code, solve it
ArrayList1: [1, 2] java.lang.IndexOutOfBoundsException: Source does not fit in dest at java.util.Collections.copy(Collections.java:558) at Datastructure. Java data type. The hash. CollectionsUtil. Copy the at (CollectionsUtil. Java: 104) sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)Copy the codeHere is the source code for the copy method. My habit is to look at the comments of the code before I look at the code
/** * Copies all of the elements from one list into another. After the operation, The index of each copied element in the destination list * will be identical to its index in the source list To another list, * The destination list must be at least as long as The source list. If it is longer, The remaining elements in the destination list are memorized * The target list must be at least as long as the source list. If longer, the rest of the target list is unaffected * This method runs in linear time. * This method runs in linear time *@param<T> The class of the objects in the lists generic *@paramDest The destination list@param src The source list.
* @throws IndexOutOfBoundsException if the destination list is too small to contain the entire source List.
* @throws UnsupportedOperationException if the destination list's list-iterator does not support the set operation.
*/
public static <T> void copy(List<? super T> dest, List<? extends T> src) {
int srcSize = src.size();
if (srcSize > dest.size())
// The destination list must be at least as long as The source.
throw new IndexOutOfBoundsException("Source does not fit in dest");
if (srcSize < COPY_THRESHOLD ||
(src instanceof RandomAccess && dest instanceof RandomAccess)) {
for (int i=0; i<srcSize; i++)
dest.set(i, src.get(i));
} else {
ListIterator<? super T> di=dest.listIterator();
ListIterator<? extends T> si=src.listIterator();
for (int i=0; i<srcSize; i++) { di.next(); di.set(si.next()); }}}Copy the codeThat is to say we got, if the size of the source, if is greater than the size of dest will throw IndexOutOfBoundsException abnormal conclusion, then you begin to modify your code, a meal, went into this
@Test
public void copy(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
// The size of the new list is the size of the source list +1
ArrayList<Integer> newNumbers = new ArrayList<>(numbers.size()+1);
// Using copy()
Collections.copy(newNumbers, numbers);
System.out.println("ArrayList2 using copy(): " + newNumbers);
}
Copy the codeDo you think you are correct, in fact, it is wrong, you run, or the error in the paper
ArrayList1: [1, 2] java.lang.IndexOutOfBoundsException: Source does not fit in dest at java.util.Collections.copy(Collections.java:558) at Datastructure. Java data type. The hash. CollectionsUtil. Copy the at (CollectionsUtil. Java: 104) sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)Copy the codeDo you know what the problem is? Haha, let’s add a line of code and you’ll know
@Test
public void copy(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
ArrayList<Integer> newNumbers = new ArrayList<>(numbers.size()+1);
System.out.println(newNumbers.size()+"\t"+numbers.size());
}
// The result is as follows
ArrayList1: [1.2]
0 2
Copy the codeBut the main problem is with the constructor of an ArrayList
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the codeInitialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity initialCapacity You can think of one as storage capacity, one as current actual storage, two different things
So, arrays.aslist () is a good choice if we just make the list’s actual storage elements look like copy
@Test
public void copy(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
List<Integer> newNumbers = Arrays.asList(new Integer[numbers.size()]);
System.out.println(newNumbers.size()+"\t"+numbers.size());
Collections.copy(newNumbers, numbers);
System.out.println("ArrayList2 using copy(): " + newNumbers);
}
// Run the result
ArrayList1: [1.2]
2 2
ArrayList2 using copy(a): [1, 2]
Copy the codeSee the utility classes Arrays and ArrayList for more details
If target is an empty collection, copy and addAll have the same effect
@Test
public void copy(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
List<Integer> newNumbers = new ArrayList<>();
newNumbers.addAll(numbers);
System.out.println(newNumbers.size()+"\t"+numbers.size());
System.out.println("ArrayList2 using copy(): " + newNumbers);
}
Copy the codeConclusion: When the target set is empty, copy and addAll() can be substituted for each other. AddAll is recommended because it is less error-prone, but when target is not empty, copy is added to the target header and overwrites the existing element. AddAll is added to the end and does not overwrite existing elements
Exchange swap
There’s no such thing as swapping two elements in a set at a given location. You can just get and then put
@Test
public void swap(a) {
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
// Using swap()
Collections.swap(numbers, 0.1);
System.out.println("ArrayList1 using swap(): " + numbers);
}
// Output the result
ArrayList1: [1.2]
ArrayList1 using swap(a): [2, 1)Copy the codeBinarySearch binarySearch
Of course, there’s a premise here, which is that the elements in the array are already sorted, and that’s the premise of binary search, because binary search is implemented in a way that requires the elements to be sorted from the bottom up
@Test
public void binarySearch(a) {
// Creating an ArrayList
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
// Using binarySearch()
int pos = Collections.binarySearch(numbers, 3);
System.out.println("The position of 3 is " + pos);
}
Copy the codeOf course we can take a quick look at the implementation here, and of course, as is my custom, take a look at the comments and the method description first
/** * Searches the specified list for the specified object using the binary search algorithm. * Searches the specified list for the specified value * The list must be sorted into ascending order according to the {@linkplain Comparable natural ordering} of its elements (as by the {@link#sort(List)} method) prior to making this call. * If it is not sorted, the results are undefined. * If the list is not sorted, * If the list contains multiple elements equal to the specified object, There is no guarantee which one will be found. This method runs in log(n) time for a "random access" list (which provides near-constant-time positional system) Access). * For collections that can be accessed by subscript (implementing RandomAccess), the time complexity of this method is log(n) * If the specified list does not implement the {@linkRandomAccess} interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons. * If the RandomAccess interface is not implemented, the iiterator-based binary lookup is used, which consists of two processes, first O(n) traversal complexity, then O(log n) search complexity *@param <T> the class of the objects in the list
* @param list the list to be searched.
* @param key the key to be searched for.
* @returnthe index of the search key, if it is contained in the list; Returns the subscript * otherwise if included, <tt>(-(<i>insertion point</i>) - 1)</tt>. The * <i>insertion point</i> is defined as the point at which the * key would be inserted into the list: the index of the first * element greater than the key, or <tt>list.size()</tt> if all * elements in the list are less than the specified key. Note * that this guarantees that the return value will be > = 0 if * and only if the key is found. *@throws ClassCastException if the list contains elements that are not <i>mutually comparable</i> (for example, strings and
* integers), or the search key is not mutually comparable
* with the elements of the list.
*/
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
// BINARYSEARCH_THRESHOLD=5000
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
private static <T> int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
int low = 0;
int high = list.size()-1;
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = list.get(mid);
int cmp = midVal.compareTo(key);
// This determines the size of the element
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
Copy the codeFrequency statistics
@Test
public void frequency(a) {
// Creating an ArrayList
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
int count = Collections.frequency(numbers, 2);
System.out.println("Count of 2: " + count);
}
// Output the result
ArrayList1: [1.2.3.2]
Count of 2: 2
Copy the codeIntersection disjoint
Determine whether two sets have an intersection
@Test
public void disjoint(a) {
// Creating an ArrayList
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(2);
System.out.println("ArrayList1: " + numbers);
ArrayList<Integer> newNumbers = new ArrayList<>();
newNumbers.add(5);
newNumbers.add(6);
System.out.println("ArrayList2: " + newNumbers);
boolean value = Collections.disjoint(numbers, newNumbers);
System.out.println("Two lists are disjoint: " + value);
}
// Output the result
ArrayList1: [1.2.3.2]
ArrayList2: [5.6]
Two lists are disjoint: true
Copy the codeMaximum minimum value
@Test
public void extremeValues(a) {
// Creating an ArrayList
ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
// Using min()
int min = Collections.min(numbers);
System.out.println("Minimum Element: " + min);
// Using max()
int max = Collections.max(numbers);
System.out.println("Maximum Element: " + max);
}
// Output the result
Minimum Element: 1
Maximum Element: 3
Copy the codeThread-safe operation
In other words, the following operation can turn a collection that is not thread-safe into a thread-safe collection, and I’m going to give you an example here, and there are lots of examples of maps on the web, and I’m going to give you an example of a List
Example 1 Insert operation
// Defines a thread class
class SynchroProblem implements Runnable {
private List<Integer> numList;
//Constructor
public SynchroProblem(List<Integer> numList) {
this.numList = numList;
}
@Override
public void run(a) {
System.out.println("in run method");
for (int i = 0; i < 10; i++) {
numList.add(i);
try {
// introducing some delay
Thread.sleep(50);
} catch(InterruptedException e) { e.printStackTrace(); }}}}@Test
public void test(a) throws Exception {
List<Integer> numList = new ArrayList<Integer>();
// Creating three threads
Thread t1 = new Thread(new SynchroProblem(numList));
Thread t2 = new Thread(new SynchroProblem(numList));
Thread t3 = new Thread(new SynchroProblem(numList));
t1.start();
t2.start();
t3.start();
try {
t1.join();
t2.join();
t3.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
// Here our expected output is 30
System.out.println("Size of list is " + numList.size());
// This is 0-9
for(Integer i : numList){
System.out.println("num - "+ i); }}Copy the codeNow let’s take a look at the results. The size is not 30, and 6 only prints twice. When you run multiple times, you’ll notice that the results of each run may be different
in run method in run method in run method Size of list is 29 num - 0 num - 0 num - 0 num - 1 num - 1 num - 1 num - 2 num - 2 num - 2 num - 3 num - 3 num - 3 num - 4 num - 4 num - 4 num - 5 num - 5 num - 6 num - 6 num - 6 num - 7 num - 7 num - 7 num - 8 num - 8 num - 8 num - 9 num - 9 num - 9Copy the codeHow do you fix it, using the method that we introduced today
@Test
public void test(a) throws Exception {
// You can also use Vector
//List<Integer> numList = new Vector<Integer>();
List<Integer> numList = Collections.synchronizedList(new ArrayList<Integer>());
// Creating three threads
Thread t1 = new Thread(new SynchroProblem(numList));
Thread t2 = new Thread(new SynchroProblem(numList));
Thread t3 = new Thread(new SynchroProblem(numList));
t1.start();
t2.start();
t3.start();
try {
t1.join();
t2.join();
t3.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Size of list is " + numList.size());
for(Integer i : numList){
System.out.println("num - "+ i); }}// Output the result
Size of list is 30
Copy the code@Test
public void safe(a) {
Random random = new Random();
class Mt extends Thread {
int xAnInt;
List<Integer> list;
public Mt(int i, List<Integer> list) {
xAnInt = i;
this.list = list;
}
@Override
public void run(a) {
try {
TimeUnit.MILLISECONDS.sleep(random.nextInt(1000));
} catch (InterruptedException e) {
e.printStackTrace();
}
list.add(xAnInt);
}
}
ArrayList<Integer> list = new ArrayList();
for (int i = 0; i < 1000; i++) {
new Mt(i, list).start();
}
System.out.println(list.size());
}
// Output results (each run is different, indicating that a data error has occurred)
29
Copy the codeNow let’s make a few changes to this code, and it should work
@Test
public void safe(a) {
Random random = new Random();
class Mt extends Thread {
int xAnInt;
List<Integer> list;
public Mt(int i, ArrayList<Integer> list) {
xAnInt = i;
this.list = list;
}
@Override
public void run(a) {
try {
TimeUnit.MILLISECONDS.sleep(random.nextInt(1000));
} catch (InterruptedException e) {
e.printStackTrace();
}
list.add(xAnInt);
}
}
ArrayList<Integer> list = new ArrayList();
// Create a new thread-safe list
List<Integer> asfeList = Collections.synchronizedList(list);
for (int i = 0; i < 1000; i++) {
new Mt(i, list).start();
}
System.out.println(list.size());
}
Copy the codeExample Three traversal operation
Because we know that in the collection traversal process, if the collection is modified, traversal will Fail, which is caused by the fail-fast, but in multi-threaded environment, it will cause other thread data problems, so we want to be fai-safe, which means that during the traversal process, the collection is modified, can also continue traversal. Instead of interrupting the traversal and throwing an exception
@Test
public void traverseSafe(a) {
List<Integer> numList = new ArrayList<>();
numList.add(1);
numList.add(2);
numList.add(3);
numList.forEach(ele -> {
if (ele==2) {new Thread(()->numList.remove(1)).start();
}
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(ele);
});
}
Copy the codeAs a result, we can see that the run failed
1
2
java.util.ConcurrentModificationException
at java.util.ArrayList.forEach(ArrayList.java:1260) at datastructure. Java data type. A hash. CollectionsUtil. TraverseSafe (CollectionsUtil. Java:260)
Copy the codeNext, let’s take a look at the solution we introduced today
@Test
public void traverseSafe(a) {
// Of course you can still use Vector here
List<Integer> numList = Collections.synchronizedList(new ArrayList<Integer>());
numList.add(1);
numList.add(2);
numList.add(3);
numList.forEach(ele -> {
if (ele==2) {new Thread(()->numList.remove(1)).start();
}
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(ele);
});
}
// Run the result
1
2
3
Copy the code