腾讯一面

自我介绍这里一笔带过，给对面介绍自己内在 + 外在 + 校园经历 + 校园项目 + 意向岗位

腾讯子公司云智研发一面

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;
}