Arrays.java

相关类：

* /Library/Java/JavaVirtualMachines/openjdk-11.0.1.jdk/Contents/Home/lib/src.zip!/java.base/java/util/Arrays.java
* /Library/Java/JavaVirtualMachines/openjdk-11.0.1.jdk/Contents/Home/lib/src.zip!/java.base/jdk/internal/util/ArraysSupport.java
* /Library/Java/JavaVirtualMachines/openjdk-11.0.1.jdk/Contents/Home/lib/src.zip!/java.base/java/util/DualPivotQuicksort.java

easy: fill, equals, toString, copyOf, copyOfRange, hashCode, binarySearch

medium: compare, compareUnsigned​, mismatch, sort

have not learnt: parallelPrefix​, parallelSetAll,parallelSort​,setAll​,spliterator,stream​

have not learnt: deepEquals, deepHashCode, deepToString

1.binarySearch

注意float和double的写法:

1.数组排序后：[-Infinity, -0.0, 0.0, Infinity, NaN]

2.一些定义以及实验：

public static final float NaN = 0.0f / 0.0f;

jshell> Float.floatToIntBits(Float.NaN)
$19 ==> 2143289344

jshell> Float.floatToIntBits(0.0f / 0.0f)
$20 ==> 2143289344

jshell> Float.floatToIntBits(Float.POSITIVE_INFINITY)
$21 ==> 2139095040

jshell> Float.floatToIntBits(Float.NEGATIVE_INFINITY)
$22 ==> -8388608

jshell> Float.floatToIntBits(0.0f)
$27 ==> 0

jshell> Float.floatToIntBits(-0.0f)
$28 ==> -2147483648

jshell> 2 > 1.0f/0.0f
$31 ==> false

jshell> 2 < 1.0f/0.0f
$32 ==> true

jshell> 2 < Float.NaN
$29 ==> false

jshell> 2 > Float.NaN
$30 ==> false           //所以如果target是NaN，会进入else进行比较

jshell> -0.0 < 0      //所以如果target是0.0或者-0.0，会进入else进行比较
$38 ==> false

参考：https://stackoverflow.com/a/55673220

3.binarySearch代码：

private static int binarySearch0(float[] a, int fromIndex, int toIndex,
                                    float key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        float midVal = a[mid];

        if (midVal < key)
            low = mid + 1;  // Neither val is NaN, thisVal is smaller
        else if (midVal > key)
            high = mid - 1; // Neither val is NaN, thisVal is larger
        else {
            int midBits = Float.floatToIntBits(midVal);
            int keyBits = Float.floatToIntBits(key);
            if (midBits == keyBits)     // Values are equal
                return mid;             // Key found
            else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN): 如果0.0或NaN是target，-0.0和0.0出现在数组中
                low = mid + 1;
            else                        // (0.0, -0.0) or (NaN, !NaN)
                high = mid - 1;
        }
    }
    return -(low + 1);  // key not found. 返回-low-1
}

2.Arrays.asList

  • 作用： The method acts as bridge between array-based and collection-based APIs.
  • 为什么需要转换：为了效率和功能之间的选择
  • 注意点和正确使用方法
Integer[] original = {1, 3, 4}; //初始数组Integer[]
// List<Integer> correct = new ArrayList<Integer>(original); // 没有这个方法
List<Integer> intermediate = Arrays.asList(original); // 实际上生成的是Arrays中private class ArrayList，和真正的ArrayList不是一个类
// intermediate.add(1); // Unsupported operation..
List<Integer> correct = new ArrayList<Integer>(Arrays.asList(original)); //正确的初始化方法

另外toArray()方法存在于在Arrays中的private class ArrayList和真正的ArrayList中，所以ArrayList都能转换成数组。

toString, fill

这两个方法比较简单

public static String toString(int[] a) {
    if (a == null)
        return "null"; // 返回的是字符串null而不是null
    int iMax = a.length - 1;
    if (iMax == -1)
        return "[]";

    StringBuilder b = new StringBuilder();
    b.append('[');
    for (int i = 0; ; i++) {
        b.append(a[i]);
        if (i == iMax)
            return b.append(']').toString(); // 只有一个return语句，iMax减少了边界的计算
        b.append(", ");
    }
}

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

equals, compare, mismatch

这仨都用到了ArraysSupport.mismatch, 最底层的mismatch返回数组中从第一个不相等元素的index，如果没有返回-1。原理是用二进制进行xor。

// 比较数组是否相等：逻辑是看若有一个元素不相等，立刻返回。所以不能找出所有不相等的元素。
public static boolean equals(int[] a, int[] a2) {
    if (a==a2)
        return true;
    if (a==null || a2==null)
        return false;

    int length = a.length;
    if (a2.length != length)
        return false;

    return ArraysSupport.mismatch(a, a2, length) < 0; // 进行int和boolean的转换
}

// 0: equal, -1: less than, 1: greater than
public static int compare(int[] a, int[] b) {
    if (a == b)
        return 0;
    if (a == null || b == null)
        return a == null ? -1 : 1;

    int i = ArraysSupport.mismatch(a, b,
                                    Math.min(a.length, b.length));
    if (i >= 0) {
        return Integer.compare(a[i], b[i]);
    }

    return a.length - b.length; // 如果前面元素都相等则比较长度
}

// 用来单纯的调用
public static int mismatch(int[] a, int[] b) {
    int length = Math.min(a.length, b.length); // Check null array refs
    if (a == b)
        return -1;

    int i = ArraysSupport.mismatch(a, b, length);
    return (i < 0 && a.length != b.length) ? length : i;
}

其他需要注意的一些方法：

private static int exactLog2(int scale) {
    if ((scale & (scale - 1)) != 0) // trick: 确认是否为2的power，和leetcode的一题很像
        throw new Error("data type scale not a power of two");
    return Integer.numberOfTrailingZeros(scale); // 计算二进制尾部0的个数。func(8) = 3; fuc(170) = 1
}

3.hashCode

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

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

    return result;
}

Arrays.hashCode的目的：让地址相同的数组根据elements内容计算出不同的hashvalue

一般情况下重写hashCode的目的：逻辑上不以Object地址为判断相等对象的时候需要进行重写判断相等，比如红色的苹果需要被看成相同的苹果。

Object a1 = new Object();
Object a2 = new Object();
Object a3 = new int[] {1, 2,3};

Object[] apple = {a1, a2};
System.out.println(apple.hashCode());
System.out.println(Arrays.hashCode(apple)); // -2062837901
apple[0] = a3;
System.out.println(apple.hashCode()); // should be the same : 1142020464
System.out.println(Arrays.hashCode(apple)); // should be different: -366009229

4.copyOf

调用JVM中的代码

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

@HotSpotIntrinsicCandidate
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

5. sort

6. parallelSort

切割数组进行同时排序。有最低数组大小的限制(1<<13=8192)。如果太小，会因为memory contention限制而导致不如普通排序

其他

  • 注意边界检查
static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
    if (fromIndex > toIndex) {
        throw new IllegalArgumentException(
                "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
    }
    if (fromIndex < 0) {
        throw new ArrayIndexOutOfBoundsException(fromIndex);
    }
    if (toIndex > arrayLength) {
        throw new ArrayIndexOutOfBoundsException(toIndex);
    }
}
  • 多个内部私有函数封装API, 通常都有对全部数组或者局部数组操作的方法
  • 注意内部类和Generics的写法

一些常识

results matching ""

    No results matching ""