Maven是什么

Maven是一个免费、开源的，用Java编写的项目构建和依赖管理工具。

Maven的特点

• 默认的目录结构
• 第三方依赖管理
  通过配置pom.xml文件，从远程仓库下载相关Jar包。解决了依赖维护问题。
• 提供了一致的项目构建管理方式
  生命周期。减少了构建工作量。
• 插件式架构，大量的可重用插件
• 方便地集成于IDE

Tomcat简介

Tomcat是一个典型的Web应用服务器软件，通过运行Tomcat服务器，我们就可以快速部署我们的Web项目，并交由Tomcat进行管理，我们只需要直接通过浏览器访问我们的项目即可。

---

安装及配置

当前支持的版本：

Apache Tomcat® - Which Version Do I Want?

Servlet Spec	JSP Spec	EL Spec	Apache Tomcat Version	Supported Java Versions
6.1	4.0	6.0	11.0.x	17 and later
6.0	3.1	5.0	10.1.x	11 and later
4.0	2.3	3.0	9.0.x	8 and later

Apache Tomcat® - Apache Tomcat 10 Software Downloads下载压缩包64-bit Windows zip，解压到合适的目录文件下，运行bin目录下的startup.bat/shutdown.bat，即可启动/关闭 Tomcat。

conf文件夹

conf文件夹下放置tomcat的配置文件，其中server.xml是服务器核心配置文件。

• 连接端口相关设置

• 主机相关设置

  默认端口号为8080.

  <Serveice name="Catalina">
      <!-- 默认端口号：8080 -->
      <Connector port="8080" protocol="HTTP/1.1" 
                 connectionTimeout="20000"
                 redirectPort="8443" />
      
      <!-- 默认主机名称：localhost 等价于127.0.0.1 -->
      <!-- 默认网站应用存放的根目录：webapps -->
      <Host name="localhost" appBase="webapps"
            unpackWARs="true" autoDeploy="true">
  </Serveice>

---

环境变量

环境变量的配置可选，真实的开发环境，都是在IDEA中操作。

如有需要，后续补充

---

部署项目到Tomcat

一般的项目结构：

• webapps：Tomcat服务器的web目录

  • ROOT

  • 项目名

    • WEB-INF

      • classes：java程序
      • lib：依赖的jar包
      • web.xml：网站的配置文件

    • index.html：默认的首页

    • static

      • css
        • style.css
      • js
      • img

    • …

---

手动

将自己写的网页放到tomcat中网站应用(webapps)文件夹下，就可以访问了。

版本控制工具

版本控制是一种记录一个或若干文件内容变化，以便将来查阅特定版本修订情况的系统。版本控制能方便查看更改历史，备份以及恢复以前的版本，保证多人协作不出问题。

Git对待数据的方式，更像是把数据看作是对小型文件系统的一组快照。每次提交更新或者在Git中保存项目状态时，它主要对当时的全部文件制作一个快照并保存这个快照的索引。为了高效，如果文件没有修改，Git不再重新存储该文件，而只是保留一个链接指向之前存储的文件，Git对待数据更像是一个快照流。

概述

水杉码园使用Go语言，基于Gitea开发。本文用于记录如何入坑开发。

---

开发机

先用Cisco的VPN登录，再连接开发机。

待完善……

---

Windows环境下clone代码

水杉码园的代码存储在gitlab上：ShuiShan / Gitea / gitea · GitLab。并且该地址需要拥有项目管理权限的人员（徐柴笛、周成义、李苗进、顾业鸣）进行授权才可访问。

clone代码的操作：

1. 安装Git
2. Clone With HTTPS
   1. 先在命令行执行git config --global http.sslVerify false
   2. git clone https://code.kfcoding.com/ShuiShan/Gitea/gitea.git

---

Windows下环境搭建

1. 安装go

2. 安装node.js(一定要勾选会附带安装chocolatey的选项)

3. 安装make（choco install make）

4. 设置npm的国内镜像代理npm config set registry https://registry.npm.taobao.org

5. 在Clone的项目文件夹下(\gitea)，执行TAGS="bindata" make build

6. 本地测试，执行./gitea web

7. 浏览器访问http://localhost:3000/

8. 登录水杉码园，配置本地数据库信息，记住要在可选设置中设置管理员账号

   

node版本如何升级 - 知乎

---

使用VS Code进行开发

• 解决 VS Code 中 golang.org 被墙导致的 Go 插件安装失败问题 - 简书

• vscode在windows10系统下进行go语言编程(无法代码提示)_新广州人的网络安全-CSDN博客

• 安装git历史提交记录插件 GitLens

---

课程批量导入学生

• 入口：/org/:org/teams/new_all_student

导入完成后，课程团队下会生成指定的团队：

团队为成员-仓库的形式

• Owners

  管理员-管理的仓库

• AllStuRead

  教师有操作权限，学生只有读权限。用于老师布置作业，分享数据、资料。

• AllStuWrite

  所有学生都有操作权限

课程中的仓库，除了AllStuWrite和AllStuRead这两个公开仓库之外，每个学生还有自己的个人仓库，目前以学号作为仓库名。仓库描述为student u.Name(学号) u.FullName(用户名)'s repo。

---

代码

1. routes.go下，m.Post("/teams/new_all_student", bindIgnErr(auth.CreateAllStuTeamForm{}), org.NewAllStuTeamPost)

   • auth.CreateAllStuTeamForm{}相当于是前端的表单

     其中的Studentlist表示的上传的excel文件

   这个Post函数将前端的表单传入后端的NewAllStuTeamPost函数，

2. 细看一下NewAllStuTeamPost方法

   • 首先是通过前端的form获取相应的基本信息

   • 再来我们可以先看一下这个函数最后的部分GetCache().Set

     这里把课程ID(Organization.ID)设置了1分钟的缓存

   • 再回过头来看上边的代码，如果能在缓存中获取到课程ID的缓存，说明之前一分钟内有过成功导入的记录，就会给出一个不要多次导入的提示并结束导入学生的操作

---

批量移除选中的仓库

---

批量删除成员

数组与矩阵

5. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例1：

输入：s = "We are happy."
输出："We%20are%20happy."

限制：

0 <= s 的长度 <= 10000

在网络编程中，如果URL参数中含有特殊字符，如空格、#等，则可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32,即十六进制的0x20,因此空格被替换成”%20”。再比如#的ASCII码为35，即十六进制的0x23，它在URL中被替换为”%23”。

如果是在原来的字符串上进行替换，就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上进行替换，那么我们可以自己分配足够多的内存。由于有这样两种不同的解决方案，我们应该向面试官问清楚，让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上进行替换，并且保证输入的字符串后面有足够多的空余内存。

最直观的做法是从头到尾扫描字符串，每次碰到空格时进行替换。这样做，每次碰到空格就需要把空格后面的所有字符都后移2字节。假设字符串的长度是n。对每个空格字符，需要移动后面$O(n)$个字符，因此对于含有$O(n)$个空格字符的字符串而言，总的时间效率是$O(n^2)$。这显然不是一个好的解决方案。

那么，怎么操作能减少移动次数呢？—— 试试把从前向后替换改成从后向前替换。(对于Java来说，String是不可变的，因此，严谨地说，OJ题提供的方法头的参数应该由String改为StringBuffer。)

public String replaceSpace(String s) {
	StringBuffer str = new StringBuffer(s); //将String转换为StringBuffer（可变长度）
    int P1 = str.length() - 1; //模拟指针
    for (int i = 0; i <= P1; i++)
        if (str.charAt(i) == ' ') 
            str.append("  "); //出现一个空格，就在字符串末尾添加2个任意字符

    int P2 = str.length() - 1; // 模拟指针，初始指向 将空格替换后的最后一位
    while (P1 >= 0 && P2 > P1) { //从后往前遍历，能保证原来的字符串不会因为替换字符而改变
        char c = str.charAt(P1--); // 获取原始字符串的最后一位字符
        if (c == ' ') {
            str.setCharAt(P2--, '0');
            str.setCharAt(P2--, '2');
            str.setCharAt(P2--, '%');
        } else {
            str.setCharAt(P2--, c);
        }
    }
    return str.toString();
}

时间复杂度和空间复杂度都是$O(n)$​。

---

29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：

• 0 <= matrix.length <= 100
• 0 <= matrix[i].length <= 100

矩阵不一定是方阵，四个顶点的坐标是临界点。

public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) { // 矩阵为空
            return new int[0];
        }

        int left = 0;
        int right = matrix[0].length - 1;
        int top = 0;
        int bottom = matrix.length - 1;
        int[] result = new int[(right + 1) * (bottom + 1)];
        int index = 0;

        while(true) {
            for (int i = left; i <= right; i++)  // 遍历top行
                result[index++] = matrix[top][i];
            if (++top > bottom) // 没有新的行，则遍历完成
                break;

            for (int i = top; i <= bottom; i++) 
                result[index++] = matrix[i][right];
            if (--right < left) // 没有新的列
                break;

            for (int i = right; i >= left; i--) 
                result[index++] = matrix[bottom][i];
            if (--bottom < top) // 没有新的行
                break;
            
            for (int i = bottom; i >= top; i--) 
                result[index++] = matrix[i][left];
            if (++left > right) // 没有新的列
                break;
        }
        return result;
    }

---

50. 第一个只出现一次的字符位置

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

限制：

0 <= s 的长度 <= 50000

统计字符是否仅出现一次，可以用容器存放每个字符是否只出现一次。这个容器可以根据<字符>来存放<是否多次出现>的信息。因此，可以利用哈希表。

public char firstUniqChar(String s) {
    HashMap<Character, Boolean> hm = new HashMap(); // 用布尔值表示是否只有一个字符，比用Integer统计出现次数节约空间
    char[] s2c = s.toCharArray();
    for(char c : s2c) {
        hm.put(c, !hm.containsKey(c)); // 如果已有该字符，false；否则true
    }
    for(char c : s2c) { // 按字符顺序遍历，能返回第一个只出现一次的字符
        if(hm.get(c) == true)
            return c;
    }
    return ' ';
}

时间复杂度$O(n)$​，空间复杂度$O(1)$​

---

栈、队列、堆

9. 用两个栈实现队列

剑指 Offer 09. 用两个栈实现队列 - 力扣（LeetCode）

• 栈是LIFO（后进先出），队列是FIFO（先进先出）。
• 将一个栈专门用于插入整数，另一个栈专门用于删除整数
• Stack类已被Java不推荐使用，LinkedList基于双向链表实现，只能顺序访问，但可以快速插入和删除元素。LinkedList可用作栈、队列和双向队列。

private LinkedList<Integer> list1, list2;

public CQueue() {
    list1 = new LinkedList<>();
    list2 = new LinkedList<>();
}

public void appendTail(int value) {
    list1.addLast(value); // 加到链表尾部
}

public int deleteHead() {
    if (!list2.isEmpty()) { //list2中的元素都在list1之前进入栈中
        return list2.removeLast();
    }
    if (list1.isEmpty()) { //模拟的队列中没有元素了
        return -1;
    }

    while (!list1.isEmpty()) { //将list1中已存在的元素都移入list2中
        list2.addLast(list1.removeLast());
    }
    return list2.removeLast();
}

时间复杂度：$O(n)$（deleteHead()函数在N次队首元素删除操作中总共需完成N个元素的倒序），空间复杂度$O(n)$。

---

30. 包含min函数的栈

剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）

既然是定义栈，那么push和pop功能显然不用再变动，重点在于实现min函数。栈中的最小元素会随着元素的入栈和出栈动态变化，因此需要记录每个状态对应的当前最小元素。可以构造一个辅助栈来实现。

private LinkedList<Integer> stack, minStack;

public MinStack() {
    stack = new LinkedList<>();
    minStack = new LinkedList<>();
}

public void push(int x) { //插入元素，同时记录当前最小的元素
    stack.addLast(x);
    minStack.addLast(minStack.isEmpty() ? x : Math.min(minStack.getLast(), x));
}

public void pop() { // 同步更新最小值
    stack.removeLast();
    minStack.removeLast();
}

public int top() {
    return stack.getLast();
}

public int min() {
    return minStack.getLast();
}

---

31. 栈的压入、弹出序列

剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）

一个序列是否为栈的弹出序列的规律：

1. 如果当前栈顶的数字是下一个弹出的数字，则弹出；
2. 如果当前栈顶的数字不是下一个弹出的数字，把还未入栈的数字压入栈中，直至栈顶的数字是下一个弹出的数字
3. 如果所有数字都入栈的过程中，栈顶数字始终不是需要弹出的数字，则不可能是弹出序列
4. 栈中数字全部顺利出栈，则为弹出序列

public boolean validateStackSequences(int[] pushed, int[] popped) {
    if(pushed.length == 0)
        return true;
    LinkedList<Integer> stack = new LinkedList<> ();
    int i = 0;
    for(int num : pushed) { // 遍历入栈顺序数组
        stack.addFirst(num); // 入栈
        while(!stack.isEmpty() && stack.getFirst() == popped[i]) { // 当前栈不为空，且 栈顶元素为出栈元素时
            stack.removeFirst(); // 出栈
            i++;
        }
    }
    return stack.isEmpty(); // 如果都顺利出栈，则说明弹出序列是正确的
}

时间复杂度：$O(n)$（每个元素最多进栈1次，出栈1次，$O(2n)$）​；空间复杂度：$O(n)$

---

40. 最小的K个数

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）

快速排序每次都能将选定的哨兵置于排序完成后的最终位置，当前的哨兵最终位置索引为K时，比它小的K个数将全在左侧。

public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length)
            return arr; //不限制输出顺序
        return quickSort(arr, k, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int k, int left, int right) {
        int i = left, j = right;
        while (i < j) { // 分别从左右开始，直至"相遇"；默认取第一个元素为哨兵（arr[left]）
            while (i < j && arr[j] >= arr[left]) { // 从右往左，找到比哨兵小的数（且保证左右未相遇）
                j--;
            }
            while (i < j && arr[i] <= arr[left]) { // 从左往右，找到比哨兵大的数
                i++;
            }
            swap(arr, i, j); // 交换位置（比哨兵小的放在左边，大的放在右边）
        }
        swap(arr, i, left); // 将哨兵置于最终位置i
        // 【递归判断】优化时间复杂度的关键
        if (i > k) { // 确认最终位置的哨兵，其左侧的数 > k，比最终需要的数多，继续递归
            return quickSort(arr, k, left, i - 1);
        }
        if (i < k) {
            return quickSort(arr, k, i + 1, right);
        }
        return Arrays.copyOf(arr, k); //哨兵左侧的数 = k 个，复制数组左侧的k个数，无需再进行完整的排序
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

• 时间复杂度$O(n)$： 其中n为数组元素数量；对于长度为n的数组执行哨兵划分操作的时间复杂度为$O(N)$；每轮哨兵划分后根据k和i的大小关系选择递归，由于i分布的随机性，则向下递归子数组的平均长度为$\frac{N}{2}$；因此平均情况下，哨兵划分操作一共有$N + \frac{N}{2} + \frac{N}{4} + … + \frac{N}{N} = \frac{N - \frac{1}{2}}{1 - \frac{1}{2}} = 2N - 1$（等比数列求和），即总体时间复杂度为$O(n)$。
• 空间复杂度$O(\log n)$：划分函数的平均递归深度为$O(\log n)$。

---

41. 数据流中的中位数

剑指 Offer 41. 数据流中的中位数 - 力扣（LeetCode）

• 通过建立一个大顶堆和一个小顶堆（PriorityQueue），将数据流拆分为两部分，根据两个堆顶元素就能得到中位数。

• 添加元素过程中，要保证两个堆的大小平衡

private Queue<Integer> minHeap, maxHeap;

public MedianFinder() {
    minHeap = new PriorityQueue<>(); // 默认构造小顶堆，保存较大的一半
    maxHeap = new PriorityQueue<>((x, y) -> (y - x)); //lambda表达式，大顶堆，保存较小的一半
}

public void addNum(int num) {
    if (minHeap.size() == maxHeap.size()) { // 添加新的整数后，会是奇数个数值
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll()); //取出最大堆中最大的数放入最小堆中 --> 中位数在最小堆的堆顶
    } else { // 添加新的整数后，会是偶数个数值（奇数个数值时，最小堆的数值更多）
        minHeap.offer(num);
        maxHeap.offer(minHeap.poll()); // 取出最小堆中的最大数放入最大堆
    }
}

public double findMedian() {
    return minHeap.size() == maxHeap.size() ? (minHeap.peek() + maxHeap.peek()) / 2.0 : minHeap.peek();
}

时间复杂度：

• 查找中位数$O(1)$：获取堆顶元素使用$O(1)$时间；
• 添加数字$O(\log N)$：堆的插入和弹出操作使用$O(\log N)$时间。

空间复杂度：$O(N)$

---

59.1 滑动窗口的最大值

剑指 Offer 59 - I. 滑动窗口的最大值（单调队列，清晰图解） - 滑动窗口的最大值 - 力扣（LeetCode）

如何在窗口每次滑动时，获取最大值？使用双端队列存储当前滑动窗口中的最大值以及在后续窗口中潜在的最大值。

每轮窗口滑动：

1. 如果滑出窗口的数是队首数字，则队首数字也出队（队列的大小必然<=窗口大小）
2. 如果新进入窗口的数比队尾的数大，说明队尾的数不可能成为某个窗口的最大值。将队尾元素移除，直到队尾的数字>=新进入窗口的数或队列已空。
3. 如果新进入窗口的数比队尾的数小，说明等之前的数滑出窗口后，有可能会成为后续窗口中的最大值，因此，直接加入队尾。

private Deque<Integer> deque;
public int[] maxSlidingWindow(int[] nums, int k) {
    if(nums.length == 0) {
        return new int[0];
    }
    int[] result = new int[nums.length - k + 1];
    int index = 0;
    deque = new LinkedList<>(); //双端队列，存储每个窗口中的最大值
    // 先形成一个窗口
    for(int i = 0; i < k; i++) {
        while(!deque.isEmpty() && deque.getLast() < nums[i]) { // 队列不为空，且队尾元素 < 当前进入窗口的数字
            deque.removeLast();
        }
        deque.addLast(nums[i]);
    }
    result[index++] = deque.getFirst(); // 第一个窗口中的最大值入队
    // 窗口形成后
    for(int i = k; i < nums.length; i++) {
        if(nums[i - k] == deque.getFirst()) // 如果滑出窗口的数是队首数字
            deque.removeFirst(); // 队首数字也出队
        while(!deque.isEmpty() && deque.getLast() < nums[i]) { // 队列不为空，且队尾元素 < 当前进入窗口的数字
            deque.removeLast();
        }
        deque.addLast(nums[i]);
        result[index++] = deque.getFirst();
    }
    return result;
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

---

双指针

57.1 和为S的两个数字

剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode）

递增排序的数组，查找两个数使得和为s——双指针

public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left < right) {
        if(nums[left] + nums[right] == target) {
            return new int[] {nums[left], nums[right]};
        } else if (nums[left] + nums[right] < target) { //需要更大的数
            left++;
        } else (nums[left] + nums[right] > target) { //需要更小的数
            right--;
        }
    }
    return new int[0];
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

---

57.2 和为s的连续正数序列

剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（LeetCode）

连续正整数序列 & 求和——双指针

• 遍历的终点：序列中最小的数 * 2 + 1 > target

• 双指针可以模拟滑动窗口

  滑动窗口的右指针无需向左移动，必然能遍历所有解。

public int[][] findContinuousSequence(int target) {
    int left = 1, right = 2;
    List<int[]> list = new ArrayList<>();
    int sum = 3; // 初始滑动窗口中数字的和
    while (left <= target / 2) {
        if (sum == target) {
            int[] result = new int[right - left + 1];
            for(int i = 0; i < right - left + 1; i++) {
                result[i] = left + i;
            }
            list.add(result);
        }
        if (sum < target) { // 向右移动右指针
            sum += ++right;
        } else { // 连续正数的和 >= target
            sum -= left++; //向右移动左指针
        }
    }
    return list.toArray(new int[0][]); //参数为 返回的数组类型(存储数组的数组)，不指定则为Object
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

---

58.1 翻转单词顺序列

剑指 Offer 58 - I. 翻转单词顺序 - 力扣（LeetCode）

public String reverseWords(String s) {
    s = s.trim(); // 去除首尾空格
    StringBuilder sb = new StringBuilder();
    int i = s.length() - 1;
    int j = i;
    while (i >= 0) {
        while(i >= 0 && s.charAt(i) != ' ') { //找到句中空格或遍历结束
            i--;
        }
        sb.append(s.substring(i+1, j + 1) + ' ');
        while(i >= 0 && s.charAt(i) == ' ') { //跳过多余的空格
            i--;
        }
        j = i;
    }
    return sb.toString().trim();
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

---

58.2 左旋转字符串

剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode）

public String reverseLeftWords(String s, int n) {
    StringBuilder sb = new StringBuilder();
    sb.append(s.substring(n, s.length()));
    sb.append(s.substring(0, n));
    return sb.toString();
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

---

链表

6. 从尾到头打印链表

剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode）

public int[] reversePrint(ListNode head) {
    List<Integer> list = new ArrayList<>();
    while(head != null) {
        list.add(head.val);
        head = head.next;
    }
    int[] result = new int[list.size()];
    for(int i = result.length - 1; i >= 0; i--) {
        result[i] = list.get(result.length - 1 - i);
    }
    return result;
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

---

18. 删除链表的节点

剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode）

• 无需存储所有节点，找到被删的节点，修改前一个节点的next节点即可——双指针

public ListNode deleteNode(ListNode head, int val) {
    if(head.val == val) { // 头结点即为被删的节点
        return head.next;
    }
    ListNode pre = head;
    ListNode cur = pre.next;
    while(cur.val != val) {
        pre = cur;
        cur = cur.next;
    }
    pre.next = cur.next;
    return head;
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$​

---

22. 链表中倒数第K个节点

剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）

双指针

public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode right = head;
    ListNode left = head;
    for(int i = 0; i < k; i++) { //只要让第二个指针落后于第一个指针k位，遍历完成时，即能得到倒数第k个节点
        right = right.next;
    }
    while(right != null) {
        right = right.next;
        left = left.next;
    }
    return left;
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

---

23. 链表中环的入口节点

剑指 Offer II 022. 链表中环的入口节点 - 力扣（LeetCode）

方式一：利用HashSet存储ListNode，判断后续遍历的节点是否已经在集合中。时间复杂度：$O(n\log n)$；空间复杂度$O(n)$。

方式二：一快一慢的双指针。

• 一快一慢的指针，让快的速度是慢的2倍，如果存在环，快的指针将会追上慢的指针。

• 指针到达相同节点后，如何得知入口节点？

  当前指针继续往前走向入口节点的距离 == 头结点到达入口节点的距离

  假设环入口节点为$y_1$，相遇所在节点为$z_1$。(头结点到达入口节点的距离为$X$，入口节点到达相遇节点的距离为$Y$，相遇节点到达入口节点的距离为$Z$)

  假设快指针 fast 在圈内绕了$N$圈，则总路径长度为$X+NY+(N-1)Z$​。$Z$为$N-1 $倍是因为快慢指针最后已经在$z_1$节点相遇了，后面就不需要再走了。

  而慢指针slow总路径长度为$X+Y$。

  因为快指针是慢指针的两倍，因此$X+NY+(N-1)Z = 2(X+Y)$。

  我们要找的是环入口节点$y_1$​​​，也可以看成寻找长度$X$​​的值，因此我们先将上面的等式转换为：$X=(N-2)Y+(N-1)Z = (N-2)(Y+Z)+Z$​​​。$Y+Z$​​​是圆环的总长度，右边可以看作从相遇点$z_1$​开始在圆环中走过$N-2$​圈，再走长度为$Z$​​​的长度。可以发现如果让两个指针同时从起点$x_1$​和相遇点$z_1$​开始，每次只走过一个距离，那么最后他们会在环入口节点相遇。

public ListNode detectCycle(ListNode head) {
    ListNode fast = head; // 创建一快一慢的指针，快的速度是慢的2倍
    ListNode slow = head;
    while(fast != null && slow != null) {
        fast = fast.next.next; // 一次前进两个节点
        slow = slow.next; // 一次前进一个节点
        if(fast == slow) { // 快的指针追上了慢的指针，说明存在环
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
    }
    return null;
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$​

---

24. 反转链表

剑指 Offer 24. 反转链表 - 力扣（LeetCode）

public ListNode reverseList(ListNode head) {
    ListNode cur = head; // 1
    if(cur == null) {
        return null;
    }
    ListNode nextNode = cur.next; // 2
    head.next = null;
    ListNode preNode = head; // 1
    while(nextNode != null) {
        cur = nextNode; // 2
        nextNode = nextNode.next; // 3
        cur.next = preNode; // 1
        preNode = cur; 
    }
    return cur;
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

---

25. 合并两个排序的链表

剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(1); // 创建一个任意的节点
    ListNode cur = head;
    while(l1 != null && l2 != null) {
        if(l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    cur.next = l1 != null ? l1 : l2;
    return head.next;
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$

---

35. 复杂链表的复制

剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）

• 利用哈希表，构建原链表节点和新链表对应节点的映射关系。

public Node copyRandomList(Node head) {
    Map<Node, Node> hm = new HashMap<>();
    Node cur = head;
    while(cur != null) { // 构建节点的映射
        hm.put(cur, new Node(cur.val)); 
        cur = cur.next;
    }
    cur = head;
    while(cur != null) {
        hm.get(cur).next = hm.get(cur.next); // 只有这样，才能获得新地址下的Node
        hm.get(cur).random = hm.get(cur.random);
        cur = cur.next;
    }
    return hm.get(head);
}

时间复杂度：$O(n)$

空间复杂度：$O(n)$

---

52. 两个链表的第一个公共节点

剑指 Offer 52. 两个链表的第一个公共节点 - 力扣（LeetCode）

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int step1 = 0, step2 = 0;
    ListNode A = headA, B = headB;
    while(A != null) {
        step1++;
        A = A.next;
    }
    while(B != null) {
        step2++;
        B = B.next;
    }
    int step = step1 - step2;
    A = headA;
    B = headB;
    if(step < 0) { // 第一个链表比较短
        while(step != 0) {
            B = B.next;
            step++;
        }
    } else if(step > 0) { // 第一个链表比较长
        while (step != 0) {
            A = A.next;
            step--;
        }
    }
    while (A != B) {
        A = A.next;
        B = B.next;
    }
    return A;
}

时间复杂度：$O(n+m)$

空间复杂度：$O(1)$

---

二分查找

11. 旋转数组的最小数字

剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode）

---

分治

---

数学

39. 数组中出现次数超过一半的数字

public int majorityElement(int[] nums) {
    int target = nums[0], times = 1;
    for(int i = 1; i < nums.length; i++) {
        if (target != nums[i]) {
            times--;
        } else {
            times++;
        }
        if (times == 0) {
            target = nums[i];
            times = 1;
        }
    }
    return target;
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$​

---

43. 1~n整数中1出现的次数

剑指 Offer 43. 1～n 整数中 1 出现的次数 - 力扣（LeetCode）

public int countDigitOne(int n) {
    int digit = 1, res = 0;
    int high = n / 10, cur = n % 10, low = 0; // 高位，当前位，低位；从个位开始统计
    while(high != 0 || cur != 0) {
        if(cur == 0) { // 当前位最大为0
            res += high * digit; // 该位出现1的次数，由高位决定
        } else if(cur == 1) { //当前位最大为1
            res += high * digit + low + 1; // 该位出现1的次数 由高位和低位决定
        } else { // 当前位最大 > 1
            res += (high + 1) * digit;
        }
        low += cur * digit;
        cur = high % 10;
        high /= 10;
        digit *= 10;
    }
    return res;
}

概述

Java的I/O大概可以分成以下几类：

• 磁盘操作：File
• 字节操作：InputStream 和 OutputStream
• 字符操作：Reader 和 Writer
• 对象操作：Serializable
• 网络操作：Socket
• 新的输入/输出：NIO

---

File 类

java.io.FileFile类可以用于表示文件和目录路径名，但是不表示文件的内容。

---

静态成员变量

• pathSeparator：路径分隔符

  • Windows：;

  • Linux：:

• separator：文件名称分隔符

  • Windows：反斜杠\

  • Linux：正斜杠/

  为了保证在不同系统中都能顺利执行，操作路径不能写死：

  "C:" + File.Separator + "develop" + File.Separator + "a" + File.Separator + "a.md"

---

绝对路径和相对路径

• 绝对路径：一个完整地址

• 相对路径：简化的路径，将当前地址作为根目录

---

构造方法

• File(String pathname)：将给定的路径名字符串转换为抽象路径名来创建一个新File实例。

  pathname可以以文件结尾，也可以以文件夹结尾；可以是相对路径，也可以是绝对路径；可以存在，也可以不存在。创建File对象，只是把字符串路径封装为File对象，无需考虑路径真假。

• File(String parent, String child)

  参数把路径分成了两部分，父路径和子路径可以单独书写，使用起来非常灵活。

• File(File parent, String child)

  父路径是File类型，可以使用File类的方法对路径进行一些操作。

---

常用方法

获取方法

• String getAbsolutePath()：返回此File的绝对路径名字符串

• String getPath()：将此File转换为路径名字符串(创建File时的pathname是什么样，就是什么样)

  使用toString方法有相同的效果（调用了getPath方法）

• String getName()：返回File的构造方法传递的结尾部分（文件或目录的名称）

• long length()：返回File表示的文件的大小，以字节为单位

  文件夹没有大小的概念，因此获取文件夹的大小会返回0；如果构造方法中给出的路径不存在，返回0。

---

判断方法

• boolean exists()：File表示的文件或者目录当前是否存在
• boolean isDirectory()：File对象是否是目录
• boolean isFile()：File对象是否是文件

isDirectory()和isFile()方法的正确发挥作用的前提是路径已存在，否则都会返回false。可以通过exist()先做判断：

File f = new File("C:\\download\\xx.torrent");

// 如果路径不存在，没有必要进行后续的判断
if(f.exists()) {
    System.out.println(f.isFile());
}

---

创建和删除方法

• boolean createNewFile()：当且仅当具有该名称的文件不存在时，创建一个新的空文件。

• boolean delete()：删除由此File表示的文件或目录。

  文件夹中有内容，则不会删除；路径不存在，会返回false。

  delete方法是直接在硬盘删除文件/文件夹，不走回收站（直接永久删除），要慎用。

• boolean mkdir()：创建由此File表示的目录。

• boolean mkdirs()：创建由此File表示的目录，包括任何必需但不存在的父目录（相对于mkdir()，适用范围更广，推荐）。

---

遍历目录

• String[] list()：返回一个String数组，表示该File目录中的所有子文件或目录（子目录下的内容不会获取）。
• File[] listFiles()：返回一个File数组，表示该File目录中的所有子文件或目录。

如果目录的路径不存在，或者路径不是一个目录，都会抛出空指针异常。

---

文件搜索

递归地列出一个目录下的所有文件：

public static void listAllFiles(File dir) {
    if (dir == null || !dir.exists()) {
        return;
    }
    if (dir.isFile()) {
        System.out.println(dir.getName());
        return;
    }
    for (File file : dir.listFiles()) {
        listAllFiles(file);
    }
}

---

文件过滤器

• java.io.FileFilter是一个接口，是File的过滤器。该接口的对象可以传递给File类的listFiles(FileFilter)作为参数。

  接口中的唯一方法：boolean accept(File pathname)：测试指定文件对象是否应该包含在当前File目录中。

  listFiles方法会调用参数传递的过滤器中的方法accept。

• java.io.FilenameFilter是文件名称的过滤器。

  接口中的唯一方法：boolean accept(File dir, String name)：测试指定文件是否应该包含在某一文件列表中。

两个过滤器接口没有实现类，需要自己写实现类，重写accept方法，自定义过滤规则。

---

IO 流概述

数据的传输可以看作是一种数据的流动，根据数据的流向，可以分为输入流和输出流。根据数据的类型，可以分为字节流和字符流。

	输入流	输出流
字节流	InputStream	OutputStream
字符流	Reader	Writer

---

字节流

字节输出流 OutputStream

java.io.OutputStream是一个抽象类，定义了一些成员方法如下：

• void close()：关闭输出流，并释放相关的系统资源
• void flush()：刷新输出流，并强制任何缓冲的输出字节被写出
• void write(byte[] b)：将指定的字节数组写入此输出流
• void write(byte[] b, int off, int len)：从指定的字节数组写入len字节，从偏移量off开始输出到输出流
• abstract void write(int b)：将指定的字节输出流

---

文件字节输出流 FileOutputStream

构造方法

• FileOutputStream(String name)：创建一个向具有指定名称的文件中写入数据的文件输出流

• FileOutputStream(File file)：创建一个向File对象表示的文件中写入数据的文件输出流

• FileOutputStream(String name, boolean append)

  append：追加写开关

  • true：创建对象不会覆盖源文件，在末尾追加写数据
  • false：创建新文件，覆盖源文件（默认）

---

使用步骤

1. 创建一个FileOutputStream对象，构造方法中传递写入数据的目的地

2. 调用FileOutputStream对象中的write方法，把数据写入到文件中

   当1次写多个字节时，写入的字节最后的显示：

   • 如果写的第一个字节是正数(0-127)，那么显示的时候会查询ASCII表。
   • 如果写的第一个字节是负数，则第一个字节会和第二个字节组成一个中文显示，查询系统默认码表(GBK)。

3. 释放资源(提高程序的效率)

---

写入字符的方法

可以使用String类中的方法byte[] getBytes()，把字符串转换为字节数组(默认编码方式一般为UTF-8)。

FileOutputStream fos = new FileOutputStream("C:\\download\\xx.md");
byte[] bytes = "Hellow World!".getBytes();

System.out.println(Arrays.toString(bytes)); // 可以看到字符串转换成字节数组后，再将字节数组转换为字符串形式
System.out.println(new String(bytes)); // 可以看到字符串转换成字节数组后，再转换为字符串

fos.write(bytes);

fos.close();

---

换行写入

通过写换行符完成换行写入：

• windows:\r\n
• linux: /n
• mac: /r

fos.write("\r\n".getBytes());

缓冲流有更跨平台的换行写入方式。

---

字节输入流 InputStream

java.io.InputStream是一个抽象类，定义了一些成员方法如下：

• void close(): 关闭输入流，并释放相关的系统资源

• int read(): 从输入流读取并返回输入的下一个字节

  返回-1时，表示读取到了eof(end of file)

• int read(byte[] b): 从输入流读取多个字节，并存储到字节数组b中

  • 数组b起到了缓冲作用，存储读取到的多个字节，能提高读取效率
  • 数组的大小一般定义为1024(1kb)的整数倍
  • 返回每次读取的有效字节个数（返回-1时，表示读取到了eof(end of file)）

---

文件字节输入流 FileInputStream

构造方法

• FileInputStream(String name)
• FileInputStream(File file)

---

使用步骤

1. 创建FileInputStream对象，构造方法中绑定要读取的数据源
2. 使用FileInputStream对象中的read方法，读取文件
3. 释放资源(提高程序的效率)

FileInputStream fis = new FileInputStream("C:\\download\\xx.md");

int len; // 存储读取的字节
while ((len = fis.read()) != -1) {
    System.out.print((char)len);
}

fis.close();

---

实现文件复制

public static void copyFile(String src, String dist) throws IOException {
    FileInputStream fis = new FileInputStream(src);
    FileOutputStream fos = new FileOutputStream(dist);

    byte[] buffer = new byte[20 * 1024];
    int cnt;

    // read() 最多读取 buffer.length 个字节
    // 返回的是实际读取的个数
    // 返回 -1 的时候表示读到 eof，即文件尾
    while ((cnt = fis.read(buffer)) != -1) { // 该read方法返回每次读取的有效字节个数
        fos.write(buffer, 0, cnt);
    }

    fis.close();
    fos.close();
}

---

字符流

字节流读取中文的问题

字节流读取中文字符时，可能不会显示完整的字符，因为一个中文字符可能占用多个字节存储。所以Java提供了一些字符流类，以字符为单位读写数据，专门用于处理文本文件。

---

Reader 与 Writer

不管是磁盘还是网络传输，最小的存储单元都是字节，而不是字符。但是在程序中操作的通常是字符形式的数据，因此需要提供对字符进行操作的方法。

• InputStreamReader 实现从字节流解码成字符流
• OutputStreamWriter 实现字符流编码成字节流

---

字符输出流 Writer

java.io.Writer抽象类表示用于字符输出流的所有类的超类，可以将字符信息从内存存入磁盘。

• void close()：关闭输出流，并释放相关的系统资源
• void flush()：刷新输出流，并强制任何缓冲的输出字符被写出
• void write(char[] cbuf)：将指定的字符数组写入此输出流
• void write(char[] cbuf, int off, int len)：从指定的字符数组写入len字节，从偏移量off开始输出到输出流
• void write(String str)：将字符串写入输出流
• void write(String str, int off, int len)：将子字符串写入输出流
• abstract void write(int b)：将指定的字符输出流

---

文件字符输出流 FileWriter

java.io.FileWriterextends OutputStreamWriter extends Writer

构造方法

• FileWriter(String name)：创建一个向具有指定名称的文件中写入数据的文件输出流

• FileWriter(File file)：创建一个向File对象表示的文件中写入数据的文件输出流

• FileWriter(String name, boolean append)

  append：追加写开关

  • true：创建对象不会覆盖源文件，在末尾追加写数据
  • false：创建新文件，覆盖源文件（默认）

---

使用步骤

1. 创建一个FileWriter对象，构造方法中传递写入数据的目的地
2. 调用FileWriter对象中的write方法，把数据写入到内存缓冲区中（有一个字符转换为字节的过程）
3. 使用FileWriter对象中的flush方法，把内存缓冲区中的数据刷新到文件中
4. 释放资源(也会执行把内存缓冲区中的数据刷新到文件中的操作，故第3步可以不显式写出来)

FileWriter fw = new FileWriter("C:\\download\\xx.md");

fw.write(97); // 不会直接写入文件，而是写入内存缓冲区
fw.flush();

fw.close(); 

---

换行写入

通过写换行符完成换行写入：

• windows:\r\n
• linux: /n
• mac: /r

fw.writer("\r\n");

缓冲流有更跨平台的换行写入方式。

---

字符输入流 Reader

java.io.Reader抽象类表示用于字符输入流的所有类的超类，可以读取字符信息到内存中。

• void close()：关闭输入流，并释放相关的系统资源

• int read()：从输入流读取一个字符

  返回-1时，表示读取到了eof(end of file)

• int read(char[] cbuf)：从输入流中读取多个字符，并将它们存储到字符数组cbuf中。

  • 数组cbuf起到了缓冲作用，存储读取到的多个字符，能提高读取效率
  • 数组的大小一般定义为1024(1kb)的整数倍
  • 返回每次读取的有效字符个数（返回-1时，表示读取到了eof(end of file)）

---

文件字符输入流 FileReader

java.io.FileReader extends InputStreamReader extends Reader

构造方法

• FileReader(String fileName)
• FileReader(File file)

---

使用步骤

1. 创建FileReader对象，构造方法中绑定要读取的数据源
2. 使用FileReader对象中的read方法，读取文件
3. 释放资源(提高程序的效率)

FileReader fr = new FileReader("C:\\download\\xx.md");


int len; // 存储读取的【字符】
while ((len = fr.read()) != -1) { // 一次读取一个字符
    System.out.print((char)len);
}


// 一次读取多个字符
char[] chars = new char[2 * 1024];
len = 0; // 记录有效字符个数
while((len = fr.read(chars) != -1)) {
    /*
    	String类的构造方法
    	String(char[] value) 把字符数组转换为字符串
    	String(char[] value, int offset, int count) 把字符数组的一个
    */
    System.out.println(new String(chars, 0, len));
}

fr.close();

---

IO 异常的处理

JDK 7 之前的处理

实际开发中不应该直接抛出异常，而应该使用try...catch...finally代码块对异常进行处理。

// 提高变量fw的作用域，让finally能使用
FileWriter fw = null; // 必须初始化，避免try中发生异常时，fw还没有被赋值，导致finally中的代码无法正常执行。
try {
    // 可能会产生异常的代码
    fw = new FileWriter("C:\\download\\xx.md", true);
    for (int i = 0; i < 10; i++) {
        fw.write("Hellow world!" + i + "\r\n");
    }
    fw.close();
} catch (IOException e) {
	// 异常的处理逻辑
    System.,out.println(e);
} finally {
    // 资源释放
    // 如果创建对象FileWriter对象失败，fw为null，null无法调用方法，会抛出空指针异常，需要增加一个判断
    if(fw != null) {
        try {
            fw.close(); // close方法本身也声明会抛出异常对象，因此也要处理
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

---

JDK 7 的处理

JDK 7的新特性：在try后边可以增加一个()，在括号中可以定义流对象，则这个流对象的作用域就在try中有效，try中的代码执行完毕，会自动把流对象释放，不用写finally。

try (// 1. 创建一个字节输入流对象，构造方法中绑定要读取的数据源
    FileInputStream fis = new FileInputStream("C:\\download\\xx.md");
    // 2. 创建一个字节输出流对象，构造方法中绑定要写入的文件
    FileOutputStream fos = new FileOutputStream("D:\\download\\1.jpg")) {

    int len = 0;
    while((len = fis.read()) != 1) {
        fos.write(len);
    }
} catch (IOException e) {
    System.out.println(e);
}

---

属性集 Properties

java.util.Properties继承于HashTable，虽然HashTable是一个遗留类，但Properties作为唯一和IO流相结合的集合依然活跃着。Properties表示一个持久的属性集。它使用键值对存储数据，每个键和值都是字符串，因此Properties有一些操作字符串的特有方法：

• Object setProperty(String key, String value)

• String getProperty(String key)

• Set<String> stringPropertyNames()

  返回此属性列表中的键集。

// 创建Properties集合对象
Properties prop = new Properties();

// 使用setProperty往集合中添加数据
prop.setProperty("邓肯", "21");
prop.setProperty("吉诺比利", "20");
prop.setProperty("吉诺比利", "9");

// 把Properties集合中的键取出，存储到一个Set集合中
Set<String> set = prop.stringPropertyNames();

// 遍历Set集合，获取每个键对应的值
for (String key : set) {
    String value = prop.getProperty(key);
    System.out.println(key + "=" + value);
}

---

可以使用Properties集合中的store方法，把集合中的临时数据持久化写入到硬盘中。

• void store(OutputStream out, String comments)
  • OutputStream是字节输出流，不能写中文
  • comments是注释，用来解释保存的文件的作用。（不能使用中文，会产生乱码，默认是Unicode编码）一般使用空字符串""。
• void store(Writer writer, String comments)
  • Writer是字符输出流，可以写中文

使用步骤：

1. 创建Properties集合对象，添加数据
2. 创建字节输出流/字符输出流对象
3. 使用Properties集合的store方法，将集合中的临时数据持久化写入硬盘
4. 释放资源

// 创建Properties集合对象
Properties prop = new Properties();

// 使用setProperty往集合中添加数据
prop.setProperty("邓肯", "21");
prop.setProperty("吉诺比利", "20");
prop.setProperty("吉诺比利", "9");

FileWriter fw = new FileWriter("C:\\download\\xx.md");

prop.store(fw, "save data");

fw.close();

---

可以使用Properties集合中的load方法，把硬盘中保存的文件（键值对）读取到集合中使用。

• void load(InputStream inStream)

  InputStream是字节输入流，不能读取中文

• void load(Reader reader)

  Reader是字符输入流，可以读取中文

使用步骤：

1. 创建Properties集合对象
2. 使用Properties集合的load方法，读取存储键值对的文件
   • 键值对文件，键与值默认的连接符可以用=、空格以及一些其他符号
   • 文件中可以使用#进行注释
   • 文件中的键和值默认都是字符串，无需加引号
3. 遍历Properties集合
4. 释放资源

// 创建Properties集合对象
Properties prop = new Properties();

// 读取键值对文件
prop.load(new FileReader("C:\\download\\xx.md"));

// 遍历集合
for (String key : set) {
    String value = prop.getProperty(key);
    System.out.println(key + "=" + value);
}

fw.close();

---

缓冲流

缓冲流也叫高效流，是对4个基本的FileXxx流的增强，所以也是4个流。缓冲流的基本原理，是在创建流对象时，创建一个内置的默认大小的缓冲区数组，通过缓冲区读写，减少IO次数，从而提高读写的效率。

---

缓冲字节输出流 BufferedOutputStream

java.io.BufferedOutputStream extends OutputStream

构造方法

• BufferedOutputStream(OutputStream out)

  创建一个缓冲输出流，将数据写入指定的底层输出流

• BufferedOutputStream(OutputStream out, int size)

  创建一个缓冲输出流，将具有指定缓冲区大小的数据写入指定的底层输出流

---

使用步骤

1. 创建FileOutputSream对象，构造方法中绑定要输出的目的地
2. 创建BufferedOutputStream对象，构造方法中传递FileOutputStream对象，提高FileOutputStream对象的效率
3. 使用BufferedOutputStream对象的write方法，将数据写入内部缓冲区
4. 使用BufferedOutputStream对象的flush方法，将内部缓冲区中的数据刷新到文件中
5. 释放资源(也会执行把内存缓冲区中的数据刷新到文件中的操作，故第4步可以不显式写出来)

// 1.
FileOutputStream fos = new FileOutputStream("C:\\download\\xx.md");

// 2.
BufferedOutputStream bos = new BufferedOutputStream(fos);

// 3.
bos.write("把数据写入到内部缓冲区中".getBytes());

bos.flush();

bos.close(); // 关闭缓冲流，基本流也会被自动关闭

---

缓冲字节输入流 BufferedInputStream

java.io.BufferedInputStream extends InputStream

构造方法

• BufferedInputStream(InputStream in)

  创建一个缓冲输入流，并保存输入流in，以便将来使用

• BufferedInputStream(InputStream in, int size)

  创建一个缓冲输入流，将具有指定缓冲区大小的数据写入指定的底层输入流

---

使用步骤

1. 创建FileInputSream对象，构造方法中绑定要读取的数据源
2. 创建BufferedInputStream对象，构造方法中传递FileInputStream对象，提高FileInputStream对象的效率
3. 使用BufferedInputStream对象的read方法，将数据存入缓冲区数组
4. 释放资源

// 1.
FileInputStream fis = new FileInputStream("C:\\download\\xx.md");

// 2.
BufferedInputStream bis = new BufferedInputStream(fis);

// 3.
byte[] bytes = new byte[1024]; // 存储每次读取的数据
int len = 0; // 记录每次读取的字节个数
while((len = bis.read(bytes)) != -1) {
    System.out.println(new String(bytes, 0 ,len));
}

bis.close(); // 关闭缓冲流，基本流也会被自动关闭

---

实现文件复制

和使用基本字节流进行文件复制相比，效率明显提升（1次读取单个字节或多个字节都是如此）。

long s = System.currentTimeMills(); // 测试程序效率

BufferedInputStream bis = new BufferedInputStream(new FileInputStream("C:\\download\\xx.md"));

BufferedOutStream bos = new BufferedOutputStream(new FileOutputStream("C:\\download\\yy.md"));

byte[] bytes = new byte[1024]; // 存储每次读取的数据
int len = 0; // 记录每次读取的字节个数
while((len = bis.read(bytes)) != -1) {
    bos.write(bytes, 0, len);
}

bis.close();
bos.close();

long e = System.currentTimeMills(); // 测试程序效率
System.out.println("程序共耗时：" + (e - s) + "毫秒");

---

缓冲字符输出流 BufferedWriter

java.io.BufferedWriter extends Writer

构造方法

• BufferedWriter(Writer out)

  创建一个使用默认输出缓冲区的缓冲字符输出流

• BufferedWriter(Writer out, int size)

  创建一个使用给定大小缓冲区的缓冲字符输出流

---

特有的成员方法

void newLine()：写入一个行分隔符（根据不同的操作系统，获取不同的行分隔符）

---

使用步骤

1. 创建缓冲字符输出流对象，构造方法中传递字符输出流
2. 调用缓冲字符输出流的write方法，把数据写入到内存缓冲区中
3. 调用缓冲字符输出流的flush方法，把内存缓冲区中的数据刷新到文件中
4. 释放资源

BufferedWriter bw = new BufferedWriter(new FileWriter("C:\\download\\xx.md"));

for(int i = 0; i < 10; i++) {
    bw.write("机智医生生活");
    bw.newLine(); // 换行（根据不同的操作系统，获取不同的行分隔符）
}

bw.flush();
bw.close(); // 关闭缓冲流，基本流也会被自动关闭

---

缓冲字符输入流 BufferedReader

java.io.BufferedReader extends Reader

构造方法

• BufferedReader(Reader in)
• BufferedReader(Reader in, int size)

---

特有的成员方法

String ReadLine()：读取一个文本行（根据不同的操作系统，获取不同的行分隔符）

​ 返回该行内容的字符串，不包含任何行分隔符。如果已到达流末尾，则返回null。

---

逐行读取文本文件的内容

BufferedReader br = new BufferedReader(new FileReader("C:\\download\\xx.md"));

String line;
while ((line = br.readLine()) != null) {
    System.out.println(line);
}

br.close();

---

编码与解码

编码就是把字符转换为字节，而解码是把字节重新组合成字符。如果编码和解码过程使用不同的编码方式那么就出现了乱码。

---

字符集 charset

字符集也叫编码表。是一个系统支持的所有字符的集合，包括文字、标点符号、图形符号、数字等。常见的字符集有ASCII、GBK、Unicode等。

• GBK编码中，中文字符占2个字节，英文字符占1个字节；

• Unicode字符集是为表达任意语言的任意字符而设计，是业界的一种标准。

  • UTF-8编码中，中文字符占3个字节，英文字符占1个字节；

    是电子邮件、网页级其他存储或传送文字的应用中，优先采用的编码。

  • UTF-16be编码中，中文字符和英文字符都占2个字节。

    UTF-16be中的be指的是Big Endian，也就是大端。相应地也有UTF-16le，le指的是Little Endian，也就是小端。

大端模式：高位字节排放在内存的低地址端，低位字节排放在内存的高地址端。

​ （符合直观上认为的模式）

小端模式：低位字节排放在内存的低地址端，高位字节排放在内存的高地址端。

从软件的角度理解端模式：

不同端模式的处理器进行数据传递时必须要考虑端模式的不同。在Socket接口编程中，以下几个函数用于大小端字节序的转换

#define ntohs(n)     //16位数据类型网络字节顺序到主机字节顺序的转换  
#define htons(n)     //16位数据类型主机字节顺序到网络字节顺序的转换  
#define ntohl(n)      //32位数据类型网络字节顺序到主机字节顺序的转换  
#define htonl(n)      //32位数据类型主机字节顺序到网络字节顺序的转换  

其中互联网使用的网络字节顺序采用大端模式进行编址，而主机字节顺序根据处理器的不同而不同，如PowerPC处理器使用大端模式，而Pentuim处理器使用小端模式。

Java 的内存编码使用双字节编码 UTF-16be，这不是指 Java 只支持这一种编码方式，而是说 char 这种类型使用 UTF-16be 进行编码。char 类型占 16 位，也就是两个字节，Java 使用这种双字节编码是为了让一个中文或者一个英文都能使用一个 char 来存储。

---

String的编码方式

String可以看成一个字符序列，可以指定一个编码方式将它编码为字节序列，也可以指定一个编码方式将一个字节序列解码为String。

String str1 = "中文";
byte[] bytes = str1.getBytes("UTF-8");
String str2 = new String(bytes, "UTF-8");
System.out.println(str2);

在调用无参数 getBytes() 方法时，默认的编码方式不是 UTF-16be。双字节编码的好处是可以使用一个 char 存储中文和英文，而将 String 转为 bytes[] 字节数组就不再需要这个好处，因此也就不再需要双字节编码。getBytes() 的默认编码方式与平台有关，一般为 UTF-8。

---

编码引起的问题

在IDEA中，使用FileReader读取项目中的文本文件。由于IDEA的设置，都是默认UTF-8编码，所以没有任何问题。但是，当读取Windows系统中创建的文本文件时，由于Windows系统默认的是GBK编码，所以会出现乱码。那么该如何读取GBK编码的文件？

---

转换流

OutputStreamWriter 类

转换流java.io.OutputStreamWriter是Writer的子类，是从字符流到字节流的桥梁。它读取字符，并使用指定的字符集将其编码为字节。

构造方法：

• OutputStreamWriter(OutputStream out)

• OutputStreamWriter(OutputStream out, String charsetName)

  charsetName用于指定字符集，不区分大小写。

OutputStreamWriter osw = new OutputStreamWriter(new FileOutputStream("C:\\download\\xx.md"), "GBK");

osw.write("机智医生生活"); // 不会直接写入文件，而是写入内存缓冲区（编码过程）
osw.flush();

osw.close(); 

---

InputStreamReader 类

转换流java.io.InputStreamReader是Reader的子类，是从字节流到字符流的桥梁。它读取字节，并使用指定的字符集将其解码为字符。

构造方法：

• InputStreamReader(InputStream in)

• InputStreamReader(InputStream in, String charsetName)：

  charsetName用于指定字符集，不区分大小写。

InputStreamReader isr = new InputStreamReader(new FileInputStream("C:\\download\\xx.md"), "GBK");

int len = 0;
while((len = isr.read() != -1)) {
    System.out.println((char)len);
}

// 一次读取多个字符
char[] chars = new char[2 * 1024];
len = 0; // 记录有效字符个数
while((len = isr.read(chars) != -1)) {
    System.out.println(new String(chars, 0, len));
}
isr.close(); 

---

转换文件编码

将GBK编码的文本文件，转换为UTF-8编码的文本文件。

1. 指定GBK编码的转换流，读取文本文件
2. 指定UTF-8编码的转换流，写入文本文件

InputStreamReader isr = new InputStreamReader(new FileInputStream("C:\\download\\xx.md"), "GBK");

OutputStreamWriter osw = new OutputStreamWriter(new FileOutputStream("C:\\download\\yy.md"), "UTF-8");

int len = 0;
while((len = isr.read() != -1)) {
    osw.write(len);
}

---

装饰者模式

以InputStream为例，

• InputStream是抽象组件；

• FileInputStream是InputStream的子类，属于具体组件，提供了字节流的输入操作;

• FilterInputStream属于抽象装饰者，装饰者用于装饰组件，为组件提供额外的功能。

  • 例如BufferedInputStream为FileInputStream提供缓存的功能。

    实例化一个具有缓存功能的字节流对象时，只需要在 FileInputStream 对象上再套一层 BufferedInputStream 对象即可：

    FileInputStream fileInputStream = new FileInputStream(filePath);
    BufferedInputStream bufferedInputStream = new BufferedInputStream(fileInputStream);

  • DataInputStream装饰者提供了对更多数据类型进行输入的操作，比如int、double等基本类型。

---

序列化

序列化就是将一个对象转换成字节序列，该字节序列包含对象的数据、对象的类型以及对象中存储的属性。字节序列写出到文件之后，相当于文件中持久保存了一个对象的信息。

• 序列化：void ObjectOutputStream.writeObject()
• 反序列化：Object ObjectInputStream.readObject()

不会对静态变量进行序列化，因为序列化只是保存对象的状态，静态变量属于类的状态。

---

Serializable 接口

序列化的类需要实现Serializable接口，它只是一个标准，没有任何方法需要实现。但如果不去实现它的话，会抛出异常。

public static void main(String[] args) throws IOException, ClassNotFoundException {

    A a1 = new A(123, "abc");
    String objectFile = "C:\\download\\a1.md";

    ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(objectFile));
    oos.writeObject(a1);
    oos.close();

    ObjectInputStream ois = new ObjectInputStream(new FileInputStream(objectFile));
    A a2 = (A) ois.readObject(); // 类型转换
    ois.close();
    System.out.println(a2);
}

private static class A implements Serializable {

    private int x;
    private String y;

    A(int x, String y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "x = " + x + "  " + "y = " + y;
    }
}

---

InvalidClassException 异常

当JVM反序列化对象时，能找到class文件，但是class文件在序列化对象之后发生了修改，那么反序列化操作也会失败，抛出一个InvalidClassException异常。

发生该异常的原因有：

1. 该类的序列版本号与从流中读取的类描述符的版本号不一致
2. 该类包含未知数据类型
3. 该类没有可访问的无参数构造方法

Serializable接口给需要序列化的类提供了一个序列版本号serialVersionUID，用于验证序列化的对象和对应类是否版本匹配。

解决方案：

无论是否对类的定义进行修改，都不重新生成新的序列号。可序列化的类通过声明static final long serialVersionUID来显式声明自己的序列号。

public class A implements Serializable {
    
    private static final long serialVersionUID = 20L; //显式声明序列号

    private int x;
    private String y;

    A(int x, String y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "x = " + x + "  " + "y = " + y;
    }
}

IDEA自动生成序列号

Settings - Editor - Inspections - 搜索UID - Serializable class without ‘serialVersionUID’ 右侧勾选，修改Severity为Error。

---

transient 关键字

transient（瞬态）关键字可以使一些属性不会被序列化。

ArrayList中存储数据的数组elementData是用transient修饰的，因为这个数组是动态扩展的，并不是所有的空间都被使用，因此就不需要所有的内容都被序列化。通过重写序列化和反序列化方法，使得可以只序列化数组中有内容的那部分数据。

---

序列化集合

当想在文件中保存多个对象的时候，可以把对象存储到一个集合中，对集合进行序列化和反序列化。

ArrayList<A> list = new ArrayList<>();

list.add(new A(20, "吉诺比利"));
list.add(new A(21, "邓肯"));

// 创建序列化流
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("C:\\download\\Spurs.md"));

// 对集合进行序列化
oos.writeObject(list);

oos.close();

// 创建反序列化流
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("C:\\download\\Spurs.md"));

// 读取文件中保存的集合
ArrayList<A> list2 = (ArrayList<A>)ois.readObject();

for (A a : list2) {
    System.out.println(a);
}

ois.close();    

---

打印流

java.io.PrintStream extends OutputStream与其他输出流不同，永远不会抛出IOException。

特有的方法：

• void print(任意类型的值)
• void println(任意类型的值)

构造方法：

• PrintStream(File file)：输出至文件
• PrintStream(OutputStream out)：输出至字节输出流
• PrintStream(String fileName)：输出至指定的文件路径

注意：

如果使用继承自父类的write方法写数据，那么查看数据的时候会查询编码表97 -> a；如果使用自己特有的print/println方法写数据，原样输出97 -> 97。

打印流还可以改变输出语句System.out.print/println的目的地：

static void System.setOut(PrintStream out)

System.out.println("默认在控制台输出");

PrintStream ps = new PrintStream("C:\\download\\Spurs.md");

System.setOut(ps); //更改输出语句的目的地为打印流的目的地

System.out.println("在打印流的目的地中输出");

ps.close();

反射 Reflection

概念

静态语言和动态语言

动态语言是一类在运行时可以改变其结构的语言。例如新的函数、对象甚至代码都可以在运行时引进，已有的函数可以被删除，或者结构上做一些其他的变化。主要的动态语言有：C#、JavaScript、PHP、Python等。

静态语言是运行时结构不可变的语言。例如Java、C、C++。Java虽然不是动态语言，但可以称之为准动态语言。即Java有一定的动态性，可以利用反射机制获得类似动态语言的特性。

---

Class类

JRE为每个类都保留了一个不变的Class类型的对象。

• Class本身也是一个类
• Class对象只能由系统建立对象
• 一个加载的类在JVM中只会有一个Class实例
• 一个Class对象对应的是一个加载到JVM中的一个class文件
• 通过Class可以完整地得到一个类中的所有被加载的结构
• Class类是Reflection的根源，针对任何想动态加载、运行的类，只有先获得相应的Class对象

常用方法

方法名	功能说明
static ClassforName(String name)	返回指定类名name的Class对象
Object newInstance()	调用默认构造函数，返回Class对象的一个实例
getName()	返回此Class对象所表示的实体（类、接口、数组类或void）的名称
Class getSuperClass()	返回当前Class对象的父类的Class对象
Class[] getInterfaces()	获取当前Class对象的接口
ClassLoader getClassLoader()	返回该类的类加载器
Constructor[] getConstructors()	返回一个包含某些Constructor对象的数组
Method getMethod(String name, Class.. T)	返回一个Method对象，此对象的参数类型是paramType
Field[] getDeclaredFields()	返回Field对象的一个数组

类的加载与ClassLoader的理解

• 加载

  将class文件字节码内容加载到内存中，并将这些静态数据转换成方法区的运行时数据结构，然后在堆中生成一个代表这个类的java.lang.Class对象，作为方法区中类数据的访问入口。

  标准的JavaSE类加载器可以按要求查找类，但一旦某个类被加载到类加载器中，它将维持加载（缓存）一段时间。不过JVM垃圾回收机制可以回收这些Class对象。

• 链接

  将Java类的二进制代码合并到JVM的运行状态之中的过程。

  • 验证：确保加载的类信息符合JVM规范，没有安全方面的问题。
  • 准备：正式为类变量分配内存并设置变量默认初始值的阶段，这些内存都将在方法区中进行分配。
  • 解析：虚拟机常量池内的**符号引用(常量名)替换为直接引用(地址)**的过程。

• 初始化

  • 执行类构造器<clinit>()方法的过程。该方法是由编译器自动收集类中所有类变量的赋值动作和静态代码块中的语句合并产生的（静态代码合并，按先后顺序执行）。
  • 当初始化一个类的时候，如果发现其父类还没有进行初始化，则需要先出发其父类的初始化。
  • 虚拟机会保证一个类的<clinit>()方法在多线程环境中被正确加锁和同步。

  以下情况不会发生类的初始化：

  • 访问一个静态域时，只有真正声明这个域的类才会被初始化。例如通过子类引用父类的静态变量，不会导致子类初始化。
  • 通过数组定义类引用，不会触发此类的初始化
  • 引用常量不会出发此类的初始化(在链接阶段就存入调用类的常量池中了)

---

类加载器的作用

类加载器将class文件字节码内容加载到内存中，并将这些静态数据转换成方法区的运行时结构数据，然后在堆中生成一个代表这个类的java.lang.Class对象，作为方法区中类数据的访问入口。

标准的JavaSE类加载器可以按要求查找类，但一旦某个类被加载到类加载器中，它将**维持加载（缓存）**一段时间。不过JVM垃圾回收机制可以回收这些Class对象。

• 引导类加载器 Bootstrap Classloader

  C++编写，JVM自带的类加载器，负责Java平台核心库，用来装载核心类库，无法直接获取。

• 扩展类加载器 Extension Classloader

• 系统类加载器 System Classloader / Application Classloader

  是最常用的类加载器

---

反射 (Reflection) 是 Java 的特征之一，它允许运行中的 Java 程序获取自身的信息，并且可以操作类或对象的内部属性。程序中一般的对象的类型都是在编译期就确定下来，而 Java 反射机制可以动态地创建对象并调用其属性，这样的对象的类型在编译期是未知的。所以我们可以通过反射机制直接创建对象，即使这个对象的类型在编译期是未知的。

加载完类之后，在堆内存的方法区中就产生了一个Class类型的对象（一个类只有一个Class对象），这个对象包含了完整的类的结构信息，可以通过这个对象看到类的结构。这个对象就像一面镜子，透过这个镜子看到类的结构，所以形象地称之为反射。

反射的核心是 JVM 在运行时才动态加载类或调用方法/访问属性，它不需要事先知道运行对象是谁。

Java 反射主要提供以下功能：

• 在运行时判断任意一个对象所属的类；
• 在运行时构造任意一个类的对象；
• 在运行时判断任意一个类所具有的成员变量和方法（通过反射甚至可以调用private方法）；
• 在运行时调用任意一个对象的方法
• 在运行时处理注解
• 生成动态代理

---

使用场景

很多人都认为反射在实际的 Java 开发应用中并不广泛，其实不然。当我们在使用 IDE(如 Eclipse，IDEA)时，当我们输入一个对象或类并想调用它的属性或方法时，一按点号，编译器就会自动列出它的属性或方法，这里就会用到反射。

反射最重要的用途就是开发各种通用框架。很多框架（比如 Spring）都是配置化的，为了保证框架的通用性，它们可能需要根据配置文件加载不同的对象或类，调用不同的方法，这个时候就必须用到反射，运行时动态加载需要加载的对象。

对于框架开发人员来说，反射虽小但作用非常大，它是各种容器实现的核心。

---

反射的使用

反射相关的类一般都在java.lang.relfect包里。

获得Class对象

可以获得Class对象的类型：

1. 各种Class（外部类、成员内部类、静态内部类、局部内部类、匿名内部类）
2. interface
3. 数组
4. enum
5. 注解
6. 基本数据类型
7. void

有4种方法可以获得Class对象：

1. 若已知具体的类，通过类的class属性获取，该方法最安全可靠，程序性能最高。

Class c1 = Person.class;

Class c2 = int.class;

2. 已知某个类的实例对象，调用对象的getClass()方法获取Class对象

   Class c1 = person.getClass();

3. 已知一个类的全类名，且在该类的类路径下，可使用Class类的静态方法forName()获取，可能抛出ClassNotFoundException

Class c1 = Class.forName("com.hunter.reflection.User");

4. 内置基本数据类型可以直接使用类名.Type

   Class c3 = Integer.TYPE;

---

判断是否为某个类的实例

一般地，我们用 instanceof 关键字来判断是否为某个类的实例。同时我们也可以借助反射中 Class 对象的 isInstance() 方法来判断是否为某个类的实例，它是一个 native 方法：

public native boolean isInstance(Object obj);

native方法：具体实现由非java语言实现的方法

---

创建实例

通过反射来生成对象主要有两种方式。

1. 使用Class对象的newInstance()方法来创建Class对象对应类的实例

类必须要有一个无参构造器

Class<?> c = String.class; // 当赋值的类型不确定的时候，泛型用通配符？代替
Object str = c.newInstance();

2. 先通过Class对象获取指定的Constructor对象，再调用Constructor对象的newInstance()方法来创建实例。

这种方法可以用指定的构造器构造类的实例。

Class<?> c = String.class;
Constructor constructor = c.getConstructor(String.class);
// 根据构造器创建实例
Object obj = constructor.newInstance("23333");
System.out.println(obj);

---

获取方法

获取某个Class对象的方法集合，主要有以下几个方法：

1. getDeclaredMethods

   返回类或接口声明的所有方法，包括公共、保护、默认（包）访问和私有方法，但不包括继承的方法

   public Method[] getDeclaredMethods() throws SecurityException

2. getMethods

   返回某个类的所有公共方法，包括继承的公用方法

   public Method[] getMethods() throws SecurityException

3. getMethod

   返回一个特定的方法，其中第一个参数为方法名称，后面的参数为方法的参数对应Class的对象。

   public Method getMethod(String name, Class<?>... parameterTypes)

举例如下：

public class test1 {
	public static void test() throws IllegalAccessException, InstantiationException, NoSuchMethodException, InvocationTargetException {
	        Class<?> c = methodClass.class;
	        Object object = c.newInstance();
	        Method[] methods = c.getMethods();
	        Method[] declaredMethods = c.getDeclaredMethods();
	        //获取methodClass类的add方法
	        Method method = c.getMethod("add", int.class, int.class);
	        //getMethods()方法获取的所有方法
	        System.out.println("getMethods获取的方法：");
	        for(Method m:methods)
	            System.out.println(m);
	        //getDeclaredMethods()方法获取的所有方法
	        System.out.println("getDeclaredMethods获取的方法：");
	        for(Method m:declaredMethods)
	            System.out.println(m);
	    }
    }
class methodClass {
    public final int fuck = 3;
    public int add(int a,int b) {
        return a+b;
    }
    public int sub(int a,int b) {
        return a+b;
    }
}

---

获取构造器信息

获取类构造器的用法与上述获取方法的用法类似。

• getDeclaredConstructors()：所有public的构造方法
• getConstructors()：全部构造方法
• getDeclaredConstructor
• getConstructor

主要通过Class类的getConstructor方法得到Constructor类的一个实例，而Constructor类有一个newInstance方法可以创建一个对象实例：

public T newInstance(Object... initargs)

---

获取类的成员变量信息

• getDeclaredFields：所有已声明的成员变量，但不能得到父类的成员变量
• getFields：访问公有的成员变量
• getField：获取指定的公有成员变量
• getDeclaredField：获取指定的已声明成员变量

---

反射调用方法

当从类中获取了一个方法后，就可以用invoke()方法来调用这个方法。

若原方法声明为private，则需要在调用此invoke()方法前，显式调用方法对象的setAccessible(true)方法。

Method、Field和Constructor对象都有setAccessible()方法，作用是启动和禁用访问安全检查的开关。

• 参数为true则指示反射的对象在使用时应该取消Java语言的访问检查。
  • 提高了反射效率
  • 可以访问私有成员

public Object invoke(Object obj, Object... args) throws IllegalAccessException, IllegalArgumentException, InvocationTargetException

下面是一个实例：

public class test1 {
    public static void main(String[] args) throws IllegalAccessException, InstantiationException, NoSuchMethodException, InvocationTargetException {
        Class<?> klass = methodClass.class;
        //创建methodClass的实例
        Object obj = klass.newInstance();
        //获取methodClass类的add方法
        Method method = klass.getMethod("add",int.class,int.class);
        //调用method对应的方法 => add(1,4)
        Object result = method.invoke(obj,1,4);
        System.out.println(result);
    }
}
class methodClass {
    public final int fuck = 3;
    public int add(int a,int b) {
        return a+b;
    }
    public int sub(int a,int b) {
        return a+b;
    }
}

---

反射操作注解

Annotation[] annotations = c1.getAnnotations(); // 获取注解
for (Annotation annotation : annotations) {
    System.out.println(annotation);
    String value = annotaion.value();
    System.out.println(value);
}

---

setAccessible

设置可访问方法、属性、构造器对象能否访问的方法。

setAccessible(true)指示反射的对象在使用时取消Java语言的访问检查，有两点作用：

1. 提高反射效率
2. 可以访问原本无法访问的私有对象

---

反射的优点

• 灵活性：可以动态创建对象和编译。

• 可扩展性 ：应用程序可以利用全限定名创建可扩展对象的实例，来使用来自外部的用户自定义类。

• 类浏览器和可视化开发环境 ：一个类浏览器需要可以枚举类的成员。可视化开发环境（如 IDE）可以从利用反射中可用的类型信息中受益，以帮助程序员编写正确的代码。

• 调试器和测试工具 ： 调试器需要能够检查一个类里的私有成员。测试工具可以利用反射来自动地调用类里定义的可被发现的 API 定义，以确保一组测试中有较高的代码覆盖率。

---

反射的缺点

尽管反射非常强大，但也不能滥用。如果一个功能可以不用反射完成，那么最好就不用。在我们使用反射技术时，下面几条内容应该牢记于心。

• 性能开销 ：反射涉及了动态类型的解析，所以 JVM 无法对这些代码进行优化。因此，反射操作的效率要比那些非反射操作低得多。我们应该避免在经常被执行的代码或对性能要求很高的程序中使用反射。
• 安全限制 ：使用反射技术要求程序必须在一个没有安全限制的环境中运行。如果一个程序必须在有安全限制的环境中运行，如 Applet，那么这就是个问题了。
• 内部暴露 ：由于反射允许代码执行一些在正常情况下不被允许的操作（比如访问私有的属性和方法），所以使用反射可能会导致意料之外的副作用，这可能导致代码功能失调并破坏可移植性。反射代码破坏了抽象性，因此当平台发生改变的时候，代码的行为就有可能也随着变化。

---

注解 Annotation

Annotation是JDK 1.5引入的技术，是附加在代码中的一些元信息，用于一些工具在编译、运行时进行解析和使用，起到说明、配置的功能。它以**@注释名的形式**在代码中存在，还可以添加一些参数值，例如@SuppressWarnings(value="unchecked")。

Annotation可以附加在package、class、method、filed等上面，通过反射机制编程实现对这些元数据的访问。

---

内置注解

• @Override：定义在java.lang.Override中，此注释只适用于修辞方法，表示一个方法声明打算重写超类中的另一个方法声明。

• @Deprecated：定义在java.lang.Deprecated中，此注释可以用于修辞方法、属性、类，表示不鼓励程序员使用这样的元素，通常是因为它很危险或者存在更好的选择。

• @SuppressWarnings：定义在java.lang.Suppresswarnings中，用来抑制编译时的警告信息。

  与前两个注释有所不同，需要添加一个参数才能正确使用。这些参数都是已经定义好了的，选择性使用即可：

  • @SuppressWarnings("all")：镇压全部警告
  • @SuppressWarnings("unchecked")：镇压未检查的警告
  • @SuppressWarnings(value = {"unchecked", "deprecation"})

---

元注解

元注解的作用就是负责注解其他注解，Java定义了4个标准的meta-annotation类型，他们被用来提供对其他 annotation类型作说明。这些类型和它们所支持的类在java.lang.annotation包中可以找到：

• @Target：用于描述注解的使用范围

• @Retention：表示需要在什么级别保存该注释信息，用于描述注解的生命周期

  (SOURCE < CLASS < RUNTIME)，（自定义的注解一般都写在RUNTIME）

• @Document：说明该注解将被包含在javadoc中

• @Inherited：说明子类可以继承父类中的该注解

自定义一个注解：

@Target(value = {ElementType.METHOD, ElementType.TYPE) // value 是参数名
@Retention(value = RetentionPolicy.RUNTIME)
@Document
@Inherited
@interface MyAnnocation {
    
}

---

自定义注解

使用@interface自定义注解时，自动继承了java.lang.annotation.Annotation接口。

分析：

• @interface用来声明一个注解，格式：public @Interface 注解名{定义内容}
• 其中的每一个方法实际上是声明了一个配置参数
• 方法的名称就是参数的名称
• 返回值类型就是参数的类型(只能是基本类型、Class、String、enum)
• 可以通过default来声明参数的默认值
• 如果只有一个参数成员，一般参数名为value
• 注解元素必须要有值，我们定义注解元素时，经常使用空字符串、0作为默认值。

public class Test {
    @MyAnnovation2(age = 18, name = "Hunter")
    public void test(){}
}

@Target({ElementType.TYPE, ElementType.METHOD}) // 注解可以用在类、方法上
@Retention(Retentionpolicy.RUNTIME) // 注解在运行时有效
@interface Myannotation2 {
    //注解的参数：参数类型 参数名();
    String name() default ""; //空字符串
    int age() default 0;
    int id() default -1; //如果默认值为-1，代表不存在
    String[] schools() default {"西南大学", "东南大学"};
}

概览

容器除了数组，主要包括Collection和Map这两种接口，两者也常被统称为集合框架：

• Collection存储对象的集合（单列）
• Map存储键值对的映射表（双列）

数组和集合框架的区别：

• 数组长度固定；集合的长度可变
• 数组可以存储基本数据类型；集合只能存储对象，而且对象的类型可以不一致（泛型）

在开发中，一般当对象多的时候，使用集合框架进行存储。

---

Collection 接口

java.util.Collection是单列集合类的根接口。

常用方法：

• boolean add(E e)：添加指定对象到当前集合
• void clear()：清空集合中所有的元素
• boolean remove(E e)：从当前集合中删除指定对象
• boolean contains(E e)：判断当前集合中是否包含给定的对象
• boolean isEmpty()：判断当前集合是否为空
• int size()：返回集合中元素个数
• Object[] toArray()：把集合中的元素存储到数组中

继承了Collection的接口：

• List 接口
• Set 接口
• Queue 接口

---

Iterator 接口

java.util.Iterator接口也是Java集合中的一员，主要用于迭代访问（即遍历）Collection中的元素。

Collection继承了Iterable接口，其中的public Iterator iterator()方法能够产生一个Iterator对象，通过这个对象就可以迭代遍历Collection中的元素。

迭代：即Collection集合元素的通用获取方式。需要先判断集合中有没有元素，如果有，就取出来，直至全部取出。

常用方法：

• public E next()：返回迭代的下一个元素
• public boolean hasNext()：如果仍有元素可以迭代，则返回true

Collection<String> col = new ArrayList<>();
//往集合中添加元素
col.add("甲");
col.add("乙");
col.add("丙");
col.add("丁");

Iterator<String> it = col.iterator(); //迭代器的泛型由创建它的Collection的泛型决定
while(it.hasNext()) {
    System.out.println(it.next());
}

从JDK 1.5 之后，可以使用增强for循环——foreach方法来遍历实现了Iterable接口的聚合对象：

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
for (String item : list) {
    System.out.println(item);
}

---

List 接口

java.util.List存储的元素有序且可重复。习惯性地会将实现了List接口的对象称为List集合，可以通过索引来访问集合中的指定元素。

---

常用方法

除了继承自Collection接口中的全部方法，还增加了一些根据元素索引来操作集合的方法：

• void add(int index, E element)：将指定元素添加到指定位置，原index及之后位置的元素都向后移动
• E get(int index)：返回指定位置的元素
• E remove(int index)：移除指定位置的元素，返回被移除的元素
• E set(int index, E element)：用指定元素替换集合中指定位置的元素，返回被替换的元素

list集合的三种遍历方式：

1. 普通for循环
2. 使用迭代器
3. 增强for循环

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("a");

// 1. 普通for循环
for(int i = 0; i < list.size(); i++) {
    String str = list.get(i);
    System.out.println(str);
}

// 2. 使用迭代器
Iterator<String> it = list.iterator();
while(it.hasNext()) {
    String str = it.next();
    System.out.println(str);
}

// 3.增强for循环
for (String str : list) {
    System.out.println(str);
}

---

ArrayList

java.util.ArrayList集合的存储结构是动态数组。由于日常开发中使用最多的功能为查询和遍历数据，而不是增删操作，因此ArrayList是最常用的集合。

---

LinkedList

java.util.LinkedList集合的存储结构是双向链表，可以快速完成插入和删除元素的操作。LinkedList能用作栈、队列和双向队列。

LinkedList包含了大量操作首尾元素的方法，使用这些方法时，不能使用多态：

• void addFirst(E e)

  void push(E e)等效于该方法

• void addLast(E e)

  void add(E e)等效于该方法，可读性不如

• E getFirst()

• E getLast()

• E removeFirst()

  E pop()等效于该方法

• E removeLast()

---

Vector

和ArrayList类似，但它是线程安全的。

---

Set 接口

java.util.Set同样继承自Collection接口，它与Collection接口中的方法基本一致，没有进行功能上的扩充，只是更严格。Set接口中，元素无序且不可重复。

---

Set不允许重复元素的原理

Set集合在调用add方法的时候，add方法会调用元素的hashCode方法和equals方法，判断元素是否重复。存储的元素必须重写hashCode方法和equals方法，建立自己的比较方式。

---

HashSet

java.util.HashSet是Set接口的一个实现类，元素无序且不可重复，基于哈希表（实际上是一个HashMap实例）实现。

HashSet根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。

jdk 1.8之前，哈希表 = 数组 + 链表；jdk 1.8开始，哈希表 = 数组 + 链表/红黑树。数组的初始容量为16。

1. 先计算元素的hash值，hash值即作为在数组中对应的下标；
2. 存在不同的元素拥有相同的hash值（hash冲突），数组中存储的元素为链表/红黑树，链表/红黑树中存放最终的元素（相同hash值的元素超过了8个，就会改链表为红黑树存储元素）。

---

LinkedHashSet

java.util.LinkedHashSet继承了HashSet类，基于哈希表 + 双向链表（维护元素的插入顺序），保证元素有序。

---

TreeSet

基于红黑树实现，元素有序。

查找效率不如HashSet，HashSet查找的时间复杂度为O(1)，TreeSet则为O(logN)。

---

Queue 接口

Queue实现了一个FIFO的队列，常用方法如下：

	throw Exception	返回false或null
添加元素到队尾	add(E e)	boolean offer(E e)
取队首元素并删除	E remove()	E poll()
取队首元素但不删除	E element()	E peek()

---

PriorityQueue

• PriorityQueue基于堆结构实现，可以用它来实现优先队列。

• PriorityQueue在获取队首元素时，总是返回优先级最高的元素。

• 默认按元素比较的顺序（小顶堆）排序（必须实现Comparable接口）

• 可以通过Comparator自定义排序算法（不必实现Comparable接口）

---

Deque

Deque实现了一个双端队列（Double Ended Queue），实现类有：

• ArrayDeque
• LinkedList

总是使用xxxFirst/xxxLast，以便和Queue的方法区分开。

// 多态，让LinkedList这种具有多种功能的类的角色更明确
Deque<String> deque = new LinkedList<>();

---

Collections 类

java.utils.Colletcions是集合工具类，用来对集合进行操作。部分方法如下：

• static <T> boolean addAll(Collection<T> c, T... elements)：往集合中添加多个元素
• static void shuffle(List<?> list)：打乱集合顺序
• static <T> void sort(List<T> list)：将集合中元素按照默认规则(升序)排序
• static <T> void sort(List<T> list, Comparator<? super T>)：将集合中元素按照指定规则排序

ArrayList<String> list = new ArrayList<>();
Collections.addAll(list, "a", "b", "c", "d", "e");

Collections.shuffle(list);

sort(List<T> list) 方法的使用

参与排序的集合中存储的元素，必须实现comparable接口，重写接口中的compareTo方法，定义默认排序的规则。

Comparable接口的排序规则：

• compareTo方法返回0，认为相等
• compareTo方法返回正数，当前对象后置
• compareTo方法返回负数，当前对象前置

public class Person implements Comparable<Persion> {
    private String name;
    private int age;
    
    public int getAge() {
        return age;
    }
    
    public void setAge(int age) {
        this.age = age;
    }
    
    // 重写排序的规则
    @override
    public int compareTo(Person p) {
        // 返回0表示：认为元素是相同的
        
        //自定义比较规则，比较两个人的年龄
        return this.getAge() - p.getAge(); // 按年龄升序排序
    }
    
}

---

sort(List<T> list, Comparator<? super T>) 方法的使用

Comparator和Comparable的区别：

• Comparable是自己(this)和别人(参数)比较，需要实现Comparable接口，重写compareTo方法
• Comparator相当于找一个裁判，重写compare方法，不需要实现Comparable接口

Collections.sort(list1, new Comparator<Student>() { //匿名类
    //重写比较规则
    @Override
    public int compare(Student s1, Student s2) {
        int result = s1.getAge() - s2.getAge(); // 返回正数，s1后置；返回负数，s1前置
        if (result == 0) {
		result = o1.getName().charAt(0) - o2.getName().charAt(0);
        }
        return result;
    }
})

---

Map 接口

Map<K, V>是将键映射到值的对象。元素无序且不能包含重复的键（可以有一对一和多对一的关系）。

常用方法：

• V put(K key, V value)：如果插入的键值key未重复，返回值的V为null；否则返回被替换的value
• V get(Object key)
• V remove(Object key)
• boolean containsKey(Object key)

遍历相关方法：

• Set<K> keySet()：获取Map集合中所有的键，存储到Set集合中

  第一种遍历方式：通过键找值的方式

  1. 使用Map集合的keySet()方法，把Map集合所有的key取出来，存储到一个Set集合中
  2. 遍历Set集合，获取每个key
  3. 通过Map集合的get(key)方法，通过key找到value

  Map<String, Integer> map = new HashMap<>();
  map.put("苏炳添", '32');
  map.put("刘翔", '38');
  
  for(String key : map.keySet()) {
      Integer value = map.get(key);
      System.out.println(key + "=" + value);
  }

• Set<Map.Entry<K, V>> entrySet()

  Map.Entry<K, V>是Map接口中的一个内部接口，当Map集合创建，就会在Map集合中创建一个Entry对象，用来记录键与值（键值对对象、键与值的映射关系）。

    - `K getKey()`
    - `V getValue()`
  

  entrySet()方法将Map集合内部的多个Entry对象取出来，存储到一个Set集合中。

  第二种遍历方式：通过Entry对象遍历

  1. 使用Map集合中的方法entrySet()，把Map集合中多个Entry对象取出来， 存储到一个Set集合中
  2. 遍历Set集合，获取每一个Entry对象
  3. 使用Entry对象中的getKey()和getValue()获取键与值

  Map<String, Integer> map = new HashMap<>();
  map.put("苏炳添", '32');
  map.put("刘翔", '38');
  
  Set<Entry<String, Integer>> set = map.entrySet();
  
  for(Map.Entry<String, Integer> entry : set) {
      String key = entry.getKey();
      Integer value = entry.getValue();
      System.out.println(key + "-->" + value);
  }

---

HashMap

java.util.HashMap<K, V>是Map接口的一个实现类，元素无序且不能包含重复的键，基于哈希表实现。

jdk 1.8之前，哈希表 = 数组 + 链表；jdk 1.8开始，哈希表 = 数组 + 链表/红黑树。数组的初始容量为16。

1. 先计算元素的hash值，hash值即作为在数组中对应的下标；
2. 存在不同的元素拥有相同的hash值（hash冲突），数组中存储的元素为链表/红黑树，链表/红黑树中存放最终的元素（相同hash值的元素超过了8个，就会改链表为红黑树存储元素）。

HashMap 不允许重复键的原理

HashMap在调用put方法的时候，put方法会调用key的hashCode方法和equals方法，判断元素是否重复。存储的元素必须重写hashCode方法和equals方法，建立自己的比较方式。

---

LinkedHashMap

java.util.LinkedHashMap继承了HashMap类，基于哈希表 + 双向链表（维护元素的插入顺序），保证元素有序。

---

HashTable

与其他集合框架不同，HashTableK/V都不允许存储null对象，底层是一个哈希表。另外它是线程安全的。

它是遗留类，不应该去使用它，而是使用ConcurrentHashMap来支持线程安全，ConcurrentHashMap的效率会更高，因为ConcurrentHashMap引入了分段锁。

HashTable的子类Properties(唯一和IO流相结合的集合)依然活跃着。

---

TreeMap

基于红黑树实现

---

容器中的设计模式

---

适配器模式

java.util.Arrays.asList()可以把数组类型转换为List类型：

@SafeVarargs
public static <T> List<T> asList(T... a)

值得注意的是，asList的参数是泛型的变长参数，不能使用基本类型数组作为参数，只能使用相应的包装类型数组。

Integer[] arr = {1, 2, 3};
List list = Arrays.asList(arr);

// 也可以采用如下方式调用asList()
List list = Arrays.asList(1, 2, 3);

---

泛型

泛型即参数化类型。一提到参数，最熟悉的就是定义方法时有形参，然后调用此方法时传递实参。那么参数化类型怎么理解呢？顾名思义，就是将类型由原来的具体的类型参数化，类似于方法中的变量参数，此时类型也定义成参数形式（可以称之为类型形参），然后在使用/调用时传入具体的类型（类型实参）。

泛型的本质是为了参数化类型（在不创建新的类型的情况下，通过泛型指定的不同类型来控制形参具体限制的类型）。也就是说在泛型使用过程中，操作的数据类型被指定为一个参数，这种参数类型可以用在类、接口和方法中，分别被称为泛型类、泛型接口、泛型方法。

举例

List arrayList = new ArrayList();
arrayList.add("aaaa");
arrayList.add(100);

for(int i = 0; i< arrayList.size();i++){
    String item = (String)arrayList.get(i);
    Log.d("泛型测试","item = " + item);
}

ArrayList可以存放任意类型，例子中添加了一个String类型，添加了一个Integer类型，再使用时都以String的方式使用，因此程序崩溃了。为了在编译阶段解决类似这样的问题，泛型应运而生。

List<String> arrayList = new ArrayList<String>();

---

特性

泛型只在编译阶段有效。看下面的代码：

List<String> stringArrayList = new ArrayList<String>();
List<Integer> integerArrayList = new ArrayList<Integer>();

Class classStringArrayList = stringArrayList.getClass();
Class classIntegerArrayList = integerArrayList.getClass();

if(classStringArrayList.equals(classIntegerArrayList)){
    Log.d("泛型测试","类型相同");
}

输出结果：D/泛型测试: 类型相同。

通过上面的例子可以证明，在编译之后程序会采取去泛型化的措施。也就是说Java中的泛型，只在编译阶段有效。在编译过程中，正确检验泛型结果后，会将泛型的相关信息擦除，并且在对象进入和离开方法的边界处添加类型检查和类型转换的方法。也就是说，泛型信息不会进入到运行时阶段。

泛型类型在逻辑上看以看成是多个不同的类型，实际上都是相同的基本类型。

---

泛型的使用

泛型类

泛型类型用于类的定义中，被称为泛型类。通过泛型可以完成对一组类的操作对外开放相同的接口。最典型的就是各种容器类，如：List、Set、Map。

泛型类的最基本写法：

class 类名称 <泛型标识：可以随便写任意标识号，标识指定的泛型的类型>{
  private 泛型标识 /*（成员变量类型）*/ var; 
  .....

  }
}

// 例子
//此处T可以随便写为任意标识，常见的如T、E、K、V等形式的参数常用于表示泛型
//在实例化泛型类时，必须指定T的具体类型
public class Generic<T> {
    //key这个成员变量的类型为T，T的类型由外部指定  
    private T key;

    public Generic(T key) { //泛型构造方法形参key的类型也为T，T的类型由外部指定
        this.key = key;
    }

    public T getKey() { //泛型方法getKey的返回值类型为T，T的类型由外部指定
        return key;
    }
}

//泛型的类型参数只能是类类型（包括自定义类），不能是简单类型
//传入的实参类型需与泛型的类型参数类型相同，即为Integer.
Generic<Integer> genericInteger = new Generic<Integer>(123456);

//传入的实参类型需与泛型的类型参数类型相同，即为String.
Generic<String> genericString = new Generic<String>("key_vlaue");
Log.d("泛型测试", "key is " + genericInteger.getKey());
Log.d("泛型测试", "key is " + genericString.getKey());

定义的泛型类，就一定要传入泛型类型实参么？并不是这样，在使用泛型的时候如果传入泛型实参，则会根据传入的泛型实参做相应的限制，此时泛型才会起到本应起到的限制作用。如果不传入泛型类型实参的话，在泛型类中使用泛型的方法或成员变量定义的类型可以为任何的类型。

Generic generic = new Generic("111111");
Generic generic1 = new Generic(4444);
Generic generic2 = new Generic(55.55);
Generic generic3 = new Generic(false);

---

泛型接口

泛型接口与泛型类的定义及使用基本相同。泛型接口常被用在各种类的生产器中，可以看一个例子：

//定义一个泛型接口
public interface Generator<T> {
    public T next();
}

• 未传入泛型实参时，与泛型类的定义相同，在声明类的时候，需将泛型的声明也一起加到类中。

  // 如果不声明泛型，如：class FruitGenerator implements Generator<T>，编译器会报错："Unknown class"
  class FruitGenerator<T> implements Generator<T>{
      @Override
      public T next() {
          return null;
      }
  }

• 当实现泛型接口的类，传入泛型实参时

  /**
   * 定义一个生产器实现这个接口，虽然我们只创建了一个泛型接口Generator<T>
   * 但是我们可以为T传入无数个实参，形成无数种类型的Generator接口。
   * 在实现类实现泛型接口时，如已将泛型类型传入实参类型，则所有使用泛型的地方都要替换成传入的实参类型
   * 即：Generator<T>，public T next();中的T都要替换成传入的String类型。
   */
  public class FruitGenerator implements Generator<String> {
  
      private String[] fruits = new String[]{"Apple", "Banana", "Pear"};
  
      @Override
      public String next() {
          Random rand = new Random();
          return fruits[rand.nextInt(3)];
      }
  }

---

泛型通配符

当使用泛型类或者接口时，传递的数据中，泛型类型不确定时，无法通过Object类型表示任意类型，因为泛型没有继承的概念，可以通过通配符<?>表示。但是一旦使用泛型的通配符后，只能使用Object类中的共性方法，集合中元素自身方法无法使用。

---

通配符基本使用

泛型的通配符：不知道使用什么类型来接收的时候可以使用?，表示未知通配符。

泛型通配符不能在创建对象时使用，只能作为方法的参数使用。

例：定义一个能遍历所有类型的ArrayList集合。使用通配符 ? 的方法不能向 list 添加除 null 以外的任何元素。

public static void printArray(ArrayList<?> list) {
    // 使用迭代器遍历集合
    Iterator<?> it = list.iterator();
    while(it.hasNext()) {
        Object o = it.next(); //next方法返回Object类型的元素
        System.out.println(o);
    }
}

---

泛型通配符高级使用——受限泛型

JAVA的泛型可以指定上限和下限。

• 泛型的上限

  类型名称 <? extends 类> 对象名称：只能接收该类型及其子类

• 泛型的下限

  类型名称 <? super 类> 对象名称：只能接收该类型及其父类

---

红黑树

特点

1. 根节点是黑节点

2. 叶子节点（红黑树只有null节点称为叶子节点)是黑节点(红黑树是一棵满二叉树)

   可知，红黑树中至少有一半以上的节点是黑节点

3. 红节点的子结点必须是黑节点（红节点出现的条件很严苛，红节点出现最频繁的情况下，树中的节点也是红黑交错的）

4. 新插入的节点是红节点（为了达到平衡，后续也可能会变成黑节点）

5. 从任意一个节点出发，到任意叶子节点的路径上，黑节点的数量都一样（红黑树的平衡条件）

平衡二叉树（AVL树）的平衡条件是左右子树的深度差<=1；而红黑树没有这么严格，根据上述特点，可以得知其平衡条件为左右子树深度差在一倍以内（特点3 + 5），因此红黑树写的性能更高些。

如果将红黑树中的红节点忽略，黑节点构成的树就是一棵平衡二叉树。红黑树最差情况下（红黑相间，深度翻一倍）的时间复杂度为$O(2\log n_{black}) = O(2\log {n\over2})=O(2(\log n- 1))=O(\log n)$​

---

相关面试题：JAVA 1.8 HashMap的实现，每一个**桶？**是一个链表，当链表的长度>=8，就会变成红黑树。为什么要选择红黑树这种结构，而不是二叉搜索树或者平衡二叉树？

当元素有序时，二叉搜索树会退化为链表，没有实现性能的优化；AVL树相对于红黑树，其平衡条件更严格，红黑树的插入效率要更高一些，在实际的应用中，红黑树更符合性能的需要。