Java 细节汇总(4)-Arrays 中的双轴快排

待我称王封你为后i 2023-10-06 12:10 12阅读 0赞

#### 文章目录 ####

*  1. Arrays 中的双轴快排
 *  2. Java 中 switch 支持字符串的原理
 *  3. Java 中 break，continue 标签的用法
 *  4. Java 中 Math.ceil() 向上取整的用法
 *  5. Java notify() 方法不会立刻释放锁
 *  6. Java 中的 counted 循环

## 1. Arrays 中的双轴快排 ##

Jdk 1.7 之后，工具类 `Arrays` 中的排序方法在排序对象为基本数据类型的时候会使用`双轴快排`，这种排序方法比经典排序更快

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

如我们所知，`经典快排`会挑一个数(Pivot)把数组分成两份，而 `Dual-Pivot` 其实就是用两个Pivot，把整个数组分成三份

*  `经典快排核心思想`
    
    > 接受一个数组，挑一个数(Pivot)，把比这个数小的那一摊数放在它的左边，比它大的那一摊数放在它的右边，然后再对这个数左右两摊数递归的执行快排过程，直到子数组只剩一个数为止

我们通常用`时间复杂度`来衡量一个算法的性能，对于排序算法，时间复杂度的计算依据的是排序导致的元素比较的次数，主要和 CPU 相关。如果按照`元素比较次数`来比较的话，其实`双轴快排`的元素比较次数比`经典快排`要多，而`双轴快排`更快的原因如下，它拥有比经典快排更少的元素扫描动作

*  `CPU速度和内存速度的不匹配`
    
    > CPU速度远比内存速度更快，因为CPU会等待内存传输数据，内存墙(Memory Wall)的存在限制了程序运行速度。这种情况下，`元素比较次数`的多少已经无法完全反映算法优劣，因为这种比较的方法只考虑了CPU的因素，没有考虑内存的因素
 *  `新的性能衡量标准：扫描元素个数`
    
    > 为了解决时间复杂度无法反映算法真实性能的问题，双轴排序的作者提出了新的衡量标准，即`扫描元素个数`。这种标准把对于数组里面一个元素的访问 `array[i]` 称为一次扫描，对于同一个下标其对应的值不变的话，即使多次读写也只算一次扫描。这种标准实际反映的是CPU与内存之间的数据流量的大小，将比较慢的内存的因素也考虑进去了，更能体现算法在当下计算机里面的性能

参考: https://arxiv.org/pdf/1511.01138.pdf

--------------------

## 2. Java 中 switch 支持字符串的原理 ##

一个 `switch` 的使用示例如下，代码很简单，我们无法获知任何有关于其原理的信息，因为这些都被隐藏在虚拟机的实现里

public static void main(String[] args) {
        
            String s = "nathan";
            getString(s);
        }
        public static void getString(String s) {
        
            switch (s) {
        
                case "good":
                    System.out.println("good");
                    break;
                case "ok":
                    System.out.println("ok");
                    break;
                default:
                    System.out.println(s);
                    break;
            }
        }

编译以上代码，使用 IDEA 查看其 class 文件，立马在其中发现端倪。从反编译的文件中很明显可以看到，switch 支持字符串是通过 equals() 和 hashCode() 方法来实现的

> 仔细看可以发现，进行 switch 的实际是字符串 hashCode() 方法返回的 int 类型哈希值，case 命中后通过 equals() 方法进一步进行安全检查，以避免哈希碰撞导致的错误命中  
> 其实 switch 底层只支持整型数据，比如 byte、short、char(ASCII码是整型)以及int，其他数据类型都是转换成整型之后再使用的

public static void main(String[] args) {
        
            String s = "nathan";
            getString(s);
        }
    
        public static void getString(String s) {
        
            byte var2 = -1;
            switch(s.hashCode()) {
        
            case 3548:
                if (s.equals("ok")) {
        
                    var2 = 1;
                }
                break;
            case 3178685:
                if (s.equals("good")) {
        
                    var2 = 0;
                }
            }
    
            switch(var2) {
        
            case 0:
                System.out.println("good");
                break;
            case 1:
                System.out.println("ok");
                break;
            default:
                System.out.println(s);
            }
    
        }

--------------------

## 3. Java 中 break，continue 标签的用法 ##

Java 的控制循环结构中没有 `goto` 关键字，为了弥补这方面的不足，Java 提供了 `break` 和 `continue` 的标签用法。Java 中的标签就是一个紧跟着冒号`：`的标识符，标签必须放在循环前面才有作用，其语法示例如下，Java 中需要使用标签的唯一理由是想从多层嵌套中 break 或者 continue

> break redo 跳到 redo 处，且不再进入循环  
> continue redo 跳到 redo 处，且再次进入循环

public static void main(String[] args) throws Exception {
        
            redo:
            for (; ; ) {
        
                continue redo;
            }
        }

--------------------

## 4. Java 中 Math.ceil() 向上取整的用法 ##

Math.ceil() 里要求的参数为 double 类型，如果入参不符合要求，向上取整的计算结果可能不会符合预期

错误示例：

int a = 7, b = 2
    //  int 类型变量 a / b 的值为 3， 故Math.ceil() 计算的值依然为 3
    int c= (int) Math.ceil( a / b);

正确示例：

int a = 7, b = 2
    //  变量 a * 1.0 转化为 double 变量， 除以 b 的值为 3.5， Math.ceil() 计算的值则为 4
    int c= (int) Math.ceil( a * 1.0  / b);

--------------------

## 5. Java notify() 方法不会立刻释放锁 ##

在 Java 的 `synchronized` 关键字包裹的代码块中，`wait()` 方法被执行后锁自动被释放，但 notify() 方法执行完后，锁不会立即释放

> `notify()` 方法只会唤醒等待这把锁的其他线程，通知其可以重新竞争锁了，但是这把锁必须等到持有锁的线程执行完 `synchronized` 同步代码块之后才会真正释放

--------------------

## 6. Java 中的 counted 循环 ##

像`for (int i...)` 这种就是 counted循环(可数循环)，`for (long i...)` 是 Uncounted循环(不可数循环)，可数循环在 JDK 8 中默认不会埋安全点。所以当 JVM 尝试在安全点（例如主线程 sleep 较长时间的操作）停止用户线程进行定期清理时，如果子线程在一个 counted loop 里面做了一些很慢的操作，那很有可能导致其他线程都进入安全点阻塞，JVM 还在等这个 loop 的线程执行完毕进入安全点。这样就会导致一个问题，那就是主线程从 sleep 返回时发现 JVM 仍在尝试进行定期清理的过程中，那它只能把自己挂起，等待 JVM 操作完成后才能继续执行，这样主线程指定的 sleep 时长就不准确了