首页 > Java开发面试题整理含答案(计网、Java、数据库、框架)
头像
Sun浅雨
编辑于 2020-08-15 15:03
+ 关注

Java开发面试题整理含答案(计网、Java、数据库、框架)

我最近的面试学习资料包括这个文档已经上传到GitHub

https://github.com/pure-xiaojie/JavaInterview
有需要自行下载,顺便给个star鼓励一下

Java开发面试题含答案

一、网络篇

1、OSI七层模型与TCP/IP 五层模型

​ OSI七层:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

​ TCP/IP五层:物理层、数据链路层、网络层、传输层、应用层

2、常见应用层协议和运输层、网络层协议,以及硬件如路由器之类在哪一层

​ 应用层:HTTP、SMTP、DNS、FTP

​ 传输层:TCP 、UDP

​ 网络层:ICMP 、IP、路由器、防火墙

​ 数据链路层:网卡、网桥、交换机

​ 物理层:中继器、集线器

3、TCP与UDP区别和应用场景,基于TCP的协议有哪些,基于UDP的有哪些

类型 特点 性能 应用过场景 首部字节
TCP 面向连接、可靠、字节流 传输效率慢、所需资源多 文件、邮件传输 20-60
UDP 无连接、不可靠、数据报文段 传输效率快、所需资源少 语音、视频、直播 8个字节

基于TCP的协议:HTTP、FTP、SMTP

基于UDP的协议:RIP、DNS、SNMP

4、TCP可靠传输的保证,拥塞控制目的和过程

TCP通过:应用数据分割、对数据包进行编号、校验和、流量控制、拥塞控制、ARP协议、超时重传等措施保证数据的可靠传输;

拥塞控制目的:为了防止过多的数据注入到网络中,避免网络中的路由器、链路过载

拥塞控制过程:TCP发送发将维护一个拥塞窗口的状态变量,该变量随着网络拥塞程度动态变化,通过慢开始、拥塞避免等算法减少网络拥塞的发生。

5、TCP粘包现象原因和解决方法

TCP粘包是指:发送方发送的若干包数据到接收方接收时粘成一包

发送方原因:

​ TCP默认使用Nagle算法(主要作用:减少网络中报文段的数量),而Nagle算法主要做两件事:

​ 只有上一个分组得到确认,才会发送下一个分组
​ 收集多个小分组,在一个确认到来时一起发送
​ Nagle算法造成了发送方可能会出现粘包问题

接收方原因:

​ TCP接收到数据包时,并不会马上交到应用层进行处理,或者说应用层并不会立即处理。实际上, TCP将接收到的数据包保存在接收缓存里,然后应用程序主动从缓存读取收到的分组。这样一来,如果 TCP 接收数据包到缓存的速度大于应用程序从缓存中读取数据包的速度,多个包就会被缓存,应用程 序就有可能读取到多个首尾相接粘到一起的包。

解决粘包问题:

​ 最本质原因在与接收对等方无法分辨消息与消息之间的边界在哪,通过使用某种方案给出边界,例如:

  • 发送定长包。如果每个消息的大小都是一样的,那么在接收对等方只要累计接收数据,直到数据等于一个定长的数值就将它作为一个消息。
  • 包尾加上\r\n标记。FTP协议正是这么做的。但问题在于如果数据正文中也含有\r\n,则会误判为消息的边界。
  • 包头加上包体长度。包头是定长的4个字节,说明了包体的长度。接收对等方先接收包体长度,依据包体长度来接收包体。

6、TCP三次握手过程以及每次握手后的状态改变,为什么三次? 为什么两次不行?

三次握手过程:

​ 客户端——发送带有SYN标志的数据包——服务端 一次握手 Client进入syn_sent状态

​ 服务端——发送带有SYN/ACK标志的数据包——客户端 二次握手 服务端进入syn_rcvd

​ 客户端——发送带有ACK标志的数据包——服务端 三次握手 连接就进入Established状态

为什么三次:

​ 主要是为了建立可靠的通信信道,保证客户端与服务端同时具备发送、接收数据的能力

为什么两次不行?

​ 1、防止已失效的请求报文又传送到了服务端,建立了多余的链接,浪费资源

​ 2、 两次握手只能保证单向连接是畅通的。(为了实现可靠数据传输, TCP 协议的通信双方, 都必须维 护一个序列号, 以标识发送出去的数据包中, 哪些是已经被对方收到的。 三次握手的过程即是通信双方 相互告知序列号起始值, 并确认对方已经收到了序列号起始值的必经步骤;如果只是两次握手, 至多只 有连接发起方的起始序列号能被确认, 另一方选择的序列号则得不到确认)

7、TCP四次挥手过程以及状态改变,为什么四次?CLOSE-WAIT和TIME-WAIT存在的意义?如何查看TIME-WAIT状态的链接数量?为什么会TIME-WAIT过多?解决方法是怎样的?

四次挥手过程:

​ 客户端——发送带有FIN标志的数据包——服务端,关闭与服务端的连接 ,客户端进入FIN-WAIT-1状态

​ 服务端收到这个 FIN,它发回⼀ 个 ACK,确认序号为收到的序号加1,服务端就进入了CLOSE-WAIT状态

​ 服务端——发送⼀个FIN数据包——客户端,关闭与客户端的连接,客户端就进入FIN-WAIT-2状态

​ 客户端收到这个 FIN,发回 ACK 报⽂确认,并将确认序号设置为收到序号加1,TIME-WAIT状态

为什么四次:

​ 因为需要确保客户端与服务端的数据能够完成传输。

CLOSE-WAIT:

​ 这种状态的含义其实是表示在等待关闭

TIME-WAIT:

​ 为了解决网络的丢包和网络不稳定所带来的其他问题,确保连接方能在时间范围内,关闭自己的连接

如何查看TIME-WAIT状态的链接数量?

​ netstat -an |grep TIME_WAIT|wc -l 查看连接数等待time_wait状态连接数

为什么会TIME-WAIT过多?解决方法是怎样的?

可能原因: 高并发短连接的TCP服务器上,当服务器处理完请求后立刻按照主动正常关闭连接

解决:负载均衡服务器;Web服务器首先关闭来自负载均衡服务器的连接

8、TCP、UDP、IP、以太网报文格式以及重要字段,报文从一端到另一端传递的过程。

TCP报文格式:

源端口号和目的端口号

​ 用于寻找发端和收端应用进程。这两个值加上ip首部源端ip地址和目的端ip地址唯一确定一个tcp连接。

序号字段:

​ 序号用来标识从T C P发端向T C P收端发送的数据字节流,它表示在这个报文段中的的第一个数据字节。如果将字节流看作在两个应用程序间的单向流动,则 T C P用序号对每个字节进行计数。序号是32 bit的无符号数,序号到达 2^32-1后又从0开始。

  当建立一个新的连接时,SYN标志变1。序号字段包含由这个主机选择的该连接的初始序号ISN(Initial Sequence Number)。该主机要发送数据的第一个字节序号为这个ISN加1,因为SYN标志消耗了一个序号

确认序号

​ 既然每个传输的字节都被计数,确认序号包含发送确认的一端所期望收到的下一个序号。因此,确认序号应当是上次已成功收到数据字节序号加 1。只有ACK标志为 1时确认序号字段才有效。发送ACK无需任何代价,因为 32 bit的确认序号字段和A C K标志一样,总是T C P首部的一部分。因此,我们看到一旦一个连接建立起来,这个字段总是被设置, ACK标志也总是被设置为1。TCP为应用层提供全双工服务。这意味数据能在两个方向上独立地进行传输。因此,连接的每一端必须保持每个方向上的传输数据序号。

首都长度

​ 首部长度给出首部中 32 bit字的数目。需要这个值是因为任选字段的长度是可变的。这个字段占4 bit,因此T C P最多有6 0字节的首部。然而,没有任选字段,正常的长度是 2 0字节。

标志字段:在T C P首部中有 6个标志比特。它们中的多个可同时被设置为1.
  URG紧急指针(u rgent pointer)有效
  ACK确认序号有效。
  PSH接收方应该尽快将这个报文段交给应用层。
  RST重建连接。
  SYN同步序号用来发起一个连接。这个标志和下一个标志将在第 1 8章介绍。
  FIN发端完成发送任务。

窗口大小

​ T C P的流量控制由连接的每一端通过声明的窗口大小来提供。窗口大小为字节数,起始于确认序号字段指明的值,这个值是接收端期望接收的字节。窗口大小是一个 16 bit字段,因而窗口大小最大为 65535字节。

检验和:

​ 检验和覆盖了整个的 T C P报文段:T C P首部和T C P数据。这是一个强制性的字段,一定是由发端计算和存储,并由收端进行验证。

紧急指针

​ 只有当URG标志置1时紧急指针才有效。紧急指针是一个正的偏移量,和序号字段中的值相加表示紧急数据最后一个字节的序号。 T C P的紧急方式是发送端向另一端发送紧急数据的一种方式。

选项

​ 最常见的可选字段是最长报文大小,又称为 MSS (Maximum Segment Size)。每个连接方通常都在通信的第一个报文段(为建立连接而设置 S Y N标志的那个段)中指明这个选项。它指明本端所能接收的最大长度的报文段。

UDP报文格式:

端口号

​ 用来表示发送和接受进程。由于 I P层已经把I P数据报分配给T C P或U D P(根据I P首部中协议字段值),因此T C P端口号由T C P来查看,而 U D P端口号由UDP来查看。T C P端口号与UDP端口号是相互独立的。

长度

​ UDP长度字段指的是UDP首部和UDP数据的字节长度。该字段的最小值为 8字节(发送一份0字节的UDP数据报是 O K)。

检验和

​ UDP检验和是一个端到端的检验和。它由发送端计算,然后由接收端验证。其目的是为了发现UDP首部和数据在发送端到接收端之间发生的任何改动。

IP报文格式:普通的IP首部长为20个字节,除非含有可选项字段。

4位版本

​ 目前协议版本号是4,因此IP有时也称作IPV4.

4位首部长度

​ 首部长度指的是首部占32bit字的数目,包括任何选项。由于它是一个4比特字段,因此首部长度最长为60个字节。

服务类型(TOS)

​ 服务类型字段包括一个3bit的优先权字段(现在已经被忽略),4bit的TOS子字段和1bit未用位必须置0。4bit的TOS分别代表:最小时延,最大吞吐量,最高可靠性和最小费用。4bit中只能置其中1比特。如果所有4bit均为0,那么就意味着是一般服务。

总长度

​ 总长度字段是指整个IP数据报的长度,以字节为单位。利用首部长度和总长度字段,就可以知道IP数据报中数据内容的起始位置和长度。由于该字段长16bit,所以IP数据报最长可达65535字节。当数据报被分片时,该字段的值也随着变化。

标识字段

​ 标识字段唯一地标识主机发送的每一份数据报。通常每发送一份报文它的值就会加1。

生存时间

​ TTL(time-to-live)生存时间字段设置了数据报可以经过的最多路由器数。它指定了数据报的生存时间。TTL的初始值由源主机设置(通常为 3 2或6 4),一旦经过一个处理它的路由器,它的值就减去 1。当该字段的值为 0时,数据报就被丢弃,并发送 ICMP 报文通知源主机。

首部检验和

​ 首部检验和字段是根据 I P首部计算的检验和码。它不对首部后面的数据进行计算。 ICMP、IGMP、UDP和TCP在它们各自的首部中均含有同时覆盖首部和数据检验和码。

以太网报文格式:

目的地址和源地址:

​ 是指网卡的硬件地址(也叫MAC 地址),长度是48 位,是在网卡出厂时固化的。

数据:

​ 以太网帧中的数据长度规定最小46 字节,最大1500 字节,ARP 和RARP 数据包的长度不够46 字节,要在后面补填充位。最大值1500 称为以太网的最大传输单元(MTU),不同的网络类型有不同的MTU,如果一个数据包从以太网路由到拨号链路上,数据包度大于拨号链路的MTU了,则需要对数据包进行分片fragmentation)。ifconfig 命令的输出中也有“MTU:1500”。注意,MTU 个概念指数据帧中有效载荷的最大长度,不包括帧首部的长度。

9、浏览器输入URL并回车的过程以及相关协议,DNS查询过程。

过程:DNS解析、TCP连接、发送HTTP请求、服务器处理请求并返回HTTP报文、浏览器渲染、结束

过程 使用的协议
1、浏览器查找域名DNS的IP地址
DNS查找过程(浏览器缓存、路由器缓存、DNS缓存)
DNS:获取域名对应的ip
2、根据ip建立TCP连接 TCP:与服务器建立连接
3、浏览器向服务器发送HTTP请求 HTTP:发送请求
4、服务器响应HTTP响应 HTTP
5、浏览器进行渲染

10、HTTP1.0、1.1、2.0之间的区别

HTTP1.0:默认使用Connection:cloose,浏览器每次请求都需要与服务器建立一个TCP连接,服务器处理完成后立即断开TCP连接(无连接),服务器不跟踪每个客户端也不记录过去的请求(无状态)。

HTTP1.1:默认使用Connection:keep-alive(长连接),避免了连接建立和释放的开销;通过Content-Length字段来判断当前请求的数据是否已经全部接受。不允许同时存在两个并行的响应。

HTTP2.0:引入二进制数据帧和流的概念,其中帧对数据进行顺序标识;因为有了序列,服务器可以并行的传输数据。

http1.0和http1.1的主要区别如下:
​ 1、缓存处理:1.1添加更多的缓存控制策略(如:Entity tag,If-Match)
​ 2、网络连接的优化:1.1支持断点续传
​ 3、错误状态码的增多:1.1新增了24个错误状态响应码,丰富的错误码更加明确各个状态
​ 4、Host头处理:支持Host头域,不在以IP为请求方标志
​ 5、长连接:减少了建立和关闭连接的消耗和延迟。

http1.1和http2.0的主要区别:
​ 1、新的传输格式:2.0使用二进制格式,1.0依然使用基于文本格式
​ 2、多路复用:连接共享,不同的request可以使用同一个连接传输(最后根据每个request上的id号组合成 正常的请求)
​ 3、header压缩:由于1.X中header带有大量的信息,并且得重复传输,2.0使用encoder来减少需要传输的 hearder大小
​ 4、服务端推送:同google的SPDUY(1.0的一种升级)一样

11、HTTP与HTTPS之间的区别,HTTPS链接建立的过程,了解对称加密算法和非对称加密算法不?

HTTP与HTTPS之间的区别:

HTTP HTTPS
默认端口80 HTTPS默认使用端口443
明文传输、数据未加密、安全性差 传输过程ssl加密、安全性较好
响应速度快、消耗资源少 响应速度较慢、消耗资源多、需要用到CA证书

HTTPS链接建立的过程:

​ 1.首先客户端先给服务器发送一个请求

​ 2.服务器发送一个SSL证书给客户端,内容包括:证书的发布机构、有效期、所有者、签名以及公钥

​ 3.客户端对发来的公钥进行真伪校验,校验为真则使用公钥对对称加密算法以及对称密钥进行加密

​ 4.服务器端使用私钥进行解密并使用对称密钥加密确认信息发送给客户端

​ 5.随后客户端和服务端就使用对称密钥进行信息传输

对称加密算法:

​ 双方持有相同的密钥,且加密速度快,典型对称加密算法:DES、AES

非对称加密算法:

​ 密钥成对出现(私钥、公钥),私钥只有自己知道,不在网络中传输;而公钥可以公开。相比对称加密速度较慢,典型的非对称加密算法有:RSA、DSA

12、HTTP请求有哪些。get和Post区别。

HTTP请求:

方法 描述
GET 向特定资源发送请求,查询数据,并返回实体
POST 向指定资源提交数据进行处理请求,可能会导致新的资源建立、已有资源修改
PUT 向服务器上传新的内容
HEAD 类似GET请求,返回的响应中没有具体的内容,用于获取报头
DELETE 请求服务器删除指定标识的资源
OPTIONS 可以用来向服务器发送请求来测试服务器的功能性
TRACE 回显服务器收到的请求,用于测试或诊断
CONNECT HTTP/1.1协议中预留给能够将连接改为管道方式的代理服务器

get和Post区别:

GET POST
可见性 数据在URL中对所有人可见 数据不会显示在URL中
安全性 与post相比,get的安全性较差,因为所
发送的数据是URL的一部分
安全,因为参数不会被保存在浏览器
历史或web服务器日志中
数据长度 受限制,最长2kb 无限制
编码类型 application/x-www-form-urlencoded multipart/form-data
缓存 能被缓存 不能被缓存

13、HTTP常见响应状态码,从1xx到5xx

​ 100:Continue --- 继续。客户端应继续其请求。

​ 200:OK --- 请求成功。一般用于GET与POST请求。

​ 301:Moved Permanently --- 永久重定向。

​ 302:Found --- 暂时重定向。

​ 400:Bad Request --- 客户端请求的语法错误,服务器无法理解。

​ 403:Forbideen --- 服务器理解请求客户端的请求,但是拒绝执行此请求。

​ 404:Not Found --- 服务器无法根据客户端的请求找到资源(网页)。

​ 500:Internal Server Error --- 服务器内部错误,无法完成请求。

​ 502:Bad Gateway --- 作为网关或者代理服务器尝试执行请求时,从远程服务器接收到了无效的响应。

14、重定向和转发区别

重定向:redirect:

​ 地址栏发生变化

​ 重定向可以访问其他站点(服务器)的资源

​ 重定向是两次请求。不能使用request对象来共享数据

转发:forward:

​ 转发地址栏路径不变

​ 转发只能访问当前服务器下的资源

​ 转发是一次请求,可以使用request对象共享数据

15、cookie和session区别。

​ Cookie 和 Session都是用来跟踪浏览器用户身份的会话方式,但两者有所区别:

​ Cookie 数据保存在客户端(浏览器端),Session 数据保存在服务器端。

​ cookie不是很安全,别人可以分析存放在本地的COOKIE并进行欺骗,考虑到安全应当使用session。

​ Cookie ⼀般⽤来保存⽤户信息,Session 的主要作⽤就是通过服务端记录⽤户的状态

二、操作系统篇

1、进程和线程的区别

进程:是资源分配的最小单位,是程序的执行过程,一个进程可以有多个线程,多个线程共享进程的堆和方法区资源,但每个线程又有属于自己的本地方法栈、虚拟机栈、程序计数器

线程:是任务调度和执行的最小单位,线程间可能存在相互影响,执行开销较小,不利于资源的管理和保护,线程间是共享进程中的资源的

2、协程?

​ 是一种比线程更加轻量级的存在,正如一个进程可以拥有多个线程一样,一个线程可以拥有多个协程。

3、进程间通信方式IPC

参考:https://www.jianshu.com/p/c1015f5ffa74

匿名管道pipe:

​ 匿名管道是半双工的,数据只能单向通信;需要双方通信时,需要建立起两个管道;只能用于父子进程或者兄弟进程之间(具有亲缘关系的进程)。

命名管道FIFO:

​ 不同于匿名管道之处在于它提供一个路径名与之关联,以FIFO的文件形式存在于文件系统中。这样,即使与FIFO的创建进程不存在亲缘关系的进程,只要可以访问该路径,就能够彼此通过FIFO相互通信(能够访问该路径的进程以及FIFO的创建进程之间),因此,通过FIFO不相关的进程也能交换数据。值得注意的是,FIFO严格遵循先进先出(first in first out),对管道及FIFO的读总是从开始处返回数据,对它们的写则把数据添加到末尾。

信号:

​ 信号是一种比较复杂的通信方式,信号产生的条件:按键、硬件异常、进程调用kill函数将信号发送给另一个进程、用户调用kill命令将信号发送给其他进程,信号传递的消息比较少,主要用于通知接收进程某个时间已经发生。

消息队列:

​ 消息队列是消息的链表,存放在内核中并由消息队列标识符标识,消息队列克服了信号传递信息少,管道只能承载无格式字节流以及缓冲区大小受限等特点。消息队列起信箱作用,到了就挂在那里,需要的时候去取。消息队列提供了一种在两个不相关进程间传递数据的简单有效的方法。与命名管道相比:消息队列的优势在于,它独立于发送和接收进程而存在,这消除了在同步命名管道的打开和关闭时可能产生的一些困难。消息队列提供了一种从一个进程向另一个进程发送一个数据块的方法。而且,每个数据块被认为含有一个类型,接收进程可以独立地接收含有不同类型值的数据块。

优点:

​ A. 我们可以通过发送消息来几乎完全避免命名管道的同步和阻塞问题。

​ B. 我们可以用一些方法来提前查看紧急消息。

缺点:

​ A. 与管道一样,每个数据块有一个最大长度的限制。

​ B. 系统中所有队列所包含的全部数据块的总长度也有一个上限。

共享内存(share memory):

  • 使得多个进程可以可以直接读写同一块内存空间,是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。
  • 为了在多个进程间交换信息,内核专门留出了一块内存区,可以由需要访问的进程将其映射到自己的私有地址空间。进程就可以直接读写这一块内存而不需要进行数据的拷贝,从而大大提高效率。
  • 由于多个进程共享一段内存,因此需要依靠某种同步机制(如信号量)来达到进程间的同步及互斥。

信号量(Semaphores) :

​ 信号量是⼀个计数器,⽤于多进程对共享数据的访问,信号量的意图在于进程间同步。这种通信⽅式主要⽤于解决与同步相关的问题并避免竞争条件。

套接字(Sockets) :

​ 此⽅法主要⽤于在客户端和服务器之间通过⽹络进⾏通信。套接字是⽀持TCP/IP 的⽹络通信的基本操作单元,可以看做是不同主机之间的进程进⾏双向通信的端点,简单的说就是通信的两⽅的⼀种约定,⽤套接字中的相关函数来完成通信过程。

4、用户态和核心态

​ 在计算机系统中,分两种程序:系统程序和应用程序,为了保证系统程序不被应用程序有意或无意地破坏,为计算机设置了两种状态——用户态、核心态

用户态:只能受限的访问内存,运行所有的应用程序

核心态:运行操作系统程序,cpu可以访问内存的所有数据,包括外围设备

为什么要有用户态和内核态:

​ 由于需要限制不同的程序之间的访问能力, 防止他们获取别的程序的内存数据, 或者获取外围设备的数据, 并发送到网络

用户态切换到内核态的3种方式:

a. 系统调用

​ 这是用户态进程主动要求切换到内核态的一种方式,用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作,比如前例中fork()实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现,例如Linux的int 80h中断。

b. 异常

​ 当CPU在执行运行在用户态下的程序时,发生了某些事先不可知的异常,这时会触发由当前运行进程切换到处理此异常的内核相关程序中,也就转到了内核态,比如缺页异常。

c. 外围设备的中断

​ 当外围设备完成用户请求的操作后,会向CPU发出相应的中断信号,这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序,如果先前执行的指令是用户态下的程序,那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成,系统会切换到硬盘读写的中断处理程序中执行后续操作等。

​ 这3种方式是系统在运行时由用户态转到内核态的最主要方式,其中系统调用可以认为是用户进程主动发起的,异常和外围设备中断则是被动的。

5、操作系统分配的进程空间是怎样的?线程能共享哪些?

​ 栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。

​ 堆区(heap)— 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。

​ 静态区(static)—存放全局变量和静态变量的存储

​ 代码区(text)—存放函数体的二进制代码。

线程共享堆区、静态区

6、操作系统内存管理方式,分页分段以及段页式的优缺点

参考地址:https://blog.csdn.net/qq_37189082/article/details/97963763

存管理方式:块式管理、页式管理、段式管理、段页式管理

分段管理:

​ 在段式存储管理中,将程序的地址空间划分为若干段(segment),如代码段,数据段,堆栈段;这样每个进程有一个二维地址空间,相互独立,互不干扰。段式管理的优点是:没有内碎片(因为段大小可变,改变段大小来消除内碎片)。但段换入换出时,会产生外碎片(比如4k的段换5k的段,会产生1k的外碎片)

分页管理:

​ 在页式存储管理中,将程序的逻辑地址划分为固定大小的页(page),而物理内存划分为同样大小的页框,程序加载时,可以将任意一页放入内存中任意一个页框,这些页框不必连续,从而实现了离散分离。页式存储管理的优点是:没有外碎片(因为页的大小固定),但会产生内碎片(一个页可能填充不满)

段页式管理:

​ 段⻚式管理机制结合了段式管理和⻚式管理的优点。简单来说段⻚式管理机制就是把主存先分成若⼲ 段,每个段⼜分成若⼲⻚,也就是说 段⻚式管理机制 中段与段之间以及段的内部的都是离散的。

7、页面置换算法有哪些,FIFO为什么不好?如何改进?LRU思想,手写LRU

置换算法:先进先出FIFO、最近最久未使用LRU、最佳置换算法OPT

先进先出FIFO:

​ 原理:把内存中驻留时间最久的页面置换算法予以淘汰

​ 优点:实现简单、直观

​ 缺点:没有考虑到实际的页面使用频率,性能差、与通常页面使用的规则不符合,实际应用较少

​ 改进:给每个页面增加一个R位,每次先从链表头开始查找,如果R置位,清除R位并且把该页面节点放 到链表结尾;如果R是0,那么就是又老又没用到,替换掉。

最近最久未使用LRU:

​ 原理:选择最近且最久未使用的页面进行淘汰

​ 优点:考虑到了程序访问的时间局部性,有较好的性能,实际应用也比较多

​ 缺点:实现需要比较多的硬件支持,会增加一些硬件成本

​ 手写LRU: 参考 https://www.jianshu.com/p/ec1952b9d84a

/**
 * @program: Java
 * @description: LRU最近最久未使用置换算法,通过LinkedHashMap实现
 * @author: Mr.Li
 * @create: 2020-07-17 10:29
 **/
public class LRUCache {
    private LinkedHashMap<Integer,Integer> cache;
    private int capacity;   //容量大小

    /**
     *初始化构造函数
     * @param capacity
     */
    public LRUCache(int capacity) {
        cache = new LinkedHashMap<>(capacity);
        this.capacity = capacity;
    }

    public int get(int key) {
        //缓存中不存在此key,直接返回
        if(!cache.containsKey(key)) {
            return -1;
        }

        int res = cache.get(key);
        cache.remove(key);   //先从链表中删除
        cache.put(key,res);  //再把该节点放到链表末尾处
        return res;
    }

    public void put(int key,int value) {
        if(cache.containsKey(key)) {
            cache.remove(key); //已经存在,在当前链表移除
        }
        if(capacity == cache.size()) {
            //cache已满,删除链表头位置
            Set<Integer> keySet = cache.keySet();
            Iterator<Integer> iterator = keySet.iterator();
            cache.remove(iterator.next());
        }
        cache.put(key,value);  //插入到链表末尾
    }
}
/**
 * @program: Java
 * @description: LRU最近最久未使用置换算法,通过LinkedHashMap内部removeEldestEntry方法实现
 * @author: Mr.Li
 * @create: 2020-07-17 10:59
 **/
class LRUCache {
    private Map<Integer, Integer> map;
    private int capacity;

    /**
     *初始化构造函数
     * @param capacity
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;  // 容量大于capacity 时就删除
            }
        };
    }
    public int get(int key) {
        //返回key对应的value值,若不存在,返回-1
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }
}

最佳置换算法OPT:

​ 原理:每次选择当前物理块中的页面在未来长时间不被访问的或未来不再使用的页面进行淘汰

​ 优点:具有较好的性能,可以保证获得最低的缺页率

​ 缺点:过于理想化,但是实际上无法实现(没办法预知未来的页面)

8、死锁条件,解决方式。

​ 死锁是指两个或两个以上进程在执行过程中,因争夺资源而造成的下相互等待的现象;

死锁的条件:

​ 互斥条件:进程对所分配到的资源不允许其他进程访问,若其他进程访问该资源,只能等待,直至占有该资源的进程使用完成后释放该资源;

​ 请求与保持条件:进程获得一定的资源后,又对其他资源发出请求,但是该资源可能被其他进程占有,此时请求阻塞,但该进程不会释放自己已经占有的资源

​ 非剥夺条件:进程已获得的资源,在未完成使用之前,不可被剥夺,只能在使用后自己释放

​ 循环等待条件:系统中若干进程组成环路,环路中每个进程都在等待相邻进程占用的资源

解决方法:破坏死锁的任意一条件

​ 资源一次性分配,从而剥夺请求和保持条件

​ 可剥夺资源:即当进程新的资源未得到满足时,释放已占有的资源,从而破坏不可剥夺的条件

​ 资源有序分配法:系统给每类资源赋予一个序号,每个进程按编号递增的请求资源,释放则相反,从而破坏环路等待的条件

三、Java基础篇

1、Java面向对象特性介绍、与C++区别

特性:封装、继承、多态

封装:对抽象的事物抽象化成一个对象,并对其对象的属性私有化,同时提供一些能被外界访问属性的方法,这样一个对象便有存在的意义了;

继承:在已存在类的基础上,建立新类并对其增加新的数据域或功能,同时该类可以复用父类的属性与功能,这种思路可以称为继承;通过使用继承能够方便地复用旧代码,减少不必要的代码量;

多态:指程序中的某个引用变量,它所指向的具体类型以及该引用变量发出的方法调用,在编程时不能确定,要在程序运行并使用时由机器自己判别确定;实现多态的方式有两种方式,可以通过继承(多个⼦类对同⼀⽅法的重写)、也可以通过接⼝(实现接⼝并覆盖接⼝中同⼀⽅法)

Java与C++区别:

​ 相同点:都是面向对象语言,并且都支持封装、继承、多态

​ 不同点:c++支持多继承,并且有指针的概念,由程序员自己管理内存;Java是单继承,可以用接口实现多继承,Java 不提供指针来直接访问内存,程序内存更加安全,并且Java有JVM⾃动内存管理机制,不需要程序员⼿动释放⽆⽤内存

2、多态实现原理

参考:https://www.baidu.com/link?url=qCqeY8tJInTtjEXuotB712TJtEpKeLJ9ds1ACGEnYwMyJdjf6J0C7JvOEwbV7qNG&wd=&eqid=fe3b2106001ee6ab000000065f111b6c

多态的底层实现是动态绑定,即在运行时才把方法调用与方法实现关联起来。

静态绑定与动态绑定:

​ JVM 的方法调用指令有五个,分别是:

​ invokestatic:调用静态方法;

​ invokespecial:调用实例构造器<init>方法、私有方法和父类方法;</init>

​ invokevirtual:调用虚方法;

​ invokeinterface:调用接口方法,运行时确定具体实现;

​ invokedynamic:运行时动态解析所引用的方法,然后再执行,用于支持动态类型语言。

​ invokestatic 和 invokespecial 用于静态绑定

​ invokevirtual 和 invokeinterface 用于动态绑定

​ 可以看出,动态绑定主要应用于虚方法和接口方法。

​ 虚方法的方法调用与方法实现的关联(也就是分派)有两种,一种是在编译期确定,被称为静态分派,比如方法的重载;一种是在运行时确定,被称为动态分派,比如方法的覆盖(重写)。对象方法基本上都是虚方法。

多态的实现

​ 虚拟机栈中会存放当前方法调用的栈帧(局部变量表、操作栈、动态连接 、返回地址)。多态的实现过程,就是方法调用动态分派的过程,通过栈帧的信息去找到被调用方法的具体实现,然后使用这个具体实现的直接引用完成方法调用。

以 invokevirtual 指令为例,在执行时,大致可以分为以下几步:

  1. 先从操作栈中找到对象的实际类型 class;
  2. 找到 class 中与被调用方法签名相同的方法,如果有访问权限就返回这个方法的直接引用,如果没有访问权限就报错 java.lang.IllegalAccessError ;
  3. 如果第 2 步找不到相符的方法,就去搜索 class 的父类,按照继承关系自下而上依次执行第 2 步的操作;
  4. 如果第 3 步找不到相符的方法,就报错 java.lang.AbstractMethodError ;

可以看到,如果子类覆盖了父类的方法,则在多态调用中,动态绑定过程会首先确定实际类型是子类,从而先搜索到子类中的方法。这个过程便是方法覆盖的本质。

3、抽象类和接口区别,以及各自的使用场景

抽象类:包含抽象方法的类,即使用abstract修饰的类;不能使用final修饰,final修饰的类不能被继承;抽象类不能被实例化,只能被继承

接口:接口是一个抽象类型,是抽象方法的集合,接口以interface来声明。一个类通过继承接口的方式,从而来继承接口的抽象方法;接口只能继承接口,不能继承类,接口支持多继承;接口中的定义的成员变量,默认是public static final修饰的静态常量;接口中定义的方法,默认是public abstract修饰的抽象方法

相同点:

​ ① 抽象类和接口都不能被实例化

​ ② 抽象类和接口都可以定义抽象方法,子类/实现类必须覆写这些抽象方法

不同点:

​ ① 抽象类有构造方法,接口没有构造方法

​ ③抽象类可以包含普通方法,接口中只能是public abstract修饰抽象方法(Java8之后可以)

​ ③ 抽象类只能单继承,接口可以多继承

​ ④ 抽象类可以定义各种类型的成员变量,接口中只能是public static final修饰的静态常量

抽象类的使用场景:

​ 既想约束子类具有共同的行为(但不再乎其如何实现),又想拥有缺省的方法,又能拥有实例变量

接口的应用场景:

​ 约束多个实现类具有统一的行为,但是不在乎每个实现类如何具体实现;实现类需要具备很多不同的功能,但各个功能之间可能没有任何联系

4、泛型以及泛型擦除。List类型的list,可以加入无继承关系的B类型对象吗?如何加入?

参考:https://blog.csdn.net/baoyinwang/article/details/107341997

泛型:

​ 泛型提供了编译时类型安全检测机制,该机制允许程序员在编译时检测到非法的类型。泛型的本质是参数化类型,也就是说所操作的数据类型被指定为一个参数。这种参数类型可以用在类、接口和方法的创建中,分别称为泛型类、泛型接口和泛型方法。

泛型擦除:

​ Java的泛型是伪泛型,这是因为Java在编译期间,所有的泛型信息都会被擦掉,正确理解泛型概念的首要前提是理解类型擦除。Java的泛型基本上都是在编译器这个层次上实现的,在生成的字节码中是不包含泛型中的类型信息的,使用泛型的时候加上类型参数,在编译器编译的时候会去掉,这个过程成为类型擦除。

​ 如在代码中定义的 List<object>和 List<string>等类型,在编译之后都会变成 List。JVM 看到的只是 List,而由泛型附加的类型信息对 JVM 来说是不可见的。</string></object>

如何加入:

​ 通过反射添加其它类型元素

public class Test {
    public static void main(String[] args) throws Exception {

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

        list.add(new A());  //这样调用 add 方法只能存储A,因为泛型类型的实例为 A

        list.getClass().getMethod("add", Object.class).invoke(list, new B());

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

}

5、Java异常体系

Throwable 是 Java 语言中所有错误或异常的超类。下一层分为 Error 和 Exception

Error :

​ 是指 java 运行时系统的内部错误和资源耗尽错误。应用程序不会抛出该类对象。如果出现了这样的错误,除了告知用户,剩下的就是尽力使程序安全的终止。

Exception 包含:RuntimeException 、CheckedException

RuntimeException: 运 行 时 异 常

​ 如 NullPointerException 、 ClassCastException ;

​ RuntimeException 是那些可能在 Java 虚拟机正常运行期间抛出的异常的超类,这些异常一般是由程序逻辑错误引起的,程序应该从逻辑角度尽可能避免这类异常的发生。

CheckedException:受检异 常

​ 如 I/O 错误导致的 IOException、SQLException;

​ CheckedException:一般是外部错误,这种异常都发生在编译阶段,Java 编译器会强制程序去捕获此类

异常,即会出现要求你把这段可能出现异常的程序进行 try catch,该类异常一般包括几个方面:

​ ①试图在文件尾部读取数据

​ ②试图打开一个错误格式的 URL

​ ③试图根据给定的字符串查找 class 对象,而这个字符串表示的类并不存在

6、反射原理以及使用场景

Java反射:

​ 是指在运行状态中,对于任意一个类都能够知道这个类所有的属性和方法;并且对于任意一个对象,都能够调用它的任意一个方法;这种动态获取信息以及动态调用对象方法的功能成为 Java 语言的反射机制。

反射原理:

​ 反射首先是能够获取到Java中的反射类的字节码,然后将字节码中的方法,变量,构造函数等映射成 相应的 Method、Filed、Constructor 等类

如何得到Class的实例:

     1.类名.class(就是一份字节码)
     2.Class.forName(String className);根据一个类的全限定名来构建Class对象
     3.每一个对象多有getClass()方法:obj.getClass();返回对象的真实类型

使用场景:

​ 逆向代码 ,例如反编译;

​ 动态生成类框架,如Spring:xml的配置模式。Spring 通过 XML 配置模式装载 Bean 的过程:1) 将程序内所有 XML 或 Properties 配置文件加载入内存中; 2)Java类里面解析xml或properties里面的内容,得到对应实体类的字节码字符串以及相关的属性信息; 3)使用反射机制,根据这个字符串获得某个类的Class实例; 4)动态配置实例的属性

7、ThreadLocal原理,如何使用?

ThreadLocal简介:

​ 通常情况下,我们创建的变量是可以被任何⼀个线程访问并修改的。如果想实现每⼀个线程都有⾃⼰的
专属本地变量该如何解决呢? JDK中提供的 ThreadLocal 类正是为了解决这样的问题。

原理:

​ 首先 ThreadLocal 是一个泛型类,保证可以接受任何类型的对象。因为一个线程内可以存在多个 ThreadLocal 对象,所以其实是 ThreadLocal 内部维护了一个 Map ,这个 Map 不是直接使用的 HashMap ,而是 ThreadLocal 实现的一个叫做 ThreadLocalMap 的静态内部类。

​ 最终的变量是放在了当前线程的 ThreadLocalMap 中,并不是存在 ThreadLocal 上,ThreadLocal 可以理解为只是ThreadLocalMap的封装,传递了变量值。

​ 我们使用的 get()、set() 方法其实都是调用了这个ThreadLocalMap类对应的 get()、set() 方法。例如下面的

set 方法:

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

get方法:

public T get() {   
    Thread t = Thread.currentThread();   
    ThreadLocalMap map = getMap(t);   
    if (map != null)   
        return (T)map.get(this);   

    // 如果不存在,则创建它   
    T value = initialValue();   
    createMap(t, value);   
    return value;   
}

createMap方法:

void createMap(Thread t, T firstValue) {   
    t.threadLocals = new ThreadLocalMap(this, firstValue);   
} 

ThreadLocalMap是个静态的内部类:

static class ThreadLocalMap {   
    ……  
}  

如何使用:

​ 1)存储用户Session

private static final ThreadLocal threadSession = new ThreadLocal();

public static Session getSession() throws InfrastructureException {
    Session s = (Session) threadSession.get();
    try {
        if (s == null) {
            s = getSessionFactory().openSession();
            threadSession.set(s);
        }
    } catch (HibernateException ex) {
        throw new InfrastructureException(ex);
    }
    return s;
}

​ 2)解决线程安全的问题

public class DateUtil {
    //SimpleDateFormat不是线程安全的,所以每个线程都要有⾃⼰独⽴的副本
    private static ThreadLocal<SimpleDateFormat> format1 = new                     ThreadLocal<SimpleDateFormat>() {
        @Override
        protected SimpleDateFormat initialValue() {
            return new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        }
    };

    public static String formatDate(Date date) {
        return format1.get().format(date);
    }
}

8、ThreadLocal内存泄漏的场景

​ 实际上 ThreadLocalMap 中使用的 key 为 ThreadLocal 的弱引用,⽽ value 是强引⽤。弱引用的特点是,如果这个对象持有弱引用,那么在下一次垃圾回收的时候必然会被清理掉。

​ 所以如果 ThreadLocal 没有被外部强引用的情况下,在垃圾回收的时候会被清理掉的,这样一来 ThreadLocalMap中使用这个 ThreadLocal 的 key 也会被清理掉。但是,value 是强引用,不会被清理,这样一来就会出现 key 为 null 的 value。 假如我们不做任何措施的话,value 永远⽆法被GC 回收,这个时候就可能会产⽣内存泄露。

​ ThreadLocalMap实现中已经考虑了这种情况,在调用 set()、get()、remove() 方法的时候,会清理掉 key 为 null 的记录。如果说会出现内存泄漏,那只有在出现了 key 为 null 的记录后,没有手动调用 remove() 方法,并且之后也不再调用 get()、set()、remove() 方法的情况下。

​ 因此使⽤完ThreadLocal ⽅法后,最好⼿动调⽤ remove() ⽅法。

9、static关键字和final关键字使用情况,一个类不能被继承,除了final关键字之外,还有什么方法(从构造函数考虑)?

static:可以修饰属性、方法

static修饰属性:

​ 所有对象共享一份,一个对象对其修改,其他的调用也会受到影响,类级别;随着类的加载而加载(只加载一次),先于对象的创建;可以使用类名直接调用。

static修饰方法:

​ 随着类的加载而加载;可以使用类名直接调用;静态方法中,只能调用静态的成员;非静态的方法中,可以调用静态和非静态的成员;在静态方法中,不会出现this。

final:关键字主要⽤在三个地⽅:变量、⽅法、类。

final修饰变量:

​ 对于⼀个 final 变量,如果是基本数据类型的变量,则其数值⼀旦在初始化之后便不能更改;如果是引⽤类型的变量,则在对其初始化之后便不能再让其指向另⼀个对象。

final修饰方法:

​ 把⽅法锁定,以防任何继承类修改它的含义(重写);类中所有的 private ⽅法都隐式地指定为 final。

final修饰类:

​ final 修饰类时,表明这个类不能被继承。final 类中的所有成员⽅法都会被隐式地指定为 final ⽅法。

10、序列化和反序列化。反序列化失败的场景。

​ 序列化的意思就是将对象的状态转化成字节流,以后可以通过这些值再生成相同状态的对象。对象序列化是对象持久化的一种实现方法,它是将对象的属性和方法转化为一种序列化的形式用于存储和传输。反序列化就是根据这些保存的信息重建对象的过程。

序列化:将java对象转化为字节序列的过程。

反序列化:将字节序列转化为java对象的过程。

优点:

​ a、实现了数据的持久化,通过序列化可以把数据永久地保存到硬盘上(通常存放在文件里)

​ b、利用序列化实现远程通信,即在网络上传送对象的字节序列。

反序列化失败的场景:

​ 序列化ID:serialVersionUID不一致的时候,导致反序列化失败

11、ArrayList和LinkedList的区别和底层实现?如何实现线程安全?

ArrayList:

​ 底层基于数组实现,支持对元素进行快速随机访问,支持元素重复;默认初始大小为10,当数组容量不够时,会触发扩容机制(扩大到当前的1.5倍),需要将原来数组的数据复制到新的数组中;当从 ArrayList 的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此,它适合随机查找和遍历,不适合插入和删除。

LinkedList:

​ 底层基于双向链表实现,适合数据的动态插入和删除;内部提供了 List 接口中没有定义的方法,用于操作表头和表尾元素,可以当作堆栈、队列和双向队列使用。

ArrayList与LinkedList区别:

​ 都是线程不安全的,ArrayList 适用于查找的场景,LinkedList 适用于 增加、删除多的场景

现线程安全:

​ 可以使用原生的Vector,或者是Collections.synchronizedList(List list)函数返回一个线程安全的ArrayList集合,或者使用concurrent并发包下的CopyOnWriteArrayList的。

​ ①、Vector: 底层通过synchronize修饰保证线程安全,效率较差

​ ② 、Collections.synchronizedList(List list):

//使用Collections.synchronizedList(List list)方法实现线程安全
List<?> list=Collections.synchronizedList(new ArrayList<>());

​ ③、CopyOnWriteArrayList:写时加锁,使用了一种叫写时复制的方法;读操作是可以不用加锁的

12、List遍历时如何删除元素?fail—fast是什么?fail—safe是什么?

①、普通for循环遍历List删除指定元素

for(int i=0; i < list.size(); i++){
   if(list.get(i) == 5) 
       list.remove(i);
}

② 、迭代遍历,用list.remove(i)方法删除元素

Iterator<Integer> it = list.iterator();
while(it.hasNext()){
    Integer value = it.next();
    if(value == 5){
        list.remove(value);
    }
}

③、foreach遍历List删除元素

for(Integer i:list){
    if(i==3) list.remove(i);
}

fail—fast:快速失败

​ 当异常产生时,直接抛出异常,程序终止;

​ fail-fast只要是体现在当我们在遍历集合元素的时候,经常会使用迭代器,但在迭代器遍历元素的过程中,如果集合的结构被改变的话,就会抛出异常ConcurrentModificationException,防止继续遍历。这就是所谓的快速失败机制。这里要注意的这里说的结构被改变,是例如插入和删除这种操作,只是改变集合里的值的话并不会抛出异常。

fail—safe:安全失败

    采用安全失败机制的集合容器,在遍历时不是直接在集合内容上访问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。

    原理:由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发ConcurrentModificationException。

    缺点:基于拷贝内容的优点是避免了ConcurrentModificationException,但同样地,迭代器并不能访问到修改后的内容,即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的。

    场景:java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。

13、详细介绍HashMap。

角度:数据结构+扩容情况+put查找的详细过程+哈希函数+容量为什么始终都是2^N,JDK1.7与1.8的区别。

参考:https://www.jianshu.com/p/9fe4cb316c05

数据结构:

​ HashMap在底层数据结构上采用了数组+链表+红黑树,通过散列映射来存储键值对数据

扩容情况:

​ 默认的负载因子是0.75,表示的是,如果数组中已经存储的元素个数大于数组长度的75%,将会引发扩容操作。

​ 【1】创建一个长度为原来数组长度两倍的新数组

​ 【2】重新对原数组中的Entry对象进行哈希运算,以确定他们各自在新数组中的新位置。

put操作步骤:

​ 1、判断数组是否为空,为空进行初始化;

​ 2、不为空,则计算 key 的 hash 值,通过(n - 1) & hash计算应当存放在数组中的下标 index;

​ 3、查看 table[index] 是否存在数据,没有数据就构造一个Node节点存放在 table[index] 中;

​ 4、存在数据,说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等,相等,用新的value替换原数据;

​ 5、若不相等,判断当前节点类型是不是树型节点,如果是树型节点,创造树型节点插入红黑树中;

​ 6、若不是红黑树,创建普通Node加入链表中;判断链表长度是否大于 8,大于则将链表转换为红黑树;

​ 7、插入完成之后判断当前节点数是否大于阈值,若大于,则扩容为原数组的二倍

哈希函数:

​ hash函数是先拿到 key 的hashcode,是一个32位的值,然后让hashcode的高16位和低16位进行异或操作。该函数也称为扰动函数,做到尽可能降低hash碰撞。

容量为什么始终都是2^N:

​ 为了能让 HashMap 存取⾼效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上⾯也讲到了过了,Hash 值的范围值-2147483648到2147483647,前后加起来⼤概40亿的映射空间,只要哈希函数映射得⽐较均匀松散,⼀般应⽤是很难出现碰撞的。但问题是⼀个40亿⻓度的数组,内存是放不下的。所以这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算,得到的余数才能⽤来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“ (n - 1) & hash ”。(n代表数组⻓度)。这也就解释了 HashMap 的⻓度为什么是2的幂次⽅。

JDK1.7与1.8的区别:

JDK1.7 HashMap:

​ 底层是 数组和链表 结合在⼀起使⽤也就是 链表散列。HashMap 通过 key 的hashCode 经过扰动函数处理过后得到 hash 值,然后通过 (n - 1) & hash 判断当前元素存放的位置(这⾥的 n 指的是数组的⻓度),如果当前位置存在元素的话,就判断该元素与要存⼊的元素的 hash值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。

DK1.8 HashMap:

​ HashMap在底层数据结构上采用了数组+链表+红黑树,通过散列映射来存储键值对数据;当链表⻓度⼤于阈值(默认为 8),数组的⻓度大于 64时,将链表转化为红⿊树,以减少搜索时间

14、HashMap如何实现线程安全?ConcurrentHashMap的底层实现?JDK1.7与JDK1.8的区别

​ 可以通过ConcurrentHashMapHashtable来实现线程安全;Hashtable 是原始API类,通过synchronize同步修饰,效率低下;ConcurrentHashMap 通过分段锁实现,效率较比Hashtable要好;

ConcurrentHashMap的底层实现:

JDK1.7的 ConcurrentHashMap 底层采⽤ 分段的数组+链表 实现;采用 分段锁(Sagment) 对整个桶数组进⾏了分割分段(Segment),每⼀把锁只锁容器其中⼀部分数据,多线程访问容器⾥不同数据段的数据,就不会存在锁竞争,提⾼并发访问率。

JDK1.8的 ConcurrentHashMap 采⽤的数据结构跟HashMap1.8的结构⼀样,数组+链表/红⿊⼆叉树;摒弃了Segment的概念,⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现,通过并发控制 synchronized 和CAS来操作保证线程的安全。

15、正则表达式会写吗?

参考:https://blog.csdn.net/qq_39331713/article/details/82871510

​ 正则通过一些特定的符号与数字来表示一串字符,其中有:元字符、重复限定符、分组、转义、条件或、区间;

16、设计模式了解吗?

单例模式、工厂模式、代理模式

17、linux指令知道哪些?

文件管理:ls、cd、touch创建普通文件、rm删除、mkdir新建目录、mv移动、cp拷贝、chmod修改权限

进程管理:ps显示进程信息、kill杀死进程

系统管理:top、free显示系统运行信息、vmstat输出各资源使用情况

网络通讯:ping测试网络连通性、netstat显示网络相关信息

18、JVM相关

1、JVM运行时内存划分?

JVM运行时数据区域:堆、方法区(元空间)、虚拟机栈、本地方法栈、程序计数器

Heap(堆):

​ 对象的实例以及数组的内存都是要在堆上进行分配的,堆是线程共享的一块区域,用来存放对象实例,也是垃圾回收(GC)的主要区域;

​ 堆细分:新生代、老年代,对于新生代又分为:Eden区和Surviver1和Surviver2区;

方法区:

​ 对于JVM的方法区也可以称之为永久区,它储存的是已经被java虚拟机加载的类信息、常量、静态变量;Jdk1.8以后取消了方法区这个概念,称之为元空间(MetaSpace);

虚拟机栈:

​ 虚拟机栈是线程私有的,他的生命周期和线程的生命周期是一致的。里面装的是一个一个的栈帧,每一个方法在执行的时候都会创建一个栈帧,栈帧中用来存放(局部变量表操作数栈动态链接返回地址);在Java虚拟机规范中,对此区域规定了两种异常状况:如果线程请求的栈深度大于虚拟机所允许的深度,将会抛出StackOverflowError异常;如果虚拟机栈动态扩展时无法申请到足够的内存,就会抛出OutOfMemoryError异常。

  • 局部变量表:局部变量表是一组变量值存储空间,用来存放方法参数、方法内部定义的局部变量。局部变量表的容量是以变量槽(variable slot)为最小的单位。Java虚拟机没有明确规定一个slot所占的空间大小。只是导向性的说了每一个slot能存放8中基本数据类型中的一种(long 和double这种64位的需要两个slot);

  • 操作数栈:是用来记录一个方法在执行的过程中,字节码指令向操作数栈中进行入栈和出栈的过程。大小在编译的时候已经确定了,当一个方法刚开始执行的时候,操作数栈中是空发的,在方法执行的过程中会有各种字节码指令往操作数栈中入栈和出栈

  • 动态链接:因为字节码文件中有很多符号的引用,这些符号引用一部分会在类加载的解析阶段第一次使用的时候转化成直接引用,这种称为静态解析;另一部分会在运行期间转化为直接引用,称为动态链接

  • 返回地址(returnAddress):类型(指向了一条字节码指令的地址)

本地方法栈:

​ 本地方法栈和虚拟机栈类似,不同的是虚拟机栈服务的是Java方法,而本地方法栈服务的是Native方法。在HotSpot虚拟机实现中是把本地方法栈和虚拟机栈合二为一的,同理它也会抛出StackOverflowErrorOOM异常。

PC程序计数器:

​ PC,指的是存放下一条指令的位置的这么一个区域。它是一块较小的内存空间,且是线程私有的。由于线程的切换,CPU在执行的过程中,一个线程执行完了,接下来CPU切换到另一个线程去执行,另外一个线程执行完再切回到之前的线程,这时需要记住原线程的下一条指令的位置,所以每一个线程都需要有自己的PC。

2、堆内存分配策略

  • 对象优先分配在Eden区,如果Eden区没有足够的空间进行分配时,虚拟机执行一次MinorGC。而那些无需回收的存活对象,将会进到 Survivor 的 From 区(From 区内存不足时,直接进入 Old 区)。

  • 大对象直接进入老年代(需要大量连续内存空间的对象)。这样做的目的是避免在Eden区和两个Survivor区之间发生大量的内存拷贝(新生代采用复制算法收集内存)。

  • 长期存活的对象进入老年代。虚拟机为每个对象定义了一个年龄(Age Count)计数器,如果对象经过了1次Minor GC那么对象会进入Survivor区,之后每经过一次Minor GC那么对象的年龄加1,直到达到阀值(默认15次),对象进入老年区。

  • 动态判断对象的年龄。如果Survivor区中相同年龄的所有对象大小的总和大于Survivor空间的一半,年龄大于或等于该年龄的对象可以直接进入老年代。

3、Full GC触发条件

​ 每次进行Minor GC时,JVM会计算Survivor区移至老年区的对象的平均大小,如果这个值大于老年区的剩余值大小,则进行一次Full GC,如果小于检查HandlePromotionFailure设置,如果true则只进行Monitor GC,如果false则进行Full GC

4、如何判断对象是否存活?回收对象的两次标记过程。

引用计数法:

​ 给对象添加一个引用计数器,每当由一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时刻计数器为0的对象就是不可能再被使用的。

​ 优点:实现简单,判定效率也很高

​ 缺点:他很难解决对象之间相互循环引用的问题。

对象可达性:

​ 通过一系列的成为“GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径成为引用链,当一个对象到GC ROOTS没有任何引用链相连时,则证明此对象时不可用的;

两次标记过程:

​ 对象被回收之前,该对象的finalize()方***被调用;两次标记,即第一次标记不在“关系网”中的对象。第二次的话就要先判断该对象有没有实现finalize()方法了,如果没有实现就直接判断该对象可回收;如果实现了就会先放在一个队列中,并由虚拟机建立的一个低优先级的线程去执行它,随后就会进行第二次的小规模标记,在这次被标记的对象就会真正的被回收了。

5、垃圾回收算法以及垃圾回收器介绍,尤其是G1和CMS的优缺点

垃圾回收算法:复制算法、标记清除、标记整理、分代收集

复制算法:

​ 将内存分为⼤⼩相同的两块,每次使⽤其中的⼀块。当这⼀块的内存使⽤完后,就将还存活的对象复制到另⼀块去,然后再把使⽤的空间⼀次清理掉。这样就使每次的内存回收都是对内存区间的⼀半进⾏回收;

​ 优点:实现简单,内存效率高,不易产生碎片

​ 缺点:内存压缩了一半,倘若存活对象多,Copying 算法的效率会大大降低

标记清除:

​ 标记出所有需要回收的对象,在标记完成后统⼀回收所有被标记的对象

​ 缺点:效率低,标记清除后会产⽣⼤量不连续的碎⽚,可能发生大对象不能找到可利用空间的问题。

标记整理:

​ 标记过程仍然与“标记-清除”算法⼀样,再让所有存活的对象向⼀端移动,然后直接清理掉端边界以外的内存;解决了产生大量不连续碎片问题

分代收集:

​ 根据各个年代的特点选择合适的垃圾收集算法。

​ 新生代采用复制算法,新生代每次垃圾回收都要回收大部分对象,存活对象较少,即要复制的操作比较少,一般将新生代划分为一块较大的 Eden 空间和两个较小的 Survivor 空间(From Space, To Space),每次使用Eden 空间和其中的一块 Survivor 空间,当进行回收时,将该两块空间中还存活的对象复制到另一块 Survivor 空间中。

​ 年代的对象存活⼏率是⽐较⾼的,⽽且没有额外的空间对它进⾏分配担保,所以我们必须选择“标记-清除”或“标记-整理”算法进⾏垃圾收集。

垃圾收集器:Serial、Parnew、parallel Scavenge、Serialold 、Parnewold、CMS、G1

Serial:

​ Serial 是一个单线程的收集器,它不但只会使用一个 CPU 或一条线程去完成垃圾收集工作,并且在进行垃圾收集的同时,必须暂停其他所有的工作线程,直到垃圾收集结束。

Parnew:

​ ParNew 垃圾收集器其实是 Serial 收集器的多线程版本,也使用复制算法,除了使用多线程进行垃圾收集之外,其余的行为和 Serial 收集器完全一样,ParNew 垃圾收集器在垃圾收集过程中同样也要暂停所有其他的工作线程。

parallel Scavenge:

​ Parallel Scavenge收集器关注点是吞吐量(⾼效率的利⽤CPU)。CMS等垃圾收集器的关注点更多的是⽤户线程的停顿时间(提⾼⽤户体验);高吞吐量可以最高效率地利用 CPU 时间,尽快地完成程序的运算任务,主要适用于在后台运算而不需要太多交互的任务。

Serial old:

Serial收集器的⽼年代版本,它同样是⼀个单线程收集器,使用标记-整理算法。主要有两个用途:

  • 在 JDK1.5 之前版本中与新生代的 Parallel Scavenge 收集器搭配使用。

  • 作为年老代中使用 CMS 收集器的后备垃圾收集方案。

parallel old:

​ Parallel Scavenge收集器的⽼年代版本。使⽤多线程和“标记-整理”算法。

CMS:重要

​ CMS收集器是一种年老代垃圾收集器,其最主要目标是获取最短垃圾回收停顿时间,和其他年老代使用标记-整理算法不同,它使用多线程的标记-清除算法。最短的垃圾收集停顿时间可以为交互比较高的程序提高用户体验。CMS 工作机制相比其他的垃圾收集器来说更复杂,整个过程分为以下 4 个阶段:

初始标记:只是标记一下 GC Roots 能直接关联的对象,速度很快,仍然需要暂停所有的工作线程。

并发标记:进行 GC Roots 跟踪的过程,和用户线程一起工作,不需要暂停工作线程。

重新标记:为了修正在并发标记期间,因用户程序继续运行而导致标记产生变动的那一部分对象的标记记录,仍然需要暂停所有的工作线程。

并发清除:清除 GC Roots 不可达对象,和用户线程一起工作,不需要暂停工作线程。由于耗时最长的并发标记和并发清除过程中,垃圾收集线程可以和用户现在一起并发工作,所以总体上来看CMS 收集器的内存回收和用户线程是一起并发地执行。

优点:并发收集、低停顿

缺点:对CPU资源敏感;⽆法处理浮动垃圾;使⽤“标记清除”算***导致⼤量空间碎⽚产⽣。

G1:重要

​ 是⼀款⾯向服务器的垃圾收集器,主要针对配备多颗处理器及⼤容量内存的机器.以极⾼概率满⾜GC停顿时间要求的同时,还具备⾼吞吐量性能特征;相比与 CMS 收集器,G1 收集器两个最突出的改进是:

​ 【1】基于标记-整理算法,不产生内存碎片。

​ 【2】可以非常精确控制停顿时间,在不牺牲吞吐量前提下,实现低停顿垃圾回收。

​ G1 收集器避免全区域垃圾收集,它把堆内存划分为大小固定的几个独立区域,并且跟踪这些区域的垃圾收集进度,同时在后台维护一个优先级列表,每次根据所允许的收集时间,优先回收垃圾最多的区域。区域划分优先级区域回收机制,确保 G1 收集器可以在有限时间获得最高的垃圾收集效率。

6、创建一个对象的步骤

步骤:类加载检查、分配内存、初始化零值、设置对象头、执行init方法

①类加载检查:

​ 虚拟机遇到⼀条 new 指令时,⾸先将去检查这个指令的参数是否能在常量池中定位到这个类的符号引⽤,并且检查这个符号引⽤代表的类是否已被加载过、解析和初始化过。如果没有,那必须先执⾏相应的类加载过程。

②分配内存:

​ 在类加载检查通过后,接下来虚拟机将为新⽣对象分配内存。对象所需的内存⼤⼩在类加载完成后便可确定,为对象分配空间的任务等同于把⼀块确定⼤⼩的内存从 Java 堆中划分出来。分配⽅式有 “指针碰撞”“空闲列表” 两种,选择那种分配⽅式由 Java 堆是否规整决定,⽽Java堆是否规整⼜由所采⽤的垃圾收集器是否带有压缩整理功能决定。

③初始化零值:

​ 内存分配完成后,虚拟机需要将分配到的内存空间都初始化为零值,这⼀步操作保证了对象的实例字段在 Java 代码中可以不赋初始值就直接使⽤,程序能访问到这些字段的数据类型所对应的零值。

④设置对象头:

​ 初始化零值完成之后,虚拟机要对对象进⾏必要的设置,例如这个对象是那个类的实例、如何才能找到类的元数据信息、对象的哈希吗、对象的 GC 分代年龄等信息。 这些信息存放在对象头中。 另外,根据虚拟机当前运⾏状态的不同,如是否启⽤偏向锁等,对象头会有不同的设置⽅式。

⑤执⾏ init ⽅法:

​ 在上⾯⼯作都完成之后,从虚拟机的视⻆来看,⼀个新的对象已经产⽣了,但从Java 程序的视⻆来看,对象创建才刚开始, <init> ⽅法还没有执⾏,所有的字段都还为零。所以⼀般来说,执⾏ new 指令之后会接着执⾏ <init> ⽅法,把对象按照程序员的意愿进⾏初始化,这样⼀个真正可⽤的对象才算完全产⽣出来。</init></init>

7、详细介绍类加载过程

过程:加载、验证、准备、解析、初始化

加载阶段:

​ 1.通过一个类的全限定名来获取定义此类的二进制字节流。

​ 2.将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构。

​ 3.在Java堆中生成一个代表这个类的java.lang.class对象,作为方法区这些数据的访问入口。

验证阶段:

​ 1.文件格式验证(是否符合Class文件格式的规范,并且能被当前版本的虚拟机处理)

​ 2.元数据验证(对字节码描述的信息进行语意分析,以保证其描述的信息符合Java语言规范要求)

​ 3.字节码验证(保证被校验类的方法在运行时不会做出危害虚拟机安全的行为)

​ 4.符号引用验证(虚拟机将符号引用转化为直接引用时,解析阶段中发生)

准备阶段:

​ 准备阶段是正式为类变量分配内存并设置类变量初始值的阶段。将对象初始化为“零”值

解析阶段:

​ 解析阶段时虚拟机将常量池内的符号引用替换为直接引用的过程。

初始化阶段:

​ 初始化阶段时加载过程的最后一步,而这一阶段也是真正意义上开始执行类中定义的Java程序代码。

8、双亲委派机制,使用这个机制的好处?如何破坏?

​ 每⼀个类都有⼀个对应它的类加载器。系统中的 ClassLoder 在协同⼯作的时候会默认使⽤ 双亲委派模型 。即在类加载的时候,系统会⾸先判断当前类是否被加载过。已经被加载的类会直接返回,否则才会尝试加载。加载的时候,⾸先会把该请求委派该⽗类加载器的 loadClass() 处理,因此所有的请求最终都应该传送到顶层的启动类加载器 BootstrapClassLoader 中。当⽗类加载器⽆法处理时,才由⾃⼰来处理。当⽗类加载器为null时,会使⽤启动类加载器 BootstrapClassLoader 作为⽗类加载器。

使用好处:

​ 此机制保证JDK核心类的优先加载;使得Java程序的稳定运⾏,可以避免类的重复加载,也保证了 Java 的核⼼ API 不被篡改。如果不⽤没有使⽤双亲委派模型,⽽是每个类加载器加载⾃⼰的话就会出现⼀些问题,⽐如我们编写⼀个称为 java.lang.Object 类的话,那么程序运⾏的时候,系统就会出现多个不同的Object 类。

破坏双亲委派机制:

​ 可以⾃⼰定义⼀个类加载器,重写loadClass方法;

9、了解下tomcat的类加载机制

步骤:

  1. 先在本地cache查找该类是否已经加载过,看看 Tomcat 有没有加载过这个类。
  2. 如果Tomcat 没有加载过这个类,则从系统类加载器的cache中查找是否加载过。
  3. 如果没有加载过这个类,尝试用ExtClassLoader类加载器类加载,重点来了,这里并没有首先使用 AppClassLoader 来加载类。这个Tomcat 的 WebAPPClassLoader 违背了双亲委派机制,直接使用了 ExtClassLoader来加载类。这里注意 ExtClassLoader 双亲委派依然有效,ExtClassLoader 就会使用 Bootstrap ClassLoader 来对类进行加载,保证了 Jre 里面的核心类不会被重复加载。 比如在 Web 中加载一个 Object 类。WebAppClassLoader → ExtClassLoader → Bootstrap ClassLoader,这个加载链,就保证了 Object 不会被重复加载。
  4. 如果 BoostrapClassLoader,没有加载成功,就会调用自己的 findClass 方法由自己来对类进行加载,findClass 加载类的地址是自己本 web 应用下的 class。
  5. 加载依然失败,才使用 AppClassLoader 继续加载。
  6. 都没有加载成功的话,抛出异常。

总结一下以上步骤,WebAppClassLoader 加载类的时候,故意打破了JVM 双亲委派机制,绕开了 AppClassLoader,直接先使用 ExtClassLoader 来加载类。

10、JVM性能调优,常用命令,以及工具

对应进程的JVM状态以定位问题和解决问题并作出相应的优化

常用命令:jps、jinfo、jstat、jstack、jmap

jps:查看java进程及相关信息

jps -l 输出jar包路径,类全名
jps -m 输出main参数
jps -v 输出JVM参数

jinfo:查看JVM参数

jinfo 11666
jinfo -flags 11666

jstat:查看JVM运行时的状态信息,包括内存状态、垃圾回收

命令格式:
jstat [option] LVMID [interval] [count]
其中LVMID是进程id,interval是打印间隔时间(毫秒),count是打印次数(默认一直打印)

option参数解释:
-class class loader的行为统计
-compiler HotSpt JIT编译器行为统计
-gc 垃圾回收堆的行为统计
-gccapacity 各个垃圾回收代容量(young,old,perm)和他们相应的空间统计
-gcutil 垃圾回收统计概述
-gccause 垃圾收集统计概述(同-gcutil),附加最近两次垃圾回收事件的原因
-gcnew 新生代行为统计
-gcnewcapacity 新生代与其相应的内存空间的统计
-gcold 年老代和永生代行为统计
-gcoldcapacity 年老代行为统计
-gcpermcapacity 永生代行为统计
-printcompilation HotSpot编译方法统计

jstack:查看JVM线程快照,jstack命令可以定位线程出现长时间卡顿的原因,例如死锁,死循环

命令格式:
jstack [-l] <pid> (连接运行中的进程)
jstack -F [-m] [-l] <pid> (连接挂起的进程)
jstack [-m] [-l] <executable> <core> (连接core文件)
jstack [-m] [-l] [server_id@]<remote server IP or hostname> (连接远程debug服务器)

option参数解释:
-F 当使用jstack <pid>无响应时,强制输出线程堆栈。
-m 同时输出java和本地堆栈(混合模式)
-l 额外显示锁信息

jmap:可以用来查看内存信息

命令格式:
jmap [option] <pid> (连接正在执行的进程)
jmap [option] <executable <core> (连接一个core文件)
jmap [option] [server_id@]<remote server IP or hostname> (链接远程服务器)

option参数解释:
<none> to print same info as Solaris pmap
-heap 打印java heap摘要
-histo[:live] 打印堆中的 java对象统计信息
-clstats 打印类加载器统计信息
-finalizerinfo 打印在f-queue中等待执行finalizer方法的对象
-dump:<dump-options> 生成java堆的dump文件
      dump-options:
      live 只转储存活的对象,如果没有指定则转储所有对象
      format=b 二进制格式
      file=<file> 转储文件到 <file>
-F 强制选项

四、多线程并发篇

1、进程线程区别,线程安全和非线程安全区别

​ 进程是程序的运行过程,是资源分配的基本单位,进程中可以包含多个线程,多个线程共享进程中堆、方法区资源

​ 线程是cpu任务调度的最小执行单位,每个线程拥有自己独立的程序计数器、虚拟机栈、本地方法栈

线程安全:多个线程对同一资源操作,不会互相影响

非线程安全:多个线程对同一资源操作,会互相影响

2、线程状态,start,run,wait,notify,yiled,sleep,join等方法的作用以及区别

线程状态:创建、就绪、运行、阻塞、死亡

方法 作用 区别
start 启动线程,由虚拟机自动调度执行run()方法 线程处于就绪状态
run 线程逻辑代码块处理,JVM调度执行 线程处于运行状态
sleep 让当前正在执行的线程休眠(暂停执行) 不释放锁
wait 使得当前线程等待 释放同步锁
notify 唤醒在此对象监视器上等待的单个线程 唤醒单个线程
notifyAll 唤醒在此对象监视器上等待的所有线程 唤醒单多线程
yiled 停止当前线程,让同等优先权的线程运行 用Thread类调用
join 使当前线程停下来等待,直至另一个调用join方法的线程终止 用线程对象调用

3、wait,notify,notifyAll阻塞唤醒确切过程?

在哪阻塞,在哪唤醒?为什么要出现在同步代码块中?

阻塞:

​ 这三个方法的调用都会使当前线程阻塞。该线程将会被放置到对该Object的请求等待队列中,然后让出当前对Object所拥有的所有的同步请求。线程会一直暂停所有线程调度,直到下面其中一种情况发生:

    ① 其他线程调用了该Object的notify方法,而该线程刚好是那个被唤醒的线程;

    ② 其他线程调用了该Object的notifyAll方法;

唤醒:

​ 线程将会从等待队列中移除,重新成为可调度线程。它会与其他线程以常规的方式竞争对象同步请求。一旦它重新获得对象的同步请求,所有之前的请求状态都会恢复,也就是线程调用wait的地方的状态。线程将会在之前调用wait的地方继续运行下去。

原因:

​ 由于wait()属于Object方法,调用之后会强制释放当前对象锁,所以在wait() 调用时必须拿到当前对象的监视器monitor对象。因此,wait()方法在同步方法/代码块中调用。

4、守护线程,线程中断

守护线程:

​ t.setDaemon(true)为守护线程,也叫精灵线程,若主线程启动t线程,则t线程是主线程的守护线程,当主线程执行完了,则守护线程也随之结束。

public class ThreadDaemon extends Thread{

    public ThreadDaemon(String name){
        super(name);
    }

    @Override
    public void run() {
        while(true){
            System.out.println(Thread.currentThread().getName() + "线程运行了。。。");
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args) {
        Thread t1 = new ThreadDaemon("线程一");
        Thread t2 = new ThreadDaemon("线程二");
        //设置为守护线程
        t1.setDaemon(true);
        t2.setDaemon(true);
        //启动线程
        t1.start();
        t2.start();
        //主线程2s后退出
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }


}

线程中断:

​ t.interrupt();调用interrupt()不会让线程立即中断,只是线程的中断状态发生变化,系统会在后续中断该线程

public class ThreadInterrupt extends Thread{

    public ThreadInterrupt(String name){
        super(name);
    }

    @Override
    public void run() {
        while(!interrupted()){//中断状态判断
            System.err.println(Thread.currentThread().getName() + "线程运行了。。。");
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args) {
        Thread t1 = new ThreadInterrupt("线程一");
        Thread t2 = new ThreadInterrupt("线程二");
        //启动线程
        t1.start();
        t2.start();
        t1.interrupt();
    }


}

5、Java乐观锁机制,CAS思想?缺点?是否原子性?如何保证?

java乐观锁机制:

​ 乐观锁体现的是悲观锁的反面。它是一种积极的思想,它总是认为数据是不会被修改的,所以是不会对数据上锁的。但是乐观锁在更新的时候会去判断数据是否被更新过。乐观锁的实现方案一般有两种(版本号机制和CAS)。乐观锁适用于读多写少的场景,这样可以提高系统的并发量。在Java中 java.util.concurrent.atomic下的原子变量类就是使用了乐观锁的一种实现方式CAS实现的。

  乐观锁,大多是基于数据版本 (Version)记录机制实现。即为数据增加一个版本标识,在基于数据库表的版本解决方案中,一般是通过为数据库表增加一个 “version” 字段来 实现。 读取出数据时,将此版本号一同读出,之后更新时,对此版本号加一。此时,将提 交数据的版本数据与数据库表对应记录的当前版本信息进行比对,如果提交的数据 版本号大于数据库表当前版本号,则予以更新,否则认为是过期数据。

CAS思想:

​ CAS就是compare and swap(比较交换),是一种很出名的无锁的算法,就是可以不使用锁机制实现线程间的同步。使用CAS线程是不会被阻塞的,所以又称为非阻塞同步。CAS算法涉及到三个操作:

​ 需要读写内存值V;

​ 进行比较的值A;

​ 准备写入的值B

​ 当且仅当V的值等于A的值等于V的值的时候,才用B的值去更新V的值,否则不会执行任何操作(比较和替换是一个原子操作-A和V比较,V和B替换),一般情况下是一个自旋操作,即不断重试

缺点:

ABA问题-知乎

​ 高并发的情况下,很容易发生并发冲突,如果CAS一直失败,那么就会一直重试,浪费CPU资源

原子性:

​ 功能限制CAS是能保证单个变量的操作是原子性的,在Java中要配合使用volatile关键字来保证线程的安全;当涉及到多个变量的时候CAS无能为力;除此之外CAS实现需要硬件层面的支持,在Java的普通用户中无法直接使用,只能借助atomic包下的原子类实现,灵活性受到了限制

6、synchronized使用方法?底层实现?

使用方法:主要的三种使⽤⽅式

修饰实例⽅法: 作⽤于当前对象实例加锁,进⼊同步代码前要获得当前对象实例的锁

修饰静态⽅法: 也就是给当前类加锁,会作⽤于类的所有对象实例,因为静态成员不属于任何⼀个实例对象,是类成员( static 表明这是该类的⼀个静态资源,不管new了多少个对象,只有⼀份)。所以如果⼀个线程A调⽤⼀个实例对象的⾮静态 synchronized ⽅法,⽽线程B需要调⽤这个实例对象所属类的静态 synchronized ⽅法,是允许的,不会发⽣互斥现象,因为访问静态synchronized ⽅法占⽤的锁是当前类的锁,⽽访问⾮静态 synchronized ⽅法占⽤的锁是当前实例对象锁。

修饰代码块: 指定加锁对象,对给定对象加锁,进⼊同步代码库前要获得给定对象的锁。

总结:synchronized锁住的资源只有两类:一个是对象,一个是

底层实现:

​ 对象头是我们需要关注的重点,它是synchronized实现锁的基础,因为synchronized申请锁、上锁、释放锁都与对象头有关。对象头主要结构是由Mark WordClass Metadata Address组成,其中Mark Word存储对象的hashCode、锁信息或分代年龄或GC标志等信息Class Metadata Address是类型指针指向对象的类元数据,JVM通过该指针确定该对象是哪个类的实例

​ 锁也分不同状态,JDK6之前只有两个状态:无锁、有锁(重量级锁),而在JDK6之后对synchronized进行了优化,新增了两种状态,总共就是四个状态:无锁状态、偏向锁、轻量级锁、重量级锁,其中无锁就是一种状态了。锁的类型和状态在对象头Mark Word中都有记录,在申请锁、锁升级等过程中JVM都需要读取对象的Mark Word数据。

​ 每一个锁都对应一个monitor对象,在HotSpot虚拟机中它是由ObjectMonitor实现的(C++实现)。每个对象都存在着一个monitor与之关联,对象与其monitor之间的关系有存在多种实现方式,如monitor可以与对象一起创建销毁或当线程试图获取对象锁时自动生成,但当一个monitor被某个线程持有后,它便处于锁定状态。

7、ReenTrantLock使用方法?底层实现?和synchronized区别?

​ 由于ReentrantLock是java.util.concurrent包下提供的一套互斥锁,相比Synchronized,ReentrantLock类提供了一些高级功能,主要有以下三项:

    1.等待可中断,持有锁的线程长期不释放的时候,正在等待的线程可以选择放弃等待,这相当于Synchronized来说可以避免出现死锁的情况。通过lock.lockInterruptibly()来实现这个机制。

    2.公平锁,多个线程等待同一个锁时,必须按照申请锁的时间顺序获得锁,Synchronized锁非公平锁,ReentrantLock默认的构造函数是创建的非公平锁,可以通过参数true设为公平锁,但公平锁表现的性能不是很好。
    3.锁绑定多个条件,一个ReentrantLock对象可以同时绑定对个对象。ReenTrantLock提供了一个Condition(条件)类,用来实现分组唤醒需要唤醒的线程们,而不是像synchronized要么随机唤醒一个线程要么唤醒全部线程。

使用方法:

​ 基于API层面的互斥锁,需要lock()和unlock()方法配合try/finally语句块来完成

底层实现:

​ ReenTrantLock的实现是一种自旋锁,通过循环调用CAS操作来实现加锁。它的性能比较好也是因为避免了使线程进入内核态的阻塞状态。想尽办法避免线程进入内核的阻塞状态是我们去分析和理解锁设计的关键钥匙。

和synchronized区别:

​ 1、底层实现上来说,synchronized 是JVM层面的锁,是Java关键字,通过monitor对象来完成(monitorenter与monitorexit),对象只有在同步块或同步方法中才能调用wait/notify方法;ReentrantLock 是从jdk1.5以来(java.util.concurrent.locks.Lock)提供的API层面的锁。synchronized 的实现涉及到锁的升级,具体为无锁、偏向锁、自旋锁、向OS申请重量级锁;ReentrantLock实现则是通过利用CAS(CompareAndSwap)自旋机制保证线程操作的原子性和volatile保证数据可见性以实现锁的功能。

​ 3、是否可手动释放:synchronized 不需要用户去手动释放锁,synchronized 代码执行完后系统会自动让线程释放对锁的占用; ReentrantLock则需要用户去手动释放锁,如果没有手动释放锁,就可能导致死锁现象。一般通过lock()和unlock()方法配合try/finally语句块来完成,使用释放更加灵活。

​ 4、是否可中断synchronized是不可中断类型的锁,除非加锁的代码中出现异常或正常执行完成; ReentrantLock则可以中断,可通过trylock(long timeout,TimeUnit unit)设置超时方法或者将lockInterruptibly()放到代码块中,调用interrupt方法进行中断。

​ 5、是否公平锁synchronized为非公平锁 ReentrantLock则即可以选公平锁也可以选非公平锁,通过构造方法new ReentrantLock时传入boolean值进行选择,为空默认false非公平锁,true为公平锁。

8、公平锁和非公平锁区别?为什么公平锁效率低?

公平锁:

​ 公平锁自然是遵循FIFO(先进先出)原则的,先到的线程会优先获取资源,后到的会进行排队等待

优点:所有的线程都能得到资源,不会饿死在队列中。

缺点:吞吐量会下降,队列里面除了第一个线程,其他的线程都会阻塞,cpu唤醒阻塞线程的开销大

非公平锁:

​ 多个线程去获取锁的时候,会直接去尝试获取,获取不到,再去进入等待队列,如果能获取到,就直接获取到锁。

优点:可以减少CPU唤醒线程的开销,整体的吞吐效率会高点,CPU也不必取唤醒所有线程,会减少唤起线程的数量。

缺点:你们可能也发现了,这样可能导致队列中间的线程一直获取不到锁或者长时间获取不到锁

公平锁效率低原因:

​ 公平锁要维护一个队列,后来的线程要加锁,即使锁空闲,也要先检查有没有其他线程在 wait,如果有自己要挂起,加到队列后面,然后唤醒队列最前面线程。这种情况下相比较非公平锁多了一次挂起和唤醒

线程切换的开销,其实就是非公平锁效率高于公平锁的原因,因为非公平锁减少了线程挂起的几率,后来的线程有一定几率逃离被挂起的开销。

9、锁优化。自旋锁、自适应自旋锁、锁消除、锁粗化、偏向锁、轻量级锁、重量级锁解释

锁优化:

​ 【1】减少锁的时间:
​ 不需要同步执行的代码,能不放在同步快里面执行就不要放在同步快内,可以让锁尽快释放;

​ 【2】减少锁的粒度:
​ 它的思想是将物理上的一个锁,拆成逻辑上的多个锁,增加并行度,从而降低锁竞争。它的思想也是用空间来换时间;java中很多数据结构都是采用这种方法提高并发操作的效率,比如:

ConcurrentHashMap:

​ java中的ConcurrentHashMap在jdk1.8之前的版本,使用一个Segment 数组:Segment< K,V >[] segments

​ Segment继承自ReenTrantLock,所以每个Segment是个可重入锁,每个Segment 有一个HashEntry< K,V >数组用来存放数据,put操作时,先确定往哪个Segment放数据,只需要锁定这个Segment,执行put,其它的Segment不会被锁定;所以数组中有多少个Segment就允许同一时刻多少个线程存放数据,这样增加了并发能力。

Segment继承自ReenTrantLock,所以每个Segment就是个可重入锁,每个Segment 有一个HashEntry< K,V >数组用来存放数据,put操作时,先确定往哪个Segment放数据,只需要锁定这个Segment,执行put,其它的Segment不会被锁定;所以数组中有多少个Segment就允许同一时刻多少个线程存放数据,这样增加了并发能力。

​ 【3】锁粗化:
​ 大部分情况下我们是要让锁的粒度最小化,锁的粗化则是要增大锁的粒度;

​ 在以下场景下需要粗化锁的粒度:

​ 假如有一个循环,循环内的操作需要加锁,我们应该把锁放到循环外面,否则每次进出循环,都进出一次临界区,效率是非常差的;

​ 【4】使用读写锁:

​ ReentrantReadWriteLock 是一个读写锁,读操作加读锁,可并发读,写操作使用写锁,只能单线程写;

​ 【5】使用cas:

​ 如果需要同步的操作执行速度非常快,并且线程竞争并不激烈,这时候使用cas效率会更高,因为加锁会导致线程的上下文切换,如果上下文切换的耗时比同步操作本身更耗时,且线程对资源的竞争不激烈,使用volatiled+cas操作会是非常高效的选择;

自旋锁:

​ 自旋锁原理非常简单,如果持有锁的线程能在很短时间内释放锁资源,那么那些等待竞争锁的线程就不需要做内核态和用户态之间的切换进入阻塞挂起状态,它们只需要等一等(自旋),等持有锁的线程释放锁后即可立即获取锁,这样就避免用户线程和内核的切换的消耗

缺点:如果锁被其他线程长时间占用,一直不释放CPU,会带来许多的性能开销;自旋次数默认值是10

自适应自旋锁:

​ 对上面自旋锁优化方式的进一步优化,它的自旋的次数不再固定,其自旋的次数由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定,这就解决了自旋锁带来的缺点

锁消除:

​ 锁削除是指虚拟机即时编译器在运行时,对一些代码上要求同步,但是被检测到不可能存在共享数据竞争的锁进行削除。

锁粗化:

​ 假如有一个循环,循环内的操作需要加锁,我们应该把锁放到循环外面,否则每次进出循环,都进出一次临界区,效率是非常差的;

偏向锁:

​ 所谓的偏向,就是偏心,即锁会偏向于当前已经占有锁的线程;也就是说,这个线程已经占有这个锁,当他在次试图去获取这个锁的时候,他会已最快的方式去拿到这个锁,而不需要在进行一些monitor操作,因此这方面他是会对性能有所提升的,因为在大部分情况下是没有竞争的,所以锁此时是没用的,所以使用偏向锁是可以提高性能的;

重量级锁:

​ 重量级锁的加锁、解锁过程和轻量级锁差不多,区别是:竞争失败后,线程阻塞,释放锁后,唤醒阻塞的线程,不使用自旋锁,不会那么消耗CPU,所以重量级锁适合用在同步块执行时间长的情况下。

10、Java内存模型

​ Java 内存模型(Java Memory Model,JMM)就是一种符合内存模型规范的,屏蔽了各种硬件和操作系统的访问差异的,保证了 Java 程序在各种平台下对内存的访问都能保证效果一致的机制及规范。

​ JMM 是一种规范,是解决由于多线程通过共享内存进行通信时,存在的本地内存数据不一致、编译器会对代码指令重排序、处理器会对代码乱序执行等带来的问题。目的是保证并发编程场景中的原子性、可见性和有序性。

​ 所以,Java 内存模型,除了定义了一套规范,还提供了一系列原语,封装了底层实现后,供开发者直接使用。我们前面提到,并发编程要解决原子性有序性一致性的问题。

原子性:

​ 在 Java 中,为了保证原子性,提供了两个高级的字节码指令 Monitorenter 和 Monitorexit。这两个字节码,在 Java 中对应的关键字就是 Synchronized。因此,在 Java 中可以使用 Synchronized 来保证方法和代码块内的操作是原子性的。

可见性:

​ Java 内存模型是通过在变量修改后将新值同步回主内存,在变量读取前从主内存刷新变量值的这种依赖主内存作为传递媒介的方式来实现的。Java 中的 Volatile 关键字修饰的变量在被修改后可以立即同步到主内存。被其修饰的变量在每次使用之前都从主内存刷新。因此,可以使用 Volatile 来保证多线程操作时变量的可见性。除了 Volatile,Java 中的 Synchronized 和 Final 两个关键字也可以实现可见性。只不过实现方式不同

有序性

​ 在 Java 中,可以使用 Synchronized 和 Volatile 来保证多线程之间操作的有序性。区别:Volatile 禁止指令重排。Synchronized 保证同一时刻只允许一条线程操作。

11、volatile作用?底层实现?单例模式中volatile的作用?

作用:

​ 保证数据的“可见性”:被volatile修饰的变量能够保证每个线程能够获取该变量的最新值,从而避免出现数据脏读的现象。

​ 禁止指令重排:在多线程操作情况下,指令重排会导致计算结果不一致

底层实现:

​ “观察加入volatile关键字和没有加入volatile关键字时所生成的汇编代码发现,加入volatile关键字时,会多出一个lock前缀指令”

  lock前缀指令实际上相当于一个内存屏障(也成内存栅栏),内存屏障会提供3个功能:

  1)它确保指令重排序时不会把其后面的指令排到内存屏障之前的位置,也不会把前面的指令排到内存屏障的后面;即在执行到内存屏障这句指令时,在它前面的操作已经全部完成;

  2)它会强制将对缓存的修改操作立即写入主存;

  3)如果是写操作,它会导致其他CPU中对应的缓存行无效。

单例模式中volatile的作用:

防止代码读取到instance不为null时,instance引用的对象有可能还没有完成初始化。

class Singleton{
    private volatile static Singleton instance = null;   //禁止指令重排
    private Singleton() {

    }
    public static Singleton getInstance() {
        if(instance==null) {
            synchronized (Singleton.class) {
                if(instance==null)
                    instance = new Singleton();
            }
        }
        return instance;
    }
}

12、AQS思想,以及基于AQS实现的lock, CountDownLatch、CyclicBarrier、Semaphore介绍

​ AQS的全称为(AbstractQueuedSynchronizer)抽象的队列式的同步器,是⼀个⽤来构建锁和同步器的框架,使⽤AQS能简单且⾼效地构造出应⽤⼴泛的⼤量的同步器,如:基于AQS实现的lock, CountDownLatch、CyclicBarrier、Semaphore

​ AQS核⼼思想是,如果被请求的共享资源空闲,则将当前请求资源的线程设置为有效的⼯作线程,并且将共享资源设置为锁定状态。如果被请求的共享资源被占⽤,那么就需要⼀套线程阻塞等待以及被唤醒时锁分配的机制,这个机制AQS是⽤CLH(虚拟的双向队列)队列锁实现的,即将暂时获取不到锁的线程加⼊到队列中。

lock:

​ 是一种可重入锁,除了能完成 synchronized 所能完成的所有工作外,还提供了诸如可响应中断锁、可轮询锁请求、定时锁等避免多线程死锁的方法。默认为非公平锁,但可以初始化为公平锁; 通过方法 lock()与 unlock()来进行加锁与解锁操作;

CountDownLatch:

​ 通过计数法(倒计时器),让一些线程堵塞直到另一个线程完成一系列操作后才被唤醒;该⼯具通常⽤来控制线程等待,它可以让某⼀个线程等待直到倒计时结束,再开始执⾏。

​ 假设我们有这么一个场景,教室里有班长和其他6个人在教室上自习,怎么保证班长等其他6个人都走出教室在把教室门给关掉。

public class CountDownLanchDemo {
    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) {
            new Thread(() -> {
                System.out.println(Thread.currentThread().getName() + " 离开了教室...");
            }, String.valueOf(i)).start();
        }
        System.out.println("班长把门给关了,离开了教室...");
    }
}

此时输出:

0 离开了教室...
1 离开了教室...
2 离开了教室...
3 离开了教室...
班长把门给关了,离开了教室...
5 离开了教室...
4 离开了教室...

发现班长都没有等其他人理他教室就把门给关了,此时我们就可以使用 CountDownLatch 来控制

public class CountDownLanchDemo {
    public static void main(String[] args) throws InterruptedException {
        CountDownLatch countDownLatch = new CountDownLatch(6);
        for (int i = 0; i < 6; i++) {
            new Thread(() -> {
                countDownLatch.countDown();
                System.out.println(Thread.currentThread().getName() + " 离开了教室...");
            }, String.valueOf(i)).start();
        }
        countDownLatch.await();
        System.out.println("班长把门给关了,离开了教室...");
    }
}

此时输出:

0 离开了教室...
1 离开了教室...
2 离开了教室...
3 离开了教室...
4 离开了教室...
5 离开了教室...
班长把门给关了,离开了教室...

CyclicBarrier:

​ 字面意思是可循环(Cyclic)使用的屏障(Barrier)。他要做的事情是,让一组线程到达一个屏障(也可以叫同步点)时被阻塞,直到最后一个线程到达屏障时,屏障才会开门,所有被屏障拦截的线程才会继续干活,线程进入屏障通过CyclicBarrier的await()方法。

我们假设有这么一个场景,每辆车只能坐4个人,当车满了,就发车。

public class CyclicBarrierDemo {
    public static void main(String[] args) {
        CyclicBarrier cyclicBarrier = new CyclicBarrier(4, () -> {
            System.out.println("车满了,开始出发...");
        });
        for (int i = 0; i < 8; i++) {
            new Thread(() -> {
                System.out.println(Thread.currentThread().getName() + " 开始上车...");
                try {
                    cyclicBarrier.await();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } catch (BrokenBarrierException e) {
                    e.printStackTrace();
                }
            }).start();
        }
    }
}

输出结果:

Thread-0 开始上车...
Thread-1 开始上车...
Thread-3 开始上车...
Thread-4 开始上车...
车满了,开始出发...
Thread-5 开始上车...
Thread-7 开始上车...
Thread-2 开始上车...
Thread-6 开始上车...
车满了,开始出发...

Semaphore:

​ 信号量主要用于两个目的,一个是用于多个共享资源的互斥作用,另一个用于并发线程数的控制。

假设我们有 3 个停车位,6 辆车去抢;指定多个线程同时访问某个资源。

public class SemaphoreDemo {
  public static void main(String[] args) {
      Semaphore semaphore = new Semaphore(3);
      for (int i = 0; i < 6; i++) {
          new Thread(() -> {
              try {
                  semaphore.acquire(); // 获取一个许可
                  System.out.println(Thread.currentThread().getName() + " 抢到车位...");
                  Thread.sleep(3000);
                  System.out.println(Thread.currentThread().getName() + " 离开车位");
              } catch (InterruptedException e) {
                  e.printStackTrace();
              } finally {
                  semaphore.release(); // 释放一个许可
              }
          }).start();
      }
  }
}

/**输出
Thread-1 抢到车位...
Thread-2 抢到车位...
Thread-0 抢到车位...
Thread-2 离开车位
Thread-0 离开车位
Thread-3 抢到车位...
Thread-1 离开车位
Thread-4 抢到车位...
Thread-5 抢到车位...
Thread-3 离开车位
Thread-5 离开车位
Thread-4 离开车位
*/

13、线程池构造函数7大参数,线程处理任务过程,线程拒绝策略

/**
* 线程池构造函数7大参数
*/
public ThreadPoolExecutor(int corePoolSize,int maximumPoolSize,long keepAliveTime,
    TimeUnit unit,BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,
    RejectedExecutionHandler handler) {
        if (corePoolSize < 0 ||maximumPoolSize <= 0 ||maximumPoolSize < corePoolSize ||
                keepAliveTime < 0)
             throw new IllegalArgumentException();
        if (workQueue == null || threadFactory == null || handler == null)
            throw new NullPointerException();
        this.corePoolSize = corePoolSize;
           this.maximumPoolSize = maximumPoolSize;
        this.workQueue = workQueue;
        this.keepAliveTime = unit.toNanos(keepAliveTime);
        this.threadFactory = threadFactory;
        this.handler = handler;
}

参数介绍:

参数 作用
corePoolSize 核心线程池大小
maximumPoolSize 最大线程池大小
keepAliveTime 线程池中超过 corePoolSize 数目的空闲线程最大存活时间;可以allowCoreThreadTimeOut(true) 使得核心线程有效时间
TimeUnit keepAliveTime 时间单位
workQueue 阻塞任务队列
threadFactory 新建线程工厂
RejectedExecutionHandler 拒绝策略。当提交任务数超过 maxmumPoolSize+workQueue 之和时,任务会交给RejectedExecutionHandler 来处理

线程拒绝策略:

​ 线程池中的线程已经用完了,无法继续为新任务服务,同时,等待队列也已经排满了,再也塞不下新任务了。这时候我们就需要拒绝策略机制合理的处理这个问题。

JDK 内置的拒绝策略如下:

AbortPolicy:直接抛出异常,阻止系统正常运行。

CallerRunsPolicy :只要线程池未关闭,该策略直接在调用者线程中,运行当前被丢弃的任务。显然这样做不会真的丢弃任务,但是,任务提交线程的性能极有可能会急剧下降。

DiscardOldestPolicy :丢弃最老的一个请求,也就是即将被执行的任务,并尝试再次提交当前任务。

DiscardPolicy :该策略默默地丢弃无法处理的任务,不予任何处理。如果允许任务丢失,这是最好的一种方案。

线程处理任务过程:

  1. 当线程池小于corePoolSize,新提交任务将创建一个新线程执行任务,即使此时线程池中存在空闲线程。
  2. 当线程池达到corePoolSize时,新提交任务将被放入 workQueue 中,等待线程池中任务调度执行。
  3. 当workQueue已满,且 maximumPoolSize 大于 corePoolSize 时,新提交任务会创建新线程执行任务。
  4. 当提交任务数超过 maximumPoolSize 时,新提交任务由 RejectedExecutionHandler 处理。
  5. 当线程池中超过corePoolSize 线程,空闲时间达到 keepAliveTime 时,关闭空闲线程 。

14、Execuors类实现的几种线程池类型,阿里为啥不让用?

  • Executors.newSingleThreadExecutor():只有一个线程的线程池,因此所有提交的任务是顺序执行,适用于一个一个任务执行的场景
  • Executors.newCachedThreadPool():线程池里有很多线程需要同时执行,老的可用线程将被新的任务触发重新执行,如果线程超过60秒内没执行,那么将被终止并从池中删除,适用执行很多短期异步的小程序或者负载较轻的服务
  • Executors.newFixedThreadPool():拥有固定线程数的线程池,如果没有任务执行,那么线程会一直等待,适用执行长期的任务,性能好很多。
  • Executors.newScheduledThreadPool():用来调度即将执行的任务的线程池

因为以上方式都存在弊端:

​ FixedThreadPool 和 SingleThreadExecutor : 允许请求的队列⻓度为 Integer.MAX_VALUE,可能堆积⼤量的请求,从⽽导致OOM。
​ CachedThreadPool 和 ScheduledThreadPool : 允许创建的线程数量为 Integer.MAX_VALUE,可能会创建⼤量线程,从⽽导致OOM。

15、线程池大小如何设置?

  • CPU 密集型

    • CPU 密集的意思是该任务需要大量的运算,而没有阻塞,CPU 一直全速运行。
    • CPU 密集型任务尽可能的少的线程数量,一般为 CPU 核数 + 1 个线程的线程池。
  • IO 密集型

    • 由于 IO 密集型任务线程并不是一直在执行任务,可以多分配一点线程数,如 CPU * 2
    • 也可以使用公式:CPU 核数 / (1 - 阻塞系数);其中阻塞系数在 0.8 ~ 0.9 之间。

16、手写简单的线程池,体现线程复用

https://blog.csdn.net/hongtaolong/article/details/87808009

17、手写消费者生产者模式

https://www.cnblogs.com/liuqing576598117/p/11233250.html

18、手写阻塞队列

https://www.cnblogs.com/keeya/p/9713686.html

19、手写多线程交替打印ABC

https://blog.csdn.net/xiaokang123456kao/article/details/77331878

五、MySQL篇

1、事务4大特性?这4个特性mysql如何保证实现的?

事务4大特性:原子性、一致性、隔离性、持久性

原⼦性: 事务是最⼩的执⾏单位,不允许分割。事务的原⼦性确保动作要么全部完成,要么全不执行

一致性: 执⾏事务前后,数据保持⼀致,多个事务对同⼀个数据读取的结果是相同的;

隔离性: 并发访问数据库时,⼀个⽤户的事务不被其他事务所⼲扰,各并发事务之间数据库是独⽴的;

持久性: ⼀个事务被提交之后。它对数据库中数据的改变是持久的,即使数据库发⽣故障也不应该对其有任何影响。

实现保证:

​ MySQL的存储引擎InnoDB使用重做日志保证一致性与持久性,回滚日志保证原子性,使用各种锁来保证隔离性。

2、事务隔离级别,4个隔离级别分别有什么并发问题?

读未提交:最低的隔离级别,允许读取尚未提交的数据变更,可能会导致脏读、幻读或不可重复读。

读已提交:允许读取并发事务已经提交的数据,可以阻⽌脏读,但是幻读或不可重复读仍有可能发⽣。

可重复读:同⼀字段的多次读取结果都是⼀致的,除⾮数据是被本身事务⾃⼰所修改,可以阻⽌脏读和不可重复读,但幻读仍有可能发⽣。

可串行化:最⾼的隔离级别,完全服从ACID的隔离级别。所有的事务依次逐个执⾏,这样事务之间就完全不可能产⽣⼲扰,也就是说,该级别可以防⽌脏读、不可重复读以及幻读。

隔离级别 并发问题
读未提交 可能会导致脏读、幻读或不可重复读
读已提交 可能会导致幻读或不可重复读
可重复度 可能会导致幻读
可串行化 不会产⽣⼲扰

3、Mysql默认隔离级别?如何保证并发安全?

默认隔离级别:可重复读;

​ 同⼀字段的多次读取结果都是⼀致的,除⾮数据是被本身事务⾃⼰所修改;

​ 可重复读是有可能出现幻读的,如果要保证绝对的安全只能把隔离级别设置成SERIALIZABLE;这样所有事务都只能顺序执行,自然不会因为并发有什么影响了,但是性能会下降许多。

​ 第二种方式,使用更新的版本控制。维护一个字段作为updateversion,修改时updateversion也作为一个参数传入,在条件语句中添加例如where id=? and update_version = ? 当然set里面要update_version+1。这样可以控制到每次只能有一个人更新一个版本。

4、RR和RC如何实现的?RR使用场景?

​ 事务隔离级别RC(read commit)和RR(repeatable read)两种事务隔离级别基于多版本并发控制MVCC(multi-version concurrency control)来实现。

​ 由于RC隔离级别需要保持语句级别的一致性,事务中每一次读取都是访问当前时间点的已提交数据,因此事务中多条查询语句会创建多个不同的ReadView,开销较大,复杂度更高;而对于RR隔离级别,仅需要一个版本的ReadView,消耗更少,因此Mysql默认使用RR隔离级别。

​ RC隔离级别获得的是语句级读一致性;RR隔离级别获得的是事务级读一致性

​ 对于RC隔离级别,访问的数据是每次语句执行时间点的数据,而对于RR隔离级别,访问的数据是事务中第一条语句执行时间点的数据。

5、隔离级别的单位是数据表还是数据行?如串行化级别,两个事务访问不同的数据行,能并发?

​ 读未提交:不加锁

​ 读已提交:加行锁,只锁要修改的行

​ 可重复读:加行锁,锁定的是查询的行

​ 可串行化:加表锁,在读取的每张表上加锁

串行化级别:读不同的行,可以并发

6、存储引擎Innodb和Myisam的区别以及使用场景

Myisam:支持表锁,适合读密集的场景,不支持外键,不支持事务,索引与数据在不同的文件

Innodb:支持行、表锁,默认为行锁,适合并发场景,支持外键,支持事务,索引与数据同一文件

7、 介绍Inodb锁机制,行锁,表锁,意向锁

InnoDB⽀持⾏级锁(row-level locking)和表级锁,默认为⾏级锁

InnoDB按照不同的分类的锁:

共享/排它锁(Shared and Exclusive Locks):行级别锁,

意向锁(Intention Locks),表级别锁

间隙锁(Gap Locks),锁定一个区间

记录锁(Record Locks),锁定一个行记录

表级锁:

​ Mysql中锁定 粒度最大 的一种锁,对当前操作的整张表加锁,实现简单 ,资源消耗也比较少,加锁快,不会出现死锁 。其锁定粒度最大,触发锁冲突的概率最高,并发度最低,MyISAM和 InnoDB引擎都支持表级锁。

行级锁:

​ Mysql中锁定 粒度最小 的一种锁,只针对当前操作的行进行加锁。 行级锁能大大减少数据库操作的冲突。其加锁粒度最小,并发度高,但加锁的开销也最大,加锁慢,会出现死锁。 InnoDB支持的行级锁,包括如下几种:

记录锁(Record Lock): 对索引项加锁,锁定符合条件的行。其他事务不能修改和删除加锁项;

间隙锁(Gap Lock): 对索引项之间的“间隙”加锁,锁定记录的范围(对第一条记录前的间隙或最后一条将记录后的间隙加锁),不包含索引项本身。其他事务不能在锁范围内插入数据,这样就防止了别的事务新增幻影行。

Next-key Lock: 锁定索引项本身和索引范围。即Record Lock和Gap Lock的结合。可解决幻读问题。

意向锁:

​ 当一个事务在需要获取资源的锁定时,如果该资源已经被排他锁占用,则数据库会自动给该事务申请一个该表的意向锁。如果自己需要一个共享锁定,就申请一个意向共享锁。如果需要的是某行(或者某些行)的排他锁定,则申请一个意向排他锁

8、介绍MVCC.

​ MVCC是一种多版本并发控制机制,在大多数情况下代替行级锁,使用MVCC,能降低其系统开销.

​ MVCC是通过保存数据在某个时间点的快照来实现的. 不同存储引擎的MVCC实现是不同的,典型的有乐观并发控制和悲观并发控制.

​ InnoDB的MVCC,是通过在每行记录后面保存两个隐藏的列来实现的,这两个列,分别保存了这个行的创建时间,一个保存的是行的删除时间。这里存储的并不是实际的时间值,而是系统版本号(可以理解为事务的ID),每开始一个新的事务,系统版本号就会自动递增,事务开始时刻的系统版本号会作为事务的ID.

​ InnoDB只会查找版本早于当前事务版本的数据行(也就是,行的系统版本号小于或等于事务的系统版本号),这样可以确保事务读取的行,要么是在事务开始前已经存在的,要么是事务自身插入或者修改过的.

​ 1.MVCC手段只适用于Msyql隔离级别中的读已提交(Read committed)和可重复读(Repeatable Read).

​ 2.Read uncimmitted由于存在脏读,即能读到未提交事务的数据行,所以不适用MVCC.

​ 原因是MVCC的创建版本和删除版本只要在事务提交后才会产生。客观上,我们认为他就是乐观锁的一整实现方式,就是每行都有版本号,保存时根据版本号决定是否成功。

9、哈希索引是如何实现的?

​ 哈希索引用索引列的值计算该值的hashCode,然后在hashCode相应的位置存执该值所在行数据的物理位置,因为使用散列算法,因此访问速度非常快,但是一个值只能对应一个hashCode,而且是散列的分布方式,因此哈希索引不支持范围查找和排序的功能

10、数据库索引为什么使用B+树,相对于B树有什么优点?为什么不能红黑树?

因为:

​ B+树的磁盘读写代价低,更少的查询次数,查询效率更加稳定,有利于对数据库的扫描

​ 相对B树,B+树是B树的升级版,只是把非叶子节点冗余一下,这么做的好处是为了提高范围查找的效率,解决数据库遍历效率低下问题B+树只有叶节点存放数据,其余节点用来索引,而B树是每个索引节点都会有Data域。

​ 在大规模数据存储的时候,红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低下的情况。所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,B树与B+树可以有多个子女,从几十到上千,可以降低树的高度。

磁盘预读原理:将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

11、聚簇索引和非聚簇索引区别

聚簇索引:将数据存储与索引放到了一块,索引结构的叶子节点保存了行数据

非聚簇索引:将数据与索引分开存储,索引结构的叶子节点指向了数据对应的位置

​ 聚簇索引的叶子节点就是数据节点,而非聚簇索引的叶子节点仍然是索引节点,只不过有指向对应数据块的指针。

12、回表查询和覆盖索引

普通索引 需要扫描两遍索引树

(1)先通过普通索引定位到主键值id=5;

(2)在通过聚集索引定位到行记录;

这就是所谓的回表查询,先定位主键值,再定位行记录,它的性能较扫一遍索引树更低。

覆盖索引:如果where条件的列和返回的数据在一个索引中,那么不需要回查表,那么就叫覆盖索引。

实现覆盖索引:常见的方法是,将被查询的字段,建立到联合索引里去。

13、如何创建索引?

CREATE TABLE 表名(
    字段名 数据类型 [完整性约束条件],
       ……,
    [UNIQUE | FULLTEXT | SPATIAL] INDEX | KEY
    [索引名](字段名1 [(长度)] [ASC | DESC]) [USING 索引方法]
);

说明:
UNIQUE:可选。表示索引为唯一性索引。
FULLTEXT:可选。表示索引为全文索引。
SPATIAL:可选。表示索引为空间索引。
INDEX和KEY:用于指定字段为索引,两者选择其中之一就可以了,作用是一样的。
索引名:可选。给创建的索引取一个新名称。
字段名1:指定索引对应的字段的名称,该字段必须是前面定义好的字段。
长度:可选。指索引的长度,必须是字符串类型才可以使用。
ASC:可选。表示升序排列。
DESC:可选。表示降序排列。
注:索引方法默认使用B+TREE。

ALTER TABLE 表名 ADD [UNIQUE | FULLTEXT | SPATIAL]  INDEX | KEY  [索引名] (字段名1 [(长度)] [ASC | DESC]) [USING 索引方法];

或

CREATE  [UNIQUE | FULLTEXT | SPATIAL]  INDEX  索引名 ON  表名(字段名) [USING 索引方法];

14、如何避免全表扫描?

1.对查询进行优化,应考虑在 where 及 order by 涉及的列上建立索引。

2.应尽量避免在 where 子句中对字段进行 null 值判断

3.应尽量避免在 where 子句中使用!=或<>操作符

4.in 和 not in 要慎用

否则将导致引擎放弃使用索引而进行全表扫描

15、Explain语句各字段的意义

参考:https://www.jianshu.com/p/8fab76bbf448

mysql> explain select * from staff;
+----+-------------+-------+------+---------------+------+---------+------+------+-------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+------+-------+
|  1 | SIMPLE      | staff | ALL  | NULL          | NULL | NULL    | NULL |    2 | NULL  |
+----+-------------+-------+------+---------------+------+---------+------+------+-------+
1 row in set
含义
id 查询序号,序号越大越先执行,一样则按顺序执行
select_type 查询类型,SIMPLE、PRIMARY、UNION、SUBQUERY等
table 表名
type join类型,const,eq_ref,ref等
possible_keys join类型
key 实际选择的索引
ken_len 索引的长度
ref 与索引作比较的列
rows 要检索的行数
Extra 额外信息

*16、最左前缀!!联合索引B+树是如何建立的?是如何查询的?当where子句中出现>时,联合索引命中是如何的? *

​ 最左前缀原则主要使用在联合索引中,联合索引的B+Tree是按照第一个关键字进行索引排列的。

​ 联合索引的底层是一颗B+树,那么联合索引的底层也就是一颗B+树,只不过联合索引的B+树节点中存储的是键值。由于构建一棵B+树只能根据一个值来确定索引关系,所以数据库依赖联合索引最左的字段来构建。

​ 采用>、<等进行匹配都会导致后面的列无法走索引,因为通过以上方式匹配到的数据是不可知的。

17、MySQL中一条SQL语句的执行过程

参考:https://zhuanlan.zhihu.com/p/126722329

查询语句:

select * from student  A where A.age='18' and A.name='张三';

结合上面的说明,我们分析下这个语句的执行流程:

  • 先检查该语句是否有权限,如果没有权限,直接返回错误信息,如果有权限,在mysql8.0版本以前,会先查询缓存,以这条sql语句为key在内存中查询是否有结果,如果有直接缓存,如果没有,执行下一步。
  • 通过分析器进行词法分析,提取sql语句的关键元素,比如提取上面这个语句是查询select,提取需要查询的表名为tb_student,需要查询所有的列,查询条件是这个表的id='1'。然后判断这个sql语句是否有语法错误,比如关键词是否正确等等,如果检查没问题就执行下一步。
  • 接下来就是优化器进行确定执行方案,上面的sql语句,可以有两种执行方案: a.先查询学生表中姓名为“张三”的学生,然后判断是否年龄是18。 b.先找出学生中年龄18岁的学生,然后再查询姓名为“张三”的学生。 那么优化器根据自己的优化算法进行选择执行效率最好的一个方案(优化器认为,有时候不一定最好)。那么确认了执行计划后就准备开始执行了。
  • 进行权限校验,如果没有权限就会返回错误信息,如果有权限就会调用数据库引擎接口,返回引擎的执行结果。

更新语句:

update student A set A.age='19' where A.name='张三';

我们来给张三修改下年龄,在实际数据库肯定不会设置年龄这个字段的,不然要被技术负责人打的。其实这条语句也基本上会沿着上一个查询的流程走,只不过执行更新的时候肯定要记录日志啦,这就会引入日志模块了,mysql 自带的日志模块式binlog(归档日志),所有的存储引擎都可以使用,我们常用的InnoDB引擎还自带了一个日志模块redo log,我们就以InnoDB模式下来探讨这个语句的执行流程。流程如下:

  • 先查询到张三这一条数据,如果有缓存,也是会用到缓存。
  • 然后拿到查询的语句,把 age 改为19,然后调用引擎API接口,写入这一行数据,InnoDB引擎把数据保存在内存中,同时记录redo log,此时redo log进入prepare状态,然后告诉执行器,执行完成了,随时可以提交。
  • 执行器收到通知后记录binlog,然后调用引擎接口,提交redo log 为提交状态。
  • 更新完成。

18、数据库几大范式

参考:数据库范式

第一范式(1NF)列不可分割

第二范式(2NF)属性完全依赖于主键 [ 消除部分子函数依赖 ]

第三范式(3NF)属性不依赖于其它非主属性 [ 消除传递依赖 ]

19、left join,right join,inner join,outer join的含义及区别

left join(左联接) 返回包括左表中的所有记录和右表中关联字段相等的记录

right join(右联接) 返回包括右表中的所有记录和左表中关联字段相等的记录

inner join(等值连接) 只返回两个表中关联字段相等的行

20、mysql主从复制过程,binlog记录格式,异步复制、同步复制、半同步复制模式区别

MySQl主从复制:

  • 原理:将主服务器的binlog日志复制到从服务器上执行一遍,达到主从数据的一致状态。
  • 过程:从库开启一个I/O线程,向主库请求Binlog日志。主节点开启一个binlog dump线程,检查自己的二进制日志,并发送给从节点;从库将接收到的数据保存到中继日志(Relay log)中,另外开启一个SQL线程,把Relay中的操作在自身机器上执行一遍
  • 优点
    • 作为备用数据库,并且不影响业务
    • 可做读写分离,一般是一个写库,一个或多个读库,分布在不同的服务器上,充分发挥服务器和数据库的性能,但要保证数据的一致性

binlog记录格式:statement、row、mixed

​ 基于语句statement的复制、基于行row的复制、基于语句和行(mix)的复制。其中基于row的复制方式更能保证主从库数据的一致性,但日志量较大,在设置时考虑磁盘的空间问题

异步复制:

​ 在异步复制中,主库执行完操作后,写入binlog日志后,就返回客户端,这一动作就结束了,并不会验证从库有没有收到,完不完整,所以这样可能会造成数据的不一致。

半同步复制:

​ 当主库每提交一个事务后,不会立即返回,而是等待其中一个从库接收到Binlog并成功写入Relay-log中才返回客户端,所以这样就保证了一个事务至少有两份日志,一份保存在主库的Binlog,另一份保存在其中一个从库的Relay-log中,从而保证了数据的安全性和一致性。

全同步复制:

​ 指当主库执行完一个事务,所有的从库都执行了该事务才返回给客户端。因为需要等待所有从库执行完该事务才能返回,所以全同步复制的性能必然会收到严重的影响。

21、主从复制或读写分离等数据不一致性问题以及如何解决

"主从复制有延时",这个延时期间读取从库,可能读到不一致的数据。

半同步复制法:

​ 当主库每提交一个事务后,不会立即返回,而是等待其中一个从库接收到Binlog并成功写入Relay-log中才返回客户端,所以这样就保证了一个事务至少有两份日志,一份保存在主库的Binlog,另一份保存在其中一个从库的Relay-log中,从而保证了数据的安全性和一致性。

全同步复制法:

​ 指当主库执行完一个事务,所有的从库都执行了该事务才返回给客户端。因为需要等待所有从库执行完该事务才能返回,所以全同步复制的性能必然会收到严重的影响。

缓存记录写key法:

​ 在cache里记录哪些记录发生过的写请求,来路由读主库还是读从库

22、银行的话,可能会考mysql数据类型,如余额要用decimal

六、Redis篇

1、为什么使用Redis

​ 速度快,完全基于内存,使用C语言实现,网络层使用epoll解决高并发问题,单线程模型避免了不必要的上下文切换及竞争条件;

​ 与传统数据库不同的是 Redis 的数据是存在内存中的,所以读写速度非常快,因此 redis 被广泛应用于缓存方向,每秒可以处理超过 10万次读写操作,是已知性能最快的Key-Value DB。另外,Redis 也经常用来做分布式锁。除此之外,Redis 支持事务 、持久化、LUA脚本、LRU驱动事件、多种集群方案。

2、分布式缓存和本地缓存有啥区别?让你自己设计本地缓存怎么设计?如何解决缓存过期问题?如何解决内存溢出问题?

​ 分布式缓存一致性更好一点,用于集群环境下多节点使用同一份缓存的情况;有网络IO,吞吐率与缓存的数据大小有较大关系;

​ 本地缓存非常高效,本地缓存会占用堆内存,影响垃圾回收、影响系统性能。

本地缓存设计:

​ 以 Java 为例,使用自带的 map 或者 guava 实现的是本地缓存,最主要的特点是轻量以及快速,生命周期随着 jvm 的销毁而结束,并且在多实例的情况,每个实例都需要各自保存一份缓存,缓存不具有一致性。

解决缓存过期:

​ 1、将缓存过期时间调为永久

​ 2、将缓存失效时间分散开,不要将缓存时间长度都设置成一样;比如我们可以在原有的失效时间基础上增加一个随机值,这样每一个缓存的过期时间的重复率就会降低,就很难引发集体失效的事件。

解决内存溢出:

第一步,修改JVM启动参数,直接增加内存。(-Xms,-Xmx参数一定不要忘记加。)

 第二步,检查错误日志,查看“OutOfMemory”错误前是否有其它异常或错误。

 第三步,对代码进行走查和分析,找出可能发生内存溢出的位置。

3、redis和Memcached的区别

redis Memcached
内存高速数据库 高性能分布式内存缓存数据库,可缓存图片、视频
支持hash、list、set、zset、string结构 只支持key-value结构
将大部分数据放到内存 全部数据放到内存中
支持持久化、主从复制备份 不支持数据持久化及数据备份
数据丢失可通过AOF恢复 挂掉后,数据不可恢复

使用场景:

​ 1、如果有持久方面的需求或对数据类型和处理有要求的应该选择redis。
​ 2、如果简单的key/value 存储应该选择memcached。

4、redis常用数据结构和使用场景

Redis主要有5种数据类型,包括String,List,Set,Zset,Hash

类型 存储值 应用场景
String 字符串、整数、浮点数 简单的键值对缓存
List 列表 存储列表型数据结构,例如:评论列表、商品列表
Set 无序集合 适合交集、并集、查集操作,例如朋友关系
Zset 有序集合 去重后排序,适合排名场景
Hash 哈希 结构化数据,比如存储对象

Redis的应用场景:

计数器

​ 可以对 String 进行自增自减运算,从而实现计数器功能。Redis 这种内存型数据库的读写性能非常高,很适合存储频繁读写的计数量。

缓存

​ 将热点数据放到内存中,设置内存的最大使用量以及淘汰策略来保证缓存的命中率。

会话缓存

​ 可以使用 Redis 来统一存储多台应用服务器的会话信息。当应用服务器不再存储用户的会话信息,也就不再具有状态,一个用户可以请求任意一个应用服务器,从而更容易实现高可用性以及可伸缩性。

其它

​ Set 可以实现交集、并集等操作,从而实现共同好友等功能。ZSet 可以实现有序性操作,从而实现排行榜等功能。

5、Zset底层实现?跳表搜索插入删除过程?

​ 跳表(skip List)是一种随机化的数据结构,基于并联的链表,实现简单,插入、删除、查找的复杂度均为O(logN)。简单说来跳表也是链表的一种,只不过它在链表的基础上增加了跳跃功能,正是这个跳跃的功能,使得在查找元素时,跳表能够提供O(logN)的时间复杂度

​ Zset数据量少的时候使用压缩链表ziplist实现,有序集合使用紧挨在一起的压缩列表节点来保存,第一个节点保存member,第二个保存score。ziplist内的集合元素按score从小到大排序,score较小的排在表头位置。

​ 数据量大的时候使用跳跃列表skiplist和哈希表hash_map结合实现,查找删除插入的时间复杂度都是O(longN)

搜索

​ 跳跃表按 score 从小到大保存所有集合元素,查找时间复杂度为平均 O(logN),最坏 O(N) 。

插入

  之前就说了,之所以选用链表作为底层结构支持,也是为了高效地动态增删。单链表在知道删除的节点是谁时,时间复杂度为O(1),因为跳表底层的单链表是有序的,为了维护这种有序性,在插入前需要遍历链表,找到该插入的位置,单链表遍历查找的时间复杂度是O(n),同理可得,跳表的遍历也是需要遍历索引数,所以是O(logn)。

删除

  删除的节点要分两种情况,如果该节点还在索引中,那删除时不仅要删除单链表中的节点,还要删除索引中的节点;另一种情况是删除的节点只在链表中,不在索引中,那只需要删除链表中的节点即可。但针对单链表来说,删除时都需要拿到前驱节点才可改变引用关系从而删除目标节点。

6、redis过期淘汰策略

1)全局的键空间选择性移除

noeviction:当内存不足以容纳新写入数据时,新写入操作会报错。

allkeys-lru:在键空间中,移除最近最少使用的key。(这个是最常用的)

allkeys-random:在键空间中,随机移除某个key。

2)设置过期时间的键空间选择性移除

volatile-lru:在设置了过期时间的键空间中,移除最近最少使用的key。

volatile-random:在设置了过期时间的键空间中,随机移除某个key。

volatile-ttl:在设置了过期时间的键空间中,有更早过期时间的key优先移除。

总结

​ Redis的内存淘汰策略的选取并不会影响过期的key的处理。内存淘汰策略用于处理内存不足时的需要申请额外空间的数据;过期策略用于处理过期的缓存数据。

7、redis持久化机制?都有什么优缺点?持久化的时候还能接受请求吗?

持久化就是把内存中的数据持久化到本地磁盘,防止服务器宕机了内存数据丢失

Redis 提供两种持久化机制 RDB(默认)AOF 机制

RDB:是Redis DataBase缩写快照

​ RDB是Redis默认的持久化方式。按照一定的时间将内存的数据以快照的形式保存到硬盘中,对应产生的数据文件为dump.rdb。通过配置文件中的save参数来定义快照的周期。

优点:

​ 1)只有一个文件 dump.rdb,方便持久化;

​ 2)容灾性好,一个文件可以保存到安全的磁盘。

​ 3)性能最大化,fork 子进程来完成写操作,让主进程继续处理命令,所以是 IO 最大化。使用单独子进程来进行持久化,主进程不会进行任何 IO 操作,保证了 redis 的高性能。

​ 4)相对于数据集大时,比 AOF 的启动效率更高。

缺点:

​ 1)数据安全性低。RDB 是间隔一段时间进行持久化,如果持久化之间 redis 发生故障,会发生数据丢失。所以这种方式更适合数据要求不严谨的时候

AOF:持久化

​ AOF持久化(即Append Only File持久化),则是将Redis执行的每次写命令记录到单独的日志文件中,当重启Redis会重新将持久化的日志中文件恢复数据。

优点:

​ 1)数据安全,aof 持久化可以配置 appendfsync 属性,有 always,每进行一次 命令操作就记录到 aof 文件中一次。

​ 2)通过 append 模式写文件,即使中途服务器宕机,可以通过 redis-check-aof 工具解决数据一致性问题。

缺点:

​ 1)AOF 文件比 RDB 文件大,且恢复速度慢。

​ 2)数据集大的时候,比 rdb 启动效率低。

8、redis事务

​ 事务是一个单独的隔离操作:事务中的所有命令都会序列化、按顺序地执行。事务在执行的过程中,不会被其他客户端发送来的命令请求所打断。事务是一个原子操作:事务中的命令要么全部被执行,要么全部都不执行。

Redis事务的概念

​ Redis 事务的本质是通过MULTI、EXEC、WATCH等一组命令的集合。事务支持一次执行多个命令,一个事务中所有命令都会被序列化。在事务执行过程,会按照顺序串行化执行队列中的命令,其他客户端提交的命令请求不会插入到事务执行命令序列中。总结说:redis事务就是一次性、顺序性、排他性的执行一个队列中的一系列命令。

Redis事务功能是通过MULTI、EXEC、DISCARD和WATCH 四个原语实现的

Redis会将一个事务中的所有命令序列化,然后按顺序执行。

Redis的事务总是具有ACID中的一致性和隔离性,其他特性是不支持的。当服务器运行在AOF持久化模式下,并且appendfsync选项的值为always时,事务也具有耐久性。

事务命令:

MULTI:用于开启一个事务,它总是返回OK。MULTI执行之后,客户端可以继续向服务器发送任意多条命令,这些命令不会立即被执行,而是被放到一个队列中,当EXEC命令被调用时,所有队列中的命令才会被执行。

EXEC:执行所有事务块内的命令。返回事务块内所有命令的返回值,按命令执行的先后顺序排列。当操作被打断时,返回空值 nil 。

WATCH :是一个乐观锁,可以为 Redis 事务提供 check-and-set (CAS)行为。可以监控一个或多个键,一旦其中有一个键被修改(或删除),之后的事务就不会执行,监控一直持续到EXEC命令。

DISCARD:调用该命令,客户端可以清空事务队列,并放弃执行事务,且客户端会从事务状态中退出。

UNWATCH:命令可以取消watch对所有key的监控。

9、缓存雪崩和缓存穿透,以及解决方法

【1】缓存雪崩:

​ 指缓存同一时间大面积的失效,所以,后面的请求都会落到数据库上,造成数据库短时间内承受大量请求而崩掉。

解决方案:

​ 1)缓存数据的过期时间设置随机,防止同一时间大量数据过期现象发生。

​ 2)一般并发量不是特别多的时候,使用最多的解决方案是加锁排队。

​ 3)给每一个缓存数据增加相应的缓存标记,记录缓存是否失效,如果缓存标记失效,则更新数据缓存。

【2】缓存穿透:

​ 缓存穿透是指缓存和数据库中都没有的数据,导致所有的请求都落到数据库上,造成数据库短时间内承受大量请求而崩掉。

解决方案:

​ 1)接口层增加校验,如用户鉴权校验,id做基础校验,id<=0的直接拦截;

​ 2)从缓存取不到的数据,在数据库中也没有取到,这时也可以将key-value对写为key-null,缓存有效时间可以设置短点,如30秒(设置太长会导致正常情况也没法使用)。这样可以防止攻击用户反复用同一个id暴力攻击;

​ 3)采用布隆过滤器,将所有可能存在的数据哈希到一个足够大的 bitmap 中,一个一定不存在的数据会被这个 bitmap 拦截掉,从而避免了对底层存储系统的查询压力。

【3】缓存击穿:

​ 这时由于并发用户特别多,同时读缓存没读到数据,又同时去数据库去取数据,引起数据库压力瞬间增大,造成过大压力。和缓存雪崩不同的是,缓存击穿指并发查同一条数据,缓存雪崩是不同数据都过期了,很多数据都查不到从而查数据库

解决方案:

​ 1)设置热点数据永远不过期

​ 2)加互斥锁,互斥锁

10、如何保证缓存和数据库的数据一致性?

方式一:

​ 读请求和写请求串行化,串到一个内存队列里去,这样就可以保证一定不会出现不一致的情况。串行化之后,就会导致系统的吞吐量会大幅度的降低,用比正常情况下多几倍的机器去支撑线上的一个请求。

方式二:

​ 先更新数据库,假如读缓存失败,先读数据库,再回写缓存的方式实现

11、redis是单线程还是多线程?为什么那么快?

redis是单线程,快的原因:

​ 1)完全基于内存,绝大部分请求是纯粹的内存操作,非常快速。数据存在内存中,类似于 HashMap,HashMap 的优势就是查找和操作的时间复杂度都是O(1);

​ 2)数据结构简单,对数据操作也简单,Redis 中的数据结构是专门进行设计的;

​ 3)采用单线程,避免了不必要的上下文切换和竞争条件,也不存在多进程或者多线程导致的切换而消耗 CPU,不用去考虑各种锁的问题,不存在加锁释放锁操作,没有因为可能出现死锁而导致的性能消耗;

​ 4)使用多路 I/O 复用模型,非阻塞 IO;

​ 5)使用底层模型不同,它们之间底层实现方式以及与客户端之间通信的应用协议不一样,Redis 直接自己构建了 VM 机制 ,因为一般的系统调用系统函数的话,会浪费一定的时间去移动和请求;

12、五种IO模型的区别

阻塞I/O:

​ 当用户线程发出IO请求之后,内核会去查看数据是否就绪,如果没有就绪就会等待数据就绪,而用户线程就会处于阻塞状态,用户线程交出CPU。当数据就绪之后,内核会将数据拷贝到用户线程,并返回结果给用户线程,用户线程才解除block状态。

非阻塞I/O:

​ 在非阻塞IO模型中,用户线程需要不断地询问内核数据是否就绪,也就说非阻塞IO不会交出CPU,而会一直占用CPU。

多路复用I/O(select和poll):

​ IO多路转接是多了一个select函数,select函数有一个参数是文件描述符集合,对这些文件描述符进行循环监听,当某个文件描述符就绪时,就对这个文件描述符进行处理。其中,select只负责等,recvfrom只负责拷贝。 IO多路转接是属于阻塞IO,但可以对多个文件描述符进行阻塞监听,所以效率较阻塞IO的高。

信号驱动I/O(SIGIO):

​ 信号驱动IO模型,应用进程告诉内核:当数据报准备好的时候,给我发送一个信号,对SIGIO信号进行捕捉,并且调用我的信号处理函数来获取数据报。

异步I/O(Posix.1的aio_系列函数):

​ 当应用程序调用aio_read时,内核一方面去取数据报内容返回,另一方面将程序控制权还给应用进程,应用进程继续处理其他事情,是一种非阻塞的状态。当内核中有数据报就绪时,由内核将数据报拷贝到应用程序中,返回aio_read中定义好的函数处理程序。

可以看出,阻塞程度:阻塞IO>非阻塞IO>多路转接IO>信号驱动IO>异步IO,效率是由低到高的

13、select、poll、epoll的区别?

参考:https://www.jianshu.com/p/dfd940e7fca2

select 函数监视的文件描述符分3类,分别是writefds、readfds、和exceptfds。调用后select函数会阻塞,直到有描述符就绪(有数据 可读、可写、或者有except),或者超时(timeout指定等待时间,如果立即返回设为null即可),函数返回。当select函数返回后,可以通过遍历fdset,来找到就绪的描述符。

*poll *本质上和select没有区别,它将用户传入的数组拷贝到内核空间,然后查询每个fd对应的设备状态,如果设备就绪则在设备等待队列中加入一项并继续遍历,如果遍历完所有fd后没有发现就绪设备,则挂起当前进程,直到设备就绪或者主动超时,被唤醒后它又要再次遍历fd。这个过程经历了多次无谓的遍历。

*epoll *支持水平触发和边缘触发,最大的特点在于边缘触发,它只告诉进程哪些fd刚刚变为就绪态,并且只会通知一次。还有一个特点是,epoll使用“事件”的就绪通知方式,通过epoll_ctl注册fd,一旦该fd就绪,内核就会采用类似callback的回调机制来激活该fd,epoll_wait便可以收到通知。

14、redis热key问题?如何发现以及如何解决?

​ 缓存中的一个Key(比如一个促销商品),在某个时间点过期的时候,恰好在这个时间点对这个Key有大量的并发请求过来,这些请求发现缓存过期一般都会从后端DB加载数据并回设到缓存,这个时候大并发的请求可能会瞬间把后端DB压垮。

解决方案:

​ 对缓存查询加锁,如果KEY不存在,就加锁,然后查DB入缓存,然后解锁;其他进程如果发现有锁就等待,然后等解锁后返回数据或者进入DB查询

15、redis数据分布方式?有什么优点?一致性hash呢?

Hash:

​ 客户端分片:哈希+取余

​ 节点伸缩:数据节点关系变化,导致数据迁移

​ 迁移数量和添加节点数量有关:建议翻倍扩容

​ 一个简单直观的想法是直接用Hash来计算,以Key做哈希后对节点数取模。可以看出,在key足够分散的情况下,均匀性可以获得,但一旦有节点加入或退出,所有的原有节点都会受到影响,稳定性无从谈起。

一致性Hash:

​ 客户端分片:哈希+顺时针(优化取余)

​ 节点伸缩:只影响邻近节点,但是还是有数据迁移

​ 翻倍伸缩:保证最小迁移数据和负载均衡

​ 一致性Hash可以很好的解决稳定问题,可以将所有的存储节点排列在收尾相接的Hash环上,每个key在计算Hash后会顺时针找到先遇到的一组存储节点存放。而当有节点加入或退出时,仅影响该节点在Hash环上顺时针相邻的后续节点,将数据从该节点接收或者给予。但这有带来均匀性的问题,即使可以将存储节点等距排列,也会在存储节点个数变化时带来数据的不均匀。而这种可能成倍数的不均匀在实际工程中是不可接受的。

16、redis主从复制

主从复制原理:

当启动一个 slave node 的时候,它会发送一个 PSYNC 命令给 master node。

如果这是 slave node 初次连接到 master node,那么会触发一次 full resynchronization 全量复制。此时 master 会启动一个后台线程,开始生成一份 RDB 快照文件,

同时还会将从客户端 client 新收到的所有写命令缓存在内存中。RDB 文件生成完毕后, master 会将这个 RDB 发送给 slave,slave 会先写入本地磁盘,然后再从本地磁盘加载到内存中,

接着 master 会将内存中缓存的写命令发送到 slave,slave 也会同步这些数据。

slave node 如果跟 master node 有网络故障,断开了连接,会自动重连,连接之后 master node 仅会复制给 slave 部分缺少的数据。

过程原理

​ 1、当从库和主库建立MS关系后,会向主数据库发送SYNC命令

​ 2、主库接收到SYNC命令后会开始在后台保存快照(RDB持久化过程),并将期间接收到的写命令缓存起来

​ 3、当快照完成后,主Redis会将快照文件和所有缓存的写命令发送给从Redis

​ 4、从Redis接收到后,会载入快照文件并且执行收到的缓存的命令

​ 5、之后,主Redis每当接收到写命令时就会将命令发送从Redis,从而保证数据的一致

缺点

​ 所有的slave节点数据的复制和同步都由master节点来处理,会照成master节点压力太大,使用主从从结构来解决

七、Spring 篇

1、Spring IOC

​ IoC(Inverse of Control:控制反转)是⼀种设计思想,就是 将原本在程序中⼿动创建对象的控制
权,交由Spring框架来管理。 IoC 在其他语⾔中也有应⽤,并⾮ Spring 特有。

​ IoC 容器是 Spring⽤来实现 IoC 的载体, IoC 容器实际上就是个Map(key,value),Map 中存放的是各种对象。将对象之间的相互依赖关系交给 IoC 容器来管理,并由 IoC 容器完成对象的注⼊。这样可以很⼤程度上简化应⽤的开发,把应⽤从复杂的依赖关系中解放出来。 IoC 容器就像是⼀个⼯⼚⼀样,当我们需要创建⼀个对象的时候,只需要配置好配置⽂件/注解即可,完全不⽤考虑对象是如何被创建出来的。

2、Spring AOP,动态代理

​ AOP(Aspect-Oriented Programming:⾯向切⾯编程)能够将那些与业务⽆关,却为业务模块所共同调⽤
的逻辑或责任(例如事务处理、⽇志管理、权限控制等)封装起来,便于减少系统的重复代码,降低模
块间的耦合度,并有利于未来的可拓展性和可维护性。

​ Spring AOP就是基于动态代理的,如果要代理的对象,实现了某个接⼝,那么Spring AOP会使⽤JDK
Proxy,去创建代理对象,⽽对于没有实现接⼝的对象,就⽆法使⽤ JDK Proxy 去进⾏代理了,这时候
Spring AOP会使⽤Cglib ,这时候Spring AOP会使⽤ Cglib ⽣成⼀个被代理对象的⼦类来作为代理,

3、Bean生命周期

单例对象: singleton

出生:当容器创建时对象出生

活着:只要容器还在,对象一直或者

死亡:容器销毁,对象消亡

总结:单例对象的生命周期和容器相同

多例对象: prototype

出生: 使用对象时spring框架为我们创建

活着:对象只要是在使用过程中就一直活着

死亡:当对象长时间不用且没有其它对象引用时,由java的垃圾回收机制回收

4、Bean作用域?默认什么级别?是否线程安全?Spring如何保障线程安全的?

名称
singleton 单例对象,默认值的作用域
prototype 每次获取都会创建⼀个新的 bean 实例
request 每⼀次HTTP请求都会产⽣⼀个新的bean,该bean仅在当前HTTP request内有效。
session 在一次 HTTP session 中,容器将返回同一个实例
global-session 将对象存入到web项目集群的session域中,若不存在集群,则global session相当于session

默认作用域是singleton,多个线程访问同一个bean时会存在线程不安全问题

保障线程安全方法:

  1. 在Bean对象中尽量避免定义可变的成员变量(不太现实)。

  2. 在类中定义⼀个ThreadLocal成员变量,将需要的可变成员变量保存在 ThreadLocal 中

    ThreadLocal

    ​ 每个线程中都有一个自己的ThreadLocalMap类对象,可以将线程自己的对象保持到其中,各管各的,线程可以正确的访问到自己的对象。

    ​ 将一个共用的ThreadLocal静态实例作为key,将不同对象的引用保存到不同线程的ThreadLocalMap中,然后在线程执行的各处通过这个静态ThreadLocal实例的get()方法取得自己线程保存的那个对象,避免了将这个对象作为参数传递的麻烦。

5、Spring事务隔离级别和事务传播属性

隔离级别:

1) DEFAULT (默认)
这是一个PlatfromTransactionManager默认的隔离级别,使用数据库默认的事务隔离级别。另外四个与JDBC的隔离级别相对应。

2) READ_UNCOMMITTED (读未提交)
这是事务最低的隔离级别,它允许另外一个事务可以看到这个事务未提交的数据。这种隔离级别会产生脏读,不可重复读和幻像读。

3) READ_COMMITTED (读已提交)
保证一个事务修改的数据提交后才能被另外一个事务读取,另外一个事务不能读取该事务未提交的数据。这种事务隔离级别可以避免脏读出现,但是可能会出现不可重复读和幻像读。

4) REPEATABLE_READ (可重复读)
这种事务隔离级别可以防止脏读、不可重复读,但是可能出现幻像读。它除了保证一个事务不能读取另一个事务未提交的数据外,还保证了不可重复读。

5) SERIALIZABLE(串行化)
这是花费最高代价但是最可靠的事务隔离级别,事务被处理为顺序执行。除了防止脏读、不可重复读外,还避免了幻像读。

Spring事务传播属性(Propagation):

1) REQUIRED(默认属性)
如果存在一个事务,则支持当前事务。如果没有事务则开启一个新的事务。 被设置成这个级别时,会为每一个被调用的方法创建一个逻辑事务域。如果前面的方法已经创建了事务,那么后面的方法支持当前的事务,如果当前没有事务会重新建立事务。

2) MANDATORY
支持当前事务,如果当前没有事务,就抛出异常。

3) NEVER
以非事务方式执行,如果当前存在事务,则抛出异常。

4) NOT_SUPPORTED
以非事务方式执行操作,如果当前存在事务,就把当前事务挂起。

5) REQUIRES_NEW
新建事务,如果当前存在事务,把当前事务挂起。

6) SUPPORTS
支持当前事务,如果当前没有事务,就以非事务方式执行。

7) NESTED
支持当前事务,新增Savepoint点,与当前事务同步提交或回滚。 嵌套事务一个非常重要的概念就是内层事务依赖于外层事务。外层事务失败时,会回滚内层事务所做的动作。而内层事务操作失败并不会引起外层事务的回滚。

6、Spring以及Spring MVC常见注解

Spring部分:

声明bean的注解

@Component 通⽤的注解,可标注任意类为 Spring 组件

@Service 在业务逻辑层使用(service层)

@Repository 在数据访问层使用(dao层)

@Controller 在展现层使用,控制器的声明(controller层)

注入bean的注解

@Autowired:可以对类成员变量、方法、构造方法进行标注

​ 默认按照类型注入,若要按照名称注入,需要搭配@Qualifier注解一起使用

@Resource:默认按照名称来装配注入

Spring MVC部分:

@Controller 声明该类为SpringMVC中的Controller

@RequestMapping 用于映射Web请求

@ResponseBody 支持将返回值放在response内,而不是一个页面,通常用户返回json数据

@RequestBody 允许request的参数在request体中,而不是在直接连接在地址后面。

@PathVariable 用于接收路径参数,比如@RequestMapping("/hello/{name}")申明的路径,将注解放在参数中前,即可获取该值,通常作为Restful的接口实现方法。

7、@autowired和@resource的区别?

@Autowired:可以对类成员变量、方法、构造方法进行标注

​ 默认按照类型注入,若要按照名称注入,需要搭配@Qualifier注解一起使用

@Resource:默认按照名称来装配注入

8、mybatis如何防止sql注入?$和#的区别是什么?传入表名用哪个?

防止sql注入:

​ 在编写mybatis的映射语句时,尽量采用“#{xxx}”这样的格式

#和$区别:

# $
相当于对数据加上双引号 相当于直接显示数据
很大程度上防止SQL注入 无法防止SQL注入
#{xxx},使用的是PreparedStatement,会有类型转换,比较安全 ${xxx},使用字符串拼接,容易SQL注入

​ 简单的说就是#{}是经过预编译的,是安全的,${}是未经过预编译的,仅仅是取变量的值,是非安全的,存在SQL注入。

要实现动态传入表名、列名,需要做如下修改:

添加属性statementType="STATEMENT"同时sql里的属有变量取值都改成${xxxx}

9、Spring MVC工作原理

  1. 客户端(浏览器)发送请求,直接请求到 DispatcherServlet 。
  2. DispatcherServlet 根据请求信息调⽤ HandlerMapping ,解析请求对应的 Handler 。
  3. 解析到对应的 Handler (也就是 Controller 控制器)后,开始由HandlerAdapter 适配器处理。
  4. HandlerAdapter 会根据 Handler 来调⽤真正的处理器开处理请求,并处理相应的业务逻辑。
  5. 处理器处理完业务后,会返回⼀个 ModelAndView 对象, Model 是返回的数据对象
  6. ViewResolver 会根据逻辑 View 查找实际的 View 。
  7. DispaterServlet 把返回的 Model 传给 View (视图渲染)。
  8. 把 View 返回给请求者(浏览器)

10、SpringBoot自动配置的原理是什么?介绍SpringBootApplication注解.

启动类:

@SpringBootApplication
public class JpaApplication {
    public static void main(String[] args) {
        SpringApplication.run(JpaApplication.class, args);
    }
}

它主要加载了@SpringBootApplication注解主配置类,这个@SpringBootApplication注解主配置类里边最主要的功能就是SpringBoot开启了一个@EnableAutoConfiguration注解的自动配置功能。

@EnableAutoConfiguration作用:

它主要利用了一个

EnableAutoConfigurationImportSelector选择器给Spring容器中来导入一些组件。

@Import(EnableAutoConfigurationImportSelector.class)
public @interface EnableAutoConfiguration 

@SpringBootApplication注解等同于下面三个注解:

  • @SpringBootConfiguration: 底层是Configuration注解,说白了就是支持JavaConfig的方式来进行配置
  • @EnableAutoConfiguration:开启自动配置功能
  • @ComponentScan:就是扫描注解,默认是扫描当前类下的package

其中@EnableAutoConfiguration是关键(启用自动配置),内部实际上就去加载META-INF/spring.factories文件的信息,然后筛选出以EnableAutoConfiguration为key的数据,加载到IOC容器中,实现自动配置功能!

11、Mybatis和Hibernate的区别

Hibernate 框架:

Hibernate是一个开放源代码的对象关系映射框架,它对JDBC进行了非常轻量级的对象封装,建立对象与数据库表的映射。是一个全自动的、完全面向对象的持久层框架。

Mybatis框架:

Mybatis是一个开源对象关系映射框架,原名:ibatis,2010年由谷歌接管以后更名。是一个半自动化的持久层框架。

区别:

开发方面

​ 在项目开发过程当中,就速度而言:

​ hibernate开发中,sql语句已经被封装,直接可以使用,加快系统开发;

​ Mybatis 属于半自动化,sql需要手工完成,稍微繁琐;

​ 但是,凡事都不是绝对的,如果对于庞大复杂的系统项目来说,复杂语句较多,hibernate 就不是好方案。

sql优化方面

​ Hibernate 自动生成sql,有些语句较为繁琐,会多消耗一些性能;

​ Mybatis 手动编写sql,可以避免不需要的查询,提高系统性能;

对象管理比对

​ Hibernate 是完整的对象-关系映射的框架,开发工程中,无需过多关注底层实现,只要去管理对象即可;

​ Mybatis 需要自行管理 映射关系;

12、spring中的@Autowired注解原理?

​ @Autowired的使用简化了我们的开发,其原理是使用 AutowiredAnnotationBeanPostProcessor 类来实现,该类实现了 Spring 框架的一些扩展接口,通过实现 BeanFactoryAware 接口使其内部持有了 BeanFactory(可轻松的获取需要依赖的的 Bean);通过实现 MergedBeanDefinitionPostProcessor 扩展接口,在 BeanFactory 里面的每个 Bean 实例化前获取到每个 Bean 里面的 @Autowired 信息并缓存下来;通过实现 Spring 框架的 postProcessPropertyValues 扩展接口在 BeanFactory 里面的每个 Bean 实例后从缓存取出对应的注解信息,获取依赖对象,并通过反射设置到 Bean 属性里面。

13、Spring中用到了哪些设计模式?单例、工厂、代理、适配、观察者之类的说一说就行

参考:spring中的设计模式

单例设计模式 : Spring 中的 Bean 默认都是单例的。

⼯⼚设计模式 : Spring使⽤⼯⼚模式通过 BeanFactory 、 ApplicationContext 创建bean 对象。

代理设计模式 : Spring AOP 功能的实现。

观察者模式: Spring 事件驱动模型就是观察者模式很经典的⼀个应⽤。

适配器模式:Spring AOP 的增强或通知(Advice)使⽤到了适配器模式、spring MVC 中也是⽤到了适配器模式适配 Controller 。

八、其它内容

大数据和空间限制与系统设计

1、100亿黑名单URL,每个64B,问这个黑名单要怎么存?判断一个URL是否在黑名单中

散列表:

​ 如果把黑名单看成一个集合,将其存在 hashmap 中,貌似太大了,需要 640G,明显不科学。

布隆过滤器:

​ 它实际上是一个很长的二进制矢量和一系列随机映射函数。

​ 它可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。对于布隆过滤器而言,它的本质是一个位数组:位数组就是数组的每个元素都只占用 1 bit ,并且每个元素只能是 0 或者 1。

​ 在数组中的每一位都是二进制位。布隆过滤器除了一个位数组,还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候,会进行如下操作:

  • 使用 K 个哈希函数对元素值进行 K 次计算,得到 K 个哈希值。
  • 根据得到的哈希值,在位数组中把对应下标的值置为 1。

更多模拟面试

全部评论

(58) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

热门推荐