读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。

它提供的操作包括:

  1. 排序 sort
  2. 查找 binarySearch()
  3. 比较 equals
  4. 填充 fill
  5. 转列表 asList()
  6. 哈希 Hash()
  7. 转字符串 toString()

这个类的代码量很多,Java1.7中有4000多行。因为每一种基本类型都做了兼容,所以整个类真正逻辑不多。下面简单介绍一下它各个功能的实现:

排序


这里的排序实现有两种

一种是为基本类型数组设计的,它的对外接口有两种,如下:

//whole array
public static void sort(primitive[] a);

//sub array
public static void sort(primitive[] a, int fromIndex, int toIndex);

它们的具体实现方式是一样的都是调用了DualPivotQuicksort.sort(...)方法。这个方法的中文含义是 双轴快速排序。它在性能上优于传统的单轴快速排序。

算法的逻辑可以参考国外一篇博客 如果想要阅读源码可以参考我的另一篇博客双轴快速排序源码阅读笔记

它是不稳定

另一种是为Object对象设计的,它要求传进来的数组对象必须实现Comparable接口。 它提供的接口如下:

// whole array, default asec
public static void sort(Object[] a);

// subArray, default asec
public static void sort(Object[] a, int fromIndex, int toIndex);

还有带泛型参数的接口,它需要指定一个比较器。

// whole array with comparator
public static <T> void sort(T[] a, Comparator<? super T> c);

// sub array with comparator
public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c);

他的实现方式如下:

// java/utils/Arrays.java
static final class LegacyMergeSort {
        private static final boolean userRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
}

//sort 方法的实现
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
       legacyMergeSort(a);
    else
       //与TimSort的逻辑是相同的
       ComparableTimSort.sort(a);
}

//legacyMergeSort
private static void legacyMergeSort(Object[] a) {
    Object[] aux = a.clone();
    mergeSort(aux, a, 0, a.length, 0);
}                    

//归并排序
    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        // 小数组直接进行普通插入排序
        if (length < INSERTIONSORT_THRESHOLD) {
             ///...
            return;
        }

        //下面是归并排序的实现,
        ///...
    }

从上面的逻辑可以看出来,它的实现方式分为两种,一种是通过Arrays.java中的归并排序实现的,另一种采用了TimSort算法。其中Arrays.java中的归并排序的逻辑相对简单,是一种插入排序与传统归并排序的结合。当待排序的数组小于INSERTIONSROT_THERSHOLD的时候直接进行插入排序,不再递归。TimSort算法也是一种插入排序与归并排序结合的算法,不过它的细节优化要比Arrays.java中的算法做的多。详细介绍可以参考维基百科或者我的TimSort 源码笔记

两种算法的切换依靠运行时系统变量的设置。具体参考StackOverFlow上的一篇回答。我们默认情况下是不打开这个开关的,也就是说没有特殊要求的情况下,我们默认使用TimSort算法来实现排序。从注释上来看,在未来某个版本,Arrays.java中的merge方法将会被删除掉。

这个排序方法是 稳定 的。

查找

Arrays.java中只提供了二分查找。二分查找的前提就是数组是经过升序排序的,所以使用之前务必确保数组是有序的。

调用的接口比较简单:

public static int binarySearch(primative[] a, primative key);
public static int binarySearch(primative[] a, int fromIndex, int toIndex, primative key);
public static int binarySearch(Object[] a, Object key);
public static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key);
public static <T> int binarySearch(T[] a, T key, Comparator< ? super T> c);
public static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key,Comparator<? super T> c);

equals

这个也比较简单,equals方法与==的不同大家应该都很熟悉了,这里直接贴出接口:

    // 基本类型
    public static boolean equals(long[] a, long[] a2) {
        //...
    }
    // 对象
    public static boolean equals(Object[] a, Object[] a2) {
        //...
    }
    // 高维数组的equal比较,通过递归实现
    // 这里没有对循环引用进行检查,如果两个如组同时存在循环引用的情况下可能出现死循环的风险。
    public static boolean deepEquals(Object[] a1, Object[] a2) {
       //...
    }

fill 填充


批量初始化的时候不要自己写for循环了,已经有人帮我们写好了。

// 基本类型批量赋值
public static void fill(int[] a, int fromIndex, int toIndex, int val) {
    rangeCheck(a.length, fromIndex, toIndex);
    for (int i = fromIndex; i < toIndex; i++)
        a[i] = val;
}
// 对象批量赋值
public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
    rangeCheck(a.length, fromIndex, toIndex);
    for (int i = fromIndex; i < toIndex; i++)
        a[i] = val;
}

复制


数组复制的最终实现是调用了JVM中的方法。具体没有深究,但在数据量大的时候应该能快些。

// @file Arrays.java
// 基本类型的复制,从0开始到指定长度
public static byte[] copyOf(byte[] original, int newLength) {
    byte[] copy = new byte[newLength];
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}
// 基本类型复制,从指定起点到指定终点
public static byte[] copyOfRange(byte[] original, int from, int to) {
    int newLength = to - from;
    if (newLength < 0)
        throw new IllegalArgumentException(from + " > " + to);
    byte[] copy = new byte[newLength];
    System.arraycopy(original, from, copy, 0,
                    Math.min(original.length - from, newLength));
    return copy;
}
//这里是泛型数组的复制, 结合泛型进阶中的内容,这里好理解很多。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

// @file System.java
public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);

// 

转换成列表 asList


将一组对象转换成列表,这里一定要注意返回的ArrayList并非平常用的java.util.ArrayList ,而是Arrays.java中定义的一个简单的静态内部类--ArrayList。它不支持添加和移除元素,不支持扩容。

@file java/util/Arrays.java

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

//注意,此ArrayList非平常用的ArrayList;这里的实现比较简单。
//不能扩容,所以不支持add,remove等操作。
private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable {
    /// ...
}

哈希 hash

高维数组的哈希计算,采用递归实现。同样,如果自己的某个元素直接或者间接持有自己,会出现死循环。

    // 基本类型哈希
    public static int hashCode(long a[]) {
       // ...
    }
    
    // 对象哈希
    public static int hashCode(Object a[]) {
       //...
    }
    
    // 高维数组哈希,采用递归实现。如果自己的某个元素直接或者间接持有自己,会出现死讯环,
    // 所以`Object[]`最好直接使用`hashcode(Object)`。
    public static int deepHashCode(Object a[]) {
       //...
    }

toString


有了这个方法,打Log的时候就不需要写循环了。 这里的高维数组直接或者间接持有自己的情况不会出现死循环。因为这里做了特殊处理,用一个Set保存了打印过的数组。

    // 基本类型
    public static String toString(int[] a) {
       // ...
    }
    // 对象
    public static String toString(Object[] a) {
        // ...
    }
    // 高维数组toString(). 这里处理了自我持有的问题。
    public static String deepToString(Object[] a) {
        // ...
        deepToString(a, buf, new HashSet<Object[]>());
        return buf.toString();
    }
    // 真正的实现方法, 递归实现。
    // 使用了一个Set来存储已经打印过的类,如果再次出现这个对象,直接打印[...]
    private static void deepToString(Object[] a, StringBuilder buf,
                                     Set<Object[]> dejaVu) {
       //...
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小灰灰

JDK容器学习之Map: HashMap,TreeMap,LinkedHashMap对比小结

HashMap, TreeMap, LinkedHashMap 对比 1. 存储结构 HashMap 存储结构: 数组 + 链表 + 红黑树 ? LinkedH...

24910
来自专栏好好学java的技术栈

“365算法每日学计划”:04打卡-自己动手写一个单链表

1503
来自专栏Jack的Android之旅

疯狂java笔记之线性表

从数据的逻辑结构来分,数据元素之间存在的关联关系被称为数据的逻辑结构。归纳起来,应用程序中的数据大致哟如下四种基本的逻辑结构。

1112
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

2646
来自专栏mySoul

​单链表 C++

1102
来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

1031
来自专栏Bingo的深度学习杂货店

Q125 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric c...

3285
来自专栏Petrichor的专栏

leetcode: 100. Same Tree

1071
来自专栏wannshan(javaer,RPC)

JDK PriorityBlockingQueue remove(Object o) 源码分析

先知道PriorityBlockingQueue 是利用数组存储二叉堆实现。最小值(最优先)放在queue[0]位置。 //删除某个元素 public bool...

3727
来自专栏程序员互动联盟

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。 它提供的操作包括: 排序 so...

37812

扫码关注云+社区

领取腾讯云代金券