Clamli

1. Java 基础知识点
2. Java 常见集合
3. 高并发编程（JUC包）
4. JVM 内存管理
5. Java 8 知识点
6. 网络协议相关
7. 数据库相关
8. 操作系统相关
- 8.1 进程死锁
9. MVC框架相关
- 9.1 Spring
10. 大数据相关
- 10.1 KafKa基本特性
- 10.2 核心概念
11. Linux命令相关
12. 线性代数相关
- 12.3 SVD
13. 机器学习相关

1. Java 基础知识点

1.1 面向对象的特性有哪些

封装：把对象的属性和行为封装起来，只提供用户可操作属性和行为的接口而隐藏内部数据。

继承：复用已有的属性和行为（父类），添加新的属性和行为（子类）。

多态：程序中定义的引用变量所指向的具体类型和通过该引用变量发出的方法在编程时不确定，在程序运行期间才确定。如Parent p = new Child()，p向上转型为Parent类型，除了能够引用父类的共性外，还可以使用子类强大的功能。

Example:

public class Wine {
    public void fun1(){
        System.out.println("Wine 的Fun.....");
        fun2();
    }
    
    public void fun2(){
        System.out.println("Wine 的Fun2...");
    }
}

public class JNC extends Wine{
    /**
     * @desc 子类重载父类方法
     *        父类中不存在该方法，向上转型后，父类是不能引用该方法的
     * @param a
     * @return void
     */
    public void fun1(String a){
        System.out.println("JNC 的 Fun1...");
        fun2();
    }
    
    /**
     * 子类重写父类方法
     * 指向子类的父类引用调用fun2时，必定是调用该方法
     */
    public void fun2(){
        System.out.println("JNC 的Fun2...");
    }
}

public class Test {
    public static void main(String[] args) {
        Wine a = new JNC();
        a.fun1();
    }
}

Output:

Wine 的Fun…

JNC 的Fun2…

原因：重载后的fun1(String a)和父类中的fun1()不是同一个方法，父类类型的引用可以调用父类中定义的所有属性和方法，不能调用只存在与子类中的方法和属性。

1.2 覆盖（重写）和重载

覆盖/重写（overriding）：子类重新定义了父类的方法，但保证方法名相同、参数列表相同、返回类型相同

重载（overloading）：方法名一样，参数类型和个数不一样，返回值类型可以相同也可以不同。前两者为必须满足。

1.3 抽象类和接口的区别

抽象类：

1
2
3

public abstract class Test {
    abstract void testAbstract(); //抽象方法
}

* 只要类中有一个抽象方法，此类就被标记为抽象类

* 抽象方法没有方法体

* 抽象类被继承后要实现其中所有抽象方法，保证方法名相同、参数列表相同、返回类型相同

为什么接口会出现？

因为有抽象类存在，所有的子类都需要继承抽象类、实现抽象方法。如果当前子类不需要该抽象方法，会造成代码冗余，但也不能将该抽象方法放于其他类中，让该方法的子类继承那个类和抽象类，因为Java规定类不能继承多个父类。

接口：

1
2
3

public interface drawTest {
    void draw(); //接口内的方法，省略abstract关键字
}

* 接口是抽象类的延伸（纯粹的抽象类），接口中所有的方法都没有方法体

* 接口中任何方法都是public和abstract的

* 接口中任何字段都是static和final的

上述的问题中，可以将部分子类要继承的方法放到接口中，这些子类实现该接口，同时也能继承父类。

抽象类和接口如何选择？

* 优先定义接口

* 如果有多个接口实现有公用的部分，使用抽象类集成它们

1.4 Java 和 C++ 的区别

1.5 Java 中的值传递和引用传递

值传递

当一个参数通过值传递时，调用函数和被调用函数对同一个值有两个不同的变量来代表，如果被调函数改变了变量的值，调用函数无法获知改变。

引用传递

当一个参数通过引用传递时，调用函数和被调用函数使用相同的变量来表示同一个参数。如果被调用函数修改了参数的值，调用函数可以获得这个改变。

Java是值传递

Java传递的是地址引用的拷贝，所以Java还是值传递。

1.6 JDK 中常用的包有哪些

java.lang

Object类
数据类型包装类：如Integer、Float、Boolean
Math类
String类和StringBuffer类
Thread类
Throwable（所有错误和异常处理的父类），Exception（处理异常，需要用户捕获处理）和Error（处理硬件错误，不要求用户捕获处理）

java.util

日期类
数据结构类：如LinkedList、Vector、Stack、Hashtable
随机数类

java.awt

提供了绘图和图像类，主要用于编写GUI程序，包括按钮、标签等常用组件以及相应的事件类

javax.swing

轻量级的窗口工具包，这是目前使用最广泛的GUI程序设计包

java.io

提供了系统输入输出类和接口，只要包括输入流类InputStream和输出流OutputStream就可以实现文件的输入输出、管道的数据传输以及网络数据传输的功能

1.7 JDK, JRE 和 JVM 的联系和区别

JVM: Java Virtual Machine

a specification that provides a runtime environment in which Java bytecode can be executed.

JRE: Java Runtime Environment

a set of software tools which are used for developing Java applications. It is used to provide the runtime environment. It is the implementation of JVM. It contains a set of libraries + other files that JVM uses at runtime.

JDK: Java Development Kit

a software development environment which is used to develop Java applications and applets. It physically exists. It contains JRE + development tools.
The JDK contains a private Java Virtual Machine (JVM) and a few other resources such as an interpreter/loader (java), a compiler (javac), an archiver (jar), a documentation generator (Javadoc), etc. to complete the development of a Java Application.

Note: 如果已经安装了 JDK，就没有必要安装 JRE了，因为 JDK中通常包括 JRE。当客户端想要执行 Java程序而不需要考虑编译时，只需要安装 JRE即可，可以减少存储占用。

1.8 Java 中的异常

Throwable为所有异常的顶层父类，派生出Error类和Exception类。

Error类：很少出现，代表JVM本身的错误，不能通过代码解决。

Exception类：代表程序运行时发送的各种不期望发生的事件，可以被Java异常处理机制使用，是异常处理的核心。
非检查异常（unchecked exception）：Error + Runtime Exception。这些异常在编译时，不会被提示或者发现。这些异常可以通过手动使用try+catch+finally来处理，但对于这些异常，正确的方法应该是修改代码，而不是通过异常处理器处理。
检查异常（checked exception）：IOException。这些异常要求程序员强制做预备处理工（try+catch+finally or throws），否则编译不通过。该异常通常是由于程序运行环境造成，由于程序可能运行在未知环境下，因此使用这些异常为未知做准备。

try：

try中放可能发生异常的代码。
如果执行完try且不发生异常，则接着执行finally和finally后面的代码。
如果发生异常，先匹配catch块。

catch：

异常匹配按照catch块的顺序从上往下寻找，只有第一个匹配的catch会得到执行。
匹配时支持父类匹配，因此如果同意try块下有多个catch异常类型有父子关系，应该将子类异常放在前面，父类异常放在后面。（这样子类异常不会匹配到父类的catch块中去）

finally：

可选块。
无论异常是否发生，异常是否匹配被处理，finally块都会被执行。
一个try块至少要有一个catch块，否则，至少要有一个finally块。
finally主要做一些清理工作，如流的关闭，数据库连接的关闭。
如果在catch里有return语句且异常被匹配，那么在return之前会先做完finally块的内容。

throws 函数声明：

如果一个方法内部代码抛出检查异常（checked exception），而方法自己没有处理（单纯用throw异常抛出语句抛出），则必须使用throws关键字声明可能抛出的异常，否则无法通过编译
throws是另一种处理异常方式，不同于try+catch+finally，throws仅仅将函数中可能出现的异常向调用者声明，自己不具体处理。

throw异常抛出语句：

使用throw语句手动抛出异常，throw Exception Object。
throw语句写在函数中，执行throw语句的地方就是一个异常抛出点。

throws 和 throw的异同:

throw用在方法体内,用来抛出一个异常：throw Exception Object
throws用在方法声明后面,用来告知此方法可能抛出的异常，方法调用者需要处理上述异常
1
public void func() throws Exception1, Exception2, ... {}
两者都是消极处理异常的方式，只是抛出或者可能抛出异常，但是不会由函数去处理异常，真正的处理异常由函数的上层调用来做

异常注意事项：

当子类重写父类带有throws声明的函数时，用于处理父类throws方法的异常处理器也必须适用于子类这个带throws的方法，为了支持多态。例如，父类throws 2个异常，子类就不能throws 2个以上的异常。父类throws IOException，子类就必须throws IOException或者其子类。
finally中的return 会覆盖 try 或者catch中的返回值，finally中的return会抑制（消灭）前面try或者catch块中的异常，finally中的异常会覆盖（消灭）前面try或者catch中的异常。因此不要在finally中使用return！！！尽量将所有的return都放到try+catch+finally外，而不是里面。

1.9 Java 中的迭代器

Iterator 是常用的遍历 Collection的方法之一。它最早在 Java 1.2 里被提出，用作 Enumerations 的替代。它具有一下特性：

引入了更符合规范的方法名
遍历 Collection 时允许删除操作
不保证遍历顺序

使用 Iterator 的步骤

drawing

获取 Collection 的 Iterator（最开始为 Iterator1 的位置）
1
2
List<Object> items = ...
Iterator<Object> iter = items.iterator();
hasNext(): 查看是否还有未迭代到的元素
1
2
3
while (iter.hasNext()) {
// ...
}
next(): 返回指针指向的元素，指针下移
1
Object next = iter.next()
remove(): 删除上次调用next方法时返回的元素
1
iter.remove()

迭代器删除

while (it.hasNext()) {
    Object obj = it.next();
    it.remove();
}

# ArrayList 为什么要实现自己的迭代器

使用范围不同，Iterator 可以应用于所有的集合，Set、List 和 Map 和这些集合的子类型。而 ListIterator 只能用于List及其子类型。
ListIterator 有add方法，可以向List中添加对象，有set()方法，可以实现对象修改。
ListIterator 有 hasPrevious() 和 previous() 方法，可以实现逆向（顺序向前）遍历。
ListIterator 可以定位当前索引的位置，nextIndex() 和 previousIndex() 可以实现。

2. Java 常见集合

Collection接口的子接口包括：Set接口和List接口
- Set接口
- List接口
Map接口的实现类主要有：HashMap, TreeMap, ConcurrentHashMap, HashTable以及Properties等
Set接口的实现类主要有：HashSet, TreeSet, LinkedHashSet等
List接口的实现类主要有：ArrayList, LinkedList, Stack以及Vector等

2.1 HashMap

# HashMap 是什么？

HashMap继承于AbstractMap抽象类，实现Cloneable和Serializable接口，以 (Key, Value) 对的形式保存数据。
HashMap内部包含了一个Node数组，如下图所示。Node数组是一个包含四个元素的类，其中有一个元素为Node对象的引用，因此每一个Node都是一个linked list。

HashMap:

Node:
1
2
3
4
5
6
Class Node {
int hash;
K key;
V value;
Node next;
}

# HashMap的两个参数

Initial Capacity: 决定了HashMap的初始大小
Load Factor: 决定了HashMap填充到何种程度时进行rehash，一般设定为0.75

# 怎么让 HashMap Synchronized ?

HashMap是unsynchronized类，因此有多个线程要同时操作同一个HashMap对象并涉及到值的更改时，需要先将其Synchronized。常见方法：

1	Map m = Collections.synchronizedMap(new HashMap(...));

# Hashing 是怎么工作的？

hashCode(): 用来得到对象的hash值，以此确定对象应该放在哪个下标对应的bucket中 (bucket就是一个Node对象构成的linked list)。
equals(): 用于确定两个对象是否相等。

Hashing首先利用hashCode()得到对象的hash值，确定对象的下标，然后用equals()比较对象和下标对应的bucket中的对象是否相等。若相等，则原Map中存在当前对象，反之则不存在。所有put, remove, containsKey等操作都是基于此。

# HashMap 在 Java 8中的变化

由于对象在HashMap中是存储于每个下标对应的linked list中，因此查找时最坏时间复杂度为$O(N)$。为了解决这个问题，Java 8中提出了平衡树（红黑树）的结构来存储linked list中的元素。当HashMap中元素个数达到一定程度后（>8），原来的线性链表结构会转化成平衡树结构，以达到$O(log N)$的时间复杂度。
扩容机制发生改变。在 Java 7 中，扩容时现存元素的位置不发生改变（头插法，在链表中的位置可能发生改变）；在 Java 8 中，扩容后原元素的位置可能不发生改变，也可能为原位置+扩容前容量，取决于hash值高位的bit是0还是1。

2.2 TreeMap

2.3 ConcurrentHashMap

# 为什么我们需要 ConcurrentHashMap?

HashMap的实现不是线程安全的
HashTable的实现是线程安全，但是代价太高

# ConcurrentHashMap是什么？

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对；Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。ConcurrentHashMap 在默认并发级别会创建包含 16 个 Segment 对象的数组。每个 Segment 的成员对象 table 包含若干个散列表的桶。每个桶是由 HashEntry 链接起来的一个链表。如果键能均匀散列，每个 Segment 大约守护整个散列表中桶总数的 1/16。ConcurrentHashMap 允许完全并发的读取，并且支持给定数量的并发更新。

drawing

# ConcurrentHashMap分离锁的细节

在 ConcurrentHashMap 中，线程对映射表做读操作时，一般情况下不需要加锁就可以完成，对容器做结构性修改的操作才需要加锁。加锁操作是针对（键的 hash 值对应的）某个具体的 Segment，锁定的是该 Segment 而不是整个 ConcurrentHashMap。当一个Segment被加锁时，其他写线程对另外 15 个Segment 的加锁并不会因为当前线程对这个 Segment 的加锁而阻塞。同时，所有读线程几乎不会因本线程的加锁而阻塞（除非读线程刚好读到这个 Segment 中某个 HashEntry 的 value 域的值为 null，此时需要加锁后重新读取该值）。

2.4 HashTable

2.5 Properties

2.6 HashSet

2.7 TreeSet

2.8 LinkedHashSet

2.9 ArrayList

2.10 LinkedList

2.11 Stack

2.12 Vector

# 相关问题

HashMap和HashTable的区别有哪些？
1. Hashtable继承自Dictionary，而HashMap继承自AbstractMap。
2. HashMap是unsynchronized，非线程安全；HashTable是Synchronized，线程安全。
3. HashMap允许出现null的key和value，而HashTable的key和value均不可为null，如果key==null，运行时会抛出NullPointerException异常。
4. HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey；Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。
ConcurrentHashMap的具体实现
HashMap的长度为什么是2的幂次方？

在计算索引时，我们一般采取h % length的方式，当length是2的幂次时，h % length=h & (length - 1) ，将取余运算转化为按位运算，提高运算效率。
List和Set的区别是什么？
List, Set和Map的初始容量和加载因子
Comparable接口和Comparator接口有什么区别？
Java集合的快速失败机制“fail - fast”

3. 高并发编程（JUC包）

3.1 多线程和单线程的区别和联系

3.2 如何指定多个线程的执行顺序

3.3 线程和进程的区别

Process

Each process provides the resources needed to execute a program. A process has a virtual address space, executable code, open handles to system objects, a security context, a unique process identifier, environment variables, a priority class, minimum and maximum working set sizes, and at least one thread of execution. Each process is started with a single thread, often called the primary thread, but can create additional threads from any of its threads.

Thread

A thread is the entity within a process that can be scheduled for execution. All threads of a process share its virtual address space and system resources. In addition, each thread maintains exception handlers, a scheduling priority, thread local storage, a unique thread identifier, and a set of structures the system will use to save the thread context until it is scheduled. The thread context includes the thread’s set of machine registers, the kernel stack, a thread environment block, and a user stack in the address space of the thread’s process. Threads can also have their own security context, which can be used for impersonating clients.

3.4 多线程产生死锁的4个必要条件

3.5 sleep()和wait(n), wait()的区别

3.6 synchronized关键字

当多个线程访问同一个变量时，可用synchronized关键字来保证访问次序，避免冲突。被synchronized修饰的代码段在同一时刻只能被一个线程执行。

synchronized关键字可以被用在三个层次

实例方法

1
2
3

public synchronized void synchronisedCalculate() {
    setSum(getSum() + 1);
}

静态方法

1
2
3

public static synchronized void syncStaticCalculate() {
    staticSum = staticSum + 1;
}

代码块

inside non-static method

public void performSynchrinisedTask() {
    synchronized (this) {
        setCount(getCount()+1);
    }
}

inside static method

public static void performStaticSyncTask(){
    synchronized (SynchronisedBlocks.class) {
        setStaticCount(getStaticCount() + 1);
    }
}

3.7 volatile关键字

volatile关键字用来标识被修饰变量是“存储在主存中”。也就是说，该变量会被从主存中读出，并写回到主存中。volatile关键字保证了对变量的修改在不同线程中都可见。

drawing

如上图所示，在多线程应用中，若计算机有多个CPU，不同线程可能运行在不同的CPU上，使用不同的CPU缓存。若使用non-volatile变量，无法保证 JVM 什么时候将主存中的数据读入CPU缓存，也无法保证什么时候将缓存中的数据写入CPU主存。这会导致在某一线程中更新的变量不一定在另一线程中可见。

Full volatile Visibility Guarantee

If Thread A writes to a volatile variable and Thread B subsequently reads the same volatile variable, then all variables visible to Thread A before writing the volatile variable, will also be visible to Thread B after it has read the volatile variable.
If Thread A reads a volatile variable, then all all variables visible to Thread A when reading the volatile variable will also be re-read from main memory.

Java volatile Happens-Before Guarantee

Reads from and writes to other variables cannot be reordered to occur after a write to a volatile variable, if the reads / writes originally occurred before the write to the volatile variable.
Reads from and writes to other variables cannot be reordered to occur before a read of a volatile variable, if the reads / writes originally occurred after the read of the volatile variable.

volatile关键字在以下两个方面影响效率

读写主存远比读写缓存代价更大。
volatile阻止了指令重排，而指令重排是提高效率的方法之一。

3.8 ThreadLocal（线程局部变量）关键字

ThreadLocal的使用场景

如，对于涉及到多线程的数据库连接操作，如果对数据库连接和关闭进行同步，会大大影响效率。如果在数据库连接的方法中才创建数据库连接，在方法调用完毕后再关闭连接，则会产生频繁的数据库开启关闭，严重影响执行效率。可否对让每一个需要数据库连接的线程有一个connect变量，让各线程之间对connect变量的访问没有依赖关系，这样线程在使用该变量时就不需要考虑其它线程是否使用了相同变量。

ThreadLocal提供的方法

public T get() { }: 获取ThreadLocal在当前线程中保存的变量副本
public void set(T value) { }: 设置当前线程中变量的副本
public void remove() { }: remove()用来移除当前线程中变量的副本
protected T initialValue() { }: 初始化ThreadLocal变量

ThreadLocal和线程本地变量的区别

此段代码中count线程不安全

public class TestRunable implements Runnable {  
    private int count = 0;  
    @Override  
    public void run() {  
       ...  
    }  
}  
public static void main(String[] args) {  
    TestRunable runable = new TestRunable();  
    Thread a = new Thread(runable, "a");  
    Thread b = new Thread(runable, "b");  
    a.start();  
    b.start();  
}

此段代码中count线程安全

public class TestRunable implements Runnable {  
    private ThreadLocal<Integer> count = new ThreadLocal<Integer>();  
    @Override  
    public void run() {  
        ...  
    }  
}  
public static void main(String[] args) {  
    TestRunable runable = new TestRunable();  
    Thread a = new Thread(runable, "a");  
    Thread b = new Thread(runable, "b");  
    a.start();  
    b.start();  
}

ThreadLocal 变量只和线程有关，相当于为每一个线程提供一个独立的变量副本。

3.9 Atomic关键字

使用Atomic关键字的原因

如果有两个或多个线程同时获取和更新同一个变量，可能会导致数据的丢失。
使用锁（synchronized和volatile）能够解决问题，可是会降低效率，因为同一时刻只能有一个线程获取数据。

Atomic操作使用CAS（compare-and-swap）来确保数据完整性，避免阻塞进程。

CAS（compare-and-swap）是什么？

CAS是下面这段代码的原子操作

function cas(p : pointer to int, old : int, new : int) returns bool {
    if *p ≠ old {
        return false
    }
    *p ← new
    return true
}

使用CAS的操作从内存中读出数据并记住，然后根据该数据计算出新数据，在写回时先比对内存中数据是否和原始读出数据一致，如果一致，即将新数据写入内存，否则，可采用 exponential backoff 的机制重复执行相同操作（读取并写回）。

当多线程使用CAS更新同一个变量时，每次只能有一个线程成功。和锁不同的是，其它线程不会被阻塞，它们会被告知更新操作没有成功，并去执行其它操作。当成功的线程完成变量值更新后，其它线程可再次尝试更新变量。如下述代码所示为一个常见的原子自增操作：

public class SafeCounterWithoutLock {
    private final AtomicInteger counter = new AtomicInteger(0);
     
    public int getValue() {
        return counter.get();
    }
    public void increment() {
        while(true) {
            int existingValue = getValue();
            int newValue = existingValue + 1;
            if(counter.compareAndSet(existingValue, newValue)) {
                return;
            }
        }
    }
}

3.10 线程池

4. JVM 内存管理

4.1 JVM 内存划分

# JVM 内存是指那一部分？

drawing

如上图所示，Java源代码被编译为字节码文件后进入JVM，由类加载器加载对应类的字节码文件，然后交由JVM引擎执行。在执行过程中用来存储所需数据的内容的空间，被叫做Runtime Data Area (运行时数据区)，也就是常说的JVM内存。

# Runtime Data Area 分成哪几部分，分别的作用是什么？

程序计数器（Program Counter Register）：程序计数器也叫PC寄存器，是用来存储程序当前执行指令的地址（或下一条指令的起始地址）的寄存器。CPU要执行当前指令时，通过程序计数器获得当前指令所在存储单元的地址，从地址中获得当前需要执行的指令，然后将程序计数器移到下一指令的地址处。当有多个线程时，每个线程含有独立的程序计数器；当执行native方法时，程序计数器中的值undefined。
Java栈（Java Virtual Machine Stack）：Java栈是Java方法执行的内存模型。结构如下：

每一个栈帧中对应一个被调用的方法，栈帧包含的内容有：
- 局部变量表（Local Variables）：存储方法中的局部变量（非静态变量（值或引用）和函数形参），在编译器就可确定大小，在程序执行过程中大小不变。
- 操作数栈（Operand Stack）：执行程序中所有计算过程。
- 当前方法的运行时常量池：方法执行过程中需要用到类中的常量，用当前引用指向运行时常量。
- 方法返回地址
- 附加信息
Java栈也是线程私有的。
本地方法栈（Native Method Stack）：本地方法栈和Java栈类似。Java栈用来执行Java方法，本地方法栈用来执行本地方法。所谓本地方法，即Java用来调用非Java代码的接口。执行这些方法时不影响到Java栈，只需要简单动态连接并直接调用本地方法。
堆（Heap）：Java堆内存存储对象本身和数组（数组的引用存储在Java栈中）。堆中的空间由Java垃圾回收机制自动处理。Java堆是被线程共享的。
方法区（Method Area）：方法区中存储了类的信息（名称、方法信息、字段信息）、静态变量、常量和编译器编译后的代码等。方法区中包含了运行时常量池，它包括类或接口的常量池的运行时表示，以及运行期间产生的新的常量。方法区是线程共享的，且不强制实现垃圾回收。

4.2 类似-Xms, -Xmn这些参数的含义

4.3 垃圾回收算法

4.4 root搜索算法中，那些可以作为root

4.5 GC什么时候开始

4.6 内存泄漏和内存溢出

5. Java 8 知识点

5.1 HashMap的底层实现有变化

由于对象在HashMap中是存储于每个下标对应的linked list中，因此查找时最坏时间复杂度为$O(N)$。为了解决这个问题，Java 8中提出了平衡树（红黑树）的结构来存储linked list中的元素。当HashMap中元素个数达到一定程度后（>8），原来的线性链表结构会转化成平衡树结构，以达到$O(log N)$的时间复杂度。
扩容机制发生改变。在 Java 7 中，扩容时现存元素的位置不发生改变（头插法，在链表中的位置可能发生改变）；在 Java 8 中，扩容后原元素的位置可能不发生改变，也可能为原位置+扩容前容量，取决于hash值高位的bit是0还是1。

5.2 JVM内存管理方面，由元空间替代了永久代

5.3 Lambda表达式

5.4 函数式接口

5.5 引入重复注解

5.6 接口中可以实现方法default方法

5.7 注解的使用场景拓宽

5.8 新的包java.time包

6. 网络协议相关

6.1 三次握手，四次挥手

6.2 滑动窗口机制

6.3 拥塞避免机制

6.4 浏览器中输入：“

6.5 常见的HTTP状态码

6.6 TCP和UDP的区别

TCP:

6.7 TCP的重传机制

7. 数据库相关

7.1 MySQL和MongoDB的区别有哪些？如何选择？

7.2 MongoDB的优缺点有哪些？

7.3 事务

事务是一系列数据库操作组成的一个完整的逻辑过程，事务在SQL语句执行后开始，只有当以下两种情况发生时一个事务结束：

Commit work：提交当前事务，让事务更新的操作在数据库中被固化（become permanent in the database）。在当前事务被提交以后，一个新的事务自动开始。
Rollback work：使当前事务回滚，会撤销所有事务中执行过的语句。数据库的状态会回退到事务执行之前。

7.4 事务的四个重要特性（ACID）

Atomicity

一个事务（transaction）中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被恢复（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。

Durability

事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

Isolation

数据库允许多个并发事务同时对其数据进行读写和修改，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。

Consistency

一致性。在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设规则。如两个人之间进行银行转账，无论事务是否成功，在事务开始之前和结束之后两个人的存款总和必须一致。

7.5 事务的隔离级别有哪几种？

Serializable

串行化，这是最严苛的事务隔离级别。将所有事务串行化执行，简单暴力低效。

Repeatable read

只允许读取提交数据，而且要求在同一个事务对提交数据的读取过程中，不允许有其它事务更改对应数据。即同一事务多次读取同一条记录时，读取结果相同，可重复读。（Mysql默认事务隔离级别）

Read committed

只允许读取提交数据，但在同一事务对提交数据的读取过程中，允许其它事务更改对应数据。即同一事务多次读取同一条记录时，读得的结果可能相同，不可重复读。（Oracle默认事务隔离级别）

Read uncommitted

允许读取未提交数据，就是允许脏读。

数据库事务并发时存在的问题

脏读：读取未提交的数据
不可重复读：同一事务多次读取同一数据得到的结果不一致
幻读：是指当事务不是独立执行时发生的一种现象。比如事务A 将 T表中所有工资不到 10000元的员工的工资改为10000元，在事务A执行结束尚未提交时，事务B又插入了一条（或删除操作）工资不满10000元的员工记录，然后再提交事务A，事务B。事务A好像发生了幻觉，没有操作成功一样，这是因为”可重复读“锁定的是已经读取的记录，而不是锁定整张表（或者超出读取范围的数据），可重复读限制了事务本身涉及数据的update行为，但是无法限制事务自身以外的数据。我们可以使用表锁或者范围锁。

不同隔离级别对应的问题

drawing

7.6 数据库中的锁有哪几种？

锁的类型

行级锁
- 行级锁是锁定粒度最细的一种锁，表示只针对当前操作的行进行加锁。行级锁能大大减少数据库操作的冲突。其加锁粒度最小，但加锁的开销也最大。行级锁分为
  - 共享锁
  - 排他锁
表级锁
- 表级锁是MySQL中锁定粒度最大的一种锁，表示对当前操作的整张表加锁，它实现简单，资源消耗较少。表级锁分为
  - 表共享读锁（共享锁）
  - 表独占写锁（排他锁）
页级锁
- 页级锁是锁定粒度介于行级锁和表级锁中间的一种锁。表级锁速度快，但冲突多，行级锁冲突少，但速度慢。所以取了折衷的页级锁，一次锁定相邻的一组记录（8K ）。

共享锁和排他锁

共享锁：如果一个事务获得了Q的共享锁S，那么该事务可以读取Q但不能写Q。
排他锁：如果一个事务获得了Q的排他锁，那么该事务可以读写Q。

两阶段加锁协议（two-phase locking protocol）

Growing阶段: 一个事务可以获取锁，但不能释放锁（事务的初始化状态）
Shrinking阶段：一个事务可以释放锁，但不能获取锁

两阶段加锁可以保证冲突串行化。我们把事务获取它最后的锁的时间点（growing阶段的结束）叫作该事务的lock point。事务可以根据他们的lock point进行排序。这个排序就是事务的串行顺序。但两阶段加锁协议不保证避免死锁，同时可能会导致级联回滚。

严格的两阶段加锁协议（strict two-phase locking protocol）

用来避免级联回滚的发生。该协议不但要求两阶段锁，同时要求排他锁要一直保留到事务提交时才能释放。这确保了所有被未提交事务写的数据都要被排他锁锁住直到事务提交，防止了其他事务读取未提交的数据。

更严格的两阶段加锁协议（rigorous two-phase locking protocol）

要求所有锁都要在事务提交时才释放。

允许锁转换的两阶段加锁协议（two-phase locking protocol with lock conversion）

常规的两阶段加锁不允许锁的转换，因此如果之前是共享锁，之后是排他锁的对象会被用排他锁锁住，影响并发性。因此在新的两阶段加锁协议中允许以下两种锁转换：

在Growing阶段允许从共享锁升级到排他锁
在Shrinking阶段允许从排他锁降级到共享锁

7.7 数据库的索引有什么作用？底层数据结构是什么，为什么使用这种数据结构？

很多查询语句的结果只涉及到很少一部分记录。比如“找到学号为22201的学生取得的学分”，只会返回一条记录。但这句查询语句需要读取海量的记录并一一比对其学号是否为“22201”，这十分低效。因此，系统需要一个方法能更快地定位到数据在哪里，因此有了数据库索引。

最常见的底层数据结构是B+树，这是一种平衡树结构，从根到叶子节点的路径长度均相同，每一个节点有n/2到n个子节点（n对特定的树是确定的）。如图所示是B+树的节点，包括了从K1，K2，…，Kn-1的n-1个搜索键，以及n个指针P1，P2，…，Pn，节点中的搜索键以升序排列。Pi指向了Ki对应的记录，Pn指向了下一个子节点或下一个同层叶节点。

drawing

如下图所示是一个叶子节点与对应的记录。

drawing

如下图所示是一个完整的B+树。

drawing

B+树的查询

开始时，函数从树的根节点开始向下查找，直到达到叶子层。在每一个节点，函数首先寻找比目标值V大的最小的搜索键Ki。如果Ki等于V，则递归寻找Pi+1指向的节点；否则，寻找Pi指向的节点。

B+树也可以用来进行范围查找，如查找范围在 (L, U) 之间时，B+树可以先搜索L所在的节点，然后按链表搜索直至当前Ki的值大于U。

B+树的更新

B+树的更新被看作是将旧记录删除，并插入新记录，因此我们只考虑插入和删除两个基本指令。

B+树的插入

不涉及节点变更的插入：和查找一样，先找到新记录的搜索键可能出现的叶子节点，插入搜索键和指向该记录的指针，插入时仍保持顺序排列。
涉及节点变更的插入（根据split方法不同）
- 插入叶子节点
- 插入父节点

B+树的删除

不涉及节点变更的删除：和查找一样，先找到搜索键可能出现的叶子节点，如果由若干个相同搜索键，则遍历并找到待删除记录，然后将其删除并将右侧元素左移。
涉及节点变更的删除

B+树和B树的对比，为什么不用B树？

B树结构图

drawing

B+树结构图

drawing

由上图可以看出B树将数据存储在非叶子节点中（这是因为B树的叶子层不包括所有数据节点，因此无法将所有数据/数据指针存储在叶子层）。

因此，B+树相对于B树的优势在于

B+树的中间节点不保存数据，所以每个节点能容纳更多元素，使树更“矮胖”，降低时间复杂度
B+树查询必须查找到叶子节点，B树只要匹配到即可不用继续往下查找，因此B+树查找更稳定（并不慢）
对于范围查找来说，B+树只需遍历叶子节点链表即可，B树却需要重复地中序遍历

7.8 MyISAM和InnoDB的区别有哪些？

7.9 数据库中的关键字

where
group by
having
having和where的区别

7.10 数据库范式

7.11 MySQL和SQL Server用法上的区别

7.12 limit关键字的使用

7.13 Memcached是什么

Memcached 是一个高性能的分布式内存对象缓存系统，用于动态Web应用以减轻数据库负载。它通过在内存中缓存数据和对象来减少读取数据库的次数，从而提高动态、数据库驱动网站的速度。Memcached基于一个存储键/值对的hashmap。其守护进程（daemon ）是用C写的，但是客户端可以用任何语言来编写，并通过memcached协议与守护进程通信。

drawing

7.14 数据库的 Pages 和 Extents

Pages是数据库中的基本存储单元。分配给数据库数据文件的磁盘空间被分配成 Pages 的形式，并被编号，从0到n。数据库的I/O操作在Pages level进行，每次读取或写回完整的Pages 。Extents是8个连续Pages的集合，被用来高效地管理 Pages 。

以SQL Server为例，Pages是8KB大小，这意味着每MB有128个Pages。每个Page有96字节的头，用于存储Page的系统信息。这些信息包括Page编号, Page 类型, Page剩余可用空间和使用当前Page的对象的分配单元编号。

数据行按顺序存放在Pages中，在Page的结尾存放了行偏移表，每一个表中的元素记录了对应的行离Pages的开始有多少字节的距离。行偏移表中的元素倒序存储。

drawing

行的存储不允许跨Page，每个Page最多存储8060字节的数据（Text/Image类型的页除外）。当Page中内容超过8060字节的限制以后，一个或者多个变长列的数据就会被移动到ROW_OVERFLOW_DATA这个分配单元，从列宽最大的列开始。在原Page中会保存一个24字节的指针指向移动后的数据，如果Page的大小减少，列会被移回原Page。

以SQL Server为例，有两种Extents：

Uniform extents: extents被一个对象拥有。
Mixed extents: extents中的每一个Page可以从属于不同的对象。

drawing

7.15 什么是关系型数据库？

关系型数据库是基于关系型模型的一组表，用来表示数据内容和数据之间的关系。关系型模型是一种基于记录的模型，它由一组类型固定的记录组成。大部分关系型数据库采用SQL语言。

7.16 数据库的bitmap indexing

对某一属性F的Bitmap index是一个向量的集合，每个向量对应该属性的一类值，向量长度为记录条数，集合中向量个数为属性取值数目，如果r记录的F属性取值v，那么F属性对应的向量集合里第v个向量的r位置就是1，否则为0。

Bitmap Indexing的作用

Bitmap indexing可能会占用大量存储空间，那么为什么还要有这个数据结构存在呢？主要原因是以下两方面

高效支持记录查找

设想，我们对一张表的两个记录name和salary设有bitmap index，当一个查询，如下
1
2
SELECT id FROM Employ
WHERE name = 'Ben' AND salary = 5000
我们就可以取出和’Ben’相关的向量以及和5000相关的向量将其做AND操作，这样就可以直接获得我们需要的查询结果。
高效支持范围查找

设想，我们要查找的是salary的范围，如下
1
2
SELECT id FROM Employ
WHERE name = 'Ben' AND salary >= 5000 AND salary <= 10000
假设salary是离散值，我们可以取出所有salary取值在5000到10000的向量先做OR操作，再将结果和’Ben’向量做AND操作，即可直接获得查找结果。

Bitmaps压缩

该压缩方法分为两步：

将向量在任一1之前有多少个0出现做记录，如对100000001000即为0，7，3。
将0出现的个数进行编码，首先求出该个数有几位，然后将这个位数按照位数减一个1加一个0进行编码，再在后面跟上对该个数的编码。如0，即为0个1加1个0，再加一个0，即为00。同理，7即为2个1加1个0，再加111，为110111。3为1011。最终这个数字的编码为~~001101111011~~。Note: 对于原向量最后的0，一般不进行编码，因此上述的编码应为 00110111。

Bitmaps更新

当记录被删除时，直接将对应位置为1的向量值置0
当记录插入时，找到所有属性对应的向量集合，在插入属性值对应的向量末尾加1，非插入属性值向量末尾加0
当有新的值插入时，在该属性对应向量集合中加入新向量，并赋值

7.17 数据库的join

数据库的join操作是将多个表根据相同属性结合的一种操作，它的结果是一张可以被存储使用的新表。join操作包括INNER JOIN，LEFT OUTER, RIGHT OUTER, FULL OUTER和CROSS。表也可以和自己进行self join（自交，好污~）。

以下的操作均在如下两张表中进行：

drawing

# Cross join: 产生一张表，包括了第一张表中的所有行和第二张表中的所有行。

1
2
3

/* explicit join*/ 
SELECT *
FROM employee CROSS JOIN department;

1
2
3

/* implicit join*/ 
SELECT *
FROM employee, department;

# Inner join: Inner join在cross join之上要求被结合的两条记录在共有列（或指定共有列）上的值满足指定条件。

/* explicit join */
SELECT employee.LastName, employee.DepartmentID, department.DepartmentName 
FROM employee 
INNER JOIN department ON
employee.DepartmentID = department.DepartmentID

/* implicit join */
SELECT *
FROM employee, department
WHERE employee.DepartmentID = department.DepartmentID;

Equi-join

Equi-join是Inner join的一种，它要求约束条件必须是等式（=），因此它可以省略写成如下形式

1 2	SELECT * FROM employee INNER JOIN department USING (DepartmentID);

Natural join

Natural join是Equi-join的一种，它结合两张表在相同属性上值相等的所有行，且只保留两个相同属性中的一个。

1 2	SELECT * FROM employee NATURAL JOIN department;

# Left outer join: 返回两张表Inner join的结果，同时保留左表上所有匹配到或没有匹配到的值，没有值的地方填NULL。

1
2
3

SELECT *
FROM employee 
LEFT OUTER JOIN department ON employee.DepartmentID = department.DepartmentID;

# Right outer join: 返回两张表Inner join的结果，同时保留右表上所有匹配到或没有匹配到的值，没有值的地方填NULL。

1
2
3

SELECT *
FROM employee RIGHT OUTER JOIN department
  ON employee.DepartmentID = department.DepartmentID;

# Full outer join: 返回两张表Inner join的结果，同时保留两张表上所有匹配到或没有匹配到的值，没有值的地方填NULL。

1
2
3

SELECT *
FROM employee FULL OUTER JOIN department
  ON employee.DepartmentID = department.DepartmentID;

7.18 Bloom filter

Bloom filter是一个概率数据结构，用来测试查询元素是否位于集合中。查询该数据结构的返回值有两个，“可能在集合中”、“一定不在集合中”。

Bloom filter是一个数组，大小为m比特。对数组定义有k个hash函数，每个hash函数都平均地将集合元素映射到m个位置中的任意一个。k通常是一个远小于m的数字，和插入元素个数有关，k的大小会决定最后的false positive rate。

drawing

每当插入一个元素时，将元素送到k个hash函数算出k个位置，并将这k个位置的值都置1。

当查询元素时，将该元素送到k个hash函数算出k个位置，如果任意一个位置的值为0，那么该元素不在集合中；否则，如果所有均为1，那么要么这个元素在集合中，要么这些位是因为其它元素的插入变1。

使用bloom filter时可以有效减少磁盘访问次数，如下图所示，键值都存储在磁盘上。很多情况下可以直接通过bloom filter获得所查找键是否存在的正确结果，只有少数情况下，bloom filter给出键存在的结果，但是经过查询磁盘会发现该结论是错误的，这会导致少量不必要的磁盘访问。

drawing

假设hash函数选择任意位置的概率相同。如果数组的大小是m，那么某一位置在元素插入的时候没有被某一hash函数置1的概率为
$$
1 - \frac{1}{m}
$$
如果hash函数个数为k，hash函数之间没有关联，那么某一位置在元素插入的时候没有被任一hash函数置1的概率是
$$
\left ( 1 - \frac{1}{m} \right )^{k}
$$
如果我们插入了n个元素，那么在这n次插入中该位置始终保持0的概率是
$$
\left ( 1 - \frac{1}{m} \right )^{kn}
$$
那么该位置为1的概率为
$$
1 - \left ( 1 - \frac{1}{m} \right )^{kn}
$$
那么当查询一个元素时，返回该元素可能存在集合中的要求是所有hash函数都返回1，概率为
$$
\left ( 1 - \left ( 1 - \frac{1}{m} \right )^{kn} \right )^{k} \approx \left ( 1- e^{-kn/m}\right )^{k}
$$
当m增加时，false positive的概率减少；当n增加时，false positive的概率增加。

设$g = kln ( 1- e^{-kn/m})$, 求$g$的导数得
$$
\frac{\partial g}{\partial k} =ln(1- e^{-kn/m})+\frac{kn}{m}\frac{e^{-kn/m}}{1-e^{-kn/m}}
$$
因此$k$的最优值为$\frac{m}{n}ln2$.

8. 操作系统相关

8.1 进程死锁

当一组进程中的每个进程都在等待一个事件，而这一事件只能由这一组进程的另一进程引起，那么这组进程就处于死锁状态。

如果一个系统中下面4个条件同时满足，那么会引起死锁：

互斥：至少有一个资源必须处于非共享模式，即一次只有一个进程使用。如果另一进程申请该资源，那么申请进程必须等到该资源被释放为止。
占有并等待：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。
非抢占：资源不能被抢占，即资源只能在进程完成任务后自动释放。
循环等待：有一组等待进程{P0, P1, …, Pn}，P0等待的资源为P1所占有，P1等待的资源为P2所占有，…, Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。

三种类型的方法可以处理死锁问题

使用协议预防或避免死锁，确保系统不会进入死锁状态
允许系统进入死锁状态，然后检测并加以恢复
忽视该问题，认为死锁不可能在系统中发生

死锁预防

由于有些资源本来就是非共享的，因此从互斥角度预防死锁不可行。

从占有并等待角度预防死锁，可保证：当一个进程申请一个资源时，它不能占有其他资源。这有两种协议可以实现：

每个进程在执行前申请并获得所有资源
允许进程在没有资源时才可申请资源

从非抢占角度，我们可采用如下协议：

如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占

从循环等待角度，我们可采用如下方法：

对所有资源进行完全排序，且要求每个进程按递增顺序来申请资源，当一个进程要申请某个资源类型，它必须先释放所有资源值大于等于该类型的资源，这样可保证循环等待不成立

死锁避免

动态地检测资源分配状态以确保循环等待的条件不可能成立。

如果系统能按某个顺序为每个进程分配资源并能避免死锁，那么系统状态就是安全的，而安全的状态一定不发生死锁。因此，当一个进程申请一个可用的资源时，系统必须确定这一资源是可以立即分配还是要等待。只有分配后使系统仍处于安全状态，才允许申请。

资源分配图算法（适用于单个实例的资源分配系统）

构建资源分配图，引入需求边（表示进程可能在将来某个时候申请该资源）
只有在将申请边变成分配边而不会导致资源分配图形成环时，才允许申请
如果没有环存在，资源分配会使得系统处于安全状态；如果有环存在，分配会导致系统处于不安全状态

如下图所示，当P2申请R2资源时，尽管R2现在可用，但是不能将它分配给P2，因为这会创造一个环，如右图所示。环表示系统处于不安全状态。如果P1申请R2且P2申请R1，那么会发生死锁。

drawing

银行家算法（适用于多个实例的资源分配系统）

当新进程进入系统时，它必须说明其可能需要的每种类型资源实例的最大数量，这一数量不能超过系统资源的总和。当用户申请一组资源时，系统必须确定这些资源的分配是否仍会使系统处于安全状态。如果是，就可分配资源；否则，进程必须等待直到某个其他进程释放足够资源为止。

所需数据结构（n个进程，m种资源）：

Available：长度为m的向量，表示每种资源的现有实例数量。如果Available[j] = k，那么资源类型Rj现有k个实例
Max：n * m矩阵，定义每个进程的最大需求。如果Max[i][j]=k，那么进程Pi最多可申请k个资源类型Rj的实例
Allocation：n * m矩阵，定义每个进程现在所分配的各种资源类型的实例数量。如果Allocation[i][j]=k，那么进程Pi现在已分配了k个资源类型Rj的实例
Need：n * m矩阵，表示每个进程还需要的剩余的资源。如果Need[i][j]=k，那么进程Pi还可能申请k个资源类型Rj的实例。Need[i][j] = Max[i][j] - Allocation[i][j]。

所需函数：

安全性算法

对于进程顺序<P1,P2,…,Pn>，如果对于每个Pi，Pi仍然可以申请的资源数小于当前可用资源加上所有进程Pj（其中j < i）所占有的资源，那么这一顺序称为安全序列。
资源请求算法

设Requesti为进程Pi的请求向量。如果Requesti[j] == k，那么进程Pi需要资源类型Rj的实例数量为k。当进程Pi作出资源请求时，采取如下动作。
1. 如果Requesti <= Needi，那么转到第2步。否则出错，这是因为进程Pi已超过其最大请求。
2. 如果Requesti <= Availablei，那么转到第3步。否则等待，这是因为没有可用资源。
3. 假定系统可以分配给进程Pi所请求的资源，并按如下方式修改状态：
  1
  2
  3
  Available = Available - Reuqesti
  Allocationi = Allocationi + Requesti
  Needi = Needi - Requesti
调用安全性算法检测，如果所产生的资源分配状态是安全的，那么交易完成且进程Pi可分配到其所需要资源。然而，如果新状态不安全，那么进程Pi必须等待Requesti并恢复到原来的分配状态。

死锁检测

等待图法（每种资源类型只有单个实例）

将资源分配图中的资源节点都删除，合并适当边，构成等待图，如下图所示。
利用图搜索算法检测图中是否有环出现，时间复杂度为O(N^2)，其中N为图中节点数。

drawing

类银行家算法

只是把判断Needi <= Work（Pi仍然可以申请的资源数小于当前可用资源加上所有进程Pj（其中j < i）所占有的资源）改成Requesti <= Work（Pi当前需要申请的资源数小于当前可用资源加上所有进程Pj（其中j < i）所占有的资源）。这里作了一个假设，已知Pi现在不参与死锁，因此可以乐观地认为Pi不再需要更多资源以完成其任务，它会返回现已分配的所有资源。如果假定的不正确，那么稍后会发生死锁。在下次调用死锁算法时，就会检测到死锁状态。

死锁恢复

进程终止
- 终止所有死锁进程。
- 一次只终止一个进程直到取消死锁循环位置
资源抢占：逐步从进程中抢占资源给其他进程使用，知道死锁环被打破为止
- 选择一个牺牲品
- 回滚被抢占进程
- 保证资源不会总是从同一个进程中被抢占。（比如可在代价因素中加上回滚次数）

9. MVC框架相关

9.1 Spring

Spring的IOC和AOP
AOP的实现方式有哪几种？如何选择？
Spring MVC的核心控制器是什么？消息处理流程有哪些？
重定向和转发的区别
动态代理和静态代理的区别

10. 大数据相关

10.1 KafKa基本特性

10.2 核心概念

11. Linux命令相关

11.1 grep, sed, awk

11.2 文件和目录

11.3 处理文件方面的命令：touch, cp, ln, mv, rm

11.4 处理目录方面的命令：mkdir

11.5 查看文件内容：file, cat, more, less, tail, head

11.6 监测程序命令：ps, top

两者的区别

11.7 压缩数据

11.8 结束进程

12. 线性代数相关

Orthogonal matrix

An orthogonal matrix is a square matrix whose transpose is equal to its inverse. $Q^{T}Q=QQ^{T}=I$

Unitary matrix

Matrices with orthogonality over the complex number field.

covariance matrix

Eigen-decompositions/PCA

12.3 SVD

Any matrix $R^{m*n}$ (w.l.o.g. $m \leq n$) can be written as:
$$
A =\sum_{i=1}^{m}\sigma_{i}u_{i}v_{i}^{T}
$$
where $\sigma_{i} \geq 0$, ${u_{i}}$, ${v_{i}}$ are orthonormal basis of $\mathbb{R}^{m}$, $\mathbb{R}^{n}$, respectively.

According to eigen decompositions, for matrix $AA^{T}$, we have
$$
u_{j}^{T}AA^{T}u_{i}=\lambda_{i}u_{j}^{T}u_{i},\ \left ( u_{j}^{T}AA^{T}u_{i}=\lambda_{i}u_{j}^{T}u_{i} \right )^{T} = u_{i}^{T}AA^{T}u_{j}=\lambda_{j}u_{i}^{T}u_{j}
$$
Assume $\delta_{ij}=u_{i}^{T}u_{j}$, $\sigma_{i} = \sqrt{\lambda_{i}}$, $v_{i} = \frac{1}{\sigma_{i}}A^{T}u_{i}$, we have
$$
v_{i}^{T}v_{j}=\frac{1}{\sigma_{i}\sigma_{j}}u_{i}^{T}AA^{T}u_{j}=\frac{\lambda_{j}}{\sigma_{i}\sigma_{j}}u_{i}^{T}u_{j}=\delta_{ij}
$$
Then, we prove $A =\sum_{i=1}^{m}\sigma_{i}u_{i}v_{i}^{T}$:
$$
\left | w^{T}\left ( A-\sum_{i=1}^{m}\sigma_{i}u_{i}v_{i}^{T} \right ) \right |=\left | \left ( \sum_{i=1}^{m}\alpha_{i}u_{i}^{T} \right )\left ( A-\sum_{i=1}^{m}\sigma_{i}u_{i}v_{i}^{T} \right ) \right |\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad= \left |\sum_{i=1}^{m}\alpha_{i}u_{i}^{T}A - \sum_{i=1}^{m}\sum_{j=1}^{m}\delta_{ij}\alpha_{i}\sigma_{j}v_{j}^{T}\right | \\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\ =\left | \sum_{i=1}^{m}\alpha_{i}\sigma_{i}v_{i}^{T}-\sum_{i=1}^{m}\sum_{j=1}^{m} \frac{\sigma_{i}}{\sigma_{j}}v_{i}^{T}v_{j} \alpha_{i}\sigma_{j}v_{j}^{T} \right |\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\ =\left | \sum_{i=1}^{m}\alpha_{i}\sigma_{i}v_{i}^{T}-\sum_{i=1}^{m}\alpha_{i}\sigma_{i}v_{i}^{T} \right | = 0
$$
In this case, the singular value decomposition (SVD) of an arbitrary matrix $A \in \mathbb{R}^{m\times n}$ is denoted as:
$$
A = U\varepsilon V_{T}
$$
Note: the singular values of a real symmetric matrix are known as absolute value of its eigenvalues.

13. 机器学习相关

13.1 拉格朗日乘子法

拉格朗日乘子法是一种在等式约束下（要求所求得变量的值满足一个或多个等式）求解函数局部最大或最小值的最优化求解方法。对于以下优化问题（见下图）

drawing
$$
minimize\ f(x, y) \
subject\ to\ g(x, y) = 0
$$
我们可以引入拉格朗日乘子$\lambda$, 定义拉格朗日函数，
$$
L(x,y,\lambda) = f(x,y) - \lambda \cdot g(x, y)
$$
其中$\lambda$可以是增或减。如果$f(x_{0}, y_{0})$是原始优化问题的最小值，那么一定存在一个$\lambda_{0}$使得$(x_{0}, y_{0}, \lambda_{0})$是该拉格朗日函数的一个驻点（驻点即使拉格朗日函数L偏导数为0的点）。这是因为当函数$f(x_{0},y_{0})$与约束$g(x,y)=0$相交时，两函数对应的偏导数一定相同，否则$f(x,y)$一定还可以沿着$g(x,y)$导数方向移动，使结果更小。换句话说，如果拉格朗日函数存在最优解，以下任一情况发生（必要条件）

$f$和$g$在该点处导数相同
$f$函数往任何方向均不改变大小

因此我们可以有等式
$$
\bigtriangledown _{x,y}f = \lambda\bigtriangledown _{x,y}g
$$
也就是$\bigtriangledown _{x_{1},…,x_{n}}L(x_{1},…,x_{n},\lambda)=0$. 求解方程得到$x_{1},…,x_{n}$代入原方程可求得最优解。

13.2 Quasi Monte Carlo(QMC) Sampling

假设我们想要在一个d维空间采样点，并使间隔不要过大，常用的方法包括最Naive的常规隔间采样，更好的方法有Chain Monte Carlo(MCMC)或者是Quasi Monte Carlo(QMC)方法。

Halton sequence

在进入正题之前，首先要介绍一下Halton sequence。它是用来产生一系列随机点所使用的算法，尽管这种计算点的方法是确定的，但是它能产生比伪随机序列更“随机”的序列。

生成序列的步骤主要有两步

确定基底
对不同基底分别计算不同的序列

确定基底的步骤要保证所选基底互质。比如我们可以生成基底为2和3的序列。

计算基底的方法又分以下三步

确定对应位置下标（从1开始）的二进制表示
将二进制表示倒过来，置于小数点后生成新的二进制
计算新的二进制所对应值即为当前点的值

如我们以2为基底举例，要生成第6个位置的值，6的二进制表示为$110_{2}$, 倒转并置于小数点后为$0.011_{2}$, 对应的十进制数为$0.011_{2} = 0 2^{-1}+12^{-2}+1*2^{-3}=\frac{3}{8}$. 所以对应位置的值为$\frac{3}{8}$。

以此我们可以得到2对应的序列为

3对应的序列为

将两个序列合起来就是二维空间上的一个随机序列。

Quasi Monte Carlo Method

QMC旨在解决什么问题呢？

数学一点说，即解决以下问题
$$
\int_{\left [ 0,1 \right ]^{s}}^{}f(u)du\approx \frac{1}{N}\sum_{i=1}^{N}f(x_{i})
$$
Approximation error bounds of quasi-Monte Carlo

估计误差可以表示为如下
$$
\varepsilon =\left | \int_{\left [ 0,1 \right ]^{s}}^{}f(u)du- \frac{1}{N}\sum_{i=1}^{N}f(x_{i}) \right |
$$
这个误差有上限，$\varepsilon \leq V(f)D_{N}$,

其中$V(f)$是函数的Hardy–Krause variation（有空写），$D_{N}$可以表示为如下形式
$$
D_{N} = sup_{Q \subseteq [0,1]^s}\left | \frac{number\ of\ points\ in\ Q}{N} - volume(Q) \right |
$$
其中$Q$是边和坐标轴平行的矩阵，$N$就是我们用随机序列生成算法产生的$N$个$d$维点。

13.3 Laplacian of Gaussian（高斯拉普拉斯算子）

拉普拉斯是对于一张图片的二阶空间导数上各向同性的测量。它可以着重显示图像亮度的变化，可以用来做边缘检测。拉普拉斯接受一张灰度图作为输入，并给出一张灰度图作为输出。

拉普拉斯算子

高斯平滑

对偶问题

熵