1. 互斥条件：线程对资源的占有是排他性的，一个资源只能被一个线程占有，直到资源被释放。

2. 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。

3. 不可剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

4. 环路等待条件：指在发生死锁时，存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

所有四个条件必须同时成立才会出现死锁。循环等待条件意味着占有并等待条件，这样四个条件并不完全独立。

1. 破坏“请求和保持”条件

　　当某个线程申请两个及以上的资源时，让它要么能一次性申请成功所有资源，要么就不申请任何资源(释放申请的部分资源)。

2. 破坏“不可抢占”条件

　　允许进程进行资源抢占。如果线程在持有部分资源的时候这部分资源发生了抢占，则允许这部分资源被抢占。更好的方法是允许操作系统抢占资源，让优先级大的线程可以抢占其他线程占有但未使用的资源。

3. 破坏“循环等待”条件

　　a. 将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序提出。

当多个线程需要相同的一些锁，但是按照不同的顺序加锁，死锁就很容易发生。

如果能确保所有的线程都是按照相同的顺序获得锁，那么死锁就不会发生。

如果一个线程（比如线程3）需要一些锁，那么它必须按照确定的顺序获取锁。它只有获得了从顺序上排在前面的锁之后，才能获取后面的锁。

例如，线程2和线程3只有在获取了锁A之后才能尝试获取锁C (获取锁A是获取锁C的必要条件)。因为线程1已经拥有了锁A，所以线程2和3需要一直等到锁A被释放。然后在它们尝试对B或C加锁之前，必须成功地对A加了锁。

b. 为线程设置加锁时限

　　在尝试获取锁的时候加一个超时时间，在尝试获取锁的过程中若超过了这个时限该线程则放弃对该锁请求。若一个线程没有在给定的时限内成功获得所有需要的锁，则会进行回退并释放所有已经获得的锁，然后等待一段随机的时间再重试。这段随机的等待时间让其它线程有机会尝试获取相同的这些锁。

4. 死锁检测及处理

　　死锁检测是一个更好的死锁预防机制，它主要是针对那些不可能实现按序加锁、不可设置锁超时、资源不可抢占、破坏请求保持条件的时间效率不高(如果一次性申请到所有的资源的可能性不大，则会出现频繁的资源申请、资源释放操作)。

死锁检测的方法

主要需要为所有的线程及资源建立一个资源分配图，根据资源分配图，如过资源分配图没有环，则系统没有发生死锁。(判断图是否成环使用拓扑排序算法)

检测到死锁了怎么办:

1. 一个可行的做法是释放所有锁，回退，并且等待一段随机的时间后重试虽然有回退和等待，但是如果有大量的线程竞争同一批锁，它们还是会重复地死锁（原因同超时类似，不能从根本上减轻竞争）。

2. 一个更好的方案是随机选取若干个线程而不是全部线程，让这些线程回退，剩下的线程就像没发生死锁一样继续保持着它们需要的锁。

ThreadPoolExecutor.AbortPolicy:丢弃任务并抛出RejectedExecutionException异常。

ThreadPoolExecutor.DiscardPolicy：也是丢弃任务，但是不抛出异常。

ThreadPoolExecutor.DiscardOldestPolicy：丢弃队列最前面的任务，然后重新尝试执行任务（重复此过程）

ThreadPoolExecutor.CallerRunsPolicy：由调用线程处理该任务 

public interface Runnable {

    public abstract void run();

}

public interface Callable<V> {

    V call() throws Exception;

}

<T> Future<T> submit(Callable<T> task);

<T> Future<T> submit(Runnable task, T result);

Future<?> submit(Runnable task);

Java1.6 中为了减少获得锁和释放锁带来的性能消耗而引入的偏向锁和轻量级锁。锁是按顺序膨胀的，且锁的膨胀是不可逆的。

偏向锁：大多数情况下，锁不仅不存在多线程竞争，而且总是由同一线程多次获得，为了让线程获得锁的代价更低而引入了偏向锁。当一个线程A访问加了同步锁的代码块时，会在对象头中存储当前线程的id，后续这个线程进入和退出这段加了同步锁的代码块时，不需要再次加锁和释放锁。

轻量级锁：在偏向锁情况下，如果线程B也访问了同步代码块，比较对象头的线程id不一样，会升级为轻量级锁，并且通过自旋的方式来获取轻量级锁。

重量级锁：如果线程A和线程B同时访问同步代码块，则轻量级锁会升级为重量级锁，线程A获取到重量级锁的情况下，线程B只能入队等待，进入BLOCK状态。

多线程并发问题的技术选择

基于TCP的应用层协议有：HTTP、FTP、SMTP、TELNET、

基于UDP的应用层协议：DNS、RIP（路由选择协议）、DHCP、BOOTP（是DHCP的前身）、IGMP（Internet组管理协议）、TFTP（简单文件传输协议）

根据HTTP标准，HTTP请求可以使用多种请求方法。

HTTP1.0定义了三种请求方法： GET, POST 和 HEAD方法。

HTTP1.1新增了五种请求方法：OPTIONS, PUT, DELETE, TRACE 和 CONNECT 方法。

HTTPS的优点（确保数据发送到正确的客户机和服务器，确保数据的完整性，增加了中间人攻击的成本）

　　尽管HTTPS并非绝对安全，掌握根证书的机构、掌握加密算法的组织同样可以进行中间人形式的攻击，但HTTPS仍是现行架构下最安全的解决方案，主要有以下几个好处：

　　（1）使用HTTPS协议可认证用户和服务器，确保数据发送到正确的客户机和服务器；

　　（2）HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，要比http协议安全，可防止数据在传输过程中不被窃取、改变，确保数据的完整性。

　　（3）HTTPS是现行架构下最安全的解决方案，虽然不是绝对安全，但它大幅增加了中间人攻击的成本。

HTTPS的缺点(效率低)

　　虽然说HTTPS有很大的优势，但其相对来说，还是存在不足之处的：

　　（1）HTTPS协议握手阶段比较费时，会使页面的加载时间延长近50%，增加10%到20%的耗电；

　　（2）HTTPS连接缓存不如HTTP高效，会增加数据开销和功耗，甚至已有的安全措施也会因此而受到影响；

Cookies和Session的区别

cookie和session的区别：

①存在的位置：

cookie 存在于客户端，临时文件夹中；  session存在于服务器的内存中，一个session域对象为一个用户浏览器服务

②安全性
cookie是以明文的方式存放在客户端的，安全性低，可以通过一个加密算法进行加密后存放；  session存放于服务器的内存中，所以安全性好

③网络传输量
cookie会传递消息给服务器；  session本身存放于服务器，不会有传送流量

④生命周期(以20分钟为例)
cookie的生命周期是累计的，从创建时，就开始计时，20分钟后，cookie生命周期结束；
session的生命周期是间隔的，从创建时，开始计时如在20分钟，没有访问session，那么session生命周期被销毁。但是，如果在20分钟内（如在第19分钟时）访问过session，那么，将重新计算session的生命周期。关机会造成session生命周期的结束，但是对cookie没有影响

⑤访问范围
cookie为多个用户浏览器共享；  session为一个用户浏览器独享
可以看自己的笔记: https://www.cnblogs.com/greatLong/articles/11146045.html

Session：

服务器为每个会话创建一个session对象，所以session中的数据可供当前会话中所有servlet共享。作用域：会话从用户打开浏览器开始，直到关闭浏览器才结束，一次会话期间只会创建一个session对象。session是服务器端对象，保存在服务器端，并且服务器可以将创建session后产生的 sessionid 通过一个 cookie 返回给客户端，以便下次验证。（session底层的一种实现依赖于cookie，session一般配合cookie来保存会话信息，但在不允许使用cookie的情况下，也可以使用url重写的形式传递信息）

Cookie

cookie是http协议提供的，不是java独有的；

cookie保存在客户端；

可以设置生命时长；

cookie有个属性是路径，但该路径指的是服务端路径；

cookie的形式是一个键值对，如uid:lxj；

http约定，单条cookie不超过4KB，单个会话最多保存20条cookie; 浏览器最多储存300条cookie;但一般浏览器对这个规定会有超出，如允许单个会话超过20个cookie;

与之对应的，session是Java独有的，全称是httpsession, 每个session 都有JSEESIONID;

session一般配合cookie来保存会话信息，但在不允许cookie的情况下，也可以使用url重写的形式传递信息

此部分知识不完全，需要进一步理解

中间人攻击和重放攻击

• 重放攻击是攻击者获取客户端发送给服务器端的包，不做修改，原封不动的发送给服务器用来实现某些功能。比如说客户端发送给服务器端一个包的功能是查询某个信息，攻击者拦截到这个包，然后想要查询这个信息的时候，把这个包发送给服务器，服务器就会做相应的操作，返回查询的信息。

防御方案: 加时间戳(需要时钟同步)，使用与当前事件有关的一次性随机数N

• 中间人攻击就不一样了，中间人攻击是攻击者把自己当作客户端与服务器端的中间人，客户端发送的信息会被攻击者截取然后做一些操作再发送给服务器端，服务器端响应返回的包也会被攻击者截取然后再发送给客户端。你可以看作是相对于客户端来说攻击者是服务器端，(攻击者假冒客户端需要证书，但是攻击者自己制作的证书不是信任的证书，会弹警告，但往往人们对于这些警告大意或不懂就忽略了);相对于服务器段来说攻击者是客户端，两边都欺骗，从而获取所有的信息。常见的有DNS劫持。

防御方案: 采用认证方式连接

转发与重定向的区别

forward(转发):是服务器内部重定向，程序收到请求后重新定向到另一个程序，客户机并不知道。服务器直接访问目标地址的URL，并把那个URL的相应内容读取过来，然后把这些内容再发给浏览器，浏览器根本不知道服务器发送的内容是从哪里来的，所以它的地址栏中还是原来的地址，转发时并不通知客户机，对象可以存储在请求中，并发给下一个资源使用，并且完全在服务器上面进行；

 

redirect(重定向):是服务器收到请求后发送一个状态头给客户，客户将再请求一次新的网址，这里多了两次网络通信的来往一般来说，浏览器会用刚才请求的所有参数重新请求，所以session，request参数都可以获取。重定向导致浏览器发出了新的请求，在重定向之前存储为请求属性的任何对象都会消失，这也是两者最大的区别。

HTTP状态码

• 1**：请求收到，继续处理

100——客户必须继续发出请求

101——客户要求服务器根据请求转换HTTP协议版本

• 2**：操作成功收到，分析、接受

200("OK") 一般来说，这是客户端希望看到的响应代码。它表示服务器成功执行了客户端所请求的动作

• 3XX 重定向

3XX系列响应代码表明：客户端需要做些额外工作才能得到所需要的资源

301 redirect: 301 代表永久性转移(Permanently Moved)

302 redirect: 302 代表暂时性转移(Temporarily Moved )

• 4**：客户端错误, 请求包含一个错误语法或不能完成

404——没有发现文件、查询或URl

401——未授权

• 5XX 服务端错误

这些响应代码表明服务器端出现错误。一般来说，这些代码意味着服务器处于不能执行客户端请求的状态，此时客户端应稍后重试。

500("Internal Server Error")

1. 这是一个通用的服务器错误响应。对于大多数web框架，如果在执行请求处理代码时遇到了异常，它们就发送此响应代码。

说一说HTTP请求头的内容

HTTP请求报文由3部分组成（请求行+请求头+请求体）：

①是请求方法，GET和POST是最常见的HTTP方法，除此以外还包括DELETE、HEAD、OPTIONS、PUT、TRACE。

②为请求对应的URL地址，它和报文头的Host属性组成完整的请求URL，③是协议名称及版本号。

④是HTTP的报文头，报文头包含若干个属性，格式为“属性名:属性值”，服务端据此获取客户端的信息。 

⑤是报文体，它将一个页面表单中的组件值通过param1=value1&param2=value2的键值对形式编码成一个格式化串，它承载多个请求参数的数据。不但报文体可以传递请求参数，请求URL也可以通过类似于“/chapter15/user.html? param1=value1&param2=value2”的方式传递请求参数。

常见的HTTP请求报文头属性

Accept：客户端接受什么类型的响应，常见的如Accept:text/plain，Accept属性的值可以为一个或多个MIME类型的值。

Cookie: 客户端的Cookie就是通过这个报文头属性传给服务端

Referer 表示这个请求是从哪个URL过来的

Cache-Control 对缓存进行控制，控制是否缓存及缓存时间为多久。

Accept-Language：接受的语言类型

User-Agent: 通过何种代理(浏览器)访问

Content-type, Content-Length等

Connection ：

Connection: keep-alive   当一个网页打开完成后，客户端和服务器之间用于传输HTTP数据的TCP连接不会关闭，如果客户端再次访问这个服务器上的网页，会继续使用这一条已经建立的连接

Connection: close  代表一个Request完成后，客户端和服务器之间用于传输HTTP数据的TCP连接会关闭， 当客户端再次发送Request，需要重新建立TCP连接。

谈谈HTTP响应报文

HTTP的响应报文也由三部分组成（响应行+响应头+响应体）： 

以下是一个实际的HTTP响应报文：

①报文协议及版本； 
②状态码及状态描述； 
③响应报文头，也是由多个属性组成； 
④响应报文体，即我们真正要的“干货”。

 响应状态码 
和请求报文相比，响应报文多了一个“响应状态码”，它以“清晰明确”的语言告诉客户端本次请求的处理结果。 
HTTP的响应状态码由5段组成： 

• 1xx 消息，一般是告诉客户端，请求已经收到了，正在处理，别急...
• 2xx 处理成功，一般表示：请求收悉、我明白你要的、请求已受理、已经处理完成等信息.
• 3xx 重定向到其它地方。它让客户端再发起一个请求以完成整个处理。
• 4xx 处理发生错误，责任在客户端，如客户端的请求一个不存在的资源，客户端未被授权，禁止访问等。
• 5xx 处理发生错误，责任在服务端，如服务端抛出异常，路由出错，HTTP版本不支持等。

从浏览器发出请求开始，到服务端应用接受到请求返回结果显示的过程

第一步，解析域名，找到ip

查本地缓存--查hosts文件--查ISP服务商的DNS缓存--从根域名开始递归搜索返回

浏览器会缓存DNS一段时间，一般2-30分钟不等，如果有缓存，直接返回ip，否则下一步。
缓存中无法找到ip，浏览器会进行一个系统调用，查询hosts文件。如果找到，直接返回ip，否则下一步。
进行1 和2 本地查询无果，只能借助于网络，路由器一般都会有自己的DNS缓存，ISP服务商DNS缓存，这时一般都能够得到相应的ip，如果还是无果，只能借助于DNS递归解析了。
这时ISP的DNS服务器就会开始从根域名服务器开始递归搜索，从.com *域名服务器，到baidu的域名服务器。 
到这里，浏览器就获得网络ip，在DNS解析过程中，常常解析出不同的IP。

第二步，浏览器于网站建立TCP连接

浏览器利用ip直接网站主机通信，浏览器发出TCP连接请求，主机返回TCP应答报文，浏览器收到应答报文发现ACK标志位为1，表示连接请求确认，浏览器返回TCP（）确认报文，主机收到确认报文，三次握手，TCP连接建立完成。

第三步， 浏览器发起默认的GET请求

浏览器向主机发起一个HTTP-GET方法报文请求，请求中包含访问的URL，也就是http://www.baidu.com/还有User-Agent用户浏览器操作系统信息，编码等，值得一提的是Accep-Encoding和Cookies项。Accept-Encoding一般采用gzip，压缩之后传输html文件，Cookies如果是首次访问，会提示服务器简历用户缓存信息，如果不是，可以利用Cookies对应键值，找到相应缓存，缓存里面存放着用户名，密码和一些用户设置项

第四步，显示页面或返回其他

返回状态码200 OK，表示服务器可以响应请求，返回报文，由于在报头中Content-type为“text/html”,浏览器以HTML形式呈现，而不是下载文件。 
但是对于大型网站存在多个主机站点，往往不会直接返回请求页面，而是重定向。返回的状态码就不是 200 OK， 而是301,302以3开头的重定向吗。浏览器在获取了重定向响应后，在响应报文中Location项找到重定向地址，浏览器重新第一步访问即可。

第三模块--操作系统、Git

Linux常用指令 (查看内存、进程之类的）

文件处理

• 文件查找：find

• 文本搜索：grep

• 排序：sort

• 按列切分文本：cut

• 统计行和字符：wc

• 文本替换：sed

• 数据流处理：awk

• 性能分析

• 进程查询：ps

• 进程监控：top

• 打开文件查询：lsof

• 内存使用量：free

• 监控性能指标：sar

监控CPU -u

监控内存 -r

网络工具

• 网卡配置：ifconfig

• 查看当前网络连接：netstat

• 查看路由表：route

• 检查网络连通性：ping

• 转发路径：traceroute

• 命令行抓包：tcpdump

• 域名解析工具：dig

• 网络请求：curl

其他

• 终止进程：kill
• 修改文件权限：chmod
• 创建链接：ln
• 显示文件尾：tail
• 版本控制：git
• 设置别名：alias

根据程序名称结束该程序

以杀掉tomcat为例子

ps -ef|grep tomcat|grep -v|awk -F '{print $2}'|xargs kill -9

等同于

kill -9 `ps -ef | grep 'tomcat' | awk '{print $2}'`

xargs接收管道前面传过来的字符;

awk '{print $2}'的意思是选取并输出第二列的数据

kill 与kill -9的区别

1. kill 的默认参数是 -15, kill pid的效果等同于kill -15 pid。  执行kill命令，系统会发送一个关闭信号给对应的程序。当程序接收到该信号后，将有机会释放资源、处理善后工作后再停止；
2. kill -9命令，系统给对应程序发送的信号是SIGKILL，即exit。exit信号不会被系统阻塞，所以kill -9能顺利杀掉进程。相当于强制关闭程序。

在使用 kill -9 前，应该先使用 kill -15，给目标进程一个清理善后工作的机会。如果没有，可能会留下一些不完整的文件或状态，从而影响服务的再次启动。

查询日志

1. 按行号查看---过滤出关键字附近的日志

首先: cat -n test.log |grep "keyword"  得到关键日志的行号

然后，得到"keyword"关键字所在的行号是102行. 此时如果想查看这个关键字前10行和后10行的日志:

cat -n test.log |tail -n +92|head -n 20

2. 刷新显示日志变动

tail -f test.log 查看日志的尾部，并刷新显示日志变动。此方法适合在调试程序的时候查看日志，日志变动会实时刷新显示到终端。

top指令能查看进程的哪些信息

包括进程的相关信息,包括进程ID,内存占用率,CPU占用率

待补充

守护进程了解吗

线程是调度的基本单位，进程是资源分配的基本单位。。

守护进程是生存期长的一种进程。它们独立于控制终端并且周期性的执行某种任务或等待处理某些发生的事件。他们常常在系统引导装入时启动，在系统关闭时终止。linux系统有很多守护进程，大多数服务器都是用守护进程实现的。linux上的守护进程类似于windows上的服务。

僵尸进程、孤儿进程

父进程在调用fork接口之后和子进程已经可以独立开，之后父进程和子进程就以未知的顺序向下执行（异步过程）。所以父进程和子进程都有可能先执行完。当父进程先结束，子进程此时就会变成孤儿进程，不过这种情况问题不大，孤儿进程会自动向上被init进程收养，init进程完成对状态收集工作。而且这种过继的方式也是守护进程能够实现的因素。如果子进程先结束，父进程并未调用wait或者waitpid获取进程状态信息，那么子进程描述符就会一直保存在系统中，这种进程称为僵尸进程。

Git常见指令

fetch和merge和pull的区别
 pull相当于git fetch 和 git merge，即更新远程仓库的代码到本地仓库，然后将内容合并到当前分支。
 git fetch：相当于是从远程获取最新版本到本地，不会自动merge
 git merge :  将内容合并到当前分支
 git pull：相当于是从远程获取最新版本并merge到本地

常用命令
git show # 显示某次提交的内容 git show $id
git add <file> # 将工作文件修改提交到本地暂存区
git rm <file> # 从版本库中删除文件
git reset <file> # 从暂存区恢复到工作文件
git reset HEAD^ # 恢复最近一次提交过的状态，即放弃上次提交后的所有本次修改
git diff <file> # 比较当前文件和暂存区文件差异 git diff
git log -p <file> # 查看每次详细修改内容的diff
git branch -r # 查看远程分支
git merge <branch> # 将branch分支合并到当前分支
git stash # 暂存
git stash pop #恢复最近一次的暂存
git pull # 抓取远程仓库所有分支更新并合并到本地
git push origin master # 将本地主分支推到远程主分支

第四模块--JAVA语言特性

Integer缓存数据的范围

java定义：在自动装箱时对于值从–128到127之间的值，它们被装箱为Integer对象后，会存在内存中被重用，始终只存在一个对象。这归结于java对于Integer与int的自动装箱与拆箱的设计，是一种模式：享元模式（flyweight）

而如果超过了从–128到127之间的值，被装箱后的Integer对象并不会被重用，即相当于每次装箱时都新建一个 Integer对象；以上的现象是由于使用了自动装箱所引起的，如果你没有使用自动装箱，而是跟一般类一样，用new来进行实例化，就会每次new就都一个新的对象。

https://www.cnblogs.com/greatLong/p/10776561.html

面向对象编程和面向过程编程的优缺点

面向过程

优点：性能比面向对象高，因为类调用时需要实例化，开销比较大，比较消耗资源;比如单片机、嵌入式开发、 Linux/Unix等一般采用面向过程开发，性能是最重要的因素。 
缺点：没有面向对象易维护、易复用、易扩展

面向对象

优点：易维护、易复用、易扩展，由于面向对象有封装、继承、多态性的特性，可以设计出低耦合的系统，使系统更加灵活、更加易于维护 
缺点：性能比面向过程低

JAVA提供了几个类加载器？分别是？怎么对类进行加载的？

根加载器、扩展类加载器、系统类加载器

Bootstrap 是JVM在启动时创建的，通常由与操作系统相关的本地代码实现，是最根基的类加载器，负责装载最核心的JAVA类，如Object, System, String；

然后第二层在JDK9中称为Platform 加载器， JDK9之前叫Extension加载器，加载一些扩展的系统类，如XML, 加密， 压缩相关的功能类；

第三层是Application 加载器， 主要加载用户定义的CLASSPATH路径下的类。

类加载的双亲委任模型

低层次的当前类加载器，不能覆盖更高层次类加载器已经加载的类。如果低层次的类加载器想加载一个未知类，要非常礼貌地向上逐级询问：“请问，这个类已经加载了吗？”被询问的高层次类加载器会自问两个问题：第一，我是否已加载过此类？第二，如果没有，是否可以加载此类？只有当所有高层次类加载器在两个问题上的答案均为“否”时，才可以让当前类加载器加载这个未知类。如图4-6所示，左侧绿色箭头向上逐级询问是否已加载此类，直至Bootstrap ClassLoader，然后向下逐级尝试是否能够加载此类，如果都加载不了，则通知发起加载请求的当前类加载器，准予加载。

JAVA类的加载过程

在JVM中，类从被加载到虚拟机内存中开始，到卸载出内存为止，它的整个生命周期包括：加载、验证、准备、解析、初始化5个阶段。而解析阶段即是虚拟机将常量池内的符号引用替换为直接引用的过程。

1. 加载：程序运行之前jvm会把编译完成的.class二进制文件加载到内存，供程序使用，用到的就是类加载器classLoader 2、
2. 连接：分为三步  验证  》准备  》解析

验证：确保类加载的正确性。

准备：为类的静态变量分配内存，将其初始化为默认值 。

解析：把类中的符号引用转化为直接引用。

3. 初始化：为类的静态变量赋予正确的初始值，上述的准备阶段为静态变量赋予的是虚拟机默认的初始值，此处赋予的才是程序编写者为变量分配的真正的初始值

现在java程序的执行就可以分为

类成员初始化顺序总结：先静态，后父类普通构造，再子类普通构造，同级看书写顺序

1.先执行父类静态变量和静态代码块，再执行子类静态变量和静态代码块

2.先执行父类普通变量和代码块，再执行父类构造器(static方法)

3.先执行子类普通变量和代码块，再执行子类构造器(static方法)

4.static方法初始化先于普通方法，静态初始化只有在必要时刻才进行且只初始化一次。

反射机制

• 定义: 在运行状态中，对于任意一个类，都能够获取到这个类的所有属性和方法，对于任意一个对象，都能够调用它的任意一个方法和属性(包括私有的方法和属性)，这种动态获取的信息以及动态调用对象的方法的功能就称为java语言的反射机制。

• 使用: 想要使用反射机制，就必须要先获取到该类的字节码文件对象(.class)，通过字节码文件对象，就能够通过该类中的方法获取到我们想要的所有信息(方法，属性，类名，父类名，实现的所有接口等等)，每一个类对应着一个字节码文件也就对应着一个Class类型的对象，也就是字节码文件对象。
• Java反射的三种实现方式

Foo foo = new Foo();

第一种：通过Object类的getClass方法

Class cla = foo.getClass();

第二种：通过对象实例方法获取对象

Class cla = foo.class;

第三种：通过Class.forName方式

Class cla = Class.forName("xx.xx.Foo");

HashCode 是干什么用的？如果重写HashCode 有哪些注意点？

hashCode方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：集合中不允许重复的元素存在）也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值， 就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了。

在每个类中，在重写 equals 方法的时侯，一定要重写 hashcode 方法。如果不这样做，就违反了hashCode的通用约定，这会阻止它在HashMap和HashSet这样的集合中正常工作。

1. 如果两个对象根据equals(Object)方法比较是相等的，那么在两个对象上调用hashCode就必须产生的结果是相同的整数。
2. 如果两个对象根据equals(Object)方法比较并不相等，则不要求在每个对象上调用hashCode都必须产生不同的结果。 但是，程序员应该意识到，为不相等的对象生成不同的结果可能会提高散列表（hash tables）的性能。

JAVA集合类的常见问题

HashMap底层是怎么实现的

数组加链表的形式

在JAVA 8 中，改进为，当链表长度达到8及以上，转为红黑树来实现; 红黑树的数据数量将为6的时候又会自动转为链表。

（因为长度为6的链表平均查询次数是3， 查找树的话，3次查询能查到8个数据）

HashMap 是一个用于存储Key-Value 键值对的集合，每一个键值对也叫做Entry。这些个Entry 分散存储在一个数组当中，这个数组就是HashMap 的主干。 每个Entry都是链表的结构，含有可以指向一个Entry的next指针；
HashMap 数组每一个元素的初始值都是Null。 

1. Put 方法的原理

调用Put方法的时候发生了什么呢？ 根据键计算哈希值，确定放在哪个Entry里，如果计算出index位置的entry已经有值，就将新加入的键值对挂在这个entry的链表尾部。
比如调用 hashMap.put(“apple”, 0) ，插入一个Key为“apple”的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）： 
index = Hash（"apple"） 
假定最后计算出的index是2，那么结果如下： 
 
但是，因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。比如下面这样： 
 
这时候该怎么办呢？我们可以利用链表来解决。 
HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可： 
 
新来的Entry节点插入链表时，使用的是头插法。

2. Get方法的原理

使用Get方法根据Key来查找Value的时候，发生了什么呢？ 
首先会把输入的Key做一次Hash映射，得到对应的index： 
index = Hash（“apple”） 
由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。假设我们要查找的Key是“apple”： 

第一步，我们查看的是头节点Entry6，Entry6的Key是banana，显然不是我们要找的结果。 
第二步，我们查看的是Next节点Entry1，Entry1的Key是apple，正是我们要找的结果。 
之所以把Entry放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。

3. HashMap的初始长度

初始长度为16，且每次自动扩容或者手动初始化的时候必须是2的幂。

对于新插入的数据或者待读取的数据，HashMap将Key的哈希值对数组长度取模，结果作为该Entry在数组中的index。在计算机中，取模的代价远高于位操作的代价，因此HashMap要求数组的长度必须为2的N次方。此时将Key的哈希值对2^N-1进行与运算，其效果即与取模等效。HashMap并不要求用户在指定HashMap容量时必须传入一个2的N次方的整数，而是会通过Integer.highestOneBit算出比指定整数大的最小的2^N值。

如何进行位运算呢？有如下的公式（Length是HashMap的长度）： 
之前说过，从Key映射到HashMap数组的对应位置，会用到一个Hash函数： 
index = Hash（“apple”） 
如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。 
index = HashCode（Key） & （Length - 1） 
下面我们以值为“book”的Key来演示整个过程：

1. 计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。
2. 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
3. 把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。 
   可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。这里的位运算其实是一种快速取模算法。

HashMap 的size为什么必须是2的幂?。这是因为2的幂用二进制表示时所有位都为1，例如16-1=15 的二进制就是1111B。我们说了Hash算法是为了让hash 的分布变得均匀。其实我们可以把1111看成四个通道，表示跟1111 做&运算后分布是均匀的。假如默认长度取10，二进制表示为1010，这样就相当于有两个通道是关闭的，所以计算出来的索引重复的几率比较大。

HashMap的扩容条件：

(size>=threshold) && (null != table[bucketIndex]) 即达到阈值，并且当前需要存放对象的slot上已经有值。

解决hash冲突的办法

1. 开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
2. 再哈希法
3. 链地址法
4. 建立一个公共溢出区

Java中hashmap的解决办法就是采用的链地址法

解决Hash冲突的开放地址检测是怎么实现的

这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述： 
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1)) 
其中： H ( key ) 为关键字 key 的直接哈希地址， m 为哈希表的长度， di 为每次再探测时的地址增量。

增量 d 可以有不同的取法，并根据其取法有不同的称呼： 
（ 1 ） d i ＝ 1 ， 2 ， 3 ， …… 线性探测再散列； 
（ 2 ） d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探测再散列； 
（ 3 ） d i ＝ 伪随机序列 伪随机再散列；

从哈希表中删除一个元素，再加入元素时恰好与原来的那个哈希冲突，这个元素会放在哪

放在冲突Entry最开始的地方，因为哈希表在冲突时采用的是头插法，之所以把Entry放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。

并发容器, hashtable和concurrenthashmap的区别

HashMap为什么线程不安全？

主要有死链和高并发下的数据用丢失两个问题

• 死链

                https://www.jianshu.com/p/e2f75c8cce01

主要发生在多线程情况下rezise时迁移数据的transfer()方法，put(), get()方法。多个线程同时扩容时， hashmap会可能产生环，造成死循环。

• 高并发下的数据丢失

新增对象丢失的原因一般有:

• • 并发赋值时被覆盖
  • resize线程已遍历区间新增元素会丢失
  • 多个线程同时resize“新表“被覆盖
  • 迁移丢失

1. 数据丢失场景： 在表扩容时，当前线程迁移数据的过程中，其他线程新增的元素有可能落在迁移线程已经遍历过的哈希槽上；在遍历完成之后，table数组引用指向了newTable, 这时刚才新增的元素就会失去引用，被GC回收。

2. 数据覆盖场景:

put的时候导致的多线程数据不一致：有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

或者多个线程同时执行resize，也会造成table的覆盖问题。

ConcurrentHashMap

Hashtable 在JDK1.0引入，以全互斥方式处理并发问题，性能极差；

HashMap在JDK1.2引入，非线程安全，在并发写的情形下，容易出现死链的问题；

ConcurrentHashMap在JDK5中引入，是线程安全的哈希式集合，JDK1.8之前采用分段锁的设计理念，相当于Hashtable和HashMap的折衷版。分段锁由内部类Segment实现，继承于ReentrantLock, 用它来管辖辖区每个HashEntry。JDK11对JDK7做了如下优化:

• 取消分段锁机制，进一步降低冲突的概率；
• 引入红黑树结构，同一个哈希槽上的元素个数超过一定阈值后（8），将单向链表转为红黑树结构（在转化中，使用同步块锁住当前槽的首元素，防止其他线程对当前槽进行修改，转化完成后利用CAS替换原有链表）；当某个槽的元素减少至6个时，由红黑树重新转回链表；
• 使用更加优化的方式统计集合内的元素数量

待补充：

快排

索引

LinkedHashMap

LinkedHashMap是有序的HashMap

map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, false)

• 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存 ;
• 第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存 ;

关于使用LinkedHashMap实现LRU和FIFO

JAVA创建对象的方法有哪些

Java中有5种创建对象的方式，下面给出它们的例子还有它们的字节码

使用new关键字	} → 调用了构造函数
使用Class类的newInstance方法	} → 调用了构造函数
使用Constructor类的newInstance方法	} → 调用了构造函数
使用clone方法	} → 没有调用构造函数
使用反序列化	} → 没有调用构造函数

• 使用Class类的newInstance方法：我们也可以使用Class类的newInstance方法创建对象，这个newInstance方法调用无参的构造器创建对象
• 使用Constructor类的newInstance方法我们可以通过这个newInstance方法调用有参数的和私有的构造函数。这两种newInstance的方法就是大家所说的反射，事实上Class的newInstance方法内部调用Constructor的newInstance方法。
• 调用一个对象的clone方法，JVM就会创建一个新的对象，将前面的对象的内容全部拷贝进去，用clone方法创建对象并不会调用任何构造函数。要使用clone方法，我们必须先实现Cloneable接口并实现其定义的clone方法。
• 使用反序列化：当我们序列化和反序列化一个对象，JVM会给我们创建一个单独的对象，在反序列化时，JVM创建对象并不会调用任何构造函数。为了反序列化一个对象，我们需要让我们的类实现Serializable接口。

Object 类有哪些方法？

九个方法：clone, getclass, toString, finalize, equals, hashcode, wait, notify, notifyAll

什么是JAVA序列化

把对象转换为字节序列的过程称为对象的序列化。
把字节序列恢复为对象的过程称为对象的反序列化。
　　对象的序列化主要有两种用途：
　　1） 把对象的字节序列永久地保存到硬盘上，通常存放在一个文件中；
　　2） 在网络上传送对象的字节序列。

String, stringbuilder, stringbuffer区别

• 首先说运行速度（特指修改的操作），在这方面运行速度快慢为：StringBuilder > StringBuffer > String

　　String最慢的原因：

String为字符串常量，String对象一旦创建之后该对象是不可更改的，Java中对String对象进行的更改操作实际上是一个不断创建新的对象并且将旧的对象回收的一个过程，所以执行速度很慢。而StringBuilder和StringBuffer均为字符串变量，对变量进行操作就是直接对该对象进行更改，而不进行创建和回收的操作，所以速度要比String快很多。

• 在线程安全上，StringBuilder是线程不安全的，而StringBuffer是线程安全的。

如果一个StringBuffer对象在字符串缓冲区被多个线程使用时，StringBuffer中很多方法可以带有synchronized关键字，所以可以保证线程是安全的，但StringBuilder的方法则没有该关键字，所以不能保证线程安全。

String：适用于少量的字符串操作的情况

　　StringBuilder：适用于单线程下在字符缓冲区进行大量操作的情况

　　StringBuffer：适用多线程下在字符缓冲区进行大量操作的情况

string的不可变如何实现

通常情况下，在java中通过以下步骤实现不可变

1. 对于属性不提供设值方法
2. 所有的属性定义为private final
3. 类声明为final不允许继承

如果读了String 的源码的话，在Java中String类其实就是对字符数组的封装, JDK6中, value是String封装的数组，offset是String在这个value数组中的起始位置，count是String所占的字符的个数。会发现String 类的所有变量（value，offset和count等）都是 private final 声明的，且没有对外提供任何set方法。所以在String类的外部无法修改String。也就是说一旦初始化就不能修改， 并且在String类的外部不能访问这三个成员。一旦String初始化了， 也不能被改变。所以可以认为String对象是不可变的了。

string为何设计为不可变

1. 字符串常量池的需要

字符串常量池(String pool, String intern pool, String保留池) 是Java堆内存中一个特殊的存储区域, 当创建一个String对象时,假如此字符串值已经存在于常量池中,则不会创建一个新的对象,而是引用已经存在的对象。假若字符串对象允许改变,那么将会导致各种逻辑错误,比如改变一个对象会影响到另一个独立对象. 严格来说，这种常量池的思想,是一种优化手段。

2. 允许String对象缓存HashCode

Java中String对象的哈希码被频繁地使用, 比如在hashMap 等容器中。字符串不变性保证了hash码的唯一性,因此可以放心地进行缓存.这也是一种性能优化手段,意味着不必每次都去计算新的哈希码.

3. 安全性

String被许多的Java类(库)用来当做参数,例如 网络连接地址URL,文件路径path,还有反射机制所需要的String参数等, 假若String不是固定不变的,将会引起各种安全隐患。

总体来说, String不可变的原因包括 设计考虑,效率优化问题,以及安全性这三大方面。

为什么String被设计为不可变？

• 安全：首要原因是安全，不仅仅体现在你的应用中，而且在JDK中，Java的类装载机制通过传递的参数（通常是类名）加载类，这些类名在类路径下，想象一下，假设String是可变的，一些人通过自定义类装载机制分分钟黑掉应用。如果没有了安全，Java不会走到今天。
• 性能： string不可变的设计出于性能考虑，当然背后的原理是string pool，当然string pool不可能使string类不可变，不可变的string更好的提高性能。
• 线程安全： 当多线程访问时，不可变对象是线程安全的，不需要什么高深的逻辑解释，如果对象不可变，线程也不能改变它。

异常

Java把异常当作对象来处理，并定义一个基类java.lang.Throwable作为所有异常的超类。Throwable 下又分为 Error 和 Exception。

• Error 用来表示 JVM 无法处理的错误

Error：Error类对象由 Java 虚拟机生成并抛出，大多数错误与代码编写者所执行的操作无关。

最常见的erro是当JVM不再有继续执行操作所需的内存资源时，将出现 OutOfMemoryError。这些异常发生时，Java虚拟机（JVM）一般会选择线程终止；

• Exception 分为两种：

1. 1. 受检异常 ：需要用 try...catch... 语句捕获并进行处理，并且可以从异常中恢复；
   2. 非受检异常 ：是程序运行时错误，例如除 0 会引发 Arithmetic Exception，此时程序崩溃并且无法恢复。

设计模式有哪些

单例模式: (懒汉模式、饥汉模式)
1、构造方法私有化，除了自己类中能创建外其他地方都不能创建

2、在自己的类中创建一个单实例（饱汉模式是一出来就创建创建单实例，而饥汉模式需要的时候才创建）

3、提供一个方法获取该实例对象(创建时需要进行方法同步)

饿汉模式

饿汉模式就是立即加载，在方法调用前，实例就已经被创建了，所以是线程安全的。

public class MyObject1 {

    private static MyObject1 myObject1 = new MyObject1();

    private MyObject1() {}

    public static MyObject1 getInstance() {

        return myObject1;

    }

}

懒汉模式

懒汉就是延迟化加载，当需要使用的时候才进行实例化。

线程不安全方式:

public class MyObject2 {

    private static MyObject2 myObject2;

    private MyObject2() {}

    public static MyObject2 getInstance() {

        if (myObject2 == null) {

            myObject2 = new MyObject2();

        }

        return myObject2;

    }

}

线程安全但是效率低下的方式:

public class MyObject3 {

    private static MyObject3 myObject3;

    private MyObject3() {}

    synchronized public static MyObject3 getInstance() {

        if (myObject3 == null) {

            myObject3 = new MyObject3();

        }

        return myObject3;

    }

}

使用DCL双检查锁(双重检查锁定)，线程安全而且效率得到提高，只将进行实例化的代码进行加锁:

public class MyObject4 {

    private volatile static MyObject4 myObject4;

    private MyObject4() {}

    public static MyObject4 getInstance() {

        if (myObject4 == null) {

            synchronized (MyObject4.class) {

                if (myObject4 == null) {

                    myObject4 = new MyObject4();

                }

            }

        }

        return myObject4;

    }

}

但要注意实例化的对象一定要声明位volatile型，以禁止指令重排序，否则仍然出现线程安全问题，分析见此。

还有其他初始化的手段，见本博客

工厂模式: Spring IOC就是使用了工厂模式.
       对象的创建交给一个工厂去创建。在工厂方法模式中，核心的工厂类不再负责所有的产品的创建，而是将具体创建的工作交给子类去做。

抽象工厂模式：抽象工厂模式可以向客户端提供一个接口，使客户端在不必指定产品的具体的情况下，创建多个产品族中的产品对象。

代理模式: Spring AOP就是使用的动态代理。

观察者模式:在对象之间定义了一对多的依赖，这样一来，当一个对象改变状态，依赖它的对象会收到通知并自动更新。

装饰器模式:在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责，在Java源码中典型的装饰器模式就是java I/O, 其实装饰者模式也有其缺点，就是产生了太多的装饰者小类，有类爆炸的趋势。

第五模块--数据结构：

BST 二叉搜索树

1 首先它也是一个二叉树，故满足递归定义;

2 需满足 左子树值<=根值<=右子树 ，BST的中序遍历必定是严格递增的。

3. 任意节点的左右子树也分别是二叉查找树.

4. 没有键值相等的节点.

5. 对于某些情况,二叉查找树会退化成一个有n个节点的线性链

AVL树

1. 是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,

2. 左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).

3. 不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。 

红黑树的六大特征

本质上是一个平衡搜索二叉树，和Btree不一样，可以说是AVL树的变种，牺牲了一定查询效率，减少了维护平衡的时间。log(n) 中序排序都能得到递增序列。

1）每个结点要么是红的，要么是黑的。（没有其他颜色）

2）根结点是黑的。

3）每个叶结点（叶结点即指树尾端NIL(Nothing In the Leaf)指针或NULL结点）是黑的。（叶子节点即为树尾端的NIL指针，或者说NULL节点。）

4）一条路径上不能出现相邻的两个红色节点

5）对于任一结点而言，其到叶结点(树尾端NIL指针)的每一条路径都包含相同数目的黑结点。（最长路径是最小路径的2倍）

6）最多三次旋转，可以达到平衡

上述条件保证红黑树的新增、查找、删除的最坏时间复杂度均为O(logN)。

通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍.它是一种弱平衡二叉树(由于是弱平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索,插入,删除操作多的情况下,我们就用红黑树.

红黑树相比于BST和AVL树有什么优点？

红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(logN)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。

相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多

在插入时，红黑树和AVL树都能在至多2次旋转内恢复平衡；在删除时，红黑树由于只追求大致上的平衡，能在至多3次旋转内恢复平衡，而追求绝对平衡的AVL树至多需要O(logN)次旋转。

B-树（B树、平衡多路树）

B-tree是一种平衡多路搜索树（并不一定是二叉的）B-tree树即B树

B树，一般用于外存储索引结构。系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的。二叉树、红黑树 [复杂度O(h)]导致树高度非常高(平衡二叉树一个节点只能有左子树和右子树),逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，IO次数多查找慢,效率低。

特点：

（1）根节点的左子树和右子树的深度最多相差1.(确保了不会出现上图右边的极端现象)

（2）是一个平衡多路搜索树，单个节点能放多个子节点

（3）所有结点都有存储关键字（数据）；

（4）不太稳定，可能走不到叶子节点

B+TREE

B+树是B-树的变体，也是一种平衡多路搜索树，非叶子节点只做索引，所有数据都保存在叶子节点中。

和B树区别

1：根节点和分支节点中不保存数据，只用于索引  。数据和索引分离

2：所有数据都保存在叶子节点中

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+Tree内节点去掉了data域，只做索引，减少了io次数，因此可以拥有更大的出度，拥有更好的性能。只利用索引快速定位数据索引范围，先定位索引再通过索引高效快速定位数据。

B+树和B树的区别

一篇详尽的解析

为什么用B+树作为数据库索引，而不是平衡树或者B树？

• 为什么平衡二叉树或者红黑树不适合作为索引

索引是存在于索引文件中，是存在于磁盘中的。因为索引通常是很大的，因此无法一次将全部索引加载到内存当中，因此每次只能从磁盘中读取一个磁盘页的数据到内存中。而这个磁盘的读取的速度较内存中的读取速度而言是差了好几个级别。注意，我们说的平衡二叉树结构，指的是逻辑结构上的平衡二叉树，其物理实现是数组。由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此，每次读取的磁盘页的数据中有许多是用不上的。因此，查找过程中要进行许多次的磁盘读取操作。而适合作为索引的结构应该是尽可能少的执行磁盘IO操作，因为执行磁盘IO操作非常的耗时。因此，平衡二叉树并不适合作为索引结构。另外一点，平衡二叉树和红黑树都是二叉树，数据量较大的时候，树的高度也比较高，因此会产生较多的磁盘IO。B树的查询，由于每层可以储存多个节点，因此可以作磁盘预读，将相关的数据一次性读进内存里，因此他的查找主要发生在内存中，而平衡二叉树的查询，则是发生在磁盘读取中。因此，虽然B树查询查询的次数不比平衡二叉树的次数少，但是相比起磁盘IO速度，内存中比较的耗时就可以忽略不计了。因此，B树更适合作为索引。

• 为什么B+树比B树更适合作索引

B树：有序数组+平衡多叉树； 
B+树：有序数组链表+平衡多叉树；

B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据。

B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了，B+树支持范围查找非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
比如要查 5-10之间的，B+树一次找到到5这个标记，再一次找到10这个标记，然后串起来就行了，B树就非常麻烦。

举个例子来对比。 
B树：

比如说，我们要查找关键字范围在3到7的关键字，在找到第一个符合条件的数字3后，访问完第一个关键字所在的块后，得遍历这个B树，获取下一个块，直到遇到一个不符合条件的关键字。遍历的过程是比较复杂的。

B+树：

相比之下，B+树的基于范围的查询简洁很多。由于叶子节点有指向下一个叶子节点的指针，因此从块1到块2的访问，通过块1指向块2的指针即可。从块2到块3也是通过一个指针即可。

数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

B+树由于非叶子节点也有数据，这样在做范围查找的时候有可能某个范围的数据散落在叶子节点和非叶子节点(各层)，这样就需要多次扫描B树才能找全数据，会产生多次的磁盘IO；而B+树所有的数据都在叶子节点，且叶子节点的数据前后用指针相连，只要通过索引找到范围数据在叶子节点中的起始或结束位置，就可以顺着叶子节点链表把这个范围内的数据全都读出来，避免了再次扫描，从而提高范围查找的效率。

八大排序的特点

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法（快选希堆），

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

链表的倒数第K个节点(快排)

树的深度优先遍历和广度优先遍历

搜索方法有哪些，稳定性怎么样

第六模块--数据库

Reids 支持的数据类型

Redis支持五种数据类型：

• string（字符串）
• hash（哈希）是一个键值(key=>value)对集合。
• list（列表）是简单的字符串列表，按照插入顺序排序
• set（集合），Set是string类型的无序集合。集合是通过哈希表实现的
• zset(sorted set：有序集合)，是string类型元素的集合,且不允许重复的成员，不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。

redis的替换策略

替换对象分为 allkeys 和 volatile,

替换方式分为LRU、random 和ttl

总的策略 = 2*3 = 6

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

腾讯一面后端问了LRU的算法原理，自己怎么实现LRU

• volatile-lru : 对具有生存周期的key（设置失效（expire set）的key）进行LRU算法置换.
• volatile-random : 对具有生存周期的key进行随机置换.
• volatile-ttl : 对具有生存周期的key随机进行抽样, 置换出抽样中生存周期最短的.
• allkeys-lru : 对整个db进行LRU算法置换.
• allkeys-random : 对整个db进行随机置换.
• noeviction : 不进行置换.

Redis 持久化方法

redis提供两种方式进行持久化:

• 一种是RDB(快照)持久化（原理是将Reids在内存中的数据库记录定时dump到磁盘上的RDB持久化）
• 另外一种是AOF（append only file）持久化（原理是将Reids的操作日志以追加的方式写入文件）

RDB持久化是指在指定的时间间隔内将内存中的数据集快照写入磁盘，实际操作过程是fork一个子进程，先将数据集写入临时文件，写入成功后，再替换之前的文件，用二进制压缩存储。

AOF持久化以日志的形式记录服务器所处理的每一个写、删除操作，查询操作不会记录，以文本的方式记录，可以打开文件看到详细的操作记录。

什么时候用RDB什么时候用AOF:

备份、全量复制时使用RDB;需要实时备份的时候采用AOF

RDB的优点：

• RDB是一个紧凑压缩的二进制文件， 代表Redis在某个时间点上的数据快照。 非常适用于备份， 全量复制等场景。 比如每6小时执行bgsave备份，并把RDB文件拷贝到远程机器或者文件系统中（如hdfs） ， 用于灾难恢复。
• Redis加载RDB恢复数据远远快于AOF的方式。

RDB的缺点：·

• RDB方式数据没办法做到实时持久化/秒级持久化。 因为bgsave每次运行都要执行fork操作创建子进程， 属于重量级操作， 频繁执行成本过高。
• RDB文件使用特定二进制格式保存， Redis版本演进过程中有多个格式的RDB版本， 存在老版本Redis服务无法兼容新版RDB格式的问题。

AOF: 通过追加写命令到文件实现持久化， 通过appendfsync参数可以控制实时/秒级持久化。 因为需要不断追加写命令， 所以AOF文件体积逐渐变大，

需要定期执行重写操作来降低文件体积。 Redis执行AOF恢复数据远远慢于加载RDB的方式。

Redis其他知识：

1）Redis提供5种数据结构，每种数据结构都有多种内部编码实现。
2）纯内存存储、IO多路复用技术、单线程架构是造就Redis高性能的三个因素。
3）由于Redis的单线程架构，所以需要每个命令能被快速执行完，否则会存在阻塞Redis的可能，理解Redis单线程命令处理机制是开发和运维Redis的核心之一。
4）批量操作（例如mget、mset、hmset等）能够有效提高命令执行的效率，但要注意每次批量操作的个数和字节数。
5）了解每个命令的时间复杂度在开发中至关重要，例如在使用keys、hgetall、smembers、zrange等时间复杂度较高的命令时，需要考虑数据规模对于Redis的影响。
6）persist命令可以删除任意类型键的过期时间，但是set命令也会删除字符串类型键的过期时间，这在开发时容易被忽视。
7）move、dump+restore、migrate是Redis发展过程中三种迁移键的方式，其中move命令基本废弃，migrate命令用原子性的方式实现了dump+restore，并且支持批量操作，是Redis Cluster实现水平扩容的重要工具。
8）scan命令可以解决keys命令可能带来的阻塞问题，同时Redis还提供了hscan、sscan、zscan渐进式地遍历hash、set、zset。

Redis应用场景:

1. 缓存功能

Redis作为缓存层，MySQL作为存储层，绝大部分请求的热点数据都从Redis中获取。由于Redis具有支撑高并发的特性，所以缓存通常能起到加速读写和降低后端压力的作用。

2. 限速

为了短信接口不被频繁访问，会限制用户每分钟获取验证码的频率，例如一分钟不能超过5次。此功能可以使用Redis来实现，利用Redis可以设置键过期的功能，在用户首次访问时为其新建一个带有过期时间的key（如60秒）,在这个key过期之前，都不允许用户再次申请短信验证码。

3. 消息队列

Redis的lpush+brpop命令组合即可实现阻塞队列，生产者客户端使用lrpush从列表左侧插入元素，多个消费者客户端使用brpop命令阻塞式的“抢”列表尾部的元素，多个客户端保证了消费的负载均衡和高可用性。

4. 用户标签系统

集合类型比较典型的使用场景是标签（tag）。例如一个用户可能对娱乐、体育比较感兴趣，另一个用户可能对历史、新闻比较感兴趣，这些兴趣点就是标签。可以通过redis set找出集合的交集并集等

5. 排行榜系统

有序集合比较典型的使用场景就是排行榜系统。例如视频网站需要对用户上传的视频做排行榜，榜单的维度可能是多个方面的：按照时间、按照播放数量、按照获得的赞数。

https://www.cnblogs.com/davygeek/p/7995072.html

数据库事物特性(acid)：

数据库事务必须具备ACID特性，ACID是Atomic原子性，Consistency一致性，Isolation隔离性，Durability持久性

MySQL的架构

• MySQL 主要分为 Server 层和引擎层，Server 层主要包括连接器、查询缓存、分析器、优化器、执行器，同时还有一个日志模块（binlog），这个日志模块所有执行引擎都可以共用,redolog 只有 InnoDB 有。

连接器： 身份认证和权限相关(登录 MySQL 的时候)。
查询缓存: 执行查询语句的时候，会先查询缓存（MySQL 8.0 版本后移除，因为这个功能不太实用）。
分析器: 没有命中缓存的话，SQL 语句就会经过分析器，分析器说白了就是要先看你的 SQL 语句要干嘛，再检查你的 SQL 语句语法是否正确。
优化器： 按照 MySQL 认为最优的方案去执行。
执行器: 执行语句，然后从存储引擎返回数据。

• 引擎层是插件式的，目前主要包括，MyISAM,InnoDB,Memory 等。

一条SQL语句的执行过程

SQL 等执行过程分为两类

• 对于查询等过程如下：权限校验—》查询缓存—》分析器—》优化器—》权限校验—》执行器—》引擎
• 对于更新等语句执行流程如下：分析器----》权限校验----》执行器—》引擎—redo log prepare—》binlog—》redo log commit

内连接、外连接 与 左连接、右连接

驱动表与被驱动表:

在两表连接查询中，驱动表只需要访问一次，被驱动表可能被访问多次。

内连接与外连接:

• 对于内连接的两个表，驱动表中的记录在被驱动表中找不到匹配的记录，该记录不会加入到最后的结果集，我们上边提到的连接都是所谓的内连接。
• 对于外连接的两个表，驱动表中的记录即使在被驱动表中没有匹配的记录，也仍然需要加入到结果集。在MySQL中，根据选取驱动表的不同，外连接仍然可以细分为2种：
  • 左外连接     选取左侧的表为驱动表
  • 右外连接     选取右侧的表为驱动表

过滤条件where 和 on:

• WHERE子句中的过滤条件

  WHERE子句中的过滤条件就是我们平时见的那种，不论是内连接还是外连接，凡是不符合WHERE子句中的过滤条件的记录都不会被加入最后的结果集。

• ON子句中的过滤条件

  对于外连接的驱动表的记录来说，如果无法在被驱动表中找到匹配ON子句中的过滤条件的记录，那么该记录仍然会被加入到结果集中，对应的被驱动表记录的各个字段使用NULL值填充。

  需要注意的是，这个ON子句是专门为外连接驱动表中的记录在被驱动表找不到匹配记录时应不应该把该记录加入结果集这个场景下提出的，所以如果把ON子句放到内连接中，MySQL会把它和WHERE子句一样对待，也就是说：内连接中的WHERE子句和ON子句是等价的。

一般情况下，我们都把只涉及单表的过滤条件放到WHERE子句中，把涉及两表的过滤条件都放到ON子句中，我们也一般把放到ON子句中的过滤条件也称之为连接条件

左连接与右连接：

左连接和右连接是左外连接和右外连接简称， 只有外连接才分左右，且外连接一定会分左右。

可以据此来分辨内连接和外连接:

如果join语句前面有left或者right, 则一定是外连接，此时on的语义与where的语义不同；

如果join语句前面没有left或者right, 则一定是内连接，此时on的语义与where相同。

标识内连接和外连接的关键字inner|cross 和 outer都是可以省略的。

1．第一范式(确保每列保持原子性)

第一范式是最基本的范式。如果数据库表中的所有字段值都是不可分解的原子值，就说明该数据库表满足了第一范式。

第一范式的合理遵循需要根据系统的实际需求来定。比如某些数据库系统中需要用到“地址”这个属性，本来直接将“地址”属性设计成一个数据库表的字段就行。但是如果系统经常会访问“地址”属性中的“城市”部分，那么就非要将“地址”这个属性重新拆分为省份、城市、详细地址等多个部分进行存储，这样在对地址中某一部分操作的时候将非常方便。

2．第二范式(确保表中的每列都和主键相关)

第二范式在第一范式的基础之上更进一层。第二范式需要确保数据库表中的每一列都和主键相关，而不能只与主键的某一部分相关（主要针对联合主键而言）。也就是说在一个数据库表中，一个表中只能保存一种数据，不可以把多种数据保存在同一张数据库表中。

3．第三范式(确保每列都和主键列直接相关,而不是间接相关)

第三范式需要确保数据表中的每一列数据都和主键直接相关，而不能间接相关。

比如在设计一个订单数据表的时候，可以将客户编号作为一个外键和订单表建立相应的关系。而不可以在订单表中添加关于客户其它信息（比如姓名、所属公司等）的字段。

数据库索引

索引是关系型数据库中给数据库表中一列或多列的值排序后的存储结构，聚集索引以及非聚集索引用的是B+树索引。

MySQL 索引类型有：唯一索引，主键（聚集）索引，非聚集索引，全文索引

聚集（clustered）索引，也叫聚簇索引，MySQL里主键就是聚集索引。

定义：数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同，一个表中只能拥有一个聚集索引。查询方面，聚集索引的速度往往会更占优势。

数据行的物理顺序与列值的顺序相同，如果我们查询id比较靠后的数据，那么这行数据的地址在磁盘中的物理地址也会比较靠后。而且由于物理排列方式与聚集索引的顺序相同，所以也就只能建立一个聚集索引了。

非聚集（unclustered）索引。

定义：该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同，一个表中可以拥有多个非聚集索引。

非聚集索引的二次查询问题

非聚集索引叶节点仍然是索引节点，只是有一个指针指向对应的数据块，此如果使用非聚集索引查询，而查询列中包含了其他该索引没有覆盖的列，那么他还要进行第二次的查询，查询节点上对应的数据行的数据。

SQL语句查询太慢怎么找原因、优化?

https://www.cnblogs.com/kubidemanong/p/10734045.html

分类:

1、大多数情况是正常的，只是偶尔会出现很慢的情况。

2、在数据量不变的情况下，这条SQL语句一直以来都执行的很慢。

偶发性:

a. 数据库在刷新脏页。例如 redo log 写满了需要同步到磁盘。

b. 拿不到锁。要执行的这条语句涉及到的表，别人在用，并且加锁了，我们拿不到锁，只能慢慢等待别人释放锁。要判断是否真的在等待锁，我们可以用 show processlist这个命令来查看当前的状态

经常性:

a. 没用到索引

b. 索引失效 (可以用explain 看一下这条语句，查看possible-key字段看一下可能用到的索引，key字段查看实际用到的索引)

c. 数据库索引选择错误。MySQL在执行一条语句的时候会通过分析器估计各种查询计划的查询代价，然后在其中选择代价最小的执行。如果分析器估计走索引的代价比较大，可能就放弃索引而走全表扫描。但分析器的代价估计有可能是不准确的(涉及到一个索引区分度的概念，这个区分度是用采样来统计的，采样会有偏差)。  解决方法， 可以强制走索引force index(a); 可以强制数据库重新统计索引区分度: analyze table t.

可以解释一下explain 一个查询语句后的一些字段吗?

一条查询语句在经过MySQL查询优化器的各种基于成本和规则的优化会后生成一个所谓的执行计划。

explain 就是用来查看一条查询语句的执行计划的。

查询计划由如下几个关键的字段:

id ： 在一个大的查询语句中每个SELECT关键字都对应一个唯一的id

table: 该查询语句涉及的表名

type: 针对单表访问的方法 (有 const[主键或者唯一二级索引列与常数进行等值匹配]、ref[普通的二级索引列与常量进行等值匹配]、all[全表扫描]、index[可以使用索引覆盖，但需要扫描全部的索引记录]等)。

possible_key：该查询可能用到的索引。

key : 该查询实际用到的索引。

rows: 执行该查询计划需要扫描的行数。(如果查询优化器决定使用全表扫描的方式对某个表执行查询时，执行计划的rows列就代表预计需要扫描的行数，如果使用索引来执行查询时，执行计划的rows列就代表预计扫描的索引记录行数)

如何查看执行计划的执行成本？

在EXPLAIN单词和真正的查询语句中间加上FORMAT=JSON。

这样我们就可以得到一个json格式的执行计划，里边儿包含该计划花费的成本

联合索引和单列索引的区别是什么?

https://www.cnblogs.com/greatLong/articles/11573588.html

联合索引本质：

是对多个列建立一个索引，称为联合索引。当创建(a,b,c)联合索引时，相当于创建了(a)单列索引，(a,b)联合索引以及(a,b,c)联合索引。所以只有查询条件满足a 或者 (a,b) 或者 (a,b,c)的时候，才会用上联合索引。这就是所谓的最左匹配原则。意思是 以最左边的为起点任何连续的索引都能匹配上。

单列索引只是对一个字段建立索引。

MySQL索引失效的情况有哪些？

1.如果条件中有or，假如or连接的两个查询条件字段中有一个没有索引的话,引擎会放弃索引而产生全表扫描。

2.对于多列索引，不是使用的第一部分(第一个)，则不会使用索引

3.like查询是以%开头(以%结尾的情况可以使用)

4. 查询时，采用is null条件时，不能利用到索引，只能全表扫描

5. 如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引

6.如果mysql估计使用全表扫描要比使用索引快,则不使用索引

7. 查询条件使用函数在索引列上，或者对索引列进行运算，运算包括(+，-，*，/，! 等) 错误的例子：select * from test where id-1=9; 正确的例子：select * from test where id=10;

8. 使用IN 关键字进行范围查找，有可能不走索引(IN 的 范围里面有超过200个单点区间的时候会放弃索引，因为这个时候优化器对这200个单点区间作成本估计的成本很高。MySQL 5.7.3之前这个单点区间的上限是10， 5.7.3之后上限是200)

如何提高数据库查询效率

a. 对查询进行优化，应尽量避免全表扫描，首先应考虑在 where 及 order by 涉及的列上建立索引；

b. 应尽量避免在 where 子句中对字段进行 null 值判断，否则将导致引擎放弃使用索引而进行全表扫描；

c. 索引并不是越多越好，索引固然可以提高相应的 select 的效率，但同时也降低了 insert 及 update 的效率，因为 insert 或 update 时有可能会重建索引，所以怎样建索引需要慎重考虑，视具体情况而定。

d. 应尽量避免在 where 子句中使用!=或<>操作符，否则将引擎放弃使用索引而进行全表扫描

数据库可以有几个聚集索引

一个，主键是聚集索引，数据行的物理顺序与列值（一般是主键的那一列）的逻辑顺序相同

哪些引擎支持聚集索引

InnoDB索引和MyISAM索引的区别：

一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。

二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。

简单的SQL语句(更新)

如何创建索引

MySQL中innodb表主键设计原则

数据库主键和外键

数据库

• Mysql的三大引擎:

InnoDB, MyISAM和Memory, 默认InnoDB, 支持事务；memory完全在内存中，除了大小限制还有断电丢失；

• redis的hash算法用的是啥

一致性哈希算法

• nosql为啥比sql快

nosql不需要满足sql关系数据库数据一致性等复杂特性，非关系型一般是缓存数据库，数据加载到内存中自然更快。redis是单线程执行的，任务都放到队列中。

• 常见关系型数据库：

Oracle、Microsoft Access、MySQL

• 常见非关系型数据库：

MongoDb、redis、HBase

• 关系型数据库和非关系型数据库的区别与联系：

非关系型数据库中，我们查询一条数据，结果出来一个数组；关系型数据库中，查询一条数据结果是一个对象。

数据库 类型	特性	优点	缺点
关系型数据库 SQLite、Oracle、mysql	1、关系型数据库，是指采用了关系模型来组织 数据的数据库； 2、关系型数据库的最大特点就是事务的一致性； 3、简单来说，关系模型指的就是二维表格模型， 而一个关系型数据库就是由二维表及其之间的联系所组成的一个数据组织。	1、容易理解：二维表结构是非常贴近逻辑世界一个概念，关系模型相对网状、层次等其他模型来说更容易理解； 2、使用方便：通用的SQL语言使得操作关系型数据库非常方便； 3、易于维护：丰富的完整性(实体完整性、参照完整性和用户定义的完整性)大大减低了数据冗余和数据不一致的概率； 4、支持SQL，可用于复杂的查询。	1、为了维护一致性所付出的巨大代价就是其读写性能比较差； 2、固定的表结构； 3、高并发读写需求； 4、海量数据的高效率读写；
非关系型数据库 MongoDb、redis、HBase	1、使用键值对存储数据； 2、分布式； 3、一般不支持ACID特性； 4、非关系型数据库严格上不是一种数据库，应该是一种数据结构化存储方法的集合。	1、无需经过sql层的解析，读写性能很高； 2、基于键值对，数据没有耦合性，容易扩展； 3、存储数据的格式：nosql的存储格式是key,value形式、文档形式、图片形式等等，文档形式、图片形式等等，而关系型数据库则只支持基础类型。	1、不提供sql支持，学习和使用成本较高； 2、无事务处理，附加功能bi和报表等支持也不好；

注1：数据库事务必须具备ACID特性，ACID是Atomic原子性，Consistency一致性，Isolation隔离性，Durability持久性。

注2：数据的持久存储，尤其是海量数据的持久存储，还是需要一种关系数据库。

 Myisam 和innodb的区别

1. MyISAM：它是基于传统的ISAM类型，ISAM是Indexed Sequential Access Method (有索引的顺序访问方法) 的缩写，它是存储记录和文件的标准方法。不是事务安全的，而且不支持外键，如果执行大量的select，insert MyISAM比较适合。
2. InnoDB：支持事务安全的引擎，支持外键、行锁、事务是他的最大特点。如果有大量的update和insert，建议使用InnoDB，特别是针对多个并发和QPS较高的情况。

3. MyISAM索引实现：MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

4. 在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

第七模块 高并发与分布式

什么是负载均衡?有哪些常用的负载均衡策略?

负载均衡

由一个独立的统一入口来收敛流量(接收请求)，再由做二次分发的过程就是「负载均衡」。

负载均衡实现方法的分类

根据实现技术不同，可分为DNS负载均衡，HTTP负载均衡，IP负载均衡，反向代理负载均衡、链路层负载均衡等。

HTTP重定向负载均衡

当用户向服务器发起请求时，请求首先被集群调度者截获；调度者根据某种分配策略，选择一台服务器，并将选中的服务器的IP地址封装在HTTP响应消息头部的Location字段中，并将响应消息的状态码设为302，最后将这个响应消息返回给浏览器。

当浏览器收到响应消息后，解析Location字段，并向该URL发起请求，然后指定的服务器处理该用户的请求，最后将结果返回给用户。

缺点:

调度服务器只在客户端第一次向网站发起请求的时候起作用。当调度服务器向浏览器返回响应信息后，客户端此后的操作都基于新的URL进行的(也就是后端服务器)，此后浏览器就不会与调度服务器产生关系。

• 由于不同用户的访问时间、访问页面深度有所不同，从而每个用户对各自的后端服务器所造成的压力也不同。而调度服务器在调度时，无法知道当前用户将会对服务器造成多大的压力，因此这种方式无法实现真正意义上的负载均衡，只不过是把请求次数平均分配给每台服务器罢了。
• 若分配给该用户的后端服务器出现故障，并且如果页面被浏览器缓存，那么当用户再次访问网站时，请求都会发给出现故障的服务器，从而导致访问失败。做不到高可用。

DNS负载均衡

当用户向我们的域名发起请求时，DNS服务器会自动地根据我们事先设定好的调度策略选一个合适的IP返回给用户，用户再向该IP发起请求。它的作用与HTTP重定向类似。问题是DNS会缓存IP，如果某一IP不可用(如机器故障)会导致部分用户无法正常访问，此时可以用动态DNS解决。

反向代理负载均衡

用户发来的请求都首先要经过反向代理服务器，服务器根据用户的请求要么直接将结果返回给用户，要么将请求交给后端服务器处理，再返回给用户。

优点：

• 隐藏后端服务器。与HTTP重定向相比，反向代理能够隐藏后端服务器，所有浏览器都不会与后端服务器直接交互，从而能够确保调度者的控制权，提升集群的整体性能。
• 故障转移。与DNS负载均衡相比，反向代理能够更快速地移除故障结点。当监控程序发现某一后端服务器出现故障时，能够及时通知反向代理服务器，并立即将其删除。
• 合理分配任务 。HTTP重定向和DNS负载均衡都无法实现真正意义上的负载均衡，也就是调度服务器无法根据后端服务器的实际负载情况分配任务。但反向代理服务器支持手动设定每台后端服务器的权重。我们可以根据服务器的配置设置不同的权重，权重的不同会导致被调度者选中的概率的不同。
• 像安全防护、故障转移等都是反向代理才有的好处。

缺点：

• 调度者压力过大 。由于所有的请求都先由反向代理服务器处理，那么当请求量超过调度服务器的最大负载时，调度服务器的吞吐率降低会直接降低集群的整体性能。
• 制约扩展。当后端服务器也无法满足巨大的吞吐量时，就需要增加后端服务器的数量，可没办法无限量地增加，因为会受到调度服务器的最大吞吐量的制约。

负载均衡的作用

1.解决并发压力，提高应用处理性能（增加吞吐量，加强网络处理能力）；

2.提供故障转移，实现高可用；

3.通过添加或减少服务器数量，提供网站伸缩性（扩展性）；

4.安全防护；（负载均衡设备上做一些过滤，黑白名单等处理）

常见的负载均衡策略

1. 轮询

2. 加权轮询

3. 最少连接次数

4. 最快响应

5. 源地址Hash法

第七模块--算法题

LRU原理及其实现

JAVA实现LRU

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

实现

最常见的实现是使用一个链表保存缓存数据，详细算法实现如下： 
 
1. 新数据插入到链表头部； 
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部； 
3. 当链表满的时候，将链表尾部的数据丢弃。 
分析 
【命中率】 
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。 
【复杂度】 
实现简单。 
【代价】 
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

证明一个数是2的N次方

(value & (value -1)) == 0;

Top K 问题

找出一个大数组里面前K个最大数，如1亿个数字中找出最大或最小的前100个数字（考虑判重和内存空间限制）？

如果不判重，可以将前100个数字做成最大堆或最小堆的数据结构（找最大的Top100用最小堆， 找最小的Top100用最大堆）， 然后依次遍历所有数字， 符合条件时替换根节点后并重新构建堆。堆的缺点是允许有重复数字！！！

如果要判重，则创建一个100个空间的空数组， 遍历1亿个数字依次插入值（按照升序）， 使用二分查找算法判断新值在数组中的位置并插入， 该数组最多容纳100个值。 当有101个值时先判重， 如果重复继续向后遍历， 如果值大于数组最小值则插入到指定位置，数组第一个元素移出数组， 因为数组是连续的，所有可以用内存拷贝方式赋值，只有新插入的值要单独赋值到对应的下标(原理类似于android.util.SparseArray)。   因内存拷贝可认为不占用时间， 该思路的总会时间复杂度是O(1亿*log100）， log100是二分查找的复杂度。

关于大数据处理的相关问题这个博客讲的非常好

热词统计问题

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

如果只有一台设备：

第一步：Query统计 (统计出每个Query出现的次数)         Query统计有以下两个个方法

1、直接排序法

首先我们最先想到的的算法就是排序了，首先对这个日志里面的所有Query都进行排序，然后再遍历排好序的Query，统计每个Query出现的次数了。

但是题目中有明确要求，那就是内存不能超过1G，一千万条记录，每条记录是255Byte，很显然要占据2.375G内存，这个条件就不满足要求了。

让我们回忆一下数据结构课程上的内容，当数据量比较大而且内存无法装下的时候，我们可以采用外排序的方法来进行排序，这里我们可以采用归并排序，因为归并排序有一个比较好的时间复杂度O(NlgN)。排完序之后我们再对已经有序的Query文件进行遍历，统计每个Query出现的次数，再次写入文件中。综合分析一下，排序的时间复杂度是O(NlgN)，而遍历的时间复杂度是O(N)，因此该算法的总体时间复杂度就是O(N+NlgN)=O（NlgN）。

2、Hash Table法  (这种方法统计字符串出现的次数非常好)  在第1个方法中，我们采用了排序的办法来统计每个Query出现的次数，时间复杂度是NlgN，那么能不能有更好的方法来存储，而时间复杂度更低呢？

题目中说明了，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query 255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择，因为Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。

那么，我们的算法就有了：

维护一个Key为Query字串，Value为该Query出现次数的HashTable，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。

本方法相比算法1：在时间复杂度上提高了一个数量级，为O（N），但不仅仅是时间复杂度上的优化，该方法只需要IO数据文件一次，而算法1的IO次数较多的，因此该算法2比算法1在工程上有更好的可操作性。

第二步：找出Top 10 (找出出现次数最多的10个)      

算法一：普通排序 （我们只用找出top10，所以全部排序有冗余）      我想对于排序算法大家都已经不陌生了，这里不在赘述，我们要注意的是排序算法的时间复杂度是NlgN，在本题目中，三百万条记录，用1G内存是可以存下的。

算法二：部分排序  题目要求是求出Top 10，因此我们没有必要对所有的Query都进行排序，我们只需要维护一个10个大小的数组，初始化放入10个Query，按照每个Query的统计次数由大到小排序，然后遍历这300万条记录，每读一条记录就和数组最后一个Query对比，如果小于这个Query，那么继续遍历，否则，将数组中最后一条数据淘汰(还是要放在合适的位置，保持有序)，加入当前的Query。最后当所有的数据都遍历完毕之后，那么这个数组中的10个Query便是我们要找的Top10了。

不难分析出，这样，算法的最坏时间复杂度是N*K， 其中K是指top多少。

算法三：堆在算法二中，我们已经将时间复杂度由NlogN优化到N*K，不得不说这是一个比较大的改进了，可是有没有更好的办法呢？

分析一下，在算法二中，每次比较完成之后，需要的操作复杂度都是K，因为要把元素插入到一个线性表之中，而且采用的是顺序比较。这里我们注意一下，该数组是有序的，一次我们每次查找的时候可以采用二分的方法查找，这样操作的复杂度就降到了logK，可是，随之而来的问题就是数据移动，因为移动数据次数增多了。不过，这个算法还是比算法二有了改进。

基于以上的分析，我们想想，有没有一种既能快速查找，又能快速移动元素的数据结构呢？

       回答是肯定的，那就是堆。借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此到这里，我们的算法可以改进为这样，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。思想与上述算法二一致，只是在算法三，我们采用了最小堆这种数据结构代替数组，把查找目标元素的时间复杂度有O（K）降到了O（logK）。那么这样，采用堆数据结构，算法三，最终的时间复杂度就降到了N*logK，和算法二相比，又有了比较大的改进。

10亿个数中找出最大的10000个数（top K问题）

先拿10000个数建堆，然后一次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O（mlogm），算法的时间复杂度为O（nmlogm）（n为10亿，m为10000）。

针对top K类问题，通常比较好的方案是分治+Trie树/hash+小顶堆（就是上面提到的最小堆），即先将数据集按照Hash方法分解成多个小数据集，然后使用Trie树活着Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
---------------------

总结：

至此，算法就完全结束了，经过上述第一步、先用Hash表统计每个Query出现的次数，O（N）；然后第二步、采用堆数据结构找出Top 10，N*O（logK）。所以，我们最终的时间复杂度是：O（N） + N'*O（logK）。（N为1000万，N’为300万）。

优化的方法：可以把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。

如果有多台设备：

可参考Map-Reduce 的思想

核心是“分治”、“归并”和哈希，  第一次遍历将关键词散列到不同的文件中（散列算法是性能关键，哈希函数的性能直接影响散列的结果， 尽量避免“数据倾斜”）， 同一个关键词一定会散列到同一个文件， 理想情况是所有关键词均匀散列到不同的文件中（即分治思想，将大文件分解为小问题）。

读取每个文件并记录各关键词的次数， 做个排序， 从每个文件中排序出前100的关键词；

取第一个文件的记录结果， 和第二个文件做“合并”， 即200个结果中排序出前100个关键词， 然后依次合并第三个、第四个。。。。第N个文件(将子结果合并为总结果)

第八模块--JVM

JVM执行模式

主流的JVM是Oracle的HotSpot JVM， 采用解释和编译混合执行的模式，JIT技术采用分层编译，极大的提高了Java的执行速度。

三种执行模式：

1. 解释执行

2.JIT编译执行

3.JIT编译与解释混合执行

混合执行的优势在于解释器在启动时先解释执行，省去编译时间。随着时间推进，JVM通过热点代码统计分析，识别高频的代码，基于强大的JIT动态编译技术，将热点代码转换成机器码，直接交给CPU执行。JIT的作用是将Java字节码动态地编译成可以直接发送给处理器指令执行地机器码。

内存布局：

程序计数器(Program Counter Register)：线程私有的，记录当前线程的行号指示器，为线程的切换提供保障

虚拟机栈(JVM Stacks)//本地方法栈： 线程私有的，主要存放局部变量表，操作数栈，动态链接和方法出口等；

堆区(Heap): 堆是所有线程共享的，主要用来存储对象。其中，堆可分为：年轻代和老年代两块区域。使用NewRatio参数来设定比例。对于年轻代，一个Eden区和两个Suvivor区，使用参数SuvivorRatio来设定大小。

元数据区 (Metaspace): JDK8才有，保存JDK8之前永久代中的类的元信息

本地方法栈(Native Method Stacks)

永久代和方法区的区别

HotSpot使用永久代来实现方法区。永久代是HotSpot对方法区的实现，方法区是Java虚拟机规范中的定义，是一种规范。而永久代是一种实现，一个是标准一个是实现。在Java虚拟机(JVM)内部，class文件中包括类的版本、字段、方法、接口等描述信息，还有运行时常量池，用于存放编译器生成的各种字面量和符号引用。在过去（自定义类加载器还不是很常见的时候），类大多是”static”的，很少被卸载或收集，因此被称为“永久的(Permanent)”

对于Java8， HotSpots取消了永久代，那么是不是也就没有方法区了呢？当然不是，方法区是一个规范，规范没变，它就一直在。那么取代永久代的就是元空间。

永久代和元空间的区别

1. 存储位置不同，永久代物理上是堆的一部分，和新生代，老年代地址是连续的，而元空间属于本地内存；

2. 存储内容不同，元空间存储类的元信息，静态变量和常量池等并入堆中。相当于永久代的数据被分到了堆和元空间中。

https://blog.csdn.net/u011635492/article/details/81046174

为什么使用 元空间+堆 取代 永久代

1. 字符串存在永久代中，容易出现性能问题和内存溢出。

2. 类及方法的信息等比较难确定其大小，因此对于永久代的大小指定比较困难，太小容易出现永久代溢出，太大则容易导致老年代溢出。永久代的垃圾收集是和老年代(old generation)捆绑在一起的，因此无论谁满了，都会触发永久代和老年代的垃圾收集。

3. 永久代会为 GC 带来不必要的复杂度，并且回收效率偏低

https://blog.csdn.net/zhushuai1221/article/details/52122880

什么时候会发生堆溢出什么时候会发生栈溢出？

1. 栈溢出

栈是线程私有的，他的生命周期与线程相同，每个方法在执行的时候都会创建一个栈帧，用来存储局部变量表，操作数栈，动态链接，方法出口灯信息。局部变量表又包含基本数据类型，对象引用类型（局部变量表编译器完成，运行期间不会变化）

栈溢出就是方法执行是创建的栈帧超过了栈的深度。那么最有可能的就是方法递归调用产生栈溢出。

2. 堆溢出

heap space表示堆空间，堆中主要存储的是对象。如果不断的new对象则会导致堆中的空间溢出。

3. 永久代溢出(OutOfMemoryError: PermGen space)

永久代物理上是堆的一部分，和新生代，老年代地址是连续的，永久代溢出的表现就是堆溢出。(永久代的GC是和老年代(old generation)捆绑在一起的，因此无论谁满了，都会触发永久代和老年代的垃圾收集。)

由于JDK7、8移除永久带，所以只有JDK1.6及以下会出现永久带溢出的现象

堆区(Heap)：

堆区储存着几乎所有的实例对象，堆由垃圾收集器自动回收，堆区由各子线程共享使用，可以通过-Xms设置最小堆容量， 和-Xmx来设置最大堆容量。

堆分成两大块:新生代和老年代。

对象产生之初在新生代，步入暮年时进入老年代，但是老年代也接纳在新生代无法容纳的超大对象。

新生代=1个Eden区+2个Survior区。绝大部分对象在Eden区生成，当Eden区装填满的时候，会触发Young Garbage Collection，即YGC。垃圾回收的时候，在Eden区实现清除策略，没有被引用的对象则直接回收。依然存活的对象会被移送到Suvivor区。Suvivor区分为S0和S1两块内存空间，送到哪块空间呢？每次YGC的时候，它们将存活的对象复制到未使用的那块空间，然后将当前正在使用的空间完全清除，交换两块空间的使用状态。如果YGC要移送的对象大于Survivor区容量的上限，则直接移交给老年代。如果老年代也无法放下，则会触发Full Garbage Collection, FGC。 如果依然无法放下，则抛出OOM。

假如一些没有进取心的对象以为可以一直在新生代的Survivor区交换来交换去，那就错了。每个对象都有一个计数器，每次YGC都会加1。 -XXiMax Tenuring Threshold参数能配置计数器的值到达某个阈值的时候，对象从新生代晋升至老年代。如果该参数配置为1，那么从新生代的Eden区直接移至老年代。默认值是15，可以在Survivor区交换14次之后，晋升至老年代。

JVM Stack(虚拟机栈)：

栈（Stack）是一个先进后出的数据结构。
JVM中的虚拟机栈是描述Java方法执行的内在区域，它是线程私有的。栈中的元素用于支持虚拟机进行方法调用，每个方法从开始调用到执行完成的过程，就是栈帧从入栈到出栈的过程。在活动线程中，只有位于栈顶的帧才是有效的，称为当前栈帧。正在执行的方法称为当前方法，栈帧是方法运行的基本结构。
在执行引擎运行时，所有指令都只能针对当前栈施进行操作。而*Error表示请求的栈溢出，导致内存耗尽，通常出现在递归方法中。

虚拟机栈通过压栈和出栈的方式，对每个方法对应的活动栈帧进行运算处理，方法正常执行结束，肯定会跳转到另一个栈帧上。在执行的过程中，如果出现异常，会进行常回溯，返回地址通过异常处理表确定。栈帧在整个JVM体系中的地位颇高，包括局部变量表、操作栈、动态连接、方法返回地址等。
（1）局部变量表
　　局部变量表是存放方法参数和局部变量的区域。

（2）操作栈
　　操作栈是一个初始状态为空的桶式结构栈。在方法执行过程中，会有各种指令往栈中写入和提取信息。

(3) 动态连接

　　每个栈帧中包含一个在常量池中对当前方法的引用，目的是支持方法调用过程的动态连接。

(4) 方法返回地址

　　方法执行遇到退出情况，将返回至方法当前被调用的位置

Native Method Stacks（本地方法栈）

本地方法栈在JVM内存布局中，也是线程对象私有的，但虚拟机“主内”，本地方法栈“主外”。这个“内外”是针对JVM来说的，线程调用本地方法时，会进入一个不再受JVM约束的世界。本地方法栈可以通过JNI（Java Native Interface）来访问虚拟机运行时的数据区，甚至可以调用寄存器，具有和JVM相同的能力和权限。最著名的本地方法应该是System.currentTimeMillis(), JNI使Java深度使用操作系统的特性功能，复用非Java代码。

Program Counter Register（程序计数寄存器）

在程序计数寄存器（Program Counter Register，PC）中，Register的命名源于CPU的寄存器，CPU只有把数据装载到寄存器才能够运行。寄存器存储指令相关的现场信息，由于CPU时间片轮限制，众多线程在并发执行过程中，任何一个确定的时刻，一个处理器或者多核处理器中的一个内核，只会执行某个线程中的一条指令。这样必然导致经常中断或恢复，如何保证分毫无差呢？每个线程在创建后，都会产生自己的程序计数器和栈帧，程序计数器用来存放执行指令的偏移量和行号指示器等，线程执行或恢复都要依赖程序计数器。程序计数器在各个线程之间互不影响，此区域也不会发生内存溢出异常。
最后，从线程共享的角度来看，堆和元空间是所有线程共享的，而虚拟机栈、本地方法栈、程序计数器都是线程内部私有的。从这个角度看一下Java的内存结构:

GC（垃圾回收）

• GC如何判断对象是否可以回收

为了判断对象是否存活，JVM 引入了GC Roots。如果一个对象与GC Roots之间没有直接或间接的引用关系，比如某个失去任何引用的对象，或者两个互相环岛状循环引用的对象等，判决这些对象“死缓”，是可以被回收的。可以作为GC Roots对象可以是：类静态属性中引用的对象、常量引用的对象、虚拟机栈中引用的对象、本地方法栈中引用的对象等。

• 垃圾回收算法

有了判断对象是否存活的标准后，再了解一下垃圾回收的相关算法。

1. “标记--清除算法”，该算法会从每个GC Roots出发，依次标记有引用关系的对象，最后将没有被标记的对象清除。但是这种算法会带来大量的空间碎片，导致需要分配一个较大连续空间时容易触发FGC。典型的例子是CMS回收器。
2. “标记--整理算法”，该算法类似计算机的磁盘整理，首先会从GC Roots出发标记存活的对象，然后将存活对象整理到内存空间的一端，形成连续的已使用空间，最后把已使用空间之外的部分全部清理掉，这样就不会产生空间碎片的问题。典型的例子是老年代的FullGC, G1回收器。
3. 复制算法，为了能够并行地标记和整理将空间分为两块，每次只激活其中一块，垃圾回收时只需把存活的对象复制到另一块未激活空间上，将未激活空间标记为已激活，将已激活空间标记为未激活，然后清除原空间中的原对象。堆内存空间分为较大的Eden和两块较小的Survivor，每次只使用Eden和Survivor区的一块。这种情形下的“Mark-Copy”减少了内存空间的浪费。典型的例子是年轻代的minGC。

垃圾回收器（Garbage Collector）

是实现垃圾回收算法并应用在JVM环境中的内存管理模块。当前实现的垃圾回收器有数十种，常见的有Serial、CMS、G1三种。

1. Serial回收器是一个主要应用于YGC的垃圾回收器，采用串行单线程的方式完成GC任务，其中“Stop The World”简称STW，即垃圾回收的某个阶段会暂停整个应用程序的执行。FGC的时间相对较长，频繁FGC会严重影响应用程序的性能
2. CMS回收器（Concurrent Mark Sweep Collector）是回收停顿时间比较短、目前比较常用的垃圾回收器。它通过初始标记（Initial Mark）、并发标记（ConcurrentMark）、重新标记（Remark）、并发清除（Concurrent Sweep）四个步骤完成垃圾回收工作。第1、3步的初始标记和重新标记阶段依然会引发STW，而第2、4步的并发标记和并发清除两个阶段可以和应用程序并发执行，也是比较耗时的操作，但并不影响应用程序的正常执行。由于CMS采用的是“标记一清除算法”，因此产生大量的空间碎片。为了解决这个问题，CMS可以通过配置-XX：+UseCMSCompactAtFullCo lection参数，强制JVM在FGC完成后对老年代进行压缩，执行一次空间碎片整理，但是空间碎片整理阶段也会引发STW。为了减少STW次数，CMS还可以通过配置一XX：+CMSFullGCsBeforeCompaction=n参数，在执行了n次FGC后，JVM再在老年代执行空间碎片整理。
3. G1回收器 是HotSpot在JDK7中推出的新一代G1垃圾回收器，在JDK11中，G1是默认的回收器。G1采用的是”Mark-Copy“，有较好的空间整理能力，不会产生大量空间碎片。G1的优势是具有可预测的停顿时间，能够尽快在指定时间完成垃圾回收任务。
4. 另外还有在JDK11中引入的实验性的ZGC，是一个可伸缩的低延迟垃圾收集器。

怎样分析查找OOM的原因

1. 使用jmap将当前的内存 Dump成一个 hprof格式的文件，MAT 读取这个文件后会给出方便阅读的信息，配合它的查找，对比功能，就可以定位内存泄漏的原因。
2. 用的最多的功能是 Histogram，它按类名将所有的实例对象列出来，可以点击表头进行排序,在表的第一行可以输入正则表达式来匹配结果

举例一个典型的分析内存泄漏的过程：

1.  使用 Heap查看当前堆大小为 23.00M

2.  添加一个页后堆大小变为 23.40M

3.  将添加的一个页删除，堆大小为 23.40M

4.  多次操作，结果仍相似，说明添加/删除页存在内存泄漏 (也应注意排除其它因素的影响)

5.  Dump 出操作前后的 hprof 文件 (1.hprof,2.hprof)，用 mat打开,并得到 histgram结果

6.  使用 HomePage字段过滤 histgram结果，并列出该类的对象实例列表，看到两个表中的对象集合大小不同，操作后比操作前多出一个 HomePage，说明确实存在泄漏

7.  将两个列表进行对比，找出多出的一个对象，用查找 GC Root的方法找出是谁串起了这条引用线路，定位结束

PS :

·        很多时候堆增大是 Bitmap引起的，Bitmap在 Histogram中的类型是 byte [],对比两个 Histogram中的 byte[] 对象就可以找出哪些 Bitmap有差异

·        多使用排序功能，对找出差异很有用

2 内存泄漏的原因分析

总结出来只有一条： 存在无效的引用! 
良好的模块设计以及合理使用设计模式有助于解决此问题。

参考：

https://blog.csdn.net/liao0801_123/article/details/82900874

https://www.cnblogs.com/lovecindywang/p/10800593.html

http://blog.sina.com.cn/s/blog_73b4b91f0102wze4.html

内存溢出的原因及解决方法

1. 内存溢出原因：

1.内存中加载的数据量过于庞大，如一次从数据库取出过多数据； 
2.集合类中有对对象的引用，使用完后未清空，使得JVM不能回收； 
3.代码中存在死循环或循环产生过多重复的对象实体； 
4.使用的第三方软件中的BUG； 
5.启动参数内存值设定的过小

2. 内存溢出的原因及解决方法：

1. 修改JVM启动参数，直接增加内存。(-Xms，-Xmx参数一定不要忘记加。)
2. 检查错误日志，查看“OutOfMemory”错误前是否有其 它异常或错误。
3. 对代码进行走查和分析，找出可能发生内存溢出的位置。
4. 使用内存查看工具动态查看内存使用情况

对代码分析找出可能发生内存溢出的位置， 可能出现的几种情况：

1、检查对数据库查询中，是否有一次获得全部数据的查询。一般来说，如果一次取十万条记录到内存，就可能引起内存溢出。这个问题比较隐蔽，在上线前，数据   库中数据较少，不容易出问题，上线后，数据库中数据多了，一次查询就有可能引起内存溢出。因此对于数据库查询尽量采用分页的方式查询。

2、检查代码中是否有死循环或递归调用。

3、检查是否有大循环重复产生新对象实体。

4、检查List、MAP等集合对象是否有使用完后，未清除的问题。List、MAP等集合对象会始终存有对对象的引用，使得这些对象不能被GC回收。

第九模块--个人

项目总结

关于三维模型搜索引擎项目相关度排序算法是怎么做的:

以文字搜模型:

基于Lucene文本搜索引擎，查找最匹配的；

以图片搜模型:

计算图片特征，对图片特征计算HashCode, 搜索的时候匹配HashCode;

以模型搜模型：

计算模型的特征得到n维特征矩阵， 对特征矩阵计算HashCode, 搜索的时候匹配HashCode;

去重和检测url有效性是怎么做的：

对外网数据去重:

一开始直接使用条件逐个字段比较判断是否重复；

后来对关键字段连接建立联合哈希值保存，用这个哈希值去重；

后来想到其实外网的url是唯一的，直接对url建立哈希值来去重；后来设想直接用url哈希之后作为主键保存，建立聚集索引；

有效性检测比较简单:

使用java.net 下的类来实现，主要用到了 URL和HttpURLConnection :

刚开始使用openStream()方法，这样使用倒是可以，但是速度慢；

最后使用了getResponseCode（）方法，可以得到请求的响应状态，该方法返回一个 int 分别是 200 and 404 如无法从响应中识别任何代码则返回 -1, 如果对该url发起的5次请求都没有应答则认为链接失效;

你的项目用了哪些技术？

Lucene, Solr

MySQL,

Redis,

Java多线程

遇到过什么问题？你是怎么解决的？

去重的过程经历了多次迭代:

刚开始直接对记录逐个字段比较判断是否重复 ——>然后对关键字段建立HashCode作为标识，对比该Hash字段——>再是对外网URL建立HashCode对比;

有什么可以改进的地方？

可以对URL使用布隆过滤器做去重；（位图+多个哈希函数）

使用缓存数据库来提高并发访问；(缓存穿透（查询一个数据库一定不存在的数据），缓存击穿（一个key非常热点，在不停的扛着大并发，大并发集中对这一个点进行访问，当这个key在失效的瞬间，持续的大并发就穿破缓存），缓存雪崩（缓存集中过期失效）)

使用Elesticsearch来替代Solr（Elasticsearch是分布式的, 不需要其他组件，分发是实时的;solr需要结合依赖其他分布式组件来实现分布式）;

第九模块--待整理问题

阿里：

一面

全局唯一有序ID：

Snowflake, timestamp, 机器id等

冯诺伊曼体系：

shell命令的执行体系：

信息熵：

程序运行中的栈式结构

TCP/IP, TCP传输层加端口号，IP网络层加ip地址；路由器主要工作在IP网络层

各层常见的协议有哪些

同步与阻塞

并行与并发

java线程的本质、内核线程与用户进程，线程调度，并行级别

内核态与用户态，中断

CPU与内存与硬盘

缓存行与伪共享

内存分配管理，段业式 jemalloc

二面：

java程序的运行原理：

缓存行与伪共享

一个线程忙碌，多个线程闲置怎么解决

Java多线程引发的性能问题以及调优策略

多重继承会带来哪些问题

单点登陆

正向代理与反向代理

反爬机制，爬虫模拟浏览器行为

cglib方法拦截

动态代理

依赖注入

servlet的本质

TCP长连接 心跳包 websocket

Netty 百万级长连接优化

DSL解析到AST

JVM 相关（gc的源码）

代码规范，包命名规范

现在流行的线程调度算法是什么(时间片轮转法)

项目用到了数据库，谈谈对事物的理解

假设你要做一个银行app，有可能碰到多个人同时向一个账户打钱的情况，有可能碰到什么问题，如何解决（还有可能出现重复提交的问题，保证服务的幂等性）

排序算法

给定一个文件名，如何在d盘找出这个文件

java对象头

知道哪些排序算法

快排怎么实现

堆排怎么实现

找出两个有序数组中的相同元素

常用集合框架

介绍下hashtable

快排如何实现

一个集合里有1000万个随机元素，快速求和(多线程)

排他锁的改进策略

map怎么实现

红黑树有什么特性

快排的思路讲一下

给大量的qq号，怎么排序(数据库外排)，问算法时间复杂度

代码:

数组里搜索第K大的数，非递归二分查找，链表相加