关于Arrays你可能还不知道的细节

陈琛

发布于 2021-04-23 11:13:21

3690

发布于 2021-04-23 11:13:21

文章被收录于专栏：陈琛的Redis文章

这是学习Java的小姐姐第60篇原创文章

Arrays 主要对数组提供了一些高效的操作，比如说排序、二分查找、填充、拷贝、相等判断，转化为list等等。我们选择部分看下，其他的可以看jdk中的Arrays源码。

1.排序sort

Arrays.sort 方法主要用于排序，入参支持 int、long、double ，char，float，short等各种基本类型的数组，也支持自定义类的数组。

1.1基本类型排序

我们可以给如下的int类型数据采用sort方法进行排序，然后打印出数组信息，可以看到已经排序完成了。

 public static void main(String[] args) {
        int[] numbers={1,2,4,6,3,5};
        Arrays.sort(numbers);
        System.out.println(Arrays.toString(numbers));
    }

1.2int类型的排序算法

大家都说 sort 方法排序的性能较高，主要原因是 sort对于不同长度的数组采用了不同的排序算法，如双轴快速排序算法，插入排序算法，归并排序算法，具体算法就不细说，后面可以专门写一篇。

1.3自定义类的排序

如果需要对自定义的类进行排序，则需要重写compare方法，制定属于自己的排序规则。如下代码，制定的规则是先按年龄排序，如果年龄相同的情况下，再按照名称排序。

public class Student {
    String name;
    int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}


   public static void main(String[] args) {
        Student[] students = new Student[]{new Student("张三", 22), new Student("李四", 22), new Student("王五", 33)};
        Arrays.sort(students, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                if (o1 == null || o2 == null) {
                    return 0;
                }
                return o1.getAge() - o2.getAge()==0?o1.getName().compareTo(o2.getName()):o1.getAge()-o2.getAge();
            }
        });
        System.out.println(Arrays.toString(students));
    }

从输出的结果中可以看到，排序之后的数组已经是有顺序的了。

2.并行排序parallelSort()

2.1源码分析

 public static void parallelSort(int[] a) {
        int n = a.length, p, g;
        if (n <= MIN_ARRAY_SORT_GRAN ||
            (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
            DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
        else
            new ArraysParallelSortHelpers.FJInt.Sorter
                (null, a, new int[n], 0, n, 0,
                 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                 MIN_ARRAY_SORT_GRAN : g).invoke();
    }

parallelSort(）它使用并行排序-合并排序算法。它将数组分成子数组，这些子数组本身先进行排序然后合并，同时还使用 ForkJoin 池。

我们可以看到上面的if条件，如果数组大小小于或等于 MIN_ARRAY_SORT_GRAN或者处理器只有一个核心，则它将使用顺序的 Dual-Pivot Quicksort 算法。否则，它使用并行排序。

2.2与排序sort性能比较

现在，让我们看看在不同数量级的数组上两种方法性能方面有什么区别。

数组大小	Arrays.sort()	Arrays.parallelSort()
1000	0.048	0.054
10000	0.847	0.425
100000	7.570	4.395
1000000	65.301	37.998

根据性能结果，我们可以得出结论，当我们要排序的数据集很大时，parallelSort() 性能表现优异。但在数组较小的情况下，最好使用 sort()。

3二分查找binarySearch

3.1采用二分查找前需先排序

如果没有先排序的话，可以看到返回的信息，即下标位置为-3，这个肯定是不对的，怎么可能是复数。?

public static void main(String[] args) {
        int[] numbers={1,2,4,6,3,5};
        int num=Arrays.binarySearch(numbers,3);
        System.out.println(num);
    }

那我们可以先排序，再看下返回结果。如下图，打印出来的结构是正常的。

public static void main(String[] args) {
        int[] numbers={1,2,4,6,3,5};
        Arrays.sort(numbers);
        int num=Arrays.binarySearch(numbers,3);
        System.out.println(num);
    }

3.2二分法源码分析

接下来，我们来看下二分法底层代码的实现：

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;
       
       // 开始位置小于结束位置，就会一直循环搜索
        while (low <= high) {
            // 假设 low =0，high =10，那么 mid 就是 5，所以说二分的意思主要在这里，每次都是计算索引的中间值
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

           // 如果数组中间值小于给定的值，说明我们要找的值在中间值的右边
            if (midVal < key)
                low = mid + 1;
            // 我们要找的值在中间值的左边
            else if (midVal > key)
                high = mid - 1;
            // 找到了
            else
                return mid; 
        }
        // 返回的值是负数，表示没有找到
        return -(low + 1);  
    }

二分的主要意思是每次查找之前，都找到中间值，然后拿我们要比较的值和中间值比较，根据结果修改比较的上限或者下限，通过循环最终找到相等的位置索引。

4.aslist

public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

作用是返回由指定数组支持的固定大小列表。

注意：这个方法返回的 ArrayList 不是我们常用的集合类 java.util.ArrayList。这里的 ArrayList 是 Arrays 的一个内部类 java.util.Arrays.ArrayList。这个内部类有如下属性和方法：

private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
{
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;

        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }

        @Override
        public int size() {
            return a.length;
        }

        @Override
        public Object[] toArray() {
            return a.clone();
        }

        @Override
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            int size = size();
            if (a.length < size)
                return Arrays.copyOf(this.a, size,
                                     (Class<? extends T[]>) a.getClass());
            System.arraycopy(this.a, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }

        @Override
        public E get(int index) {
            return a[index];
        }

        @Override
        public E set(int index, E element) {
            E oldValue = a[index];
            a[index] = element;
            return oldValue;
        }

        @Override
        public int indexOf(Object o) {
            E[] a = this.a;
            if (o == null) {
                for (int i = 0; i < a.length; i++)
                    if (a[i] == null)
                        return i;
            } else {
                for (int i = 0; i < a.length; i++)
                    if (o.equals(a[i]))
                        return i;
            }
            return -1;
        }

        @Override
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }

        @Override
        public Spliterator<E> spliterator() {
            return Spliterators.spliterator(a, Spliterator.ORDERED);
        }

        @Override
        public void forEach(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            for (E e : a) {
                action.accept(e);
            }
        }

        @Override
        public void replaceAll(UnaryOperator<E> operator) {
            Objects.requireNonNull(operator);
            E[] a = this.a;
            for (int i = 0; i < a.length; i++) {
                a[i] = operator.apply(a[i]);
            }
        }

        @Override
        public void sort(Comparator<? super E> c) {
            Arrays.sort(a, c);
        }
    }

4.1、返回的 ArrayList 数组是一个定长列表，我们只能对其进行查看或者修改，但是不能进行添加或者删除操作

通过源码我们发现该类是没有add()或者remove() 这样的方法的，如果对其进行增加或者删除操作，都会调用其父类 AbstractList 对应的方法，而追溯父类的方法最终会抛出 UnsupportedOperationException 异常。如下：

add方法

public static void main(String[] args) {
        List list = Arrays.asList("a", "b", "c");
        list.add("d");
    }

remove方法

 public static void main(String[] args) {
        List list = Arrays.asList("a", "b", "c");
        list.remove("a");
    }

原因

Arrays里面新建了一个内部类ArrayList，而这个内部类是继承于AbstractList类，AbstractList类里面的add，remove方法是会抛出UnsupportedOperationException异常的。

4.2、引用类型和基本类型区别

我们来看下先将string类型的数组转化成list，并打印listStr长度，为3；然后再将int类型的数组转化为list，并打印listI长度，为1。

public static void main(String[] args) {
         String[] str = {"学习Java","的","小姐姐"};
         List listStr = Arrays.asList(str);
         System.out.println(listStr.size());
         int[] i = {1,2,3};
         List listI = Arrays.asList(i);
         System.out.println(listI.size());
    }

这是为什么呢？我们看源码，在 Arrays.asList 中，方法声明为 <T> List<T> asList(T... a)。该方法接收一个可变参数，并且这个可变参数类型是作为泛型的参数。

我们知道基本数据类型是不能作为泛型的参数的(因为Java中的泛型是通过编译时的类型擦除来完成的，当泛型被类型擦除后都变成Object类型。但是Object类型不能指代像int，double这样的基本类型只能指代Integer，Double这样的引用类型。)但是数组是引用类型，所以数组是可以泛型化的，于是 int[] 作为了整个参数类型，而不是 int 作为参数类型。

所以我们改下，将基本类型int改为引用类型Integer，即可发现数据正常显示。

 public static void main(String[] args) {
        String[] str = {"学习Java","的","小姐姐"};
         List listStr = Arrays.asList(str);
         System.out.println(listStr.size());
         Integer[] i = {1,2,3};
         List listI = Arrays.asList(i);
         System.out.println(listI.size());
    }

　4.3、返回的列表ArrayList里面的元素都是引用，不是独立出来的对象

我们看下面的代码数组转化为list，然后修改list，发现不管是list还是原来的str数组的打印内容都改变了。因此得出ArrayList元素都是引用，并不是新建出来的对象。

public static void main(String[] args) {
        String[] str = {"学习Java","的","小姐姐"};
        List<String> listStr = Arrays.asList(str);
        //执行赋值操作前
        System.out.println(Arrays.toString(str));
        listStr.set(0, "学习C");
        //执行赋值操作后
        System.out.println(listStr.toString());
        System.out.println(Arrays.toString(str));
    }

5.拷贝copyof

从源码中，我们发现，Arrays 的拷贝方法，实际上底层调用的是 System.arraycopy 这个 native 方法，如果你自己对底层拷贝方法比较熟悉的话，也可以直接使用

6.范围拷贝copyOfRange()

数组拷贝我们经常遇到，有时需要拷贝整个数组，有时需要拷贝部分，比如 ArrayList 在 add（扩容）或 remove（删除元素不是最后一个）操作时，会进行一些拷贝。拷贝整个数组我们可以使用 copyOf 方法，拷贝部分我们可以使用 copyOfRange 方法，以 copyOfRange 为例，看下底层源码的实现：

// original 原始数组数据
// from 拷贝起点
// to 拷贝终点
public static char[] copyOfRange(char[] original, int from, int to) {
     // 需要拷贝的长度
     int newLength = to - from;
     if (newLength < 0)
     throw new IllegalArgumentException(from + " > " + to);
     // 初始化新数组
     char[] copy = new char[newLength];
     // 调用 native 方法进行拷贝，参数的意思分别是：
     // 被拷贝的数组、从数组那里开始、目标数组、从目的数组那里开始拷贝、拷贝的长度
     System.arraycopy(original, from, copy, 0,
     Math.min(original.length - from, newLength));
  return copy;
}

7.哈希值hashCode()

public static void main(String[] args) {
        int[] numbers = {1, 2, 4, 6, 3, 5};
        int n = Arrays.hashCode(numbers);
        System.out.println(n);
    }

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

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

        return result;
    }

选择值31是因为它是奇数素数。如果它是偶数，乘法溢出，信息就会丢失，因为乘2等于移位。使用素数的好处不太清楚，但它是传统的。31的一个很好的特性是，乘法可以用移位和减法来代替，以获得更好的性能：31*i==（i<<5）-i。现代虚拟机会自动进行这种优化。

8.打印toString()

8.1基本类型

public static void main(String[] args) {
        int[] numbers = {1, 2, 4, 6, 3, 5};
        System.out.println( Arrays.toString(numbers));
    }

8.2自定义对象

我们先不重写对象Student的toString方法，发现打印的为地址信息，并不是对象原来的值。

public static void main(String[] args) {
        Student[] students= {new Student("张三",12),new Student("李四",13),new Student("王五",14)};
        System.out.println( Arrays.toString(students));
    }

如果重写了toString方法，发现打印的为正确的信息。

 @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

8.3源码分析

根据打断点，我们可以看到最底层的还是调用toString方法，这就是为什么不重写toString方法，打印出来的是地址信息。

 public static String toString(Object[] 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(String.valueOf(a[i]));
            if (i == iMax)
                return b.append(']').toString();
            b.append(", ");
        }
    }

 public static String valueOf(Object obj) {
        return (obj == null) ? "null" : obj.toString();
    }

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

java

网站

本文分享自学习Java的小姐姐微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

java

网站

登录后参与评论

0 条评论

热度