第 2 章 Java 基础

太过爱你忘了你带给我的痛 2022-10-29 09:21 176阅读 0赞

# 第 2 章 Java 基础 #

## 1、58 同城 java 字符串常量池 ##

### 1.1、面试题代码 ###

代码

/**
     * @ClassName StringPool58Demo
     * @Description TODO
     * @Author Oneby
     * @Date 2020/12/23 10:52
     * @Version 1.0
     */
    public class StringPool58Demo {
        
        public static void main(String[] args) {
        
    
            String str1 = new StringBuilder("58").append("tongcheng").toString();
            System.out.println(str1);
            System.out.println(str1.intern());
            System.out.println(str1 == str1.intern());
    
            System.out.println("------------");
    
            String str2 = new StringBuilder("ja").append("va").toString();
            System.out.println(str2);
            System.out.println(str2.intern());
            System.out.println(str2 == str2.intern());
    
        }
    }

程序运行结果

58tongcheng
    58tongcheng
    true
    ------------
    java
    java
    false

### 1.2、代码讲解 ###

#### 1.2.1、intern() 方法 ####

> **`intern()` 方法的注释**

读一遍 `intern()` 方法的注释：当 `intern()` 方法被调用时

1.  如果字符串常量池中已经包含了此字符串（通过 `equals()` 方法判断），那么就将此字符串返回
2.  否则，该字符串将被添加至字符串常量池中，并且返回该字符串在常量池中的引用

![image-20201223110023309][]

> **以下内容摘自书本**

由于运行时常量池是方法区的一部分，所以这两个区域的溢出测试可以放到一起进行。前面曾经提到HotSpot从JDK7开始逐步“去永久代”的计划，并在DK8中完全使用元空间来代替永久代的背景故事，在此我们就以测试代码来观察一下，使用“永久代”还是“元空间”来实现方法区，对程序有什么实际的影响。

`String::intern()` 是一个本地方法，它的作用是如果字符串常量池中已经包含一个等于此String对象的字符串，则返回代表池中这个字符串的String对象的引用；否则，会将此String对象包含的字串添加到常量池中，并且返回此String对象的引用。在JDK6或更早之前的HotSpot虚拟机中，常量池都是分配在永久代中，我们可以通过 `-XX:PermSize` 和 `-XX:MaxPermSize` 限制永久代的大小，即可间接限制其中常量池的容量

#### 1.2.2、运行结果解释 ####

> **归根结底：“java” 已经提前被加载过了。。。**

为什么 `"58tongcheng"` 能输出 `true`？`new StringBuilder("58").append("tongcheng").toString();` 的结果是在堆中创建了一个值为 `"58tongcheng"` 的字符串，在 JDK8 中，将字符串常量池移到了堆中，因此只要堆中只要有值为 `"58tongcheng"` 的字符串，调用 `intern()` 方法返回的就是该字符串的引用

为什么 `"java"` 能输出 `false`？`"java"`字符串答案为 `false`，必然是两个不同的 `"java"`，那另外一个 `"java"` 字符串如何加载进来的？有一个初始化的 `"java"` 字符串(JDK 出娘胎自带的)， 在加载 `sun.misc.Version` 这个类的时候进入常量池

#### 1.2.3、OpenJDK8 源码 ####

> **递推步骤**

`System` 类 → `initializeSystemClass()` 方法 → `Version` 类 → 类加载器和 rt.jar → OpenJDK8源码

> **1、`System` 类**

哇哦~虚拟机会调用 `System.initializeSystemClass()` 方法完成对 `System` 类的初始化

![image-20201223110646246][]

> **2、`initializeSystemClass()` 方法**

在 `initializeSystemClass()` 方法中调用 `sun.misc.Version.init()` 完成了一些初始化工作

![image-20201223111205861][]

> **3、`Version` 类**

哇哦~ `Version` 类里面定义了一个 `launcher_name` 字段，其值为 `"java"`

![image-20201223110959457][]

> **4、类加载器和 rt.jar**

根加载器 bootstrap 会提前部署加载 rt.jar，Version 这个类就在 rt.jar 包中，位于 sun.misc 包下

![image-20201223111822760][]

> **5、OpenJDK8源码**

官网地址：http://openjdk.java.net/

类所在的路径：openjdk8\\jdk\\srclshare\\classes\\sun\\misc

![image-20201223112231717][]

### 1.3、考查点 ###

> **是否读过经典JVM书籍：《深入理解java虚拟机》书原题**

1.  代码：
    
    ![image-20201223111348446][]
2.  解释：
    
    ![image-20201223111359439][]

## 2、字节跳动两数求和 ##

### 2.1、[题目要求][Link 1] ###

> **题目描述**

![image-20201226204959392][]

### 2.2、代码实现 ###

> **1、暴力法**

双层 for 循环解决，缺点是时间复杂度为 O(n2)

class Solution {
        
        public int[] twoSum(int[] arr, int target) {
        
            for (int i = 0; i < arr.length; i++) {
        
                for (int j = i + 1; j < arr.length; j++) {
        
                    if (arr[i] + arr[j] == target) {
        
                        return new int[]{
        i, j};
                    }
                }
            }
            return null;
        }
    }

> **2、方便理解的 HashMap 版本**

HashMap 查询的时间复杂度为 O(1)，因此利用 HashMap 可以将算法复杂度降为 O(n)

// HashMap 版本
    class Solution {
        
        public int[] twoSum(int[] arr, int target) {
        
            HashMap<Integer, Integer> valueToIndex = new HashMap<>();
    
            // 构造 HashMap，Key 是数组元素的值，Value 是数组元素的下标
            for (int i = 0; i < arr.length; i++) {
        
                valueToIndex.put(arr[i], i);
            }
    
            for (int i = 0; i < arr.length; i++) {
        
                // arr[i] + remain = target
                int remain = target - arr[i];
                // remain 在 HashMap 中，且 remain 对应的下标和 arr[i] 对应的下标不同
                if (valueToIndex.containsKey(remain) && (valueToIndex.get(remain) != i)) {
        
                    return new int[]{
        i, valueToIndex.get(remain)};
                }
            }
    
            return null;
        }
    }

> **3、使用一次循环的版本**

边遍历边判断

class Solution {
        
        public int[] twoSum(int[] arr, int target) {
        
            HashMap<Integer, Integer> valueToIndex = new HashMap<>();
    
            for (int i = 0; i < arr.length; i++) {
        
                // arr[i] + remain = target
                int remain = target - arr[i];
                // 如果存在于 HashMap 之中，就返回数组下标
                if (valueToIndex.containsKey(remain)) {
        
                    return new int[]{
        valueToIndex.get(remain), i};
                }
                // 否则记录数组元素的值和下标
                valueToIndex.put(arr[i], i);
            }
    
            return null;
        }
    }

## 3、字节跳动手写LRUs算法 ##

见redis最后（请坚持到最后一章）

[image-20201223110023309]: /images/20221024/b13594b49c604b1391506632db5acc85.png
[image-20201223110646246]: /images/20221024/fb8f4ba7901a4010a36cf8dabd9ae74a.png
[image-20201223111205861]: /images/20221024/185f877ec1b74293b4780412bbab0ad0.png
[image-20201223110959457]: /images/20221024/edef9dd7abef4c91a6dbd6234df46374.png
[image-20201223111822760]: /images/20221024/09b88bc13b0849d3b949922dc4a4a38e.png
[image-20201223112231717]: /images/20221024/df05a06439e0444aa675eb56252b8e56.png
[image-20201223111348446]: /images/20221024/5cd9b2eb8ef44edda3fb99551bad1775.png
[image-20201223111359439]: /images/20221024/e71d9c5fe57b41729fba3968f601f89a.png
[Link 1]: https://leetcode-cn.com/problems/two-sum/
[image-20201226204959392]: /images/20221024/97aebeb1c36d4626b982315c72d30509.png