专栏首页程序员互动联盟读 Java Arrays 源码 笔记

读 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)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【编程基础】main函数,你知道多少?

    近期学习时对这个问题产生了迷惑,看到了这篇文章,感觉挺好。 在C/C++的学习过程中,一个很常见的问题就是void main和int main有什么区别呢?本文...

    程序员互动联盟
  • 【编程基础第九讲】main函数也有参数?

    存在问题: main函数我们使用的多关注的少,特别是参数,如何去用? 解决方案: 有C语言初学者朋友不知道怎么应用main函数的参数,其实也不难,只要对C语言...

    程序员互动联盟
  • 【答疑释惑】java中的全局变量

    首先,java中是没有全局变量这个概念的,java程序中不能像C++那样在类外定义全局变量,因为JAVA当初出现的初衷就是为了安全性和跨平台性,所以去掉了类似C...

    程序员互动联盟
  • 读 Java Arrays 源码 笔记

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

    yuxiaofei93
  • Spring Boot 2.x(十四):整合Redis,看这一篇就够了

    Redis 是一个开源的使用 ANSI C 语言编写、遵守 BSD 协议、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 ...

    山禾说
  • 张高兴的 Windows 10 IoT 开发笔记:串口红外编解码模块 YS-IRTM

    张高兴
  • 随机数_随机字符串

    用户6362579
  • 子集问题-LeetCode 78、52(无重复子集,N皇后II)

    给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明:解集不能包含重复的子集。 示例:

    算法工程师之路
  • 避免在ASP.NET Core中使用服务定位器模式

    题记:服务定位器(Service Locator)作为一种反模式,一般情况下应该避免使用,在ASP.NET Core更是需要如此。 Scott Allen在其博...

    逸鹏
  • BZOJ 1874: [BeiJing2009 WinterCamp]取石子游戏(SG函数)

    Description 小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的,每个人每次可以从一堆石子中取出若干个石子, 每次取石子的个数有限制,谁不能...

    attack

扫码关注云+社区

领取腾讯云代金券