❤️ 说一说ConcurrentHashMap的实现原理❤️介绍一下分代回收机制❤️说一说你对Spring AOP的理解？❤️UDP（用户数据报协议）是什么？❤️说一说线程同步的方式❤️说一说NIO的实现原理❤️说一说hash类型的底层数据结构给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次
❤️ 说一说ConcurrentHashMap的实现原理【得分点】
数组+链表+红黑树、锁头节点
【参考答案】
在JDK8中，ConcurrentHashMap的底层数据结构与HashMap一样，也是采用“数组+链表+红黑树”的形式。同时，它又采用锁定头节点的方式降低了锁粒度，以较低的性能代价实现了线程安全。底层数据结构的逻辑可以参考HashMap的实现，下面我重点介绍它的线程安全的实现机制。
- 初始化数组或头节点时，ConcurrentHashMap并没有加锁，而是CAS的方式进行原子替换（原子操作，基于Unsafe类的原子操作API）。插入数据时会进行加锁处理，但锁定的不是整个数组，而是槽中的头节点。所以，ConcurrentHashMap中锁的粒度是槽，而不是整个数组，并发的性能很好。扩容时会进行加锁处理，锁定的仍然是头节点。并且，支持多个线程同时对数组扩容，提高并发能力。每个线程需先以CAS操作抢任务，争抢一段连续槽位的数据转移权。抢到任务后，该线程会锁定槽内的头节点，然后将链表或树中的数据迁移到新的数组里。查找数据时并不会加锁，所以性能很好。另外，在扩容的过程中，依然可以支持查找操作。如果某个槽还未进行迁移，则直接可以从旧数组里找到数据。如果某个槽已经迁移完毕，但是整个扩容还没结束，则扩容线程会创建一个转发节点存入旧数组，届时查找线程根据转发节点的提示，从新数组中找到目标数据。
【加分回答】
ConcurrentHashMap实现线程安全的难点在于多线程并发扩容，即当一个线程在插入数据时，若发现数组正在扩容，那么它就会立即参与扩容操作，完成扩容后再插入数据到新数组。在扩容的时候，多个线程共同分担数据迁移任务，每个线程负责的迁移数量是 (数组长度 >>> 3) / CPU核心数。
也就是说，为线程分配的迁移任务，是充分考虑了硬件的处理能力的。多个线程依据硬件的处理能力，平均分摊一部分槽的迁移工作。另外，如果计算出来的迁移数量小于16，则强制将其改为16，这是考虑到目前服务器领域主流的CPU运行速度，每次处理的任务过少，对于CPU的算力也是一种浪费。
【延伸阅读】
插入数据的关键代码如下：
final V putVal(K key, V value, boolean onlyIfAbsent) {
...
for (Node[] tab = table;;) {
Node f; int n, i, fh;
// 1.若数组还未初始化，则初始化数组。
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 2.若该位置头节点为空，则初始化头节点。
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node(hash, key, value, null)))
break;
}
数组扩容的关键代码如下：
// 3.若头节点哈希值为MOVED，则表示数组正在扩容，则当前线程也去参与扩容。
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 4.若该位置头节点非空，则追加一个新节点。
else {
V oldVal = null;
// 加锁，锁的不是整个数组，而是头节点。
synchronized (f) {
if (tabAt(tab, i) == f) {
// 头节点为链表节点（参考状态常量）
if (fh >= 0) {
...
}
// 头节点为红黑树节点
else if (f instanceof TreeBin) {
...
}
}
}
// 当链表中节点数达到8时，则扩容数组或者转为红黑树。
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
...
}
}
}
// 计数，若发现数组过小则进行扩容。
addCount(1L, binCount);
return null;
}
private final void transfer(Node[] tab, Node[] nextTab) {
...
// 每个CPU处理的节点数（步长）
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
// 最少设定为16
stride = MIN_TRANSFER_STRIDE;
if (nextTab == null) {
...
// 扩容至2倍
Node[] nt = (Node[])new Node[n << 1];
...
}
// 特殊节点，标识该位置的元素已被转移，并指向新的数组。
ForwardingNode fwd = new ForwardingNode(nextTab);
// bound为遍历的边界，因为每个线程负责转移一部分节点，不是全部。
for (int i = 0, bound = 0;;) {
Node f; int fh;
// advance表示从transferIndex-1遍历到bound位置的过程中，是否需要继续。
// 自旋
while (advance) {
...
// 抢任务（CAS修改TRANSFERINDEX）
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
...
}
}
// i越界，整个集合遍历完成。
if (i < 0 || i >= n || i + n >= nextn) {
// 转移完成
if (finishing) {
// 替换旧数组
nextTable = null;
table = nextTab;
// 将sizeCtl设置为扩容后的1.5倍
sizeCtl = (n << 1) - (n >>> 1);
return;
}
...
}
// tab[i]迁移完毕
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// tab[i]正在迁移
else if ((fh = f.hash) == MOVED)
advance = true;
else {
synchronized (f) {
...
}
}
}
}
❤️介绍一下分代回收机制
【得分点】
新生代收集、老年代收集、混合收集、整堆收集
【参考答案】
标准回答
当前商业虚拟机的垃圾收集器，大多数都遵循了“分代收集”的理论进行设计，分代收集名为理论，实质是一套符合大多数程序运行实际情况的经验法则。而分代收集理论，建立在如下三个分代假说之上，即弱分代假说、强分代假说、跨代引用假说。依据分代假说理论，垃圾回收可以分为如下几类：
- 新生代收集：目标为新生代的垃圾收集。老年代收集：目标为老年代的垃圾收集，目前只有CMS收集器会有这种行为。混合收集：目标为整个新生代及部分老年代的垃圾收集，目前只有G1收集器会有这种行为。整堆收集：目标为整个堆和方法区的垃圾收集。
【加分回答】
HotSpot虚拟机内置了很多垃圾收集器，其中针对新生代的垃圾收集器有Serial、ParNew、Parallel Scavenge，针对老年代的垃圾收集器有CMS、Serial Old、Parallel Old。此外，HotSpot还内置了面向整堆的G1收集器。在上述收集器中，常见的组合方式有：
- Serial + Serial Old，是客户端模式下常用的收集器。ParNew + CMS，是服务端模式下常用的收集器。Parallel Scavenge + Parallel Old，适用于后台运算而不需要太多交互的分析任务。
【延伸阅读】
三个分代假说：
弱分代假说：绝大多数对象都是朝生夕灭的。
强分代假说：熬过越多次垃圾收集过程的对象越难以消亡。
跨代引用假说：跨代引用相对于同代引用来说只占极少数。
前两条假说奠定了多款常用垃圾收集器的一致的设计原则：收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄分配到不同的区域之中存储。根据这两条假说，设计者一般至少会把Java堆划分为新生代和老年代两个区域。在新生代中，每次垃圾收集时都发现有大批对象死去，而每次回收后存活的少量对象，将会逐步晋升到老年代中存放。
第三条假说是根据前两条假说推理得出的隐含结论：存在互相引用关系的两个对象，是应该倾向于同时生存或者同时消亡的。依据这条假说，我们就不应再为了少量的跨代引用去扫描整个老年代，也不必浪费空间专门记录每一个对象是否存在及存在哪些跨代引用，只需在新生代上建立一个全局的数据结构，这个结构把老年代划分成若干小块，标识出老年代的哪一块内存会存在跨代引用。
【得分点】
概念、作用、实现
【参考答案】
标准回答
AOP是一种编程思想，是通过预编译方式和运行期动态代理的方式，在不修改源代码的情况下实现给程序动态统一添加功能的技术。面向对象编程将程序抽象成各个层次的对象，而面向切面编程是将程序抽象成各个切面。所谓切面，相当于应用对象间的横切点，我们可以将其单独抽象为单独的模块。
AOP技术利用一种称为“横切”的技术，剖解开封装对象的内部，将影响多个类的公共行为封装到一个可重用的模块中，并将其命名为切面。所谓的切面，简单来说就是与业务无关，却为业务模块所共同调用的逻辑，将其封装起来便于减少系统的重复代码，降低模块的耦合度，有利用未来的可操作性和可维护性。
利用AOP可以对业务逻辑各个部分进行隔离，从而使业务逻辑各部分之间的耦合度降低，提高程序的可重用性，同时提高开发效率。
AOP可以有多种实现方式，而Spring AOP支持如下两种实现方式。
· JDK动态代理：这是Java提供的动态代理技术，可以在运行时创建接口的代理实例。Spring AOP默认采用这种方式，在接口的代理实例中织入代码。
· CGLib动态代理：采用底层的字节码技术，在运行时创建子类代理的实例。当目标对象不存在接口时，Spring AOP就会采用这种方式，在子类实例中织入代码。
【加分回答】
在应用场景方面，Spring AOP为IoC的使用提供了更多的便利。一方面，应用可以直接使用AOP的功能，设计应用的横切关注点，把跨越应用程序多个模块的功能抽象出来，并通过简单的AOP的使用，灵活地编制到模块中，比如可以通过AOP实现应用程序中的日志功能。另一方面，在Spring内部，例如事务处理之类的一些支持模块也是通过Spring AOP来实现的。
AOP不能增强的类：
Spring AOP只能对IoC容器中的Bean进行增强，对于不受容器管理的对象不能增强。
由于CGLib采用动态创建子类的方式生成代理对象，所以不能对final修饰的类进行代理。
【延伸阅读】
AOP的术语：
· 连接点（join point）：对应的是具体被拦截的对象，因为 Spring 只能支持方法，所以被拦截的对象往往就是指特定的方法， AOP将通过动态代理技术把它织入对应的流程中。
· 切点（point cut）：有时候，我们的切面不单单应用于单个方法，也可能是多个类的不同方法。这时，可以通过正则式和指示器的规则去定义，从而适配连接点。切点就是提供这样一个功能的概念。
· 通知（advice）：就是按照约定的流程下的方法，分为前置通知（ befor advice ）、后置通知（ after advice ）、环绕通知 （around advice）、事后返回通知（afterRetuming advice）和异常通知 ( after Throwing advice ），它会根据约定织入流程中，需要弄明白它们在流程中的顺序和运行的条件。
· 目标对象（target）：即被代理对象。
· 引入（introduction）： 是指引入新的类和其方法，增强现有 Bean 的功能。
· 织入（weaving）：它是一个通过动态代理技术，为原有服务对象生成代理对象然后将与切点定义匹配的连接点拦截，并按约定将各类通知织入约定流程的过程。
· 切面（aspect）：是一个可以定义切点、各类通知和引入的内容，SpringAOP 将通过它的信息来增强 Bean 的功能或者将对应的方法织入流程。
❤️UDP（用户数据报协议）是什么？udp介绍
❤️说一说线程同步的方式【得分点】
synchronized、Lock
【参考答案】
【标准回答】
Java主要通过加锁的方式实现线程同步，而锁有两类，分别是synchronized和Lock。
synchronized可以加在三个不同的位置，对应三种不同的使用方式，这三种方式的区别是锁对象不同：
加在普通方法上，则锁是当前的实例（this）。
加在静态方法上，则锁是当前类的Class对象。
加在代码块上，则需要在关键字后面的小括号里，显式指定一个对象作为锁对象。
不同的锁对象，意味着不同的锁粒度，所以我们不应该无脑地将它加在方法前了事，尽管通常这可以解决问题。而是应该根据要锁定的范围，准确的选择锁对象，从而准确地确定锁的粒度，降低锁带来的性能开销。
synchronized是比较早期的API，在设计之初没有考虑到超时机制、非阻塞形式，以及多个条件变量。若想通过升级的方式让synchronized支持这些相对复杂的功能，则需要大改它的语法结构，不利于兼容旧代码。因此，JDK的开发团队在1.5引入了Lock，并通过Lock支持了上述的功能。Lock支持的功能包括：支持响应中断、支持超时机制、支持以非阻塞的方式获取锁、支持多个条件变量（阻塞队列）。
【加分回答】
synchronized采用“CAS+Mark Word”实现，为了性能的考虑，并通过锁升级机制降低锁的开销。在并发环境中，synchronized会随着多线程竞争的加剧，按照如下步骤逐步升级：无锁、偏向锁、轻量级锁、重量级锁。
Lock则采用“CAS+volatile”实现，其实现的核心是AQS。AQS是线程同步器，是一个线程同步的基础框架，它基于模板方法模式。在具体的Lock实例中，锁的实现是通过继承AQS来实现的，并且可以根据锁的使用场景，派生出公平锁、不公平锁、读锁、写锁等具体的实现。
【延伸阅读】
想要保证线程安全，不止线程同步一种手段，还包含如下常见办法：
- 原子类：可以用原子方式更新一个变量，即在变量未被其他线程修改时才出发更新，否则会引发失败。volatile：volatile是一个轻量级的锁，它通过保证内存可见性的办法来实现线程安全。并发工具：还有很多并发工具类，一样可以保证线程安全，如Semaphore、CountDownLatch、CyclicBarrier。
【得分点】
Buffer、Channel、Selector
【参考答案】
【标准回答】
NIO是基于IO多路复用模型的实现，它包含三个核心组件，分别是Buffer、Channel、Selector。
- NIO是面向缓冲区的，在NIO中所有的数据都是通过缓冲区处理的。Buffer就是缓冲区对象，无论读取还是写入，数据都是先进入Buffer的。Buffer的本质是一个数组，通常它是一个字节数组，也可以是其他类型的数组。Buffer是一个接口，它的实现类有ByteBuffer、CharBuffer、ShortBuffer、IntBuffer、LongBuffer、FloatBuffer、DoubleBuffer。Channel是一个通道，可以通过它读取和写入数据。与流不同的是，流是单向的，而Channel是双向的。数据可以通过Channel读到Buffer里，也可以通过Channel写入到Buffer里。为了支持不同的设备，Channel接口有好几种子类，如FileChannel用于访问磁盘文件、SocketChannel和ServerSocketChannel用于TCP协议的网络通信、DatagramChannel用于UDP协议的网络通信。Selector是多路复用器，可以通过它监听网络IO的状态。它可以不断轮询注册的Channel，如果某Channel上有连接、读取、写入事件发生，则这个Channel就处于就绪状态，就会被Selector轮询出来。所有被轮询出来的Channel集合，我们可以通过SelectionKey获取到，然后进行后续的IO操作。
【加分回答】
Buffer对象包含三个重要的属性，分别是capacity、position、limit。其中，capacity代表Buffer的容量，就是说Buffer中最多只能写入capacity个数据。position代表访问的位置，它的初始值为0，每读取/写入一个数据，它就会向后移动一个位置。limit代表访问限制，就是本次操作最多能读取/写入多少个数据。这三个属性的关系是，position<=limit<=capacity，Buffer通过不断调整position和limit的值，使得自身可以不断复用。
【延伸阅读】
Java NIO根据操作系统的不同，会对Selector做不同的实现。如Linux上的PollSelectorProvider、Windows上的WindowsSelectorProvider、MacOS上的KQueueSelectorProvider等。在使用Selector时，我们不需要指定哪一个实现，JDK会自动选择合适的Selector实现。
【得分点】
ziplist、hashtable
【参考答案】
标准回答
Redis的哈希对象的底层存储可以使用ziplist（压缩列表）和hashtable（字典）。当哈希类型元素个数小于hash-max-ziplist-entries 配置（默认512个），同时所有值都小于hash-max-ziplist-value配置（默认64 字节）时，Redis会使用ziplist作为哈希的内部实现。ziplist使用更加紧凑的结构实现多个元素的连续存储，所以在节省内存方面比hashtable更加优秀。当哈希类型无法满足ziplist的条件时，Redis会使用hashtable作为哈希的内部实现，因为此时ziplist的读写效率会下降，而 hashtable的读写时间复杂度为O（1）。
加分回答
压缩列表是Redis为了节约内存而开发的，它是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者一个整数值。一个压缩列表的重要保存部分包括—zlbytes、zltail、zllen、entryX、zlend，其类型长度以及用途如下表所示：
| 属性 | 类型 | 长度 | 说明 |
|---|---|---|---|
| zlbytes | uint32_t | 4字节 | 压缩列表占用的内存字节数； |
| zltail | uint32_t | 4字节 | 压缩列表表尾节点距离列表起始地址的偏移量（单位字节）； |
| zllen | uint16_t | 2字节 | 压缩列表包含的节点数量，等于UINT16_MAX时，需遍历列表计算真实数量； |
| entryX | 列表节点 | 不固定 | 压缩列表包含的节点，节点的长度由节点所保存的内容决定； |
| zlend | uint8_t | 1字节 | 压缩列表的结尾标识，是一个固定值0xFF； |
字典（dict）又称为散列表，是一种用来存储键值对的数据结构。C语言没有内置这种数据结构，所以Redis构建了自己的字典实现。Redis字典的实现主要涉及三个结构体：字典、哈希表、哈希表节点。其中，每个哈希表节点保存一个键值对，每个哈希表由多个哈希表节点构成，而字典则是对哈希表的进一步封装。
【延伸阅读】
压缩列表结构示意图：
压缩列表节点示意图：
字典：三个结构体：字典、哈希表、哈希表节点之间的关系图：
其中，dict代表字典，dictht代表哈希表，dictEntry代表哈希表节点。可以看出，dictEntry是一个数组，这很好理解，因为一个哈希表里要包含多个哈希表节点。而dict里包含2个dictht，多出的哈希表用于REHASH。当哈希表保存的键值对数量过多或过少时，需要对哈希表的大小进行扩展或收缩操作，在Redis中，扩展和收缩哈希表是通过REHASH实现的，执行REHASH的大致步骤如下：
- 为字典的ht[1]哈希表分配内存空间
如果执行的是扩展操作，则ht[1]的大小为第1个大于等于ht[0].used*2的2n。如果执行的是收缩操作，则ht[1]的大小为第1个大于等于ht[0].used的2n。将存储在ht[0]中的数据迁移到ht[1]上
重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。将字典的ht[1]哈希表晋升为默认哈希表
迁移完成后，清空ht[0]，再交换ht[0]和ht[1]的值，为下一次REHASH做准备。
当满足以下任何一个条件时，程序会自动开始对哈希表执行扩展操作：
- 服务器目前没有执行bgsave或bgrewriteof命令，并且哈希表的负载因子大于等于1；服务器目前正在执行bgsave或bgrewriteof命令，并且哈希表的负载因子大于等于5。
为了避免REHASH对服务器性能造成影响，REHASH操作不是一次性地完成的，而是分多次、渐进式地完成的。渐进式REHASH的详细过程如下：
- 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表；在字典中的索引计数器rehashidx设置为0，表示REHASH操作正式开始；在REHASH期间，每次对字典执行添加、删除、修改、查找操作时，程序除了执行指定的操作外，还会顺带将ht[0]中位于rehashidx上的所有键值对迁移到ht[1]中，再将rehashidx的值加1；随着字典不断被访问，最终在某个时刻，ht[0]上的所有键值对都被迁移到ht[1]上，此时程序将rehashidx属性值设置为-1，标识REHASH操作完成。
REHSH期间，字典同时持有两个哈希表，此时的访问将按照如下原则处理：
- 新添加的键值对，一律被保存到ht[1]中；删除、修改、查找等其他操作，会在两个哈希表上进行，即程序先尝试去ht[0]中访问要操作的数据，若不存在则到ht[1]中访问，再对访问到的数据做相应的处理。
class Solution {
public:
int kmp(string s, string t) {
// write code here
int n = s.size(), m = t.size();
s = ' ' + s, t = ' ' + t;
int ne[n + 10];
memset(ne, 0, sizeof ne);
for (int i = 2, j = 0; i <= n; i ++) {
while (j && s[j + 1] != s[i]) j = ne[j];
if (s[j + 1] == s[i]) j ++;
ne[i] = j;
}
int ans = 0;
for (int i = 1, j = 0; i <= m; i ++) {
while (j && s[j + 1] != t[i]) j = ne[j];
if (s[j + 1] == t[i]) j ++;
if (j == n) ans ++;
}
return ans;
}
};
