This series of articles have been supplemented and improved, and has been revised and organized into a book, The Logic of Java Programming (written by Ma Junchang), published by Huazhang Branch of China Machine Press, which was on the market in January 2018 and received high praise from readers. Major online shops and bookstores are available for sale, welcome to buy: JINGdong self-run link

An array is a basic data structure that stores multiple elements of the same type. The elements in the array are stored consecutively in memory. You can directly locate any element by array subscript, which is very efficient compared to other containers we will discuss in the following chapters.

Array manipulation is a common basic operation in computer programs. The Java class Arrays contains some static methods for array manipulation. This section mainly discusses these methods. By learning the usage of Arrays, we can avoid reinventing wheels and use them directly. By learning its realization principle, we can realize the functions that they do not have when we need them.

usage

toString

The toString method of Arrays can easily output the string form of an array for viewing. It has nine overloaded methods, including eight basic array types and one object type array. Here are two of them:

public static String toString(int[] a)
public static String toString(Object[] a) 
Copy the code

Such as:

int[] arr = {9.8.3.4};
System.out.println(Arrays.toString(arr));

String[] strArr = {"hello"."world"};
System.out.println(Arrays.toString(strArr));
Copy the code

The output is:

[9, 8, 3, 4]
[hello, world]
Copy the code

If you don’t use arrays.tostring, just print the array itself:

int[] arr = {9.8.3.4};
System.out.println(arr);

String[] strArr = {"hello"."world"};
System.out.println(strArr);
Copy the code

The output will look like this:

[I@1224b90
[Ljava.lang.String;@728edb84
Copy the code

The output is hard to read, and the number after the @ is the address of memory.

Array sort – Basic type

Sorting is a very common operation. Just like toString, Arrays has sort methods for every primitive type (except Boolean), such as:

public static void sort(int[] a)
public static void sort(double[] a)
Copy the code

Sort in ascending order from smallest to largest.

int[] arr = {4.9.3.6.10};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
Copy the code

The output is:

[3, 4, 6, 9, 10]
Copy the code

The array is sorted.

Sort can also accept two arguments to sort elements in a specified range, such as:

public static void sort(int[] a, int fromIndex, int toIndex)
Copy the code

Elements that include the fromIndex position, but not the toIndex position, such as:

int[] arr = {4.9.3.6.10};
Arrays.sort(arr,0.3);
System.out.println(Arrays.toString(arr));
Copy the code

The output is:

[3, 4, 9, 6, 10]
Copy the code

Sort only the first three elements.

Array sort – Object type

In addition to primitive types, sort can accept object types directly, but objects need to implement the Comparable interface.

public static void sort(Object[] a)
public static void sort(Object[] a, int fromIndex, int toIndex) 
Copy the code

Let’s look at an example of a String array:

String[] arr = {"hello"."world"."Break"."abc"};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
Copy the code

The output is:

[Break, abc, hello, world]
Copy the code

“Break” comes first because uppercase letters are smaller than lowercase letters. What if you want to ignore case when sorting?

Array sort – custom comparator

Sort has two other overloaded methods that can accept a comparator as a parameter:

public static <T> void sort(T[] a, Comparator<? super T> c)
public static <T> void sort(T[] a, int fromIndex, int toIndex,
                                Comparator<? super T> c)
Copy the code

The T in the method declaration stands for generics, which we will cover in a later section. This means that the method can support any object type, as long as the comparator corresponding to that type is passed. A Comparator is an interface that defines:

public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);
}
Copy the code

The main one is the compare method, which compares two objects and returns a value indicating the result of the comparison. -1 means o1 is less than O2, 0 means equal, and 1 means o1 is greater than O2.

Sort is implemented by comparison. The sort method calls the compare method when it needs to compare objects during sorting.

The String class has a public static member that represents a case-insensitive comparator:

public static final Comparator<String> CASE_INSENSITIVE_ORDER
                                     = new CaseInsensitiveComparator();
Copy the code

Let’s use the comparator to sort the String array above:

String[] arr = {"hello"."world"."Break"."abc"};
Arrays.sort(arr, String.CASE_INSENSITIVE_ORDER);
System.out.println(Arrays.toString(arr));
Copy the code

Thus, case is ignored and the output becomes:

[abc, Break, hello, world]
Copy the code

To further understand the Comparator, let’s look at the main implementation code for String:

private static class CaseInsensitiveComparator
        implements Comparator<String> {
    public int compare(String s1, String s2) {
        int n1 = s1.length();
        int n2 = s2.length();
        int min = Math.min(n1, n2);
        for (int i = 0; i < min; i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if(c1 ! = c2) { c1 = Character.toUpperCase(c1); c2 = Character.toUpperCase(c2);if(c1 ! = c2) { c1 = Character.toLowerCase(c1); c2 = Character.toLowerCase(c2);if(c1 ! = c2) {// No overflow because of numeric promotion
                        returnc1 - c2; }}}}returnn1 - n2; }}Copy the code

The code is pretty straightforward, so I won’t explain it.

Sort by default, sort from smallest to largest. For the object type, you can specify a different Comparator. You can implement the Comparator using an anonymous inner class. For example:

String[] arr = {"hello"."world"."Break"."abc"};
Arrays.sort(arr, new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        returno2.compareToIgnoreCase(o1); }}); System.out.println(Arrays.toString(arr));Copy the code

The program output is:

[world, hello, Break, abc]
Copy the code

This code implements the Comparator interface using an anonymous inner class that returns the result of a case-insensitive comparison between O2 and O1, ignoring case and ordering in order from largest to smallest. Why is the ratio of O2 to O1 in reverse order? Because by default, it’s o1 over O2.

The Collections class has two static methods that return reverse-order comparators, such as

public static <T> Comparator<T> reverseOrder(a)
public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
Copy the code

We’ll cover the Collections class in more detail in a later section.

Thus, the above code for reverse ordering strings regardless of case can be changed to:

String[] arr = {"hello"."world"."Break"."abc"};
Arrays.sort(arr, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
System.out.println(Arrays.toString(arr));
Copy the code

Pass Comparator Comparator to sort method, which reflects an important way of thinking in program design. It separates invariant and change. The basic steps and algorithm of sort are unchanged, but according to what sort is changed, sort method designs the invariant algorithm as the subject logic, and the changing sort method as the parameter. Allowing callers to specify dynamically is also a common design pattern. It has a name called policy pattern. Different sorting methods are different policies.

Binary search

Arrays contain many and sort the corresponding search method, can be in the sorted array for binary search, the so-called binary search is to find it from the middle, if less than the middle element, in the first half, otherwise the back half of the find, every comparison, or find, or to find half range, so the search efficiency is very high.

Binary lookup can be for an array of primitive types, an array of objects, a Comparator can be passed for an array of objects, and a range can be specified as follows:

For int arrays

public static int binarySearch(int[] a, int key)
public static int binarySearch(int[] a, int fromIndex, int toIndex,
                                       int key)
Copy the code

For object arrays

public static int binarySearch(Object[] a, Object key)
Copy the code

Custom comparators

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) 
Copy the code

If found, binarySearch returns the index of the found element, for example:

int[] arr = {3.5.7.13.21};
System.out.println(Arrays.binarySearch(arr, 13));
Copy the code

The output is 3. If not found, return a negative number equal to: -(insertion point +1). The insertion point indicates that the array can be kept in order if the missing element is inserted at this position, for example:

int[] arr = {3.5.7.13.21};
System.out.println(Arrays.binarySearch(arr, 11));
Copy the code

The output is -4, indicating that the insertion point is 3. If we insert 11 at 3, we can keep the array in order, that is, the array becomes {3,5,7,11,13,21}.

Note that binarySearch must be for sorted arrays. If a Comparator is specified, it must be the same as that specified when sorting. If there are multiple matching elements in the array, it is uncertain which one is returned.

Copy an array

Like toString, there are several overloaded forms, such as:

public static long[] copyOf(long[] original, int newLength)
public static <T> T[] copyOf(T[] original, int newLength)
Copy the code

This method can support any object type, the array type of the argument, the result of the array type.

NewLength indicates the length of the new array. If it is larger than the original array, the following element values are set to the default values. To review the defaults, the value is 0 for numeric types, false for Boolean, ‘\0’ for char, and null for objects.

Here’s an example:

String[] arr = {"hello"."world"};
String[] newArr = Arrays.copyOf(arr, 3);
System.out.println(Arrays.toString(newArr));
Copy the code

The output is:

[hello, world, null]
Copy the code

In addition to the copyOf method, the copyOfRange method of Arrays supports copying elements of a specified range, such as:

public static int[] copyOfRange(int[] original, int from, int to)
Copy the code

From represents the index of the first element to be copied. The length of the new array is to-from. To can be greater than the length of the original array.

Here’s an example:

int[] arr = {0.1.3.5.7.13.19};
int[] subArr1 = Arrays.copyOfRange(arr,2.5);
int[] subArr2 = Arrays.copyOfRange(arr,5.10);
System.out.println(Arrays.toString(subArr1));
System.out.println(Arrays.toString(subArr2));
Copy the code

The output is:

[3, 5, 7]
[13, 19, 0, 0, 0]
Copy the code

SubArr1 is a normal subarray. When subArr2 is copied, to is greater than the length of the original array. Set the value to 0.

The array is

Basic and object types are supported, as follows:

public static boolean equals(boolean[] a, boolean[] a2)
public static boolean equals(double[] a, double[] a2)
public static boolean equals(Object[] a, Object[] a2)
Copy the code

Return true only if the array is the same length and each element is the same, otherwise return false. For objects, same means equals returns true.

Filling it

Arrays contains many fill methods that set each element of the array to the same value:

public static void fill(int[] a, int val)
Copy the code

It is also possible to set the same value for each element in a given range of arrays:

public static void fill(int[] a, int fromIndex, int toIndex, int val)
Copy the code

Such as:

int[] arr = {3.5.7.13.21};
Arrays.fill(arr,2.4.0);
System.out.println(Arrays.toString(arr));
Copy the code

Set elements indexed from 2 inclusive to 4 inclusive to 0, and the output is:

[3, 5, 0, 0, 21]
Copy the code

Hash value

For arrays, compute an array hash:

public static int hashCode(int a[]) 
Copy the code

The algorithm for calculating hashCode is similar to String, so let’s look at the code:

public static int hashCode(int a[]) {
    if (a == null)
        return 0;

    int result = 1;
    for (int element : a)
        result = 31 * result + element;

    return result;
}
Copy the code

As a refresher, String evaluates hashCode similarly. Each element in the array affects the hash value, depending on where it is located. Using 31 produces a more diffuse hash, but it also computes more efficiently.

Multidimensional array

Arrays can also be multidimensional. Let’s look at two-dimensional arrays, for example:

int[][] arr = new int[2] [3];
for(int i=0; i<arr.length; i++){for(int j=0; j<arr[i].length; j++){ arr[i][j] = i+j; }}Copy the code

Arr is just a two-dimensional array with a first dimension of length 2 and a second dimension of length 3, similar to a rectangular matrix, or similar to a table with a first dimension representing rows and a second dimension representing columns. Arr [I] represents the ith row, which is itself an array, and arr[I][j] represents the JTH element in the ith row.

In addition to two dimensions, arrays can also be three dimensional, four dimensional, etc., but generally speaking, seldom use more than three dimensional arrays, there are several dimensions, several [], for example, a three-dimensional array declaration:

int[][][] arr = new int[10] [10] [10];
Copy the code

When creating an array, you do not need to specify the length of the other dimensions except the first dimension, or even the length of the second dimension of each element in the first dimension.

int[][] arr = new int[2] []; arr[0] = new int[3];
arr[1] = new int[5];
Copy the code

Arr is a two-dimensional array with length 2 in the first dimension, 3 in the second dimension for the first element, and 5 in the second dimension for the second element.

What exactly is a multidimensional array? In fact, you can think of a multidimensional array as just an illusion, just a one-dimensional array, but each element in the array can be an array, so that’s a two-dimensional array, and if each element in the array is an array, then it’s a three-dimensional array.

Multidimensional array operations

The toString, equals, and hashCode methods of Arrays all have corresponding methods for multi-dimensional Arrays:

public static String deepToString(Object[] a)
public static boolean deepEquals(Object[] a1, Object[] a2)
public static int deepHashCode(Object a[])
Copy the code

Each of these deepXXX methods determines whether the elements in the argument are also arrays, and if so, operates recursively.

Here’s an example:

int[][] arr = new int[] [] {{0.1},
        {2.3.4},
        {5.6.7.8}}; System.out.println(Arrays.deepToString(arr));Copy the code

The output is:

[2, 3, 4], [5, 6, 7, 8]]Copy the code

Realize the principle of

Now, let’s look at the implementation principle of the above method.

The implementation of hashCode has already been covered, and the implementation of fill and Equals are simple, circular operations.

toString

ToString’s implementation is also very simple, using StringBuilder, and we’ll list the code but won’t explain it.

public static String toString(int[] a) {
    if (a == null)
        return "null";
    int iMax = a.length - 1;
    if (iMax == -1)
        return "[]";

    StringBuilder b = new StringBuilder();
    b.append('[');
    for (int i = 0; ; i++) {
        b.append(a[i]);
        if (i == iMax)
            return b.append('] ').toString();
        b.append(","); }}Copy the code

copy

CopyOf and copyOfRange make use of System.arrayCopy, and the logic is very simple, so we simply list the code:

public static int[] copyOfRange(int[] original, int from, int to) {
    int newLength = to - from;
    if (newLength < 0)
        throw new IllegalArgumentException(from + ">" + to);
    int[] copy = new int[newLength];
    System.arraycopy(original, from, copy, 0,
                     Math.min(original.length - from, newLength));
    return copy;
} 
Copy the code

Binary search

Binary lookup binarySearch code is also relatively straightforward, the main code is as follows:

private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
                                     T key, Comparator<? super T> c) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        T midVal = a[mid];
        int cmp = c.compare(midVal, 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 code

There are two flags, low and high, to indicate the range of the search. In the while loop, the search is performed against the intermediate value, if greater than that, the search is performed in the latter half (raising low), otherwise the search is performed in the first half (lowering high).

The sorting

Finally, we come to sort sorting method, compared with these simple directly in front of the methods, sort is more complicated, the sorting is a very important aspect in the computer program, for decades, computer scientists and engineers have carried out extensive research and design to achieve the various algorithms and implementation, a lot of optimization. Generally speaking, there is no one best algorithm, and different algorithms often have different applications.

So how does the Sort of Arrays implement?

For primitive arrays, The Java algorithm is dual-pivot Quicksort, which was introduced in Java 1.7. Prior to that, Java used normal Quicksort, which is an optimization of Quicksort. The new algorithm implementation code in Java classes. Util. DualPivotQuicksort.

For object types, Java uses TimSort, which was introduced in Java 1.7. Before that, Java used merge sort. TimSort is actually a set of optimizations for merge sort. The implementation code for TimSort is in the java.util.timsort class.

In these sorting algorithms, if the array length is small, they also use insertion sort, which is more efficient.

Why is the algorithm different for primitive types and object types? Sorting algorithm has a concept of stability, the so-called stability is the same value of the elements, if the algorithm before and after sorting, can ensure that their relative order is unchanged, then the algorithm is stable, otherwise it is unstable.

Quicksort is faster, but unstable, whereas merge sort is stable. For primitive types, identical values are identical, so it doesn’t matter if they’re stable or not. But for object types, the same is only the same comparison results, they are still different objects, other instance variables are not necessarily the same, stability or instability may be very relevant, so use merge sort.

The implementation of these algorithms is quite complex, but fortunately, Java provides us with a good implementation, and most of the time, we can use it.

More methods

As a matter of fact, Arrays contains few array methods and many common operations are not available. For example, binarySearch of Arrays can only search sorted Arrays, so how can it be easy to search unsorted Arrays?

Apache (http://commons.apache.org/proper/commons-lang/) is an open source package, there is a class ArrayUtils (in package org.apache.com mons. Lang3), Just like Arrays, each of which has a lot of overloaded methods, we’ll just list one.

Flipping array elements

public static void reverse(final int[] array)
Copy the code

The sort of primitive Arrays can only be sorted from small to large. If you want to sort from large to small, you can reverse the array using Reverse after sorting.

Look for the element

// Go back to the beginning
public static int indexOf(final int[] array, final int valueToFind)

// Look forward from the tail
public static int lastIndexOf(final int[] array, final int valueToFind)

// Check if elements are included
public static boolean contains(final int[] array, final int valueToFind)
Copy the code

Remove elements

Because the array length is fixed, deletion is done by creating a new array and then copying the elements other than the deleted ones.

// Remove the element at the specified position
public static int[] remove(final int[] array, final int index)

// Remove multiple elements at specified positions
public static int[] removeAll(final int[] array, final int. indices)// Delete the element with the value element, only the first one
public static boolean[] removeElement(final boolean[] array, final boolean element) 
Copy the code

Add elements

As with deleting, because the array length is fixed, adding is done by creating a new array and then copying the contents of the original array and the new element.

// Add an element
public static int[] add(final int[] array, final int element)

// Add an element at the specified location
public static int[] add(final int[] array, final int index, final int element)

// Merge two arrays
public static int[] addAll(final int[] array1, final int. array2)Copy the code

Checks whether the array is sorted

public static boolean isSorted(int[] array) 
Copy the code

summary

In this section, we examine the Arrays class, introduce its usage, and basic implementation principles. We also introduce multi-dimensional Arrays and the ArrayUtils class in Apache. For the sorting method with the Comparator parameter, we mentioned that this is a thinking and design pattern worth learning.

Arrays are basic data structures in computer programs. The Arrays and ArrayUtils classes encapsulate common operations on Arrays. Use these methods.

In the next video, we’ll look at another common operation in a computer program, and that’s the operation on dates.

To be continued, check the latest articles, please pay attention to the wechat public account “Lao Ma said programming” (scan the qr code below), simple and simple, Lao Ma and you explore the nature of Java programming and computer technology. All rights reserved.