Blog: bugstack.cn
Precipitation, share, grow, let yourself and others can gain something! 😄
One, foreword
Algorithms are the soul of data structures!
A good algorithm with the right data structure can make the code function much more efficient. Of course, algorithm learning is not just brush problems, but also need to be implemented and applied, otherwise when it comes to writing code, it will still be for loop +ifelse.
When developing a slightly more complex business process, it is often necessary to use the corresponding data structure and algorithm logic, combined with the design pattern, so that you can write high-performance code, but also make the code has good scalability.
In previous chapters, we have introduced the basic data structures commonly used in Java, which have been included:Jump -> Face Classics ManualChapter content as below;
So, with these data structures in place, let’s take a look at the algorithms utility class provided in Java, Collections.
2. Interview questions
Thank plane, today how listless, and black eye?
A: A lot of blind spots. I’ve been trying to fill in the gaps recently, as well as the data structures in the manual.
Ask: that data structure see about it, you have considered 🤔, data structure involved in sorting, binary search?
A: Binary search is better, blah blah blah.
Q: Not bad. Did you know that this method has a corresponding utility class in Java? Is which!
A: it! ? I don’t think I’ve noticed. I haven’t!
Q: Go ahead, go home to read a book, these two days also rest.
The plane quietly went out, but the overall answer of the interview is still good, the interviewer decided to give him another chance.
The Collections utility class
Java.util. Collections, a utility class of the Java Collections framework, is used primarily for common algorithms provided by Collection; Sorting, binary search, shuffling algorithm operation.
From data structure to concrete implementation, and then to the algorithm, the overall structure is as follows.
1. The Collections. The sort order
1.1 Initializing the Collection
List<String> list = new ArrayList<String>();
list.add("Seven");
list.add("4");
list.add("8");
list.add("3");
list.add("9");
Copy the code1.2 Default Sequence [Positive order]
Collections.sort(list);
// Test result: [3, 4, 7, 8, 9]
Copy the code1.3 Comparator sorting
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
returno2.compareTo(o1); }});Copy the code- We use the
o2与o1Compare and contrast. This will give you a sort of reverse order. - At the same time,
ComparatorYou can also sort object classes by a field. - The test results are as follows;
[9.8.7.4.3]
Copy the code1.4 reverseOrder inversion
Collections.sort(list, Collections.<String>reverseOrder());
// Test result: [9, 8, 7, 4, 3]
Copy the codeCollections.<String>reverseOrder()The source section is the same as we transposed the two contrasted classes above.c2.compareTo(c1);
1.5 Source Code Description
There’s a lot of information about sorting, and it’s a little complicated. This article focuses on the Collections collection utility class, and then dives into each sorting algorithm.
Collections.sort
Sort ((E[]) elementData, 0, size, c);
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null.0.0); }}Copy the code- And this part of the sort logic includes the old version of merge sort
legacyMergeSortå’ŒTimSortSorting. - But because of the switch,
LegacyMergeSort.userRequested = false, basically walk toTimSortSorting. - It also depends on whether the number of elements is greater than or equal to
32And the choiceSegmented sortingandBinary insertion sort.This is the part where we’re going to focus on sorting
2. Collections. BinarySearch
- If you’re familiar with this picture, this is the set element 5 specified by binary lookup.
- The premise of binary search is that the set is ordered, otherwise the search process of binary algorithm cannot be satisfied.
- Find set element 5, which is divided into three parts;
- The first step,
(0 + 7) >>> 1 = 3, positioninglist.get(3) = 4, continue binary search to the right. - The second step,
(4 + 7) >>> 1 = 5, positioninglist.get(5) = 6, continue to search to the left dichotomy. - The third step,
(4 + 4) >>> 1 = 4, positioninglist.get(4) = 5, finds the element and returns the result.
- The first step,
2.1 Function Usage
@Test
public void test_binarySearch(a) {
List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
list.add("6");
list.add("Seven");
list.add("8");
int idx = Collections.binarySearch(list, "5");
System.out.println("Binary search:" + idx);
}
Copy the code- This function is the concrete implementation in the figure above, through
Collections.binarySearchLocate elements. - Test results:
Binary search: 4
2.2 Source Code Analysis
Collections.binarySearch
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
Copy the codeList instanceof RandomAccess ArrayList implements RandomAccess, but LinkedList does not. BINARYSEARCH_THRESHOLD = 5000. If the threshold is smaller than 5000, use indexedBinarySearch. So the LinkedList is actually used to store data, and when elements are located, a get loop is required to retrieve the elements, which is much more time-consuming than an ArrayList.
The Collections. IndexedBinarySearch (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);
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 codeThe above code is to locate the element by half at a time, and the time point mentioned above is list.get(mid), which we discussed when we analyzed the data structure. LinkedList inserts faster than ArrayList? Are you sure?
The Collections. IteratorBinarySearch (list, key) :
private static <T> int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
{
int low = 0;
int high = list.size()-1;
ListIterator<? extends Comparable<? super T>> i = list.listIterator();
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = get(i, mid);
int cmp = midVal.compareTo(key);
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 codeThe above code performs binary lookup using the list.listIterator for linkedLists with more than 5000 elements. It is also an optimization, but for linked list data structure, still not as fast as array data structure, binary processing speed, mainly in the time complexity of acquiring elements O(1) and O(n).
3. Collections. Shuffle
Shuffle algorithm, in fact, is to scramble the elements in the List set, generally can be used in the lottery, lottery, shuffle and other scenes.
3.1 Using Functions
Collections.shuffle(list);
Collections.shuffle(list, new Random(100));
Copy the codeIt is very simple to use, there are mainly two ways, one can directly pass in the collection, the other can also pass in a fixed random seed this way can control the shuffling scope
3.2 Source code Analysis
According to the shuffling logic, we will implement the specific core logic code, as follows;
@Test
public void test_shuffle(a) {
List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
list.add("6");
list.add("Seven");
list.add("8");
Random random = new Random();
for (int i = list.size(); i > 1; i--) {
int ri = random.nextInt(i); // Random position
int ji = i - 1; / / postpone
System.out.println("ri：" + ri + "Ji." + ji);
list.set(ji, list.set(ri, list.get(ji))); // Element substitution
}
System.out.println(list);
}
Copy the codeRunning results:
Ri:6Ji:7Ri:4Ji:6Ri:1Ji:5Ri:2Ji:4Ri:0Ji:3Ri:0Ji:2Ri:1Ji:1
[8.6.4.1.3.2.5.7]
Copy the codeThis part of the code logic is mainly to find the corresponding element from the gradually narrowing set through random number, and then replace the element with the decreasing subscript position. The overall execution process is as follows.
4. Collections.rotate Rotate algorithm
The rotation algorithm, which takes an ArrayList or Linkedlist and spins it forward or backward from a specified position. It’s a little bit like thinking of a set as a disk, where you rotate the elements you want, and the rest of the elements follow.
4.1 Function Applications
List<String> list = new ArrayList<String>();
list.add("Seven");
list.add("4");
list.add("8");
list.add("3");
list.add("9");
Collections.rotate(list, 2);
System.out.println(list);
Copy the codeHere we have set order; 7, 4, 8, 3, 9, clockwise rotation 2, the test results are as follows; Counterclockwise rotation is negative
The test results
[3.9.7.4.8]
Copy the codeFrom the test results, we can see that starting from element 7, the forward rotation is two places.
4.2 Source Code Analysis
public static void rotate(List<? > list,int distance) {
if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
rotate1(list, distance);
else
rotate2(list, distance);
}
Copy the codeThe realization of rotation algorithm is divided into two parts.
- An Arraylist or a small number of elements,
ROTATE_THRESHOLD = 100, then through the algorithmrotate1The implementation. - If the number of LinkedList elements exceeds ROTATE_THRESHOLD, an algorithm is required
rotate2The implementation.
So, what’s the difference between these two algorithms?
4.2.1 Rotation Algorithm, Rotate1
private static <T> void rotate1(List<T> list, int distance) {
int size = list.size();
if (size == 0)
return;
distance = distance % size;
if (distance < 0)
distance += size;
if (distance == 0)
return;
for (int cycleStart = 0, nMoved = 0; nMoved ! = size; cycleStart++) { T displaced = list.get(cycleStart);int i = cycleStart;
do {
i += distance;
if (i >= size)
i -= size;
displaced = list.set(i, displaced);
nMoved ++;
} while (i != cycleStart);
}
}
Copy the codeThis part of the code looks a little bit more, but the operation of the array structure is not very complicated, basically like the circle operation above, mainly including the following steps;
distance = distance % size;Gets the rotation position.- The for loop and the dowhile, in conjunction with each rotation operation, for example, the first time we replace the element in position 0 to position 2, and then in the dowhile we decide
i ! = cycleStartIf the condition is satisfied, we continue to replace the element in position 2 further down. Until a loop puts everything in the right place. - Finally, the list element is replaced by a loop, which is equivalent to a rotation of two positions starting at one position.
4.2.2 Rotation algorithm rotate2
private static void rotate2(List<? > list,int distance) {
int size = list.size();
if (size == 0)
return;
int mid = -distance % size;
if (mid < 0)
mid += size;
if (mid == 0)
return;
reverse(list.subList(0, mid));
reverse(list.subList(mid, size));
reverse(list);
}
Copy the codeThe following part of the source code is mainly for the operation of LinkedList of more than 100 elements, so the whole algorithm is more interesting, its main operations include;
- -distance % size + size, which is the location of the element we want to find after rotation
- For the first flip, move from position 0 to unchain position
- For the second time, flip the chain to the end
- Flip the third time, flip the entire list
The overall execution process, can refer to the figure below, more convenient to understand;
5. Other APIS
This part of the API content, the use and design is relatively simple, usually may not use much, but some partners have not used, when you are illiterate.
5.1 Maximum and Minimum Values
String min = Collections.min(Arrays.asList("1"."2"."3"));
String max = Collections.max(Arrays.asList("1"."2"."3"));
Copy the codeCollectionsThe toolkit can do the best value fetching.
5.2 Element Replacement
List<String> list = new ArrayList<String>();
list.add("Seven");
list.add("4");
list.add("8");
list.add("8");
Collections.replaceAll(list, "8"."9");
// Test result: [7, 4, 9, 9]
Copy the code- You can replace all of the elements in the set with new elements.
5.3 Judgment of position of continuous set
@Test
public void test_indexOfSubList(a) {
List<String> list = new ArrayList<String>();
list.add("Seven");
list.add("4");
list.add("8");
list.add("3");
list.add("9");
int idx = Collections.indexOfSubList(list, Arrays.asList("8"."3"));
System.out.println(idx);
// Test result: 2
}
Copy the codeIn the String operation, we know “74839”.indexof (“8”); To get the position of an element. In an ArrayList collection operation, you can get the positions of successive elements in the collection.
5.4 synchronized
List<String> list = Collections.synchronizedList(new ArrayList<String>());
Map<String, String> map = Collections.synchronizedMap(new HashMap<String, String>());
Copy the code- This one is familiar, and even used often, but it may be overlooked that these thread-safe methods come from
CollectionsCollection toolkit.
Four,
- This chapter will basically
java.util.CollectionsToolkit common methods are introduced, as well as some algorithms. This way, when the algorithm logic is needed later, it can be used directly without having to re-build the wheel. - Study data structure, algorithm, design mode, these three aspects of knowledge, the focus can be implemented in daily business development, otherwise empty, false, virtual, only suitable for bragging, will not bring actual value to the project research and development.
- Understand is really understand, don’t let yourself too uncomfortable. Rote memorization who also can’t stand, spent a lot of time, knowledge has not been absorbed, learning a knowledge point is best from the root of learning, do not be impetuous.
Five, series recommendation
- DDD domain driver design implementation scheme
- Relearning Java Design Patterns (22 Real Life Development Scenarios)
- Interview manual (get the fastest car, get the most expensive offer)
- Bytecode Programming (Non-invasive Full-link Monitoring Practice)