(传送门)
开场白: 自我介绍这里一笔带过,给对面介绍自己内在 + 外在 + 校园经历 + 校园项目 + 意向岗位 面试公司: 腾讯子公司云智研发一面
1. 有了解过C++吗?接受转语言吗?
2. 有没有了解过一些框架的底层原理、底层优化、数据库的索引优化
3. 了解过哪些Map,可以从底层简单说下嘛?
比如我最常使用的有HashMap
、HashTable
、CurrentHashMap
这三种
HashMap
它的底层是采用了数组+链表的数据结构
从源码中分析,HashMap
有一个静态内部类Node
,HashMap
通过成员变量table
(Node
数组类型)来采取put
和get
操作,该成员变量用关键字transient
加以修饰,表明禁止序列化。
而Node
是table
数组的一个结点,内部成员数据有hash
、key
、value
和指向Node
类的next
-- 初始化阶段 --
在这里,put
操作后,table
会先调用resize
方法进行扩展,扩展后table
才从null
变为16
位的Node
数组,初始化后的每一个下标依旧为null
,并且初始化阈值threshold
,默认为0.75 * size
,作用是与成员变量size
(成员变量size
会在每次put
而且要该key
值为首次操作即不存在该Map
中会自增)进行比较,如果size
数即表明put
的key-value
对的数量超过阈值threshold
,进行下一步操作,即resize
方法另一作用。
-- 扩容阶段 --
扩容阶段更简单,就是将阈值*2
来扩容,然后遍历整个table
即Node
数组,如果发现有Node
结点,那么这里就出现了两种情况,第一种为每个结点上是链表结构,另一种则是红黑树结构。
扩容操作是创建新table
来扩容,没有在旧table
上直接扩容,遍历旧table
进行扩容时,将会对每个table
槽位置空,多线程在扩容时会发生一些导致线程安全的问题。
ConcurrentHashMap
在JDK7
扩容时使用到了ReentrantLock
对段加锁,这样该段的旧table
也无法操作,JDK
则通过一种手段设置标志位,后面操作使用CAS
乐观锁来操作,成功则退出,不成功发现扩容标志后则参与扩容。
扩容成功的结果就是发生链表转移或者是红黑树转移,都是为了将节点分散,以至于发挥出Hash
一次命中取出和保存的高性能。
当然刚开始没有结点数据,oldTable
为null
,不需要转移结点,然后什么事都没干,接着通过hash
与table
的长度进行&
操作命中槽位,put
操作会保存到数组对应下标处即槽位中的结点。
-- 结点初始化 --
保存之前很简单,得判断对应Node
数组下标结点是否为null
,因为这里是懒加载嘛,刚开始没有初始化数组的每一个元素,resize
初始化方法也只是new
了个Node
数组,而且这也一样是懒加载。
所以在这里会将put
中key
的hash、key和value
值封装到Node
结点中并实例化,然后赋值到对应的Node
数组下标中。
如果结点已经实例化了,那么这里有两种方式,一是链表寻址,二是树寻址,然后就是找到就覆盖,找不到就追加。
-- 链表寻址 --
寻址前会先判断结点类型,如果instanceof
不是TreeNode
,那么便是链表,然后就可以开始遍历链表了,如果找到了的话,key-value
当然就是要覆盖了,但是这里对key
的处理分为了两种:
分析之前,其实链表中所有结点都位于同一个数组下标,那么应该都必须满足每个结点的hash
值相同,即槽位相同,所以会再一次判断hash
值,才会用key
去比较。
- 如果
key
为基本数据类型,那么是直接通过运算符==
来比较的,为true
,那么就直接跳出链表遍历了,然后将刚刚在链表访问后命中的Node
结点value
覆盖 - 如果key为复杂类型,那么仅仅通过
==
运算符比较是错误的,这里就需要我们去主动重写equals
方法,让key
值怎么比较才能相等,因为默认equals
是Object
比较,这里涉及到内存指针了,所以创建的对象一般内存都不同,除非浅拷贝。 - 只是我们一般都用
String
类型,而String
类型已经帮我们重写过了,虽然String
类型也算是复杂类型,它重写了Object
的equals
方法,使得不同对象可以进行比较,比较的是对应字符串序列的内容是否相同。
如果没找到,那么将实例化新的Node
结点,然后追加到链表末尾,在JDK7
中是追加到头结点,后来发现线程安全,即多线程情况下,有几率会导致链表出现死锁。
-- 树寻址 --
首先了解下TreeNode
,它继承了LinkedHashMap.Entry
,而Entry
又继承了HashMap.Node
,归根结底还是跟链表的Node
类似,只不过多了一些成员和方法。
树寻址是判断结点是否为树节点,一般在链表转变为红黑树之后才会进行,红黑树是一棵平衡的二叉有序树,即由哈希值排序的二叉树,从根节点依次比较哈希值并遍历到叶子节点依旧没有找到,通过哈希值比较的大小直接实例出一个新的树节点给原来叶子节点的左孩子节点或右孩子节点。
如果找到该节点,与链表一样的方法,则中断遍历并将该节点返回,在外部进行赋值操作。
-- 链表转移 --
链表转移前会判断链表是否只有表头,即只有一个元素,那么通过寻找该结点Node
的Hash
值,与扩容后的lenth
长度&
操作命中新的槽位
/**
e : table即Node数组中的一个下标元素
newCap: 新table的容量
e.hash: 哈希值,常用于与table长度做&操作来命中寻址
newTab: 新table
*/
newTab[e.hash & (newCap - 1)] = e;
如果是链表结构,那么按照hash
值对链表拆成高位和低位链表,这里的高低位不是字面意思,我是直译源码字面意思,从代码分析:
/**
如果 hash 二进制数中 与 旧table的容量表示的二进制数 所在的 位为1 & 为 真,则表示为高位链表
如果 hash 二进制数中 与 旧table的容量表示的二进制数 所在的 位为1 & 为 假,则表示为低位链表
从随机性角度考虑,这两种散列均匀的话各占一半
hash: 4字节的 int 类型
oldCap: 4字节的 int 类型,默认初始化为 16,二进制表示为 10000
*/
e.hash & oldCap) == 0
由于新table
是旧table
的两倍,那么低位链表命中赋值给新table
中与旧table
相同的下标,而高位从字面上理解,就要比低位更靠右,所以它的下标是原下标+oldCap
,oldCap
大小也是新table
大小的一半,看图
-- 转化红黑树 --
转化红黑树刚开始是不会触发的,在put
操作的时候,在table
中某个槽遍历链表时,如果链表长度达到扩展树阈值8
,并且table
长度要大于64
。
链表满足长度8
是树转移的必要条件,在table
初始化后且发生转化红黑树前,会先去判断table
长度是否达到64
,没有则会扩容,扩容前面也详细说了,上面的图就很明确,达到8
个节点的链表,扩容后链表拆成两部分,很明显没有必要再次去转化了。
如果长度满足,这时会先转变为双向链表,用于辅助树节点增加和删除以及维护树根节点。
转换红黑树是从遍历该链表开始,特殊处理第一个链表节点转成树节点,遍历这棵树,通过哈希值构造一颗排序树,每次构造新节点都是从叶子节点开始,不平衡就利用红黑标记来转为平衡树。
-- 树转移 --
树转移发生在resize
方法中,触发的事件是当前put
成功后的所有元素个数大于table
的阈值(容量 * 负载因子),接着会先扩容table
的容量,树转移时,在put
时hash
命中的table
中一个插槽发现是树节点,就开始转移,转移不是从树的逻辑转移,跟链表一样,只不过还有考虑前置节点,也就是跟树转移一样构造双向链表,拆成两条待转移成树的双向链表。
拆成的子双向链表,长度小于6
就直接退化为链表,否则才将红黑树转移到新table
的高低位上。
-- 特殊key --
对于key为null
值,JDK7
与JDK8
做法不同,但结果都是从table
的0
下标开始遍历。
JDK7
的做法是对Null
做了单独的put
处理,不与非空的key
放一起,直接单独在一个方法里面遍历table
的0
下标。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
所以常常说JDK7
版本可读性比JDK8
版本要强,这是无须质疑的。
JDK8
的做法更绝了,是对Null
做了单独的hash
处理,因为前面的JDK7
版本对key
做单独处理,无外乎就是null
没法调用本地native
方法hashCode
取的哈希值,所以干脆就在外面传入hash
值,并且将为null
的key
哈希值处理为0
。
return putVal(hash(key), key, value, false, true);
-- 哈希定位 --
在HashMap
中其实哈希的影响还是蛮大的,所以版本迭代对哈希也做了一些改进。
JDK7
版本的做法其实也是将32位
的int
哈希类型在命中table
中的下标是能够分布均衡,因为table
的数组长度没有像哈希值一样每个位随机均匀,它高位字节一般为0
,这就导致很多时候不同的哈希值高位虽然不同,但结果命中了同一个下标,JDK
的做法通过无符号右移,让每12
位无差别异或,即高低位能够很好的利用到了。
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
但这种做法还不够极致,JDK8
版本的做法,更加简单明了。
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4. 你项目中是如何去实现幂等性的?
先说下我对幂等性的理解,这样再去理解我项目对幂等性的处理。
定义
用户对于同一操作发起的一次请求或者多次请求的结果是一致的,不会因为多次点击而产生了副作用。
实现
幂等性在RPC
上的实现,不仅要考虑结果一致性,还有考虑请求失败后负载到其他机器依旧保证幂等性,这就不能使用本地缓存来实现,而要用到分布式缓存,推荐的分布式缓存可以是Redis
。
需要考虑到重试的时机来恰当设置缓存的失效时间,一般逻辑上只要保证请求次数达到阈值后重试请求成功即可失效,可从逻辑成功调用后去手动失效,或者是达到阈值后手动失效,不过这种做法增大了Redis
的阻塞,因为Redis
是单线程,没法做到并发,Jedis
虽然可以并发,但会导致线程安全问题,而Jedis
每次请求都需要建立连接, 所以可以考虑共享一个连接,不过请求速度将大大降低。
而考虑Lettuce
则需要提前准备线程池,后面就可以直接从从线程池取连接,连接数更好管控,性能也相对高一些。
5. RPC的协议讲一讲,怎么处理的?
RPC
的请求过程:
- 服务端启动,并将服务注册到注册中心;
- 客户端启动通过代理调用所需的远程方法;
- 代理从注册中心拉取服务,并使用某种负载策略调用其中一个服务;
- 代理将客户端想要调用的方法等调用信息序列化,然后通过网络传输给服务端;
- 服务端接收到数据后,进行反序列化;
- 服务端得到反序列化的数据,包含需要调用的方法、参数数据,接着调用本地方法;
- 服务端调用完成将结果进行序列化,然后通过网络传输给代理;
- 代理拿到结果后,将结果反序列化,然后返回给客户端;
- 客户端接收到服务端远程方法调用的结果;
6. 项目中是怎么序列化的?
项目中使用到了两种序列化方式,一种是Jackson
,另一种是Kryo
序列化;
这两种序列化工具都提供对Java对象的序列化,即转成二进制,然后进行网络传输;
接收到网络传输的二进制,再反过来进行反序列化成对象;
不过项目序列化的是核心数据,对一些请求包头协议,是使用了自定义编解码的方式;
对特定的字节码进行编解码解析,从而可以避免出现粘包的问题;
拆完包之后,对包中的核心数据进行反序列化操作;
当然具体的操作还有考虑到包的其他安全问题,比如重发包和校验码失败包。
7.说一说深拷贝和浅拷贝
浅拷贝主要拷贝了对象的指针,本身数据引用的是同一块内存;
深拷贝则拷贝了对象本身,引用的是不同的内存。
在Java
中,深拷贝和浅拷贝有Object
的clone
拷贝方法(浅拷贝);
Arrays.copy
(浅拷贝)和System.arraycopy
(浅拷贝)
序列化则是深拷贝,比如Java内置的ObjectOutputStream
的writeObject
方法和ObjectInputStream
的readObject
方法;
更深入来讲,浅拷贝中,目标对象对内存的操作会影响到原对象,而深拷贝则受影响。
8. TCP和UDP了解下?
TCP
与UDP
都是传输层协议,TCP
基于连接的,UDP
基于非连接的;
从连接上看,TCP需要有三次握手才能完成连接,之后才能进行通信,是可靠的连接;
而UDP
不需要连接,没有TCP
严谨的三次握手、确认连接和四次挥手过程,是不可靠的连接;
TCP
可以保证服务的可靠,一般用于高可靠服务,UDP
不能保证服务是否可靠。
特点
TCP:
- 稳定可靠,适用于要求较高的场景,需要准确无误的传输给对方,比如文件传输、发送邮件和浏览网页等;
UDP:
- 速度快,性能损耗少、资源占用少,但是可能产生丢包,所以适用于对实时性要求较高,但是对少量丢包,并没有太大的要求的场景,比如域名查询、电话通信和视频直播等。
9. Http底层使用了什么:
TCP协议,是基于连接的。
http请求报文
HTTP请求报文由请求行(request line
)、请求头部(header
)、空行和请求数据等4个部分组成。
请求行:(get/post
方法,url
中的path
路径,http
版本)
请求头部(header
)关键字/值对组成,每行一对,关键字和值用英文冒号
请求数据 (body
)
http响应报文
HTTP响应报文由四个部分组成:
- 状态码(
Status Code
):描述了响应的状态。可以用来检查是否成功完成了请求。请求失败的情况下,状态码可用来找出失败的原因。如果Servlet
没有返回状态码,默认会返回成功的状态码HttpServletResponse SC OK
。 - HTTP头部(
HTTP Header
):它们包含了更多关于响应的信息。比如:头部可以指定任务响应过期的过期日期,或者是指定用来给用户安全的传输实体内容的编码格式。如何在Servlet
中检索HTTP
的头部看这里。 - 空行
- 主体(
Body
):它包含了响应的内容。它可以包含HTML代码、图片等。主体是由传输在HTTP消息中紧跟在头部后面的数据字节组成的。
请求过程
客户端连接服务器:
客户端一般为Web
浏览器,通过url
访问服务端,与服务端建立一个TCP
的套接字。
发送HTTP请求:
通过TCP
套接字,发送HTTP请求时,客户端向服务端发送了一个文本的请求报文,一个请求报文由请求行、请求头部、空行和请求数据四部分组成。
返回HTTP响应:
Web服务器解析请求,定位请求资源。服务器将资源副本写到TCP套接字,有客户端读取。一个响应由状态行、响应头部、空行和响应数据四部分组成。
释放TCP连接:
- 当
connection
模式为close
,主动关闭方为服务端,客户端被动关闭连接,释放TCP
连接; - 当
connection
模式为keepalive
,则该连接会保持一段时间,在该时间可以继续接收其他请求,长连接复用,与2.0的多路复用目的都是为了重用连接,减少连接开销。
10. 三次挥手说下?
三次挥手与四次挥手很像,先说下四次挥手。
四次挥手
由主动关闭方(Client)
发起中断连接请求,也就是FIN
报文,被动关闭方(Server)
接收到FIN
报文后,从协议上来说是主动关闭方在等待收到FIN + ACK
报文段,被动关闭方由于有数据要方法,第二次挥手只发了ACK
确认号,接着主动关闭方进入FIN_WAIT
状态,继续等待被动关闭方的FIN报文。
当被动关闭方数据发送完成后,将发送FIN报文给主动关闭方,主动关闭方收到FIN报文后,主动关闭方完成关闭,但被动关闭方并不知道FIN报文是否被接收成功,所以主动关闭方关闭前还需发送ACK
给被动关闭方,表示已成功接收被动关闭方的FIN
报文,这时被动关闭方就可以断开连接了。
如果没收到将再次发送FIN
报文给主动关闭方,最后主动关闭方也不知道被动关闭方是否接收,需要等待2MSL
时间,如果没收到重发包即成功了。
三次挥手
三次挥手不同于四次挥手,不同是第二次与第三次挥手合并了,如果服务端没有数据要发送,就可以将第二次与第三次挥手合并,而如果有数据要发,并且客户端允许延迟收到确认,那么服务端可以将结果封装到第二次与第三次合并的报文段中一起发送。
11. 进程和线程的关系?
定义
进程是资源分配的基本单位,线程是CPU调度和分派的基本单位。
包含关系
线程是进程的一部分,一个线程只能属于一个进行,一个进程可以有多个线程,但至少有一个线程。
内存角度
每个进程分配了不同的内存空间,每个进程都有独立的代码和数据空间,多个进程可以同时运行在内存中,而同一个进程的多个线程(简称同类线程)在其分配的指定内存中运行,需要CPU来调度这一块内存区域。
系统不会为线程分配资源,只能通过CPU来调度和分派资源,也就是说,进程分配内存资源,然后线程需要CPU来过渡使用这块内存。
进程切换开销大,线程切换开销小。
共享角度
同类线程之间可以共享堆空间和方法区和运行时常量池,每个线程都有自己独立的虚拟机栈和程序计数器。
进行共享的方式
线程共享环境:进程代码段、进程公有数据、进程打开的文件描述符、信号处理器、进程当前目录和进程用户ID与进程组ID
进程通信的方式
- 匿名管道 (PIPE)
半双工,即不能同时在两个方向上传输数据,有的系统可能支持全双工。
速度慢,容量有限,且只能在父子进程间。经典的形式就是管道由父进程创建,进程fork子进程之后,就可以在父子进程之间使用了。
- 命名管道 (FIFO)
不想关的进程也能够进行数据交换。
- 消息队列
消息队列,就是一个消息的链表,是一系列保存在内核中消息的列表。
- 信号量
信号量是互斥信号量,能够用来同步通信。
- 共享内存
通过共享内存机制来实现。
- 套接字
套接字通过Socket绑定套接字,服务端开启监听被动连接,客户端主动连接,向套接字读写数据实现通信。
- 信号
一种异步通信方式,可在用户态和内核态中交互,也可以在内核态中通知用户态事件的发生。
12. 了解过CAS嘛?
CAS
是一种乐观锁的实现,CAS
操作包含三个操作数——内存位置(V
)、预期原值(A)期待值(B
)。
如果内存位置的值与预期值向匹配,那么处理器会自动将该位置值更新为期待值,否则不做任何操作。
缺陷:无法解决ABA
问题,在Java
中解决该问题使用到了AtomicStampReference
和AtomicMarkableReference
来解决
数据库中MySQL的锁机制也是通过乐观锁来实现,更具体的实现则是MVCC
多版本并发控制。
具体是两个数据结构,一个为undo log
日志,一个为readView
可读视图。
每张表中都会有隐藏的两列,一列是undo log
指针,指向当前行数据操作指向的数据链表结构,另一列为事务版本号id
,即每次事务开启后都会获取一个自增长的事务id
,这样在ReadView
可读视图中实现乐观操作,回到最先定义乐观锁三个操作数,实现方式差不多。
-
undo log
主要对所有并发修改结果保存了下来,并以链表的形式组织。 -
ReadView
主要处理事务id
的可见性,包含当前活跃事务版本Id列表,活跃最小事务id
(up_limit_id
)即已提交最大事务id + 1
,活跃最大事务id
(low_limit_id
)即最小不可见事务id - 1
和creator_trx_id
表示当前事务开启的版本号。 - 活跃事务即为同一时间并发下,所有发生了交叉的事务。
13. 你的RPC项目怎么怎么划分模块的?
- 服务发现(从注册中心获取服务及对应地址、使用负载均衡策略选择服务)
- 服务注册者(注册服务名和对应地址到注册中心、连接注册中心、清除服务)
- 服务提供者(存放服务实例、获取服务实例)
- 客户端代理(处理客户端请求、处理超时重试、负责分布式请求id生成)
- 服务端(启动服务时将服务所有类实例化并存放到服务提供者,将所有服务类对应服务名注册到服务注册者、处理客户端请求方法、处理超时包、处理重发包、处理异常包)
- 服务端处理器(从服务提供者获取服务实例、读取请求包代理执行服务对应方法)
- 异步请求池(客户端请求调用后立马返回future结果,由netty客户端正确读取结果后返回给异步请求池)
- 编码与解码器(对请求包和响应包的封包和拆包)
- 包检查器(对请求包和响应包的安全检验)
- 注册中心(暴露服务真实地址和端口号、提供服务注册与发现)
- 分布式缓存(缓存时间戳与序列号、重试请求号与请求结果、机器码)
- 服务宕机钩子(中心服务下线与本地服务清除、下线机器码、线程池关闭)
14. 做一套算法题
如有升序链表:list1 = [1,2,3],list2 = [1,4,5],则合并后的链表:list = [1,1,2,3,4,5]
private List concat(List list1, List list2) {
// 头结点存储数据
List p = list1;
List q = list2;
List newNode = new List();
List head = newNode;
while(p.next != null && q.next != null) {
if (p.data < q.data) {
newNode.next = p;
p = p.next;
} else {
newNode.next = q;
q = q.next;
}
newNode = newNode.next;
}
// list2 仍存在节点
if (p.next == null && q.next != null) {
newNode.next = q;
}
// list1 仍存在节点
if (p.next != null && q.next == null) {
newNode.next = p;
}
return head.next;
}