读 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) { //... }

原文发布于微信公众号 - 程序员互动联盟(coder_online)

原文发表时间:2016-06-06

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏拭心的安卓进阶之路

Java 集合源码解析(1):Iterator

Java, Android 开发也有段时间了,当初为了早点学 Android,Java 匆匆了解个大概就结束了,基础不够扎实。 虽然集合框架经常用,但是一直...

2165
来自专栏微信公众号:Java团长

Java HashMap的工作原理

面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下...

592
来自专栏Java Web

数据结构与算法(4)——优先队列和堆什么是优先队列?堆和二叉堆LeetCode相关题目整理

听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优...

3481
来自专栏专注研发

java大数(BigInteger)

 Math类:   java.lang.Math类中包含基本的数字操作,如指数、对数、平方根和三角函数。   java.math是一个包,提供用于执行任意精度整...

3222
来自专栏Android开发小工

Java集合解惑

本文取自工匠若水的qq群里的Java基础题目,把里面有关Java集合放在一起。 全文github地址

1112
来自专栏mukekeheart的iOS之旅

Java基础——集合框架

  Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型...

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

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

1433
来自专栏wannshan(javaer,RPC)

JDK PriorityBlockingQueue remove(Object o) 源码分析

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

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

Q125 Valid Palindrome

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

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

自己动手写一个单链表

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

2176

扫码关注云+社区