Java源码 —— Arrays

喜欢ヅ旅行 2022-05-29 00:16 102阅读 0赞

# Java源码 —— Arrays #

Arrays包含了一系列操作数组的方法（比如排序和搜索）；

Arrays提供了一个能够将数组转换成List列表的方法；

Arrays如果指定数组引用为null，将抛出NullPointerException（一些特定方法除外，比如hashCode）。

## 一、Arrays类图 ##

![Image 1][]

## 二、Arrays ##

此类中不同类型重载方法过多，这里只记载一种类型的方法，其他类型的重载方法与之类似。

此类中提供的方法均为static修饰，且不允许通过new来创建Arrays对象。

### 2.1 asList(T... a) ###

1.  返回一个受指定数组支持的大小固定的列表；
2.  传入数组如果是一个基本类型数组（如int\[\]），那么将返回一个大小为1的列表，且列表元素就是传入的这个数组；  
    
3.  返回的列表不可添加或删除元素，可以对列表中数据做替换操作（即不可更改列表的大小）；  
    
4.  更改列表中元素内容即更改传入数组的内容（返回的列表持有传入数组参数的引用，不是单独的两个对象）。

public static <T> List<T> asList(T... a) {
            // 这里的ArrayList并非java.util包下的类，而是Arrays中的内部类，查看详情
            return new ArrayList<>(a);// ArrayList持有数组a的引用
        }

### 2.2 binarySearch(byte\[\] a, byte key) ###

1.  使用二分搜索法来搜索指定的数组，以获得指定的值；
2.  查找元素时，不包括toIndex的值，因此传入的toIndex应比实际下标大1；  
    
3.  返回结果小于0，表示搜索不到指定的元素；  
    
4.  Arrays还提供了一个含Comparator对象的方法，此方法能够更快速的定位到搜索值。

//    public static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key) {
        public static int binarySearch(byte[] a, byte key) {
            return binarySearch0(a, 0, a.length, key);
        }
        private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
                                         byte key) {
            int low = fromIndex;
            int high = toIndex - 1;
    
            while (low <= high) {
                int mid = (low + high) >>> 1;
                byte midVal = a[mid];
    
                if (midVal < key)
                    low = mid + 1;
                else if (midVal > key)
                    high = mid - 1;
                else
                    return mid; // key found
            }
            return -(low + 1);  // key not found.
        }

### 2.3 copyOf(int\[\] original, int newLength) ###

1.  复制指定的数组，截取或用默认值填充，以使副本具有指定的长度；
2.  Arrays.copyOf调用System.arraycopy方法，copy出来的每个副本都是单独的对象。

public static int[] copyOf(int[] original, int newLength) {
            int[] copy = new int[newLength];
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }

### 2.4 deepEquals(Object\[\] a1, Object\[\] a2) ###

1.  如果两个指定数组彼此是深层相等的，则返回true；
2.  不支持基本数据类型数组；  
    
3.  先比较数组长度，长度相等时再用==比较，==结果为false时再用equals比较；  
    
4.  Arrays为每种基本类型数组定义了一个equals方法。

public static boolean deepEquals(Object[] a1, Object[] a2) {
            if (a1 == a2)
                return true;
            if (a1 == null || a2==null)
                return false;
            int length = a1.length;
            if (a2.length != length)
                return false;
    
            for (int i = 0; i < length; i++) {
                Object e1 = a1[i];
                Object e2 = a2[i];
    
                if (e1 == e2)
                    continue;
                if (e1 == null)
                    return false;
    
                // Figure out whether the two elements are equal
                boolean eq = deepEquals0(e1, e2);
    
                if (!eq)
                    return false;
            }
            return true;
        }
    
        static boolean deepEquals0(Object e1, Object e2) {
            assert e1 != null;
            boolean eq;
            if (e1 instanceof Object[] && e2 instanceof Object[])
                eq = deepEquals ((Object[]) e1, (Object[]) e2);
            else if (e1 instanceof byte[] && e2 instanceof byte[])
                eq = equals((byte[]) e1, (byte[]) e2);
            else if (e1 instanceof short[] && e2 instanceof short[])
                eq = equals((short[]) e1, (short[]) e2);
            else if (e1 instanceof int[] && e2 instanceof int[])
                eq = equals((int[]) e1, (int[]) e2);
            else if (e1 instanceof long[] && e2 instanceof long[])
                eq = equals((long[]) e1, (long[]) e2);
            else if (e1 instanceof char[] && e2 instanceof char[])
                eq = equals((char[]) e1, (char[]) e2);
            else if (e1 instanceof float[] && e2 instanceof float[])
                eq = equals((float[]) e1, (float[]) e2);
            else if (e1 instanceof double[] && e2 instanceof double[])
                eq = equals((double[]) e1, (double[]) e2);
            else if (e1 instanceof boolean[] && e2 instanceof boolean[])
                eq = equals((boolean[]) e1, (boolean[]) e2);
            else
                eq = e1.equals(e2);
            return eq;
        }

### 2.5 fill(byte\[\] a, byte val) ###

1.  将指定的值分配给指定数组的每一个元素；
2.  指定范围时，替换值时不包括toIndex下标值，因此作为下标需要+1。

public static void fill(byte[] a, byte val) {
            for (int i = 0, len = a.length; i < len; i++)
                a[i] = val;
        }
        public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
            rangeCheck(a.length, fromIndex, toIndex);
            for (int i = fromIndex; i < toIndex; i++)
                a[i] = val;
        }

### 2.6 parallelPrefix(int\[\] array, IntBinaryOperator op) ###

1.  对数组arr进行二元迭代；
2.  从头到尾逐个按照left op right的方式更新，更新后的值继续迭代下一个元素；  
    
3.  TypeBinaryOperator表示二元运算法，Type目前支持类型为：Int、Double、Long；  
    
4.  JDK1.8新增方法。

public static void parallelPrefix(int[] array, IntBinaryOperator op) {
            Objects.requireNonNull(op);
            if (array.length > 0)
                new ArrayPrefixHelpers.IntCumulateTask
                        (null, op, array, 0, array.length).invoke();
        }

// left op right 数组元素（数组[1, 2, 3]）
            // 1 * 2        [1, 2, 3]
            // 2 * 3        [1, 2, 6]
            //System.out.println(Arrays.toString(arr));// [1, 2, 6]

### 2.7 parallelSetAll(int\[\] array, IntUnaryOperator generator) ###

1.  使用填充算法为数组arr的每一个元素赋值；
2.  默认使用元素的索引为该元素赋值；  
    
3.  可自定义如何生成赋值；  
    
4.  JDK1.8新增方法。

public static void parallelSetAll(int[] array, IntUnaryOperator generator) {
            Objects.requireNonNull(generator);
            IntStream.range(0, array.length)
                    .parallel().forEach(i -> {
                array[i] = generator.applyAsInt(i);
            });
        }

### 2.8 parallelSort(int\[\] a) ###

1.  JDK1.8新增排序方法；
2.  可指定数组范围排序。

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();
        }

Jdk1.8之前的排序方法sort

public static void sort(byte[] a) {
            DualPivotQuicksort.sort(a, 0, a.length - 1);
        }

### 2.9 spliterator(int\[\] array) ###

1.  获取一个分割器，可用于遍历数组；
2.  可指定范围获取分割器，获取到的分割器中内容不包括endExclusive下标的元素；  
    
3.  除支持复杂类型数组遍历之外，还支持int、double、long三种基本类型数组遍历；  
    
4.  分割器持有数组的引用，并非独立的对象（即改变数组元素将影响遍历的结果）；  
    
5.  JDK1.8新增方法。

//    public static <T> Spliterator<T> spliterator(T[] array, int startInclusive, int endExclusive) {
        public static <T> Spliterator<T> spliterator(T[] array) {
            return Spliterators.spliterator(array,
                         Spliterator.ORDERED | Spliterator.IMMUTABLE);
        }

### 2.10 stream(T\[\] array) ###

JDK1.8新增方法，将数组作为一个连续的流使用，用法上与spliterator相似。

//    public static <T> Stream<T> stream(T[] array, int startInclusive, int endExclusive) {
        public static <T> Stream<T> stream(T[] array) {
            return stream(array, 0, array.length);
        }

## 三、LegacyMergeSort ##

1.  排序时可能会用到，外部无法调用；
2.  可在运行代码前设置java.util.Arrays.useLegacyMergeSort参数来控制Arrays.sort方法是否使用老版的排序方法。

**LegacyMergeSort类定义：**

/**
         * Old merge sort implementation can be selected (for
         * compatibility with broken comparators) using a system property.
         * Cannot be a static boolean in the enclosing class due to
         * circular dependencies. To be removed in a future release.
         */
        static final class LegacyMergeSort {
            private static final boolean userRequested =
                java.security.AccessController.doPrivileged(
                    new sun.security.action.GetBooleanAction(
                        "java.util.Arrays.useLegacyMergeSort")).booleanValue();
        }

**排序方法：**

public static void sort(Object[] a) {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a);
            else
                ComparableTimSort.sort(a, 0, a.length, null, 0, 0);// JDK1.8新增排序方法
        }

## 四、NaturalOrder ##

![Image 1][]

一个比较器，它实现了一组相互比较的元素的自然排序。当未提供或提供的比较器为空时使用。

**NaturalOrder类定义：**

/**
         * A comparator that implements the natural ordering of a group of
         * mutually comparable elements. May be used when a supplied
         * comparator is null. To simplify code-sharing within underlying
         * implementations, the compare method only declares type Object
         * for its second argument.
         *
         * Arrays class implementor's note: It is an empirical matter
         * whether ComparableTimSort offers any performance benefit over
         * TimSort used with this comparator.  If not, you are better off
         * deleting or bypassing ComparableTimSort.  There is currently no
         * empirical case for separating them for parallel sorting, so all
         * public Object parallelSort methods use the same comparator
         * based implementation.
         */
        static final class NaturalOrder implements Comparator<Object> {
            @SuppressWarnings("unchecked")
            public int compare(Object first, Object second) {
                return ((Comparable<Object>)first).compareTo(second);
            }
            static final NaturalOrder INSTANCE = new NaturalOrder();
        }

**比较方法：**

public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
            if (cmp == null)
                cmp = NaturalOrder.INSTANCE;
            int n = a.length, p, g;
            if (n <= MIN_ARRAY_SORT_GRAN ||
                (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
                TimSort.sort(a, 0, n, cmp, null, 0, 0);
            else
                new ArraysParallelSortHelpers.FJObject.Sorter<T>
                    (null, a,
                     (T[])Array.newInstance(a.getClass().getComponentType(), n),
                     0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
                     MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
        }

## 五、ArrayList ##

![Image 1][]

Arrays定义的一个大小固定的私有静态列表类，继承自AbstractList，可用于遍历，不可添加或删除元素（可替换元素）；

此列表中元素内容为所持有的数组对象，变更数组中的值时影响列表的使用。

### 5.1 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);
            }
        }

### 5.2更变列表大小的方法（AbstractList） ###

**Add：**

public boolean add(E e) {
            add(size(), e);
            return true;
        }
        public void add(int index, E element) {
            throw new UnsupportedOperationException();
        }

**Remove：**

public E remove(int index) {
            throw new UnsupportedOperationException();
        }

[Image 1]: