春招经过一个月的刷面经，我顺利拿到字节offer

春招

携程

https://www.nowcoder.com/discuss/600989?source_id=discuss_experience_nctrack&channel=-1

Object有哪些方法

首先答Object是所有类的父类，任何类都默认继承自Object，它的方法有：

（1）getClass，获取运行时的类型，返回一个Class对象

（2）equals方法，判断对象引用的地址是否相等，所以默认与==一样，一般子类都要重写。

（3）hashCode方法，返回对象的hash值，一般子类重写了equals就要重写hashcode，保证相同对象有相同hash值。

（4）toString方法，打印对象的信息

（5）clone方法，实现对象的浅拷贝，需实现克隆的接口。

（6）wait() 和 notify()方法，是多线程中的方法，等待唤醒

wait() 和 notify(), 具体使用场景

让当前线程进入等待状态（超时等待），同时也会让当前线程释放它所持有的锁。

直到其他线程调用此对象的 notify() 方法或 notifyAll() 方法，以及中断该线程，或者时间间隔到了，当前线程被唤醒

equals() 和 hashcode()

重写equals方法时，建议重写hashcode方法来保证相同对象的hashcode值相同。

HashMap的put方法

put方法就是通过计算对象的hash值，插入到对应桶中，如果桶中有元素就插入到链表中（8之前头插，8之后尾插法），二者都可能会造成线程不安全的情况。

头插法因为链表前后顺序倒置，多线程插入时，指向会混乱，从而可能形成环形链表，造成数据丢失。尾插法可能还是会造成数据的覆盖。

给个单链表，找到中间元素。（快慢指针）

https://www.nowcoder.com/discuss/600820?source_id=discuss_experience_nctrack&channel=-1

三道算法

如何实现一个栈（一个数组，一个栈顶指针来控制先进后出）
如何实现最小栈（原地肯定没办法，要保持原有的结构，需要加一个栈，在对应值push时与栈顶作比较，值小就放，大就再冗余一个栈顶）
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

双指针，一头一尾，是奇数才++，后者是偶数才–，然后交换，再判断。（奇偶判断， &1 操作）

类、抽象类、接口的区别

（1）类一般是具有实例化功能，接口不能实例化，抽象类必须实现了全部实例方法的类才能实例化。

（2）接口全是抽象方法，而抽象类可以有非抽象方法。

（3）抽象类抽象方法必须实现完，但如果自身还是抽象类就可以不用实现，但是接口必须全部实现方法。

（4）Java中不能多继承，但可以多实现接口

（5）我们一般想要一些默认实现，就会选抽象类，有利于代码复用。接口一般就是多态的实现，实现功能拓展，对不同功能模块实现名字统一。

顺丰科技

https://www.nowcoder.com/discuss/518354?type=post&order=time&pos=&page=0&channel=1009&source_id=search_post

like什么时候可以用索引

只有%在后面时，索引才会生效
bean的生命周期

（1）一般就先实例化嘛（2）然后Spring再用bean读取器根据配置的xml文件，通过构造方法，set方法来进行属性的注入，或者直接加Autowired注解注入。

（3）容器就可以正常的使用（4）最后根据它的scope配置进行销毁，单例就跟随容器销毁，或者每次使用就创建然后销毁，或者每次请求完后销毁

数据库的隔离级别，分别有什么问题

数据库事务的隔离级别呢，主要是四种：（1）读未提交，读写锁均在操作完成后就释放，会产生脏读、不可重复读、幻读三种情况。（2）读已提交，读锁在操作完后释放，而写锁一直持续到事务结束。这样就避免了脏读，会产生不可重复读、幻读情况。（3）可重复读，读写锁均持续到事务结束，这样就可以重复读了，但还是会产生幻读（4）最后一种就是串行化，封锁住表，这样就不会产生同步问题。

线程和进程的区别

（1）进程呢是cpu资源分配的基本单位，而线程是cpu调度的基本单位。（2）进程拥有完整的资源，而线程只独享部分资源，例如寄存器和栈（3）所以线程能减少并发执行的时间和空间上的开销，而进程呢还需要进行内存管理，涉及到用户态和内核态的切换。

如何判断链表是否成环（快慢指针）
线程池的参数

主要参数有核心线程数，最大线程数，以及等待队列，还有就是keep-alivetime最大的等待时间，创建线程的factory，以及拒绝策略。

如何创建线程

（1）最简单就是继承Thread类来创建（2）第二种是比较常见的，实现Runnable来创建代理类然后创建线程，因为Thread底层也是通过Runnable来创建

（3）实现Callable和Future来创建一个可以返回值的线程，同时可以抛出异常。（4）使用线程池来创建。

二分查找算法

public int binarySearch(int[] nums, int k) {
    int begin = 0;
    int end = nums.length;

    while (begin < end) {
        int mid = (begin + end) >> 1;
        if (nums[mid] == k) {
            return mid;
        } else if (k < nums[mid]) {
            end = mid;
        } else {
            begin = mid + 1;
        }
    }
    return -1;
}

https://www.nowcoder.com/discuss/408306?type=2&order=0&pos=60&page=1&source_id=discuss_tag&channel=666

数组转list的方式

在new ArrayList<>（添加一个Arrays.asList(nums));，因为Arrays.asList(strArray)返回值是java.util.Arrays类中一个私有静态内部类java.util.Arrays.ArrayList，它并非我们util包下的ArrayList，它不支持增删改查。

为什么重写equals要重写hashcode方法

（1）因为equals方法默认与==一样，对象的话就比较引用的地址。而有时在一些集合中，例如HashMap就需要key，value相同就相同，就需要重写equals方法来保证自定义对象的相同。

（2）一般重写equals还要重写hashcode方法，要保证相同的对象hashcode相同。例如HashMap中，必须key的hashcode值与value的hashcode值作为其hashcode值。

HashMap的 hashcode和equals方法。

public final int hashCode() {
    return Objects.hashCode(this.key) ^ Objects.hashCode(this.value);
}
public final boolean equals(Object var1) {
    if (var1 == this) {
        return true;
    } else {
        if (var1 instanceof Entry) {
            Entry var2 = (Entry)var1;
            if (Objects.equals(this.key, var2.getKey()) && Objects.equals(this.value, var2.getValue())) {
                return true;
            }
        }

        return false;
    }
}

synchronized锁的底层原理（升级后的策略）

（1）synchronized是JVM层面的锁，它底层主要是Monitor管程来实现的同步机制。（2）当同步对象时，会在对象头中有对应的Monitor指针；同步方法时，方法中会设置Monitor标志位，其他线程会阻塞；同步代码块时，同理两段代码进出，底层依赖操作系统的mutex lock原语。

（3）在Java6之后，对synchronized这种重量级的锁进行锁升级。开始的时候无锁都能访问；

然后一旦有线程锁定了这一个对象，对象的标志位修改，进入偏向模式，同一个线程可以持续获取锁（重入），对标志位加1即可；

一旦有多个线程访问时，会升级为轻量级锁，将Mark Word字段拷贝到该线程对应的jvm栈中生成一段空间，里面有owner指针指向当前对象。成功即加锁成功，然后在锁对象的Mark Word字段中又指向栈中的锁记录，实现绑定。其它线程CAS不成功时，会进行自旋，当自旋个数超过cpu一半，或者次数超过10次就升级为重量级锁；

使用monitor来实现线程的同步。与之前是一致的。

volatile以及cas原理，cas底层实现

volatile的原理：volatile主要依赖于Java的内存模型和缓存一致性协议，主要实现可见性，有序性。底层主要是基于lock前缀指令，在对共享变量进行写操作时，必须马上写回到主存中，然后其他CPU通过总线嗅探机制监听总线，监听到修改后，工作内存中的值失效，重新触发一次内存的 read， load，use操作。

string以及stringbuffer

String是不可变的字符序列，底层是char数组，8之后就改成了byte数组。不可变主要是节约空间，同时保证多线程的线程安全。而StringBuffer与StringBuilder同样，是可变的字符序列，同时StringBuffer是线程安全的，方法都通过了synchronized修饰。

计算机网络，tcp拥塞控制

tcp的拥塞控制主要是避免发送方的数据将整个网络通信通道填满，在发送方那边调节发送量。主要有四种算法

（1）开始时慢启动，先一点点发送数据包，每返回一个ack，拥塞窗口就加1，当达到门限时结束慢启动。

（2）进入到拥塞避免的模式，进入到对数增长，增加窗口分之1。

（3）当重传计时器超时，网络出现拥塞，进入到拥塞发生算法，之后就分两种 超时重传和快速重传 。（超时重传门限降为1/2，窗口置为1，不用太抖了了，造成网络卡顿）

快速重传是当收到三个相同的ack时触发，窗口和门限置为当前窗口的1/2。

（4）最后进行快速恢复，窗口设置为门限 + 3，重传丢失的，进入拥塞避免状态。

在这里插入图片描述

红黑树，b+树原理，数据库为什么选择b+

（1）红黑树是一种AVL树，红色节点是被黑色节点隔开的，叶子节点都是黑色的空节点，搜索的时间复杂度为logn级别。

（2）b+树，它是一种横向的树，非叶子节点都是存储的是索引，叶子节点冗余的存储所有索引字段（依次递增），叶子节点之间是用指针连接的

优势：它主要可以放更多的索引，并且叶子之间指针相互连接，增加了区间的访问效率，利于数据库查询。

快排，以及Arrays.sort()原理

（1）快排就是先找一个轴点begin（使用随机数和方向标志增加分散概率），end那边是大于原先轴点pivot的，小于的话就扔过去，begin那边同理。

最后begin与end相等处，nums[begin] = pivot；return begin（轴点索引）即可。

（2）Arrays.sort()：在数组的数量小于47的情况下使用插入排序；在大于或等于47或少于286会进入快速排序（双轴快排）；大于286采用归并排序

redis为啥快

（1）redis是运行在内存的，自然就快（2）redis的数据结构简单，操作节省时间

（3）redis是单线程（基于内存，单线程不会让cpu成为瓶颈）的，节省了上下文切换时间。采用了多路复用io阻塞机制，一个线程可以复用多个连接，自然就读取速度快。

阿里

https://www.nowcoder.com/discuss/598750?source_id=discuss_experience_nctrack&channel=-1

Java内存模型、主内存和工作内存交互操作

（1）Java的内存模型，描述了多线程情况下对共享变量的访问规则。规定了（1）共享资源都是存储在主内存中的（2）每个线程有自己的工作空间，每次read主内存中的共享变量load进工作内存进行操作。（3）最重要的就是线程间不能访问对方的工作内存，线程值只能通过主内存进行中转。

（2）主内存和工作内存交互操作：主要是read，load，use还有回主内存的assign，lock，store，write，unlock操作。他们对应工作内存对主内存的读取，记载进工作内存，到引擎中使用。然后操作完毕后赋给工作内存，加锁，存储，写入主内存，解锁。

voliatle怎么实现的、工作原理是什么、总线嗅探机制了解吗

voliatle可以实现可见性、有序性。它的工作原理依赖于Java的内存模型和缓存一致性原则。 底层基于lock前缀指令，对共享变量写操作时，必须是马上写回主内存，然后其他线程通过总线嗅探机制，得知到修改，会使工作内存中的值失效，然后重新触发一次read load use的操作。

synchronized的锁优化有哪些、讲一下锁状态和锁升级

（1）锁优化一共有：自旋锁，当阻塞时，先不进行阻塞，看能否循环获取锁，如果成功就拿到锁，当达到一定次数时（个数为cpu一半，次数为10次），就自旋失败作调整。锁消除，JVM发现这个锁对象不会被其他的线程引用，就会消除掉锁。锁粗化，当一个资源同时加很多锁，会合并为粗锁。

（2）其他的偏向锁，轻量级锁，在synchronized锁升级讲到。

什么情况下用ReentrantLock而不用synchronized

ReentrantLock在这些场景下使用，例如可中断、实现公平锁、实现选择通知（创建多个Condition对象来通知，线程注册到Condition上，有选择性的通知线程。）

Java的中断怎么实现，synchronized不能中断，ReentrantLock可以中断

Java中断是对线程调用interrupt方法

（1）当线程处于运行态RUNNABLE时，不会抛出异常，至少修改线程的中断状态值。（2）当线程通过sleep，wait等方法进入到阻塞态时，会抛出中断异常。（3）当线程使用LockSupport来挂起时，会修改中断状态值并返回。

ReentrantLock默认不可中断，但可通过lockInterrupt方法来可中断的获取锁，可以让等待中挂起的线程响应中断。

ReentrantLock怎么实现的

ReentrantLock是基于AQS这种同步管理框架来实现的可重入锁，有个int状态值state，表示锁被占用情况，还有一个node队列，有个内部类sync继承自AQS，实现了AQS的功能，sync有公平锁和非公平锁两种实现，默认非公平锁。

列举几种你知道的垃圾回收机制

标记-清除算法

先把内存区域中的这些对象进行标记，哪些属于可回收标记出来，然后把这些垃圾拎出来清理掉。但它存在一个很大的问题，那就是内存碎片。

标记-整理算法

标记-整理算法标记过程仍然与标记-清除算法一样，但后续是让所有存活的对象都向一端移动，再清理掉端边界以外的内存区域。

复制算法

它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。保证了内存的连续可用，但内存使用率只有原先一半，代价实在太高。

分代收集算法

在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。

在老年代中，因为对象存活率高、没有额外空间对它进行分配担保，就必须使用标记-清理算法或者标记-整理算法来进行回收。

CMS垃圾收集的原理

CMS是老年代的并发垃圾收集器：垃圾回收与用户线程并发执行

老年代的收集器，使用标记-清除算法，分四步，两步执行时间较长的步骤（并发标记，并发清除）运行工作线程一起执行，但只能搭配Serial收集器或者parNew收集器。

特点：并发操作使得程序变慢；并发阶段产生新的浮动垃圾；因为是标记-清除算法，使得碎片化，出现大对象无法分配从而Full GC，进行碎片整理。

过程

初始标记：标记GC Roots直接关联到的对象，这个过程要使得所有工作线程停顿

并发标记：进行GC Roots 整个对象可达性标记，耗时所以和工作线程并发运行

重新标记：工作线程的运行会导致标记发生变动，这一步用于修正标记。

并发清除：开始垃圾回收，可以与工作线程一起执行（所以是标记-清除）

有什么方法来避免Full GC

避免频繁创建销毁大对象，将大对象设置为单例模式。
把新生代Eden区内存空间调大

谈一下Java类加载机制

（1）类加载的时机

使用new实例化对象时
读取或设置一个静态字段（final除外）、调用静态方法
对类型反射调用，没有被初始化就进行初始化
初始化子类时，发现父类还未初始化
虚拟机启动时，要执行的主类会被初始化

上述为主动引用，而其他方式都是被动引用，不会触发初始化。例如：子类调用父类静态字段、数组定义形式引用类、调用类的final静态字段则不会触发本类的初始化。

（2）类加载过程

类的加载被分为了加载–>验证–>准备–>解析->初始化几个阶段：

加载主要是通过全限定类名生成Class文件，Class文件按照JVM设定的格式存储在方法区。
验证是验证Class文件是否符合JVM的规范。
准备是为类变量等分配内存，设置零值。
解析时将常量池中的符号引用转换为直接引用（通过全限定类名去找，com那些包里面的）。
初始化赋值，执行构造器方法，如果一个类没有static变量赋值操作和static块，可以不生成。

缓存一致性问题

先删除缓存，再更新数据库。然后更新数据库的操作与缓存查询数据库的操作在同一个MQ里面。

快排的时间复杂度是什么，最坏的时间复杂度什么情况下会发生、怎样避免

快排的平均时间复杂度是nlogn，最坏的时间复杂度是n^2，枢纽元为最大或者最小数字，那么所有数都划分到一个序列去了。

避免的话：

每次快排选取区间中随机的一个值作为枢纽，不再是第一个或最后一个元素。
当待排序序列的长度分割到一定大小后，使用插入排序

NIO和BIO

Java BIO ：同步阻塞IO，服务器端为一个连接一个线程，即客户端有连接请求时服务器端就需要启动一个线程进行处理，如果这个连接不执行会造成不必要的线程开销。

而Java NIO ：同步非阻塞，区别于操作系统中的I/O模型，NIO是多路复用的，在内核设立了专门的线程selector去轮询访问所有的socket，而不需要具体操作的线程阻塞等待。NIO是面向缓冲区。数据读取到一个它稍后处理的缓冲区，需要时可在缓冲区中前后移动。

BIO和NIO的比较：

效率：BIO 以流的方式处理数据,而 NIO 以块的方式处理数据,块 I/O 的效率比流 I/O 高很多
阻塞：BIO 是阻塞的，NIO 则是非阻塞的
BIO基于字节流和字符流进行操作，而 NIO 基于 Channel(通道)和 Buffer(缓冲区)进行操作，数据总是从通道读取到缓冲区中，或者从缓冲区写入到通道中。Selector(选择器)用于监听多个通道的事件（比如：连接请求，数据到达等），因此使用单个线程就可以监听多个客户端通道。
阻塞与非阻塞，同步与异步

（1）我们平时说的阻塞或非阻塞是指应用程序在发起 I/O 操作时，是等待还是立即返回。

（2）同步和异步，是指应用程序在与内核通信时，数据从内核空间到应用空间的拷贝，是由内核主动发起还是由注册了的回调函数也就是应用程序来触发。

https://www.nowcoder.com/discuss/603294?source_id=discuss_experience_nctrack&channel=-1

TCP里面遇到滑动窗口为0会发生什么？

TCP有窗口探测机制，发送方在窗口为0时候，会启动计时机制，在超时未收到窗口信息，就会发送窗口探测包，以便知道接收方窗口发生改变。

了解协程吗？

协程是一轻量级的线程，正如一个进程可以拥有多个线程一样，一个线程可以拥有多个协程。

协程仅仅是一个特殊的函数，但这些函数都是串行运行的。当一个协程运行时，其它协程必须挂起。

sql的主键索引和辅助索引（区别于非聚集索引存的是磁盘指针）

主键索引和非主键索引的区别是：主键索引的叶子节点存放的是整行数据，非主键索引的叶子节点存放的是主键的值。非主键索引也被称为二级索引，需要回表进行二次查询

了解回表吗?

回表应用于基于非主键索引的查询需要多扫描一次索引树，就是先通过数据库索引扫描出数据所在的行，再通过行主键id取出索引中未提供的数据。

sql的执行过程

查询语句的执行流程如下：
连接器==》缓存==》分析器 ==》优化器 ==》执行器 ==》引擎
更新语句执行流程如下：
分析器 ==》权限校验 ==》执行器 ==》引擎 ==》redo log(prepare 状态 ==》binlog ==》redo log(commit状态)

字节

https://www.nowcoder.com/discuss/600811?source_id=discuss_experience_nctrack&channel=-1

怎么创建线程

四种方式，（1）最简单就是继承Thread类来创建（2）第二种是比较常见的，实现Runnable来创建代理类然后创建线程，因为Thread底层也是通过Runnable来创建（3）实现Callable和Future来创建一个可以返回值的线程，同时可以抛出异常。（4）使用线程池来创建。

索引建立的根据

（1）索引一般建立在表的主键和外键（2）索引建立在经常使用where连接的字段（3）经常需要范围查找的列

哪些列不适合建索引？

很少查询的列，更新很频繁的列，数据值的取值比较少的列（比如性别）

为什么要使用redis

使用redis主要是来作为缓存，可以减轻数据库的压力，对应一些频繁操作的数据，考虑用redis，主要是她会将数据保存在内存中，来提高用户的访问速度。

redis之所以快，是因为（1）redis是基于内存的操作，操作都在内存中（2）redis它的value数据结构比较简单，操作效率高（3）redis是单线程的，实现IO的多路复用机制，线程可以复用来处理多个连接请求，自然效率就会很高。（连接请求和事件处理都是放到队列中，依次进行分派）

什么是UDP，UDP有什么特点

UDP是计网中传输层的协议，它是面向报文，无连接，一对多的，不可靠的一种传输层协议，同时它头部开销小，传输数据报文也比较高效。头部只有源和目的端口号。

（1）它的面向报文，应用层用户发送过来的报文，添加完头部数据后 8byte，直接发给网络层了。

（2）它的面向无连接，是指它不需要通过三次握手建立连接，随时发送数据，传输数据只添加udp的头信息。

（3）它的一对多呢，是指不像TCP是单个连接一对一传输，支持多向传输。一对多，多对多之类的。

（4）它的不可靠性体现在无连接上，不需要建立连接，也就不知道报文是否完整到达接收方；还有就是UDP不像TCP一样有拥塞控制，它发送速率一致，这也导致网络通道的阻塞，会丢包。

算法：找出数组中出现次数超过一半的数字(众数)；股票一天交易

int value = array[0];
int count = 1;
for (int num : array) {
    if (num == value) {
        count++;
    } else {
        count--;
    }
    if (count == 0) {
        value = num;
        count = 1;
    }
}
// value就是出现最多的数，然后count = 0

// 动态规划求解
int maxPrices = 0;
int pre = prices[0];
for (int i = 1; i < prices.length; i++) {
    maxPrices = Math.max(maxPrices, prices[i] - pre);
    pre = Math.min(prices[i], pre);
}

https://www.nowcoder.com/discuss/604160?source_id=discuss_experience_nctrack&channel=-1

项目里用到数据库，了解索引吗？数据库的事务？

索引是能够增加数据库查询效率的，主要有聚集索引和非聚集索引，还有就是多个字段的话，就联合索引。

（1）聚集索引，数据库中物理行的顺序与主键顺序是一样的。数据库由于与非聚集索引顺序不同，则可以有多个非聚集索引。

（2）非聚集索引，叶子节点中就存储的是磁盘指针。还需要进行二次的磁盘查询。

（3）Mysql索引数据结构采用b+树，hash与b树一样不适合范围查询。b+树好处：非叶子节点不存储数据只存索引，可以放更多索引；非叶子节点冗余而且是递增的，利于指针连接，增加了区间查询的效率。

（4）联合索引（辅助索引）的最左前缀原则：因为查询时，联合索引的第一个字段优先级最高，可以在b+树中搜索。如果abc三个字段联合索引，sql里只有bc的话就使用不到索引了，只能在叶子节点中进行遍历。

事务：事务保证了操作只能成功或者失败，mysql默认的事务隔离级别是可重复读，读写锁均在事务完成后进行释放。

sql优化：

（1）可以使用explain关键字，来查看sql语句的执行情况，以及索引的一些使用情况。

（2）在查询频率高的地方，使用索引，来提高查询效率。

（3）避免使用select *，返回没必要的列，用具体的字段来查询。

（4）使用limit，不返回没必要的行

（5）使用缓存来避免在数据库中进行查询。

Http状态码？状态码301，302的区别？502，503，504？

（1）状态码是在http响应中响应行位置，像100-200之间的话就是需要用户进行操作的提示；2xx之间的呢就是返回成功，操作被接收处理；

3xx的呢就是返回重定向的操作，4xx返回的是客户端的错误，5xx返回的是服务器端的错误。

（2）301，302的区别，都是重定向，区别在于请求资源的url路径是否被永久的移动，301是永久移动，302只是临时的移动。

（3）502,503,504的区别，503是服务器无法处理请求，502是从远端服务器获取到了无效的响应，而504是从服务器端获取响应超时。

服务端需要输入一个数字，客户端输入了一个字符串，返回什么状态码？

应该是返回400的，客户端请求错误。

http头部？

头部包括，请求和响应的行，头，体。

请求行就是请求的方式，get，post，请求的url路径，以及协议的类型比如http1.1之类

请求头就是请求对应的主机信息，连接类型（1.1是长连接，流水线多个请求），cookie等等

请求体里面主要就是请求的参数

响应行里面，主要就是一些状态码，协议类型

响应头里面，响应文本的类型，格式等等

响应体里面，响应的文本，就是返回给我们的数据。

get和post的区别

get方法是从服务器端读取数据，而post是向服务器端推送数据，数据放在请求体里面。

（1）post方法是不安全不幂等的，请求会破坏服务器的资源，并且多次提交结果可能不会相同。

（2）get请求，浏览器直接会连同请求体推出去，并返回响应。post会先将发送请求行，请求头推送，然后100状态码后，确认安全后，再推送请求体的数据。

tcp，http为什么用到tcp，tcp怎么做到可靠？

（1）因为http需要tcp这种可靠性的传输层协议来传输请求。

（2）TCP是面向连接的，传输时需要三次握手建立连接，维护传输双方的序列号（通过双方的ip和端口，再加上一个计时器通过算法得出一个序号），以及滑动窗口的大小。

（3）TCP拥有超时重传与快速重传机制，超时重传是当发送数据时，针对每个数据设定一个ACK的定时器，如果超时就重发。快速重传是，当接收到三次相同的ACK时，会触发重传机制。例如，接收方发现 6、8、9 都已经接收了，就是 7 没来，那肯定是丢了，于是发送三个相同的 ACK，要求下一个是 7。客户端收到 3 个，就会发现 7 的确又丢了，不等超时，马上重发。

（4）TCP有流量控制机制，发送方发送数据 <= 接收方获取数据的能力，主要通过滑动窗口来实现。

滑动窗口大小，会一直根据接收方反馈作出调整，发送方<=接收方，采用累计应答的方式来ACK应答。

窗口根据收到的ACK来移动，窗口前都是已确认收到应答的，窗口中包含已发送没收到应答的和待发送的，窗口后是不可发送的。接收方就是同理的还是三部分。

（5）TCP有拥塞控制机制，避免发送的数据占满网络。主要是四种算法，1.开始时是慢启动，一点点的发送，每返回一个ACK拥塞窗口就加1，到达门限时就退出；2.然后是拥塞避免，每接收一个ACK就增加窗口分之1，对数增长；3.当拥塞发生时，出现丢包现象，进入重传机制，一般进入快速重传机制。窗口和门限都为原先窗口的1/2。4.快速恢复然后觉得还能收到3个相同的ACK，说明了还是不那么糟糕嘛，再将窗口+3，进入拥塞避免。

java单例模式，两个if作用

两个if主要是为了保证单例对象实例化时，是懒加载的，同时创建时保证线程安全问题。

/**
 * 单例模式模拟
 */
class Singleton{
    // 单例对象 使用volatile修饰
    private static volatile Singleton singletonInstance;

    // 将构造方法私有化
    private Singleton() {}

    // 提供静态的方法
    // 双重检验锁实现单例
    public static Singleton getInstance() {
        if (singletonInstance == null) {
            // a,b
            synchronized (Singleton.class) {
                if (singletonInstance == null) {
                    singletonInstance = new Singleton();
                }
            }
        }
        return singletonInstance;
    }
}

（1）第一个if，如果实例对象还没被创建，然后多个线程才开始争抢锁。

（2）第二个if，开始时某个线程获取锁，并创建了实例对象，然后第二个线程又进入到同步代码块中，发现对象被实例化，就会退出。这一步需要将变量使用valatile修饰来保证可见性，并且避免了指令重排。

https://www.nowcoder.com/discuss/603916?source_id=discuss_experience_nctrack&channel=-1

Redis的底层数据结构说一下

redis里面key始终是string，而value有五种结构，string，list，hash，set，zset有序集合，底层实现

string底层是一个动态的字符串，维护了字符数组和len长度。

list底层是一个双向的链表，可在头尾插入

hash底层是一个hash表，使用链地址解决hash冲突

set是集合，它是无序的，且不可重复，底层是通过map实现,value为空

zset底层是跳跃表，表中的节点按照分值大小进行排序。

Redis雪崩、击穿、穿透

缓存穿透，大量访问一个缓存和数据库中没有的数据。

缓存击穿，某个数据过期，大量访问这个数据，造成请求击穿到数据库中，解决：设置热点数据不过期，或者加个锁来实现访问

缓存雪崩，大量数据过期，然后请求大量访问这些数据，造成雪崩，解决：就避免同时过期，可以将过期时间hash分散

算法

两个栈实现一个队列（注意当栈2不为空直接return，为空才stack1push进去完）

两个队列实现一个栈（push时先存入辅助队列，然后从头取再依次存入另一个队尾）

进程和线程有什么区别？

（1）资源分配，cpu调度；

（2）线程是一种轻量级的进程，是进程中的一端执行序列，主要拥有一些进程的共享资源，比如寄存器，堆栈等

（3）在系统调度方面，在创建或撤销进程时，开销较大。因为进程要维护内存空间和I/O设备等资源类似地，在进行进程切换时，涉及上下文内容的保存，而线程切换时只需保存和设置少量寄存器内容，开销很小。

（4）在通信方面，同一进程间线程可以直接通信，而进程却不行。

进程通信有哪些？

进程间通信，主要是进程间交换以及传输信息，主要是为了达到进程同步的目的。主要的通信方式有：

（1）管道通信，实现了一条半双工的通信管道，连接两个父子进程，并且写完才能读，读完才能写。

拓展：其实，所谓的管道，就是内核里面的一串缓存。从管道的一端写入的数据，另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格式的流且大小受限（这点区别于消息队列的数据独立）。 它使用fork创建子进程，创建的子进程会复制父进程的文件描述符信息，这样两个进程可以通过各自的文件id写入和读取同一个管道文件实现跨进程通信了。

（2）命名管道，与管道相似，不受父子进程的限制，进行进程间的通信。

（3）消息队列，它是一种在内核空间中的数据结构，各部分是独立的，它的特点：不是实时性的，有选择性的接收消息，会进行内存拷贝，涉及到用户态和内核态切换。适用于邮箱发送的情况。

（4）共享内存：多个进程共享的内存空间，不需要复制，原理：两个进程拿自己的一块虚拟内存来映射到相同的物理内存。

（5）信号量：它实质是一个计数器，多个进程提供对共享数据对象的互斥同步。

（6）socket：它是一种用于不同主机间的进程网络通信，通过绑定IP和端口，来实现数据传输。底层实际上是封装了TCP/IP协议簇。

管道通信底层是怎么实现的，如上拓展
既然提到了socket，你清楚socket编程的流程么？

socket主要是应用层与TCP/IP协议族通信的中间软件抽象层，它是一组接口，封装了TCP/IP协议族。

（1）服务器端先初始化ServerSocket，然后与端口绑定(bind)，对端口进行监听(listen)，调用accept阻塞，等待客户端连接。

（2）客户端初始化一个Socket，然后连接服务器(connect)，如果连接成功，这时客户端与服务器端的连接就建立了。客户端发送数据请求，服务器端接收请求并处理请求，然后把回应数据发送给客户端，客户端读取数据，最后关闭连接，一次交互结束。

进程调度

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

（1）批处理系统，没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.先来先服务，有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行；所以就有了2.短作业优先，按估计运行时间最短的顺序进行调度，但这种长作业有可能会饿死，处于一直等待状态。

3.高响应比优先，也是按剩余运行时间的顺序进行调度。新进程运行时间与当前进程的剩余时间作比较，如果新的进程需要的时间更少，则挂起当前进程，运行新的进程，否则新的进程等待。

（2）交互式系统有大量的用户交互操作，在该系统中调度算法的目标就是快速地进行响应。

1.时间片轮转，维护一个队列，每次调度时，把时间片分配给队首进程。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

2.优先级调度，为每个进程分配一个优先级，按优先级进行调度，低优先级会随着时间的推移增加等待进程的优先级。

3.多级反馈队列，维护多个队列，每个队列时间片大小都不同，进程在第一个队列没执行完，就会被移到下一个队列。每个队列优先权从上往下依次降低。

这种调度可以看成看成是前两种的结合。

什么是内核态和用户态

内核态与用户态主要区分在于运行时特权级的大小，对应的权限不同，用户态不能直接访问操作系统的资源，这是不安全的。3以上就是用户态，反之就是内核态；

内核态和用户态，二者如何切换

第一种就是系统调用，主要是对用户开放了一个中断，用户主动申请切换。

第二种是异常，当用户态程序发生异常时，操作系统会切换到对应内核态的异常处理程序，比如发生了缺页异常。

第三种是外部I/O的中断，当外部设备请求，向cpu发送中断信号，则cpu会转而去执行与中断信号对应的处理程序。

说说死锁

死锁是多个对象竞争同一资源时，互相等待对方的资源这样一种情况，如果没有外力作用就会一直等待下去。

（1）死锁形成的条件是：资源互斥：资源只能被一个进程使用，占有和等待：也就是占有了资源可以获取另一个资源，不可抢占：占有了资源不能被抢占，只能主动释放，环路等待：多个进程形成了环路，互相等待对方占有的资源。

（2）死锁的预防：程序执行前预防死锁。主要是破坏死锁的四个条件，同时使用，一次性获取所有资源，可以被抢占，对资源进行编号按编号请求资源

（3）死锁的避免：运行时避免死锁，防止系统进入不安全的状态，每次让最少需要资源的进程获取到全部资源。

tcp和udp的区别

（1）TCP是面向连接的；UDP是无连接，发送前无需连接，但可以用connect指定只与这台主机交互。

TCP建立连接，主要是通过三次握手，双方维护状态信息，例如窗口大小，双方的开始序列号（序列号是通过双方的端口，地址，通过一个随机值进行算法得出的）等等

（2）TCP是一对一的；而UDP可以支持一对一，一对多，多对多通信。

（3）TCP是面向字节流的，把数据看做一长串字符流；而UDP则是面向报文的。

（4）TCP是可靠的，数据保证无差错，不丢失，不重复，主要是超时重传来实现；而UDP是不可靠性的。

（5）TCP拥有拥塞控制以及流量控制机制；而UDP则是无论如何拥堵依旧保持一样的发送速率。

（6）TCP头部较长，开销大，且长度可变；而UDP头部较小固定8字节，开销小。

TCP中的CLOSE-WAIT状态是什么，为什么要有CLOSE-WAIT状态？ TIME_WAIT 说一下

（1）因为服务器端ACK和FIN是分开发送的，服务器端可能还需要处理和发送数据。

（2）客户端接收到服务器端发送的FIN报文后进入此状态，此时并不是直接进入 CLOSED 状态，还需要等待一个时间计时器设置的时间 2MSL。这么做有两个理由：

确保最后一个确认报文能够到达。如果 B 没收到 A 发送来的确认报文，那么就会重新发送连接释放请求报文，A 等待一段时间就是为了处理这种情况的发生。
等待一段时间是为了让本连接持续时间内所产生的所有报文都从网络中消失，使得下一个新的连接不会出现旧的连接请求报文。

Http请求了解吗，说说1.0，1.1，2.0之间的区别

（1）Http1.0 与 Http1.1：

说明短连接：每进行一次 HTTP 短连接就要新建一个 TCP 连接，那么开销会很大。长连接：只需要建立一次 TCP 连接就能进行多次 HTTP 通信。HTTP/1.1 开始默认是长连接的。

1.0是短连接，1.1默认是长连接，建立一次TCP连接，可以发送多个Http请求。
1.1一次打开多个请求支持流水线形式，不用等待响应返回，这样可以减少延迟。
1.0不支持指定主机名，WEB浏览器无法使用主机头名来明确表示要访问服务器上的哪个WEB站点，1.1支持
1.1比起1.0新增了状态码100
1.0不支持缓存，1.1支持缓存

（2）Http1.1 与 Http2.0

Http2.0压缩了头部，降低了网络流量。客户端和服务器同时维护和更新一个包含之前见过的首部字段表，从而避免了重复传输。
2.0的报文采用了二进制帧的形式，相比之前传输速率更快。
2.0提供了服务器端推送功能，服务器端会将资源一次性的推送给客户端，不用再发多次请求。
2.0是多路复用的，多个请求复用同一个连接，避免了建立关闭连接的开销。

HTTPS的加解密过程

Https是HTTP先和SSL通信，再由 SSL 和 TCP 通信

HTTPS 是综合了对称加密和非对称加密算法的 HTTP 协议。既保证传输安全，也保证传输效率。

先利用 非对称密钥加密方式将私钥传输给通信方，保证安全性;
获取到私钥后，再使用对称密钥加密方式进行通信，从而保证效率。

数据库了解吗，索引是什么，索引查询的过程说一下（类似于 select … where i = 1），这里底层是怎么工作的

（1）索引是存储引擎层实现的，可以帮助加快查询速率的。MyIsam是非聚集索引，索引和数据文件是分离的(非聚集)，每个叶子节点存储的都是数据的磁盘指针；InnoDB是聚集索引，表数据文件本身就是按B+Tree组织的一个索引结构文件。

（2）索引查询过程：一般索引是基于b+树的，当有个字段值，拿到字段值到b+树中去查询，从根结点开始向下搜索区间，最终找到索引值。

数据库的唯一索引知道吗

不允许其他行存在相同索引字段，主键索引就是一种唯一索引，每次插入和删除时都会查询数据，维护好唯一索引。

MySQL索引与锁的关系

走索引锁粒度小因为是走的行锁，不走索引锁粒度大（走的是表锁）

行锁和表锁了解吗

MySQL 中提供了两种封锁粒度：行级锁以及表级锁。

行锁就是一锁锁一行或者多行记录，mysql的行锁是基于索引加载的，锁冲突概率低，并发性高，但是会有死锁的情况出现。
表锁响应的是非索引字段，即全表扫描

计算机网络输入一个URL全过程

加分：首先浏览器查找当前URL是否存在缓存，并比较缓存是否过期。过期就会重新加载
然后就开始DNS进行域名的解析，获取到对应的IP。加分：先检查（1）本地hosts文件是否有这个网址映射关系，如果有就调用这个IP地址映射，完成域名解析。没有才会（2）查找本地DNS解析器缓存。如果还是没有找到则会（3）查找DNS服务器，如果找到则返回。
根据IP，通过三次握手建立TCP连接，维护好双方的序列号，滑动窗口大小。
然后再向服务器发送HTTP请求。
服务器处理请求，返回HTTP响应。
前端就渲染页面，显示功能。
通过Tcp四次挥手，关闭TCP连接。

虚拟内存、分页内存管理、多级分页、局部性原理

虚拟内存：是将内存抽象成地址空间。每个程序拥有自己的地址空间，让物理内存扩充成更大的逻辑内存。

分页主要是通过页表来管理着地址空间和物理内存的转换，虚拟内存中是页号 + 偏移地址，物理内存中是固定大小的页，一般4kb。后来为了节省多级页表的转换开销，引入了快表，里面存的是经常访问的页。

局部性原理：进程不会一次性申请全部的内存，需要时再申请。

段页式管理、页面置换算法

（1）分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据在逻辑上独立的地址空间并且有助于共享和保护。

段页式管理：程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

地址结构：段号 + 段内页号 + 页内偏移。

（2）最佳，太理想；先进先出（导致经常使用的换出，容易缺页中断）；LRU最近最少使用，这样经常使用的就不容易换出；第二次机会：FIFO的改进，页面访问时置1，如果需要从头替换的话先看标志位，标志位为1，就置0，放到后面，为0就替换；时钟算法：第二次机会的环形链表版本，指针指向老节点。

https://www.nowcoder.com/discuss/605380?source_id=discuss_experience_nctrack&channel=-1

TCP连接过程，哪些字段，分别什么用

序号：用于对字节流进行编号，例如序号为 301，表示第一个字节的编号为 301，如果携带的数据长度为 100 字节，那么下一个报文段的序号应为 401。
确认号 ：期望收到的下一个报文段的序号。例如 B 正确收到 A 发送来的一个报文段，序号为 501，携带的数据长度为 200 字节，因此 B 期望下一个报文段的序号为 701，B 发送给 A 的确认报文段中确认号就为 701。
确认 ACK ：当 ACK=1 时确认号字段有效，否则无效。TCP 规定，在连接建立后所有传送的报文段都必须把 ACK 置 1。
同步 SYN ：在连接建立时用来同步序号。当 SYN=1，ACK=0 时表示这是一个连接请求报文段。若对方同意建立连接，则响应报文中 SYN=1，ACK=1。
终止 FIN ：用来释放一个连接，当 FIN=1 时，表示此报文段的发送方的数据已发送完毕，并要求释放连接。

数据偏移 ：指的是数据部分距离报文段起始处的偏移量，实际上指的是首部的长度。

三次握手的原因

（1）防止旧的重复连接初始化造成混乱。client端会将过期或者超时的序列号，发送RST报文，终止。不三次握手就没有足够的上下文判断

（2）不能保证同步双方初始序列号，两次握手只保证了客户端的初始序列号能被对方成功接收，没办法保证服务器端的初始序列号都能被确认接收。

（3）第三次握手是为了防止失效的连接请求到达服务器，让服务器错误打开连接，从而造成资源的浪费

客户端发送的连接请求如果在网络中滞留，这个滞留的连接请求最后还是会到达服务器，如果不进行三次握手，那么服务器就会打开两个连接。三次握手后客户端会忽略服务器之后发送的对滞留连接请求的连接确认，不进行第三次握手，因此就不会再次打开连接。

四次挥手的原因

主要是接收方报文与FIN报文分两次发送，客户端发送了 FIN 连接释放报文之后，服务器收到了这个报文，先返回ACK报文，就进入了 CLOSE-WAIT 状态。服务器端发送还未传送完毕的数据，传送完毕之后，服务器会发送 FIN 连接释放报文。而客户端接收到FIN报文，再回复一次ACK。

序列号是随机取的吗

双方通过三次握手建立连接时，约定序列号，主要是通过双方的ip地址，和端口号，再添加一个计时器来通过算法实现。

幻读是什么？MySQL怎么解决幻读

事务A对表操作时，事务B添加了新的记录，都能受到B的操作影响了，比如A进行插入时ID与B中刚插入重复，失败。

算法：最小连续子序列之和>=target

二面

JAVA异步实现，线程池

jdk1.8之前使用的Future代表了未来的某个结果，当我们向线程池中submit任务时的时候会返回该对象。但它是阻塞的异步操作，或者轮询。

jdk1.8之后才有了CompletableFuture可以实现异步的操作，向线程池提交任务后，注册回调函数来实现异步。

ExecutorService executor = Executors.newFixedThreadPool(2);
CompletableFuture<Integer> future = CompletableFuture.supplyAsync(new Supplier<Integer>() {
//..........
}, executor);
future.thenAccept(e -> System.out.println(e));

ThreadLocal

实际上每个Thread，内部都维护了一个ThreadLocalMap类型的变量threadsLocals，这样每次创建一个绑定线程的ThreadLocal时，就存入线程的threadLocals中。

ThreadLocalMap 是个Map结构，但不是实现Map接口，key是ThreadLocal，而Value是ThreadLocal set的值。

他的Entry是继承WeakReference（弱引用），没有HashMap中的next，所以不存在链表

算法题：堆排序

算法：k个一组反转列表，不足k个也要反转

https://www.nowcoder.com/discuss/605166?source_id=discuss_experience_nctrack&channel=-1

生产者消费者同步：使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 p(mutex) 再执行 p(empty)。如果这么做了，那么可能会出现这种情况：

生产者对缓冲区加锁后，执行 p(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 v(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        p(&empty);
        p(&mutex);
        insert_item(item);
        v(&mutex);
        v(&full);
    }
}

void consumer() {
    while(TRUE) {
        p(&full);
        p(&mutex);
        int item = remove_item();
        consume_item(item);
        v(&mutex);
        v(&empty);
    }

mysql的undo log redo log binlog

undo log

原子性的实现原理，undo log存储的是相反的sql语句，也就是数据库的备份数据，通过此日志可以恢复到事务开始的状态（回滚的实现）。

例如插入一条数据，undo log里面就是存的删除语句（因为执行删除才能恢复到原样）。

redo log

持久性的实现原理，redo log存储的是更新数据的备份，因为在提交前将redo log持久化，不需要数据进行持久化。
binlog

主从复制的原理实现。

主数据库操作，sql语句写入数据库的同时，写入binlog二进制文件，主要是一些SQL语句（写库，所以是增删改）。主库通过I/O线程发送binlog，写入至从库replay log。从库执行SQL线程将replay log，写入至从库的bin log data中。

主从复制

主数据库操作，sql语句写入数据库的同时，写入binlog二进制文件，主要是一些SQL语句（写库，所以是增删改）。
主库通过I/O线程发送binlog，写入至从库replay log
从库执行SQL线程将replay log，写入至从库的bin log data中。

操作系统的select poll epoll

我只知道select是I/O多路复用模型的实现，多个网络socket连接注册到select中，select会一直轮询各个事件，当有事件发生时（即有数据可读时）再调用线程进行数据的读写。避免了每个连接都调用一个线程来实现读写，系统开销小。

https://www.nowcoder.com/discuss/599399?source_id=profile_create_nctrack&channel=-1

一面：

map下的实现类，详细介绍

HashMap： 使用位桶和链表实现（最近的jdk1.8改用红黑树存储而非链表），它是线程不安全的Map，方法上都没有synchronize关键字修饰

HashTable： hashTable是线程安全的一个map实现类，它实现线程安全的方法是在各个方法上添加了synchronize关键字。但是现在已经不再推荐使用HashTable了，因为现在有了ConcurrentHashMap这个专门用于多线程场景下的map实现类，其大大优化了多线程下的性能。

ConcurrentHashMap：主要实现原理是segment段锁，它不再使用和HashTable一样的synchronize一样的关键字对整个方法进行加锁，而是分段锁。

ConcurrentHashMap允许获取不同段锁的线程同时持有该资源，segment有多少个，理论上就可以同时有多少个线程来持有它这个资源。

segment是一个数组，默认长度为16。也就是说理论商可以提高16倍的性能。这样，只要多个修改(写)操作发生在不同的段上，它们就可以并发进行。

jdk1.8中则对ConcurrentHashMap又再次进行了大的修改，取消了segment段锁字段，采用了CAS+Synchronize技术来保障线程安全。底层采用数组+链表+红黑树的存储结构，也就是和HashMap一样。这里注意Node其实就是保存一个键值对的最基本的对象。其中Value和next都是使用的volatile关键字进行了修饰，以确保线程安全。

在插入元素时，会首先进行CAS判定，如果OK就插入其中，并将size+1，但是如果失败了，就会通过自旋锁自旋后再次尝试插入，直到成功。

get方法是非阻塞，无锁的。重写Node类，通过volatile修饰next来实现每次获取都是最新设置的值。

同hashMap一样，在JDK1.8中，如果链表中存储的Entry超过了8个则就会自动转换链表为红黑树，提高查询效率。

TreeMap：TreeMap也是一个很常用的map实现类，因为他具有一个很大的特点就是会对Key进行排序，使用了TreeMap存储键值对，再使用iterator进行输出时，会发现其默认采用key由小到大的顺序输出键值对，如果想要按照其他的方式来排序，需要重写也就是override 它的compartor接口。TreeMap底层的存储结构也是一颗红黑树。

LinkedHashMap：LinkedHashMap它的特点主要在于linked，带有这个字眼的就表示底层用的是链表来进行的存储。相对于其他的无序的map实现类，还有像TreeMap这样的排序类，linkedHashMap最大的特点在于有序，但是它的有序主要体现在先进先出FIFIO上。没错，LinkedHashMap主要依靠双向链表和hash表来实现的。这里虽然在计算hashcode时还是发生了hash冲突，采用了链地址法解决了冲突，但是这里的Entry对象是采用双向链表保存的，每个Entry都有一个after和before的属性。当插入一个entry时，如果发生了冲突，就可以将新的Entry插入Entry链表中的头部，但是按照双向链表的角度来说，又会将该Entry插入到双向链表的尾部。

说一下哈希冲突，hashmap扩容

List实现类，详细介绍

ArrayList：

底层实现是数组
ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍
在增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)

LinkedList：

底层实现是双向链表[双向链表方便实现往前遍历]

Vector：

底层是数组，现在已少用，被ArrayList替代，原因有两个：
- Vector所有方法都是同步，有性能损失。
- Vector初始length是10 超过length时以100%比率增长，相比于ArrayList更多消耗内存。

总结：查询多用ArrayList，增删多用LinkedList。

ArrayList增删慢不是绝对的(在数量大的情况下，已测试)：

如果增加元素一直是使用add()(增加到末尾)的话，那是ArrayList要快
一直删除末尾的元素也是ArrayList要快【不用复制移动位置】
至于如果删除的是中间的位置的话，还是ArrayList要快！

但一般来说：增删多还是用LinkedList，因为上面的情况是极端的~

介绍一下AQS

AQS其实就是一个可以给我们实现锁的框架
内部实现的关键是：先进先出的队列、state状态
定义了内部类ConditionObject
拥有两种线程模式：独占模式、共享模式
在LOCK包中的相关锁(常用的有ReentrantLock、 ReadWriteLock)都是基于AQS来构建

二面：

双亲委派

一个类加载器收到一个类加载的请求，它不会自己去尝试加载这个类，它会调用自己的loadClass方法，把请求向父类加载器委派，每一层次都是如此，所以最终所有类加载请求都会委派到启动类加载器。当父类加载器搜索不到相应类时，才会反馈自己无法完成请求，子类加载器才会调用findclass方法去加载。

作用的话我觉得：

保证同一层级的类都由同一类加载器加载，避免有些类被重复加载。
保护程序的安全，防止核心API被随缘篡改。

当我们自己写java包下的类时，并打包到同样的包下，由于双亲委派模型的原因，这个类不会被加载，因为已经有一个一样的类被加载了，这时会返回异常。

算法：螺旋矩阵

三面：

Redis的高性能

因为它所有的数据都在内存中，所有的运算都是内存级别的运算，单线程避免了多线程的切换性能损耗问题。实现IO的多路复用机制，线程可以复用来处理多个连接请求，自然效率就会很高。（连接请求和事件处理都是放到队列中，依次进行分派）
能说一说Redis中缓存淘汰策略嘛

Redis 具体有 6 种淘汰策略：

策略	描述
volatile-lru	从已设置过期时间的数据集中挑选最近最少使用的数据淘汰
volatile-ttl	从已设置过期时间的数据集中挑选将要过期的数据淘汰
volatile-random	从已设置过期时间的数据集中任意选择数据淘汰
allkeys-lru	从所有数据集中挑选最近最少使用的数据淘汰
allkeys-random	从所有数据集中任意选择数据进行淘汰
noeviction	禁止驱逐数据

zset结构，跳表+hashtable

跳跃表是基于多指针有序链表实现的，可以看成多个有序链表。在查找时，从上层指针开始查找，找到对应的区间之后再到下一层去查找。

4.rdb和aof区别，aof下always的安全性

Redis的持久化主要分为两种，一个是RDB快照，一个是AOF日志

RDB快照是数据库的完整备份，里面有全部数据，保存时就将快照保存在dump.rdb文件中，启动时加载。
RDB实现：主要是fork出一个子进程，然后这个子进程就会处理接下来的所有保存工作，父进程无须执行任何磁盘 I/O 操作。
AOF：将写命令添加到 AOF 文件（Append Only File）的末尾。使用 AOF 持久化需要设置同步选项，从而确保写命令同步到磁盘文件上的时机。这是因为对文件进行写入并不会马上将内容同步到磁盘上，而是先存储到缓冲区，然后由操作系统决定什么时候同步到磁盘。有以下同步选项：

选项同步频率

always 每个写命令都同步

everysec 每秒同步一次

no 让操作系统来决定何时同步
- always 选项会严重减低服务器的性能；
- everysec 选项比较合适，可以保证系统崩溃时只会丢失一秒左右的数据，并且 Redis 每秒执行一次同步对服务器性能几乎没有任何影响；
- no 选项并不能给服务器性能带来多大的提升，而且也会增加系统崩溃时数据丢失的数量。
随着服务器写请求的增多，AOF 文件会越来越大。Redis 提供了一种将 AOF 重写的特性，能够去除 AOF 文件中的冗余写命令。

二者的比较：

RDB 在恢复大数据集时的速度比 AOF 的恢复速度要快，但是故障宕机时丢失数据。

AOF 文件的体积通常要大于 RDB 文件的体积，因为有数据的过期，所以恢复慢。

选项	同步频率
always	每个写命令都同步
everysec	每秒同步一次
no	让操作系统来决定何时同步

5.redis数据过期策略

定时删除：定时遍历redis，查看有无过期数据，删除之。
惰性删除：数据被get即被访问时时，再检查其是否过期。

综合（定期删除）：定时随机抽取某个expires[*]中的数据检查有无过期删除，同时使用惰性删除。

6.redis如何作为分布式锁的

使用setnx，仅当key不存在。若给定的key已经存在，则SETNX不做任何操作。

由于 Redis 的单线程命令处理机制，如果多个客户端同时执行，则只有一个设置成功，所以可以用作分布式锁的一种实现。

7.你在设计数据库索引的时候会依据什么原则

（1）索引一般建立在表的主键和外键（2）索引建立在经常使用where连接的字段（3）表与其他表的连接处，在连接的字段上也考虑建立索引

8.数据内容过多，如何分页查询，分库分表如何做

水平切分将同一个表中的记录拆分到多个结构相同的表中。

垂直切分是将一张表按列切分成多个表，通常是按照列的关系密集程度进行切分，也可以利用垂直切分将经常被使用的列和不经常被使用的列切分到不同的表中。在数据库的层面使用垂直切分将按数据库中表的密集程度部署到不同的库中，例如将原来的电商数据库垂直切分成商品数据库、用户数据库等。

算法：下一个排列

从后往前搜，找到第一个比前面大的值例如 1 2 4 3，即找到了4，排序后面 4 到结尾，1 2 3 4然后再去这个位置的值3，往前找，比3小的数2，然后交换即为下一个排列，1 3 2 4。

https://www.nowcoder.com/discuss/595230?type=2&channel=-1&source_id=discuss_terminal_discuss_hot_nctrack

Tcp的三次握手四次挥手？可不可以三次挥手？三次握手期间除了建立连接，还有互相交换什么信息？

如果server不发包的话就可以，给一条FIN=1的ACK-
双方的开始序列号，窗口大小

做个题

思路：二分，如果中点不满足条件（比mid - 1大，比mid + 1大），哪边比中点大往哪边走

二面：

Redis是用在什么场景？

对一致性要求不高的统计类数据，或者是对一致性要求较高但是对后端压力较大的查询。

怎样处理一致性的？

加入手动删除缓存的机制，先删除缓存，在更新数据库。更新数据库的操作与缓存查询数据库的操作在同一队列。

三面：

虚拟内存是什么用途，如何实现？

根据程序的局部性，不会一次项读取，所以就设立虚拟内存为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。通过分页来实现虚拟内存与物理内存的映射关系。

mvcc是怎么解决幻读问题

用next key lock（间隙锁与行锁），阻止新纪录的插入；版本号实现了可重复读，一个事务在第一次SELECT的时候生成一个ReadView，之后的查询复用这个ReadView；

https://www.nowcoder.com/discuss/604516?type=2&order=3&pos=22&page=1&channel=-1&source_id=discuss_tag_nctrack

ping是通过什么协议实现的？

Ping 主要用来测试两台主机之间的连通性。是使用ICMP协议来进行工作的。封装了IP数据报，但还是属于网络层的协议。不断的向目的主机发送 ICMP Echo 请求报文，目的主机收到之后会发送 Echo 回答报文。Ping 会根据时间和成功响应的次数估算出数据包往返时间以及丢包率。

DNS的主要过程

DNS是个分布式的数据库，存储着ip地址与主机名转换服务。一般使用udp进行传输，长度超过 512 字节时使用 TCP进行传输。

查询ip使用迭代查询，先按根域服务器库（.com,.cn,.vip,.top…）->顶级域（.com），然后根据顶级域（.com）->第二层域子域（baidu.com），最后根据baidu.com的域名找到相应的IP，返回给浏览器。

如何实现UDP的可靠数据传输？

用应用层ACK来实现超时重传，设定一个计时器，超时就重新传输数据。

介绍一下IPv6
使用Redis进行数据统计，在高并发的情况下会不会有问题？

（1）会出现数据库与缓存不一致性。先删除缓存，在更新数据库。更新数据库的操作与缓存查询数据库的操作在同一队列。

（2）缓存穿透、击穿和雪崩

数据库的三大范式

第一范式 (1NF)：属性不可分。

第二范式 (2NF)：每个非主属性完全函数依赖于主键码。

第三范式 (3NF)：非主属性不传递函数依赖于键码。

数据库事务的特性 ACID

原子性和持久性是通过日志恢复（undo log，redo log）实现；隔离性是通过并发控制（锁）来实现的，而原子性、隔离性、持久性巩固实现一致性。

事务是如何实现隔离性的？

隔离性是通过并发控制（锁）来实现的，Innodb 行表锁，读锁，写锁，MyIsam 表锁，读写锁

引入MVCC机制是为了实现什么？

多版本并发控制（MVCC）+ Next-Key Locking 防止幻读。

B树和B+树的区别，能不能用二叉搜索树作为数据库的索引？

①非叶子节点不存储data,只存储索引(冗余)，可以放更多的索引。
②叶子节点包含所有索引字段，且节点索引依次递增。
③叶子节点用指针连接，提高区间访问的性能。

如果采用普通的树来存储索引的话，树的高度h就会很高，每次查找都会进行一次I/O操作访问磁盘，影响性能。故就需要树横向发展，“平铺开来”，于是考虑B+树。

Spring中IOC，AOP的原理？哪种动态代理方式的性能更好？

IOC（控制反转）就是依赖倒置原则的一种代码设计思路。就是把原先在代码里面需要实现的对象创建、对象之间的依赖，反转给容器来帮忙实现。
Spring IOC容器通过xml,注解等其它方式配置类及类之间的依赖关系，完成了对象的创建和依赖的注入。

AOP主要是面向切面编程，对应事务处理、日志管理、权限控制等操作，封装起来，便于减少系统的重复代码。

AOP代理可以用JDK动态代理或CGLIB代理实现。

jdk动态代理：目标类要实现InvocationHandler接口，并在属性中创建Object对象保存要代理的对象实例，重写invoke 方法，底层其实就是基于Java的反射机制。利用反射机制生成一个实现代理接口的匿名类，在调用具体方法前调用InvokeHandler来处理。
CGlib：对指定的类生成一个子类，实现MethodInterceptor接口，实现intercept方法，保存要代理对象的实例。

JDK调用代理方法，是通过反射机制调用，Cglib是通过FastClass机制直接调用方法，Cglib执行效率更高。

互斥和信号量

互斥：多个进程在同一时刻只有一个进程能进入临界区。

信号量是一个计数器，可以对资源进行共享访问。若取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

算法：

https://www.nowcoder.com/discuss/607444?source_id=discuss_experience_nctrack&channel=-1

为什么StringBuilder快?

String在java中是不可变长的,一旦初始化就不能修改长度,简单的字符串拼接其实是创建新的String对象，再把拼接后的内容赋值给新的对象,在频繁修改的情况下会频繁创建对象,而StringBuilder则不会，从头到尾只有一个实例对象。

StringBuilder在append时放到一个value的char数组中,字符串是固定长度的,而数组是可以扩容的,这样就不需要不停创建对象了。

超时重传和快重传的区别

超时重传：设定一个定时器，当超过指定的时间后，没有收到对方的 ACK 确认应答报文，就会重发该数据。
快速重传：3次接受到同一个ACK，因为有一个请求发送未到达发生丢包，后几次响应返回相同的ACK。

java 堆内存的情况，垃圾回收算法，young gc和full gc的区别

（1）堆：存放对象实例和字符串常量池、数组。几乎所有对象实例都在这里分配内存。同时也是GC的主要收集部分。

同时堆内存分代进行存储，新生代 + 老年代 + TLAB（每个线程私有的分配缓冲区）

新生成的对象TLAB作为内存分配首选，一旦对象在TLAB上分配失败就就会通过加锁（堆内存是线程共享）在年轻代eden区分配内存。
大对象和生命周期长的放在老年代

（2）垃圾回收算法，经典三种一思想。

（3） GC就分为两种，一个是Minor GC，一种是Full GC。

young GC：针对新生代的回收，当Eden区域空间不足时触发

full GC：针对老年代和方法区的回收，当老年代和方法区空间不足时；新生代中创建大对象直接扔到老年代，老年代存不下时；主动调用System.gc时；

线程安全是什么，如何实现

在拥有共享数据的多条线程并发执行的过程中，不会出现数据不一致问题产生。

为什么会出现线程不安全？

通过互斥同步机制保证各个线程都实现线程安全，加锁（synchronized，Lock锁）实现，或者使用volatile加cas实现无锁的并发操作。

ACID，每个都解释一下

原子性（Atomicity）：事务中所有操作是不可再分割的原子单位。事务中所有操作要么全部执行成功，要么全部执行失败。
一致性（Consistency）：事务执行后，数据库状态与其它业务规则保持一致。如转账业务，无论事务执行成功与否，参与转账的两个账号余额之和应该是不变的。
隔离性（Isolation）：隔离性是指在并发操作中，不同事务之间应该隔离开来，使每个并发中的事务不会相互干扰。
持久性（Durability）：一旦事务提交成功，事务中所有的数据操作都必须被持久化到数据库中。

总结：原子性和持久性是通过日志恢复（undo log，redo log）实现；隔离性是通过并发控制（锁）来实现的，而原子性、隔离性、持久性巩固实现一致性。

知道什么MySQL的存储引擎，有什么区别，MyISAM有什么好处？

InnoDB：支持事务，实现了四个标准的隔离级别，默认是可重复读。InnoDB是聚集索引，表数据文件本身就是按B+Tree组织的一个索引结构文件。支持共享锁（读锁）+排它锁（写锁，更新操作默认），既支持表锁也支持行锁。
MyISAM：不支持事务。MyIsam是非聚集索引，索引和数据文件是分离的(非聚集)，每个叶子节点存储的都是数据的磁盘指针；不支持行级锁，只能对整张表加锁，支持写锁和读锁。但在表有读取操作的同时，也可以往表中插入新的记录，这被称为并发插入。
InnoDB表必须有主键，并且推荐使用整型的自增主键，B+树有序，插入数据方便，并且范围查找高效。
MyISAM 设计简单，支持压缩表和空间数据索引。

可重复读的实现？

读写锁均持续到事务结束释放。

为什么用B+树做索引？

非叶子节点不存储data,只存储索引(冗余)，可以放更多的索引。
叶子节点包含所有索引字段，且节点索引依次递增。
叶子节点用指针连接，提高区间访问的性能。

访问网站延迟，可能发生什么？

网络带宽不够，却同时有多个应用需要传输远超带宽的数据量，这时候会造成大量数据丢失，从而表现为响应延时。
服务器端处理能力不足，也会造成响应延时。

https://www.nowcoder.com/discuss/609710?source_id=discuss_experience_nctrack&channel=-1

自己的字节面经

项目中容器的实现？

Container容器里面维护了一条Context管道（valve是context，对应着webapps下每个web应用）。

在容器初始化时，会使用线程池，并发的初始化每个webapp，本质就是将每个文件夹下的web应用作为valve加入到管道中。Web应用的下一层也有一条对应处理请求的servlet管道，servlet管道中维护一个servletName与url对应的map。并发操作，选用线程安全的容器。

然后web应用的管道内部还会维护一个它下面所有Servlet的管道，和一个执行下一层操作的valve。valve会在后序处理请求时被调用，然后沿着管道找到与第一层url对应的web应用，然后调用该层的执行valve，会进到下一层管道，然后再沿着管道，找到与第二层url对应的处理请求的servlet。调用该层的执行valve，反射创建servlet，调用其service方法执行请求，返回response响应。

场景题：海量电话的处理topk处理（hash表+堆），如果数据量大hashmap存不到，分治分成小的数据。
怎么知道http发送的请求结束

http请求的消息实体必须由一个合法的Content-Length请求头指定其结束位置。

响应的消息实体，可以由Content-Length头或者服务端关闭连接指定。

linux操作系统命令行查看内存大小，以及常见命令

除了最基础的命令外，还有

service命令：调用位于/etc/init.d/目录处的脚本，并执行脚本。有两种方法可以启动任何服务；比如说，我们使用service命令，启动名为httpd的服务。

free命令显示了闲置内存、总内存和交换内存等方面的信息，单位是字节。-t 显示了已使用的总内存和可以使用的内存，单位是字节。

top命令显示了系统的任务活动，进行任务管理。-u + xxx查看xxx用户进程的信息

ps命令显示了系统中运行的进程方面的信息；下面这个例子只显示init进程。# ps -ef | grep init

使用kill命令来发送信号；先使用ps命令找到进程id，如下所示，然后使用kill -9命令，终止进程。

# ps -ef | grep init
 root         1     0  0 07:53 ?        00:00:04 /sbin/init
 root      7508  6825  0 11:48 pts/1    00:00:00 grep init
# kill- 9 7508

算法：最长的回文子串

//回文串是从中间向两边进行遍历
//begin 和 end是它的窗口大小
int begin = 0;
int end = 0;
for (int i = 0; i < length; i++) {
    //判断begin到end是不是回文串
    //以某一点或某两点开始看是不是回文串，返回其回文串长度
    int lenjishu = huiwen(chars, i, i);
    int lenoushu = huiwen(chars, i, i + 1);
    int len = Math.max(lenjishu, lenoushu);

    if (len >= end - begin + 1) {
        begin = i - (len - 1) / 2 ;
        end = i + (len >> 1);
    }
}
//截取是左闭右开
return s.substring(begin, end + 1);


//返回以一点或两点的回文串长度
private int huiwen(char[] chars, int begin, int end) {
    while (begin >= 0 && end < chars.length && chars[begin] == chars[end]) {
        begin--;
        end++;
    }
    return end - begin - 1;
}

https://www.nowcoder.com/discuss/609854?channel=-1&source_id=profile_follow_post_nctrack

说一下MVCC

快照读的实现是基于多版本并发控制（MVCC），读-写冲突的无锁并发控制

在并发读写数据库时，可以做到在读写时不阻塞，提高了数据库并发读写的性能。
同时还可以解决幻读，但不能解决更新丢失问题。

redis如何保证高可用的

主要是通过哨兵模式进行故障转移实现。Redis采用哨兵进程监控主redis服务器和从redis服务器。当主服务器宕机，哨兵通知其他从服务器切换为主机。（哨兵之间也会互相监控）哨兵会向主从服务器发送hello指令，以确保其状态，然后在哨兵之间网络进行消息互通。

领头哨兵在主机故障时进行自动故障转移，并从从服务器间选择一个作为一个新服务器。

redis怎么保证缓存一致性

（1）先删除缓存，然后把更新数据库和缓存的操作放在一个消息队列中，实现类原子的这样一个操作。

（2）延时双删策略：先删除缓存，更新数据库，延时，再次删除缓存，就能大概率避免。

https://www.nowcoder.com/discuss/609177?type=2&order=1&pos=1&page=1&channel=-1&source_id=discuss_tag_nctrack

http和https的区别

HTTP 的默认端口是 80，而 HTTPS 的默认端口是 443。
HTTP 连接建立相对简单， TCP 三次握手之后便可进行 HTTP 的报文传输。而 HTTPS 在 TCP 三次握手之后，还需进行 SSL/TLS 的握手过程，才可进入加密报文传输。
HTTP信息是明文传输，存在安全风险的问题。HTTPS 也就是在 HTTP 与 TCP 层之间增加了 SSL/TLS 安全传输层，使得报文能够加密传输。HTTPS在通信建立前采用非对称加密的方式交换密钥保持安全性，后续全部使用对称加密的方式使用密钥进行加密明文数据。

cookie和session的区别

cookie数据存放在客户的浏览器上，session数据放在服务器上，session id是存在cookie中的jsessionid 。
两者最大的区别在于生存周期，一个是预先设置的生存周期，或永久的保存于本地的文件。session是一次会话级别的，即浏览器访问。

操作系统有哪些功能

（1）处理机管理：主要控制和管理CPU调度的工作。（2）进程管理：也称为作业管理，是指对计算机所进行的操作进行管理。（3）内存管理：主要进行内存的分配和管理。（4）设备管理：主要管理基本的I/O设备。（5）文件管理：负责对计算机文件的组织、存储、操作和保护等。

常见的排序算法的时间复杂度

二叉搜索树说一下？可以用来干什么？查找的最坏时间复杂度？什么情况下出现最坏？

（1）BST树：若左子树不空，则左子树上所有节点的值均小于它的根节点的值；若右子树不空，则右子树上所有节点的值均大于它的根节点的值；左、右子树也分别为二叉排序树。功能就是利于我们查找，提高查找效率。

（2）当二叉树退化形成单链表时，其深度为n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。

平衡二叉树、红黑树，目的

两边高度差不高于1，同理红黑树增加查询效率。

快排和堆排说一下

快排的原理：一趟排序将数据分割成一部分的所有数据都比轴点数据小，另外一部分比轴点数据都要大。然后再按此方法对这两部分数据分别进行快速排序，递归进行让整个数据变成有序序列。最好情况，轴点选取合适，分布均匀，是O（nlogn），最坏的话，即选取的轴点为最值，导致两边数据都要换到另一边，或者是相当于没有快排，需要对一边再选轴点进行排序，O（n^2）。

堆排序的原理：先原地建堆，小顶堆或者大顶堆。然后将堆顶元素（当前最值）与末尾元素进行交换，得到排列好的值，堆大小减一，重新维护堆。

调整堆的顺序是从上至下？

可以从上往下上溢，也可以从下往上下溢，但后者更好，因为可以不用下溢叶子节点。

Linux命令了解哪些

jobs

查看当前控制台的后台进程，想要停止后台进程，使用jobs命令查看其进程号（比如为num），然后kill %num即可
ps 查看后台进程
top 查看所有进程和资源使用情况，类似Windows中的任务管理器

停止进程：界面是交互式的，在窗口输入k 之后输入PID，会提示输入停止进程模式有SIGTERM和 SIGKILL 如果留空不输入，就是SIGTERM（优雅停止）
free：查看当前系统的总内存大小以及使用内存的情况；
if config：查ip地址，MAC地址
netstat：查看端口

用共享存储方式通信会有什么问题，如何解决

共享内存的效率最高，缺点是没有提供同步机制，需要使用锁等其他机制进行同步。

计算机网络五层每一层说一下

物理层

例如光纤啊，电缆啊，双绞线啊等物体把他们联起来。然后才能进行通信，也就是说，物理层负责把两台计算机连起来，然后在计算机之间传送0,1这样的电信号。

数据链路层

工作在物理层之上，制定一套规则来进行0，1的传送。例如多少个电信号为一组啊，每一组信号应该如何标识才能让计算机读懂。然后另一方再按照相应的规则来进行解读。

（1）以太网协议

以太网协议规定，一组电信号构成一个数据包，把这个数据包称之为“桢”。每一个桢由标头(Head)和数据(Data)两部分组成。如下：

对于表头和数据这两个部分，他们存放的都是一些什么数据呢？我猜你眯着眼睛都能想到他们应该放什么数据。毫无疑问，我们至少得知道这个桢是谁发送，发送给谁的等这些信息吧？所以标头部分主要是一些说明数据，例如发送者，接收者等信息。而数据部分则是这个数据包具体的，想给接受的内容。

大家想一个问题，一个桢的长度是64~1518个字节，也就是说桢的长度不是固定的，那你觉得标头部分的字节长度是固定的吗？它当然是固定的啊，假如不是固定的，每个桢都是单独发的，那计算机怎么知道标头是几个字节，数据是几个字节。所以标头部分的字节是固定的，并且固定为18个字节。

（2）MAC地址

把一台计算的的数据通过物理层和链路层发送给另一台计算机，究竟是谁发给谁的，计算机与计算机之间如何区分，你总得给他们一个唯一的标识吧？

这就是MAC地址，连入网络的每一个计算机都会有网卡接口，每一个网卡都会一个地址，这个地址就叫做MAC地址。计算机之间的数据传送，就是通过MAC地址来唯一寻找、传送的。MAC地址在网卡生产是就被唯一标识了。

（3）广播与ARP协议

实际上，计算机A是通过广播的方式把数据发送给计算机B。在同一个子网中，计算机A要向计算机B发送一个数据包，这个数据包包含接收者的MAC地址。这个时候同一个子网中的计算机C,D也会收到这个数据包的，然后收到这个数据包的计算机，会把数据包的MAC地址取出来，与自身的MAC地址对比，如果两者相同，则接受这个数据包，否则就丢弃这个数据包。

那么问题来了，计算机A是如何知道计算机B的MAC地址的呢？这个时候就得由ARP协议这个家伙来解决了，不过ARP协议会涉及到IP地址，不过我们下面才会扯到IP地址。因此我们先放着，就当作是有这么一个ARP协议，通过它我们可以知道子网中其他计算机的MAC地址。

网络层

上面我们有说到子网这个关键词，实际上我们所处的网络，是由无数个子网络构成的。广播的时候，也只有同一个子网里面的计算机能够收到。假如没有子网这种划分的话，计算机A发一个数据包给计算机B,其他所有计算机也都能收到这个数据包，然后进行对比再舍弃。世界上有那么多它计算机，每一台计算机都能收到其他所有计算机的数据包，那就不得了了。那还不得奔溃。因此产生了子网这么一个东西。

那么问题来了，我们如何区分哪些MAC地址是属于同一个子网的呢？假如是同一个子网，那我们就用广播的形式把数据传送给对方，如果不是同一个子网的，我们就会把数据发给网关，让网关进行转发。

为了解决这个问题我们引入了一套新的地址协议，这个地址协议能够帮助我们区分MAC地址是否处于同一个子网中。这也是网络层负责解决的问题。

（1）IP协议

这个协议就是IP协议，它所定义的地址，我们称之为IP地址。IP协议有两种版本，一种是IPv4,另一种是IPv6。不过我们目前大多数用的还是IPv4，我们现在也只讨论IPv4这个版本的协议。

这个IP地址由32为的二进制数组成，我们一般把它分成4段的十进制表示，地址范围为0.0.0.0~255.255.255.255

每一台想要联网的计算机都会有一个IP地址。这个IP地址被分为两部分，前面一部分代表网络部分，后面一部分代表主机部分。并且网络部分和主机部分的二进制位数是不固定的。

假如两台计算机的网络部分是一模一样的，我们就说这两台计算机是处于同一个子网中。例如192.168.43.1和192.168.43.2,假如这两个IP地址的网络部分为24为，主机部分为8位。那么他们的网络部分都为192.168.43，所以他们处于同一个子网中。

可是问题来了，你怎么知道网络部分是占几位。也就是说，单单从两台计算机的IP地址，我们是无法判断他们的是否处于同一个子网中的。

这就引申出了另一个关键词————子码掩码。子码掩码和IP地址一样也是32位二进制数，不过它的网络部分规定全部为1，主机部分规定全部为0.也就是说，假如上面那两个IP地址的网络部分为24为，主机部分为8为的话，那他们的子码掩码都为11111111.11111111.11111111.00000000，即255.255.255.0。

那有了子字码掩码，如何来判端IP地址是否处于同一个子网中呢。显然，知道了子码掩码，相当于我们知道了网络部分是几位，主机部分是几位。我们只需要把IP地址与它的子码掩码做与(and)运算，然后把各自的结果进行比较就行了，如果比较的结果相同，则代表是同一个子网，否则不是同一个子网。

例如，192.168.43.1和192.168.43.2的子码掩码都为255.255.255.0，把IP与子码掩码相与，可以得到他们都为192.168.43.0，进而他们处于同一个子网中。

（2）ARP协议

有了上面IP协议的知识，我们回来讲一下ARP协议。
有了两台计算机的IP地址，我们就可以判断出它们是否处于同一个子网之中。假如他们处于同一个子网之中，计算机A要给计算机B发送数据时。我们可以通过ARP协议来得到计算机B的MAC地址。ARP协议也是通过广播的形式给同一个子网中的每台电脑发送一个数据包(当然，这个数据包会包含接收方的IP地址)。对方收到这个数据包之后，会取出IP地址与自身的对比，如果相同，则把自己的MAC地址回复给对方，否则就丢弃这个数据包。这样，计算机A就能知道计算机B的MAC地址了。

可能有人会问，知道了MAC地址之后，发送数据是通过广播的形式发送，询问对方的MAC地址也是通过广播的形式来发送，那其他计算机怎么知道你是要传送数据还是要询问MAC地址呢？其实在询问MAC地址的数据包中，在对方的MAC地址这一栏中，填的是一个特殊的MAC地址，其他计算机看到这个特殊的MAC地址之后，就能知道广播想干嘛了。

假如两台计算机的IP不是处于同一个子网之中，这个时候，我们就会把数据包发送给网关，然后让网关让我们进行转发传送

（3）DNS服务器

这里再说一个问题，我们是如何知道对方计算机的IP地址的呢？这个问题可能有人会觉得很白痴，心想，当然是计算机的操作者来进行输入了。这没错，当我们想要访问某个网站的时候，我们可以输入IP来进行访问，但是我相信绝大多数人是输入一个网址域名的，例如访问百度是输入www.baidu.com这个域名。其实当我们输入这个域名时，会有一个叫做DNS服务器的家伙来帮我们解析这个域名，然后返回这个域名对应的IP给我们的。

传输层

虽然我们已经把数据成功从计算机A传送到计算机B了，可是，计算机B里面有各种各样的应用程序，计算机该如何知道这些数据是给谁的呢？

这个时候，端口(Port)这个家伙就上场了，也就是说，我们在从计算机A传数据给计算表B的时候，还得指定一个端口，以供特定的应用程序来接受处理。
也就是说，传输层的功能就是建立端口到端口的通信。相比网络层的功能是建立主机到主机的通信。

也就是说，有了IP和端口，我们就可以进行通信了。这个时候可能有人会说，我输入IP地址的时候并没有指定一个端口啊。其实呢，对于有些传输协议，已经有设定了一些默认端口了。例如http的传输默认端口是80，这些端口信息也会包含在数据包里的。

应用层

作用：规定应用程序的数据格式的。规定传输层传来的数据，例如html格式的，mp4格式的，确保收到后才好解读渲染。

场景题：rand3()实现rand7()：通过公式rand3 * 3 = 3 * （rand3 - 1） + rand3（）

比如Rand9= 3( Rand3()-1 ) + Rand3()可以生成1到9之间的随机数。我们可以只要1到21

int rand7(){
    int x=INT_MAX;
    while(x>7){
      x=3*(rand3()-1)+rand3();
    }
    return x;
}

https://ac.nowcoder.com/discuss/575784?type=2&channel=-1&source_id=0&page=1

HTTPS怎么握手

在这里插入图片描述

（1）非对称加密

客户端会发送 Client Hello 消息到服务器，以明文传输版本信息、加密套件、压缩算法。另外，还会产生一个随机数，用于协商对称密钥的时候使用。
服务端返回 Server Hello 消息, 告诉客户端，服务器选择使用的协议版本、加密套件、压缩算法等，还有一个随机数，用于后续的密钥协商。
服务器端还会返回一个证书，然后说：Server Hello Done，信息结束。
客户端从自己信任的证书中，拿里面的公钥去解密服务端的证书。如果能够成功，则说明可信。
证书验证完毕之后，于是客户端计算产生随机数字 Pre-master，发送 Client Key Exchange，用证书中的公钥加密，再发送给服务器，服务器可以通过私钥解密出来。

到目前为止，无论是客户端还是服务器，都有了三个随机数，分别是：自己的、对端的，以及刚生成的 Pre-Master 随机数。通过这三个随机数，可以在客户端和服务器产生相同的对称密钥。

（2）对称加密

有了对称密钥，客户端就可以说：“Change Cipher Spec，咱们以后都采用协商的通信密钥和加密算法进行加密通信了。”

然后发送一个 Encrypted Handshake Message，将已经商定好的参数等，采用协商密钥进行加密，发送给服务器用于数据与握手验证。

同样，服务器也可以发送 Change Cipher Spec，说：“没问题，咱们以后都采用协商的通信密钥和加密算法进行加密通信了”，并且也发送 Encrypted Handshake Message 的消息试试。当双方握手结束之后，就可以通过对称密钥进行加密传输了。

这个过程除了加密解密之外，其他的过程和 HTTP 是一样的，过程也非常复杂。

上面的过程只包含了 HTTPS 的单向认证，也即客户端验证服务端的证书，是大部分的场景，也可以在更加严格安全要求的情况下，启用双向认证，双方互相验证证书。

ARP解析

ARP协议也是通过广播的形式给同一个子网中的每台电脑发送一个数据包(当然，这个数据包会包含接收方的IP地址)。

算法：

（1）请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大

//法2，利用二分查找，把每一行看成有序递增的数组，通过遍历每一行得到答案
//i从0开始，mid取low + high一半，
for(int i=0;i<array.length;i++){
    int low=0;
    int high=array[i].length-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(target>array[i][mid])
            low=mid+1;
        else if(target<array[i][mid])
            high=mid-1;
        else
            return true;
    }
}
return false;

（2）给定一个字符串m（只含有26个小写字符，假设m的总长度不大于1000），要求在字符串中找到最长的一个连续回文子串k，返回其长度。其中连续回文子串 k 需满足以下条件：

整个字符串是回文串（从前往后和从后往前看字符串是一样的）
该字符串中的任意相邻字符在ASCII 码表中也是相邻的
字符串中字母序必须是且只能是先升序后降序，且字母序只能改变一次

public int findMaxSubStr(String s) {
    char[] chars = s.toCharArray();
    int length = chars.length;
    //回文串是从中间向两边进行遍历
    //begin 和 end是它的窗口大小
    int begin = 0;
    int end = 0;
    System.out.println(chars[5] < chars[6]);
    for (int i = 0; i < length; i++) {
        //判断begin到end是不是回文串
        //以某一点或某两点开始看是不是回文串，返回其回文串长度
        int lenjishu = huiwen(chars, i, i);
        int lenoushu = huiwen(chars, i, i + 1);
        int len = Math.max(lenjishu, lenoushu);

        if (len >= end - begin + 1) {
            begin = i - (len - 1) / 2 ;
            end = i + (len >> 1);
        }
    }
    return end - begin + 1;
}

//返回以一点或两点的回文串长度
private int huiwen(char[] chars, int begin, int end) {
    while (begin >= 0 && end < chars.length && chars[begin] == chars[end]) {
        if (begin >= 1 && end <= chars.length - 2 && chars[begin - 1] < chars[begin] && chars[end + 1] < chars[end]) {
            begin--;
            end++;
        } else {
            break;
        }
    }
    return end - begin + 1;
}

（3）最大子序和，变形：不仅想要最大的和，还想要区间范围呢。

//2.若求区间
int begin = 0;
int end = 0;
int dp = nums[0];
int sumMax = nums[0];
//[begin, end]为最大子序和区间
for (int i = 1; i < length; i++) {
    if (dp > 0) {
        dp += nums[i];
    } else {
        //begin在dp < 0时进行迭代
        dp = nums[i];
        begin = i;
    }
    //end在所求dp > sumMax，sumMax迭代时进行更新
    if (dp >= sumMax) {
        sumMax = dp;
        end = i;
    }
}

https://www.nowcoder.com/discuss/611814?source_id=discuss_experience_nctrack&channel=-1

公平锁和不公平锁的区别

区别是对于一个对象释放了锁，那是否会按照线程获取锁的先后顺序来获取该锁对象。

ReentrantLock非公平锁即在有线程释放锁时，随机唤醒阻塞队列中的一个线程

可重入锁是什么

一个线程可以重复获取锁，例如synchronized，里面有对应的计数器可以对线程获取次数++，释放时依次释放。而api层面的锁，

例如reentrantlook，重入的获取锁时，直接增加state的值

jvm内存的分类

主要分成两类，线程独享的，线程间共享的。

线程独享：虚拟机栈，本地方法栈，程序计数器类似于pc

线程共享：堆（实例化的对象，GC 的主要位置）方法区（实现的话jdk7是永久代，用于存放类信息，字符串常量池，静态变量。jdk8以及以后是元空间存放类信息和静态变量，字符串常量池被放到了堆中。无论是元空间还是永久代，都只是方法区的一种实现。

虚拟机栈存了什么

以栈帧形式存储Java方法的数据，局部变量表，对象的引用，当该线程以轻量级锁的形式占有一个锁对象时，栈中会存放lock record，记录了锁对象头的mark word副本，以及一个owner指针指向该锁对象。

堆存了什么，怎么分区，为什么要分代

存放对象实例和字符串常量池。几乎所有对象实例都在这里分配内存。
java的引用有哪些

强引用：最传统的引用定义。任何情况下，只要强引用关系存在，GC永远不会回收掉被引用对象。

软引用：还有用，但并非必须的对象。在系统即将发生内存溢出异常前，会把软引用关联对象列入回收范围进行第二次回收。

弱引用：强度比软引用更弱。下一次垃圾收集发生时，无论内存是否足够，都进行回收。threadlocal在自身threadlocalmap的Entry被设置为弱引用，每次gc就会回收，最后使用remove方法，将所有value对象置为null避免内存泄露

虚引用：最弱的引用关系。虚引用的唯一作用就是在该对象被GC回收时收到一个通知。
进程和进程的通信方式？共享内存？如何共享？拿出一块自己的内存映射到相同的物理内存。

算法题

（1）括号生成，生成所有可能的并且有效的括号组合，dfs

// 枚举这一层所有可能的选择，该层可能选左，可能选右
// 选左
if (left < n) {
    chars[index] = '(';
    // 进入下一层
    dfs(index + 1, left + 1, right, n, chars, list);
}

// 选右
//重点：要保证right个数要少于左括号个数
if (right < n && right < left) {
    chars[index] = ')';
    dfs(index + 1, left, right + 1, n, chars, list);
}

秋招

美团

链接：https://www.nowcoder.com/discuss/712956?source_id=profile_create_nctrack&channel=-1

操作系统

进程和线程的区别？

什么是临界区？

一个访问共用资源的程序片段，而这些共用资源又无法同时被多个线程访问的特性。

当有线程进入临界区段时，其他线程或是进程必须等待，有一些同步的机制必须在临界区段的进入点与离开点实现，以确保这些共用资源是被互斥获得使用。只能被单一线程访问的设备。

进程间通信的方法？

主要是进程间交换以及传输信息，或者是达到进程的目的。主要的通信方式有：

（1）管道通信，实现了一条半双工的通信管道，连接两个父子进程，并且写完才能读，读完才能写。

（2）命名管道，与管道相似，不受父子进程的限制，进行进程间的通信。

（4）共享内存：多个进程共享的内存空间，不需要复制，原理：两个进程拿自己的一块虚拟内存来映射到相同的物理内存。

（5）信号量：它实质是一个计数器，多个进程提供对共享数据对象的互斥同步。

（6）socket：它是一种用于不同主机间的进程网络通信，通过绑定IP和端口，来实现数据传输。底层实际上是封装了TCP/IP协议簇。

主要接触到的就是管道和socket，socket的话就在实现客户端和服务端的不同主机的网络通信，通过绑定IP和端口；

管道的话，例如Java nio中的channel 是双向的, 可以返回底层操作系统的情况底层的操作系统通道就是双向的

进程有哪些调度算法？

作业调度算法主要分为两类:非抢占式调度和抢占式调度。

(1)非抢占式:一个线程被调度运行完后，才会运行下一个线程，期间一直被阻塞。先来先服务:最基本的算法，非抢占式的，有利于长作业。短作业优先:顾名思义，利于短作业，长作业可能会长期等待。高响应比优先:兼顾了长短作业，要求服务时间少 + 等待时间长(分别对应短作业和长作业)会优先执行。

(2)抢占式调度:一个线程执行过程中，时间片用完发生中断调度下一个线程运行。时间片轮转:每个线程分配相同时间片，执行完后调度下一个。优先级调度:顾名思义，选择最高的优先级进行调度，一般是动态优先级，等待时间长的线程优先级就增加，防止永远等待。

多级反馈队列调度算法:基于最高优先级 + 时间片轮转算法 (1)维护多个优先级队列:优先级越高，时间越短 (2)调度按照优先级调度，如果时间片结束未执行完线程，则加入后面队列的尾部，等待调度，以此类推兼顾了长短作业，有较好的响应时间。

什么是死锁？死锁的条件？

两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种相互等待的现象。

资源进行互斥等待
资源不可被抢占
保持并等待（阻塞不放弃自己资源）
循环等待（相互等待其释放资源）

Java基础

Java的异常体系？

Exception:这就是我们常说的异常，偶然因素引起，可以用针对性的代码处理。数组越界 ArrayIndexOutOfBound，空指针异常 NullPointException，网络连接中断等。Exception 分为编译期异常 (javac.exe)、运行时异常(java.exe)，编译时(受检)异常:FileNotFoundException，I/O 异常， ClassNotFound 等，运行时(不受检)异常:ArrayIndexOutOfBound，NullPointException，ClassCastException (类型转换异常)NumberFormatException(数字转换异常，例如字符串通过 Interger 的方法想转成数字)
Integer类有缓存吗？为什么需要缓存？

缓存是当再次创建值在-128-127区间的Integer实例时，会复用缓存中的实例，避免重复创建，缓存工作都是在静态块中完成，在类加载的初始化阶段执行。

注意，这里的创建不包括用new创建，new创建对象不会复用缓存实例。

我可以自己实现一个包名和类名都一样的Integer类吗？

integer属于jdk核心类库，由于双亲委派模型的原因，这个类不会被加载，因为已经有一个一样的类被加载了，这时会返回异常。

JVM

JVM的类加载机制

加载:通过一个类的全限定名(灵活度提高)来获取定义此类的二进制字节流，并把此二进制字节流表示的静态存储结构转化为方法区运行时数据结构，并生成代表这个类的 class 对象放在方法区(HotSpot 放在方法区，其他的可能不一样)中作为类数据的访问入口。

验证:确保 class 文件的自己留包含信息符合 jvm 的要求，是否符合 java 规范，符号引用验证(解析)

准备:为类变量(static 修饰的变量，不是所有的变量哦)分配内存，并设初值(设初值，全部是零值，真正赋值在初始化那里)，但对于像存在 final 修饰的类变量会使用属性表附带的值直接初始化。

解析:将符号引用变为直接引用。符号引用包含如类引用，方法和字段的引用，都要找到对应的类或接口中寻找，并转化为直接引用(指向目标的指针)，用全限定名去找。

初始化:收集类中所有赋值语句和静态块内容，组合成类构造器，收集顺序按照出现顺序，且静态块里面对于在其后定义的变量可写不可读。然后执行这个类构造器，且执行顺序会先执行最顶级父类，从上往下，所有最先执行的永远是 Object(接口(无静态块，但有赋值)与实现类顺序是先子类)

有几种类加载器？为什么要有双亲委派模型？

三种系统提供的类加载器

启动类加载器和扩展类加载器 Extension ClassLoader，负责加载 JAVA_HOME/lib 下的类库。扩展类用 JAVA 编写，且它的父亲加载器是启动类加载器。

应用程序类加载器(Application ClassLoader)，也称为系统类加载器，默认负责加载应用程序 classpath 目录下的所有 jar 和 class 文件(用户写代码路径下)。

三者呢是以组合的方式成所谓的父子类。

双亲委派模型

如果一个类加载器收到了一个类加载请求，它不会自己去尝试加载这个类，它会调用自己的 loadClass 方法:首先把这个请求转交给父类加载器去完成。每一个层次的类加载器都是如此。因此所有的类加载请求都应该传递到最顶层的启动类加载器中，*只有到父类加载器反馈自己无法完成这个加载请求(在它的搜索范围没有找到这个类)时，子类加载器才会调用自己的 findClass 方法尝试自己去加载。 *

作用：

保证同一层级的类都由同一类加载器加载，保证了基础类型的一致性。
保护程序的安全，防止核心API被随缘篡改。当我们自己写 java 包下的类时，并打包到同样的包下，由于双亲委派模型的原因，这个类不会被加载，因为已经有一个一样的类被加载了，这时会返回异常。

打破双亲委派模型的例子

tomcat 中打破了双亲委派模型，如果不打破势必导致webapps中不同的context的的不同版本的jar，不能被加载到

通过自定义加载器，Web应用默认的类加载顺序是（打破了双亲委派规则）：

先从JVM的BootStrapClassLoader中加载。
加载Web应用下/WEB-INF/classes中的类。
加载Web应用下/WEB-INF/lib/*.jap中的jar包中的类。
加载上面定义的System路径下面的类。
加载上面定义的Common路径下面的类。
Java有哪些GC算法？

标记-清除算法，即标记可回收对象，再回收标记对象，需要维持空闲列表。缺点：内存空间碎片化

复制算法（新生代）：将可用内存划分为大小相等的两块。每次只用其中一块。当这一块内存用完时，将仍存活的对象复制到另一块上。然后把已使用过的内存块一次清除，对象分配空间为指针碰撞。

在这里插入图片描述

堆中：将新生代划分为一块较大的内存(Eden)和两块较小的内存(Survivor)。Eden和Survivor默认大小比8:1。每次分配内存只使用Eden和一块Survivor，发生垃圾收集时，将存活的对象复制到另一块Survivor中，清除Eden和使用过的Survivor。当Survivor中的空间不足以容纳一次Minor GC的存活对象时，需要依赖老年代区域进行分配担保（即多余的存活对象进入老年代区）。

优缺点：不会出现“碎片问题”。但是需要两倍空间，需要维护引用与对象之间的关系，不管是内存占用和时间开销都比较大

标记-整理算法：针对老年代对象的回收算法。将存活的对象向内存一端移动，直接清理掉边界以外的内存。

在这里插入图片描述

优缺点：适合于老年代这种比较少对象的gc

了解过G1收集器吗？g1缺点？

追问：四个步骤中哪些步骤会STW？

第四步的并发回收变成了筛选回收：局部可看做复制算法，将回收集中的Region中的存活对象复制到空Region，再清理回收集中的Region，整体上是标记-压缩算法。（涉及存活对象，需stw）没有内存碎片产生，有利于程序长时间运行。

![image-20210830095906885](/Users/bytedance/Library/Application Support/typora-user-images/image-20210830095906885.png)

Java集合

HashMap扩容时发生死循环是什么情况？

Java1.8之前采用头插法来rehash数组中位于同一个桶的 node，链表中元素会在扩容的插入时前后链表顺序倒置，多线程进行插入时，由于插入会改变前后链表的指针指向，就会陷入死循环，指向混乱或丢失，从而形成环形链表，或者数据丢失。

Java1.8 之后 hash 碰撞就采用尾插法，不会改变前后链表顺序，就不会形成这种情况，但我觉得还是会造成数据覆盖的情况。因为多线程可能同时进入判断桶中是否有数据，判断目前没有数据后，进行线程的切换，可能桶中有数据，这样就会覆盖掉原数据。

ConcurrentHashMap底层
追问：ConcurrentHashMap扩容机制

1.7 中的 concurrentHashMap 使用了多段锁的机制，定义了segment，每个 segment 是一个单独的容器，也是一把锁。初始化时会为 16 个 segment 的第一个进行初始化，并用 CAS 操作放入，初始化第一个的作用在于后面的 segment 初始化都直接在第一个里面拿值进行初始化。在进行 put 操作时通过 hash 计算节点应该放到哪个 segment 里面，接着查看这个 segment 是否为空，为空要进行初始化，初始化时线程需要用 CAS 操作修改某个标志的值，修改成功再进行初始化，不成功就放弃初始化，这保证只有一个线程初始化了 segment，初始化时是利用第一个 segment 的值来初始化的。

初始化成功后再进入 segment 之前要操作获得这个 segment 的锁，获取锁成功后在内部再次散列获得数组元素节点，遍历链表，若键存在就更新对应的值，若不存在建立节点后使用头插法插入节点。插入时使用 CAS 操作保证与 get 之间的并发性，最后有锁的释放。获取失败会进行自旋尝试获得，并且在自旋时还会尝试去预先创建节点。插入数据后是可能触发 rehash 的，rehash 会让当前 segment 下数组长度扩容两倍后依次移动放入，建立的临时数组要用 volatile 修饰，保证 get 时是可见的。

1.8 中只使用了一个数组，用链地址法解决 hash 冲突，同样的数据过多会使得链表变成红黑树，访问效率提高，put 时首先检查对应数组节点是不是空的，空的话尝试用 CAS 插入，然后判断是否当前节点的 hash 值为 MOVED，这表示有线程再进行 rehash，那么当前线程要去帮忙 rehash，然后前面两种都不满足，说明尝试访问非空的数组节点，这是会首先以链表头作为锁对象利用 synchronized 关键字建立同步代码块，然后对节点进行访问遍历，有相等的键覆盖，没有就尾插到链表尾，然后计算节点数据个数看要不要转换为红黑树，计算负担因子看要不要扩容。前面说 MOVED 表示当前有线程再扩容，这是个特殊节点对应的 hash 值常量，并且此时会发现指向新数组的引用不为空，线程帮忙时会被分配任务，执行对于数组节点上的链表搬运，线程首先检查当前节点的头节点是不是特殊节点，是的话表示这个节点已经被其他节点搬运走了，不是的话，尝试获取头结点的锁，获得成功就锁起来，然后开始搬运链表中的节点，首先把节点根据 hash 值分成两条链表，再分别放到新数组的两个节点下，最后把久的节点的头节点设置为特殊节点，表示搬运完毕。接着搬运其他，直到结束 rehash。

JDK1.8：数组+ 链表（红黑树）来实现，以下数组=table，链表为bin，红黑树为TreeNode

初始化，使用cas保证并发安全，懒惰初始化table
树化，当table长度<64时，尝试扩容；当bin的长度>8，会将链表转化成红黑树，树化过程用synchronized锁住链表头。
put，没链表时为cas创建链表，有就尾插法
get，无锁仅需保证可见性
扩容，需要对每个链表进行synchronized
size，元素个数保存在baseCount，并发时将个数变动保存到CounterCell[]中，最后统计数量时再进行累加即可

链接：https://www.nowcoder.com/discuss/717065

项目

主要问的实习项目过程中遇到的难点

技术问题上：掘金翻译：这块每天推荐3篇文章限制，我们考虑使用redis来实现限制，通过设置到晚上12点的过期时间来限定，以及后面的消息推送相关的未读数，我们也是存储在；还有就是认领时的并发控制，因为一篇推荐后的文章只能被一个人认领。在单机场景下，可以使用语言的内置锁来实现单机的线程同步。但是在分布式场景下，需要同步的进程可能位于不同的节点上，所以这我们就要考虑分布式锁，这里我们主要通过数据库唯一索引来实现，我就在数据库查询操作时，因为查询的条件语句是文章 id，是索引字段走的是行锁，获得锁时向表中插入一条记录，释放锁时删除这条记录。唯一索引可以保证该记录只被插入一次，那么就可以用这个记录是否存在来判断是否处于锁定状态。

掘金沸点话题：目前刚刚确定了技术方案，遇到的难点的话我想一下，主要有话题热度那里，热度的计算时带该话题的展现量（主要包括列表页和详情页）这个的话是基于客户端的埋点数据去做的统计，统计后的日志数据，我开始的时候设计的时候不知道选什么来接收数据存储，后面就跟我mentor需要考虑大数据的存储组件，这里我们主要用到了bmq它是Kafka升级版，是分布式提交日志或者分布式流平台，高吞吐量、低延迟。

统计后的埋点日志生产进入bmq，然后我们再消费里面对应topic的数据，因为我们要展示近7天的数据量，因为过了7天话题可能会过时，因为用户侧拉取这些个话题，是从mysql话题表里获取，然后排序处理。进行隔离，我们使用中间件，来进行缓存简单，高效一些，然后每天同步同步数据。每次消费掉一条log，对应的每天的技术量就+1，所以单话题最大需要7个，话题数我们按照500每天的量去预估的，redis的key的数量就是3500个7天最多。每隔5min同步一次数据到mysql，则将redis 计数刷入mysql表（因为我们要做热度排序使用），服务端数据读取不会直接读redis，会用mysql的数据对用户暴露。

并发

Java与并发相关的关键字？

谈了一下synchronized，主要说了一下锁升级。

计算机网络

得到网页的IP地址之后是如何建立连接的？

加分：首先浏览器查找当前URL是否存在缓存，并比较缓存是否过期。过期就会重新加载
然后就开始DNS进行域名的解析，获取到对应的IP。加分：先检查（1）本地hosts文件是否有这个网址映射关系，如果有就调用这个IP地址映射，完成域名解析。没有才会（2）查找本地DNS解析器缓存。如果还是没有找到则会（3）查找DNS服务器，如果找到则返回。
根据IP，通过三次握手建立TCP连接，维护好双方的序列号，滑动窗口大小。
然后再向服务器发送HTTP请求。
服务器处理请求，返回HTTP响应。
前端就渲染页面，显示功能。
通过Tcp四次挥手，关闭TCP连接。

MySQL

索引设计的原则

追问：给一个简单的SQL，问如何设计索引。
追问：两个用=判断的可以变换顺序吗？

Redis

Redis是单线程还是多线程？单线程为什么依然快？

Redis的多路复用是如何保证读写的顺序正确？

他会维持两个队列先到先服务，Redis 会将每个客户端套接字都关联一个指令队列。客户端的指令通过队列来排队进行顺序处理，先到先服务。多个套接字产生的事件，由IO多路复用程序将它们放到一个队列中，然后通过这个队列，有序、同步地传递给文件事件分派器。

逻辑题

要吃一颗A药一颗B药，两种药看起来一样，现在手上有一粒A两粒B，怎样吃才能不浪费？
再取出一片A药，这样手上就有2片A+2片B，每片吃一半，只掉的就恰好是1粒A+1粒B。
1000瓶液体，1瓶有毒，一小时毒发，需要多少只老鼠才能一小时试出哪瓶有毒？

逐位排除的方法，10个老鼠，每次喝其中一位为1的药，则老鼠死掉即为该位为1，则最后组成毒药的二进制编号

链接：https://www.nowcoder.com/discuss/721283?source_id=profile_create_nctrack&channel=-1

算法题

求二叉树距离最远的两个节点的距离
求二叉树距离最远的两个点

结束之后就是简单聊了一下实习项目

成都蚂蚁

链接：https://www.nowcoder.com/discuss/701729?source_id=discuss_experience_nctrack&channel=-1

1. 面向对象的三大特征？

封装:把客观事物抽象成具体的类，并把对类的数据的操作抽象为方法，通过不同的修饰符对内部数据提供不同级别的保护，封装以后也使得信息和操作对用户透明化。
继承:通过继承，子类可以使用父类的非私有变量和方法，主要作用就是实现代码复用，等级划分等，包括接口和类继承
多态:是指一个类实例的相同方法在不同情形有不同表现形式。提高了代码的可拓展性和复用性通过同一个上级引用指向不同的子类，使得对同一消息做出不同回应。

追问：多态的好处？在Java中有哪些应用场景？

（1）提高了代码的维护性（继承保证）；提高了代码的扩展性。（2）多态的应用主要就是接口吧，通过实现接口可以应用于不同的情形与表现形式。

重载和重写是面向对象多态性的体现，重载指的是同一个类中的同名方法可以根据不同的参数列表来区分，重写，指的是子类可以重写父类的方法。

重载是在编译期确定的，下面的例子可以说明，在编译期，编译器并不知道对象的实际类型，所以在调用方法的时候通过静态类型判断来选择重载的方法。

重写是在运行期确定的，如果没有重写，子类的方法表中方法的地址就是父类方法表中方法的地址，重写之后子类的方法表中方法的地址就会替换为子类重写的方法的地址。所以在运行期，Son的方法表指向的是Son.hardChoice(QQ());

2. JVM的内存区域？具体介绍一下每个区域的作用。

主要分成两类，线程独享的，线程间共享的。

线程独享：虚拟机栈（存放一些局部的变量表），本地方法栈，程序计数器类似于pc

3. 讲解GC机制？

gc是主要是jvm进行回收一些没有任何指向的对象，如果不进行gc，内存迟早会消耗殆尽。

gc的过程主要分为两个阶段，一个是垃圾标记阶段，检查对象是否需要释放，主要有两种方法。

哪些作为gc root？gc root从这些节点开始，根据引用关系向下搜索，所以必须是一些活跃的引用

(1)在虚拟机栈中有引用的对象（参数、局部变量等）（栈帧出栈后不再作为GC Roots）

(2) 方法区中的类静态属性引用的对象（即static的类变量）

(3) 方法区中常量引用的对象（即final变量）

内存溢出（OOM）

没有空闲内存，并且垃圾收集器GC后也无法提供更多的内存了，会尝试回收软引用对象。

原因：（1）堆内存设置的不够：可能有内存泄露问题

（2）创建大量的大对象，并且没有被回收。
内存泄露：严格来说，只有对象不会再被程序用到，并且GC不会回收到它们，才叫做内存泄露。

宽泛讲：对象的生命周期变得很长（比如局部变量，设置成Static变量）。单例对象的生命周期同应用程序一样长，如果它有外部引用的话，则外部对象不会被回收，则导致内存泄露。threadlocal的value值如果后续不置为null也会造成内存泄露，一些提供了close()的资源未使用close()：例如：数据库连接，使用dataSource.getConnection()，网络连接Socket 和 IO流未手动close()，否则都无法回收。

另一个是回收阶段，垃圾回收三个算法，一个理论

GC应将java堆划分出不同区域，把java堆划分为新生代和老年代两个区域。

年轻代：对象比较短，生命周期短，使用复制算法比较好（Eden Survivor0 复制到 Survivor1）
老年代：使用标记-清除-整理结合，平时使用标记-清除算法，当内存碎片化过于严重，以致影响对象分配时，使用一次标记-整理算法消除碎片化空间。

7. 进程间通信的方法？

追问：用过哪些？具体怎么调用的？ socket。。

8. 多线程同时读写会发生什么问题？

会造成线程安全问题，线程安全就是多线程访问或者说读写一个对象时，会出现数据不一致的结果。

为什么会有这种问题？

Java 内存模型规定了所有的变量都存储在主内存中，每条线程有自己的工作内存。线程的工作内存中保存了该线程中用到的变量的主内存副本拷贝，线程对变量的所有操作都必须在工作内存中进行，而不能直接读写主内存。线程访问一个变量，首先将变量从主内存拷贝到工作内存，对变量的写操作，不会马上同步到主内存。不同的线程之间也无法直接访问对方工作内存中的变量，线程间变量的传递均需要自己的工作内存和主存之间进行数据同步。

怎么解决？

synchronized在写时进行同步代码

对变量加volatile 写时进行cas自旋的修改

9. 死锁是什么？如何避免？

银行家算法。，防止系统进入不安全的状态，每次让最少需要资源的进程获取到全部资源。

追问：死锁的必要条件是什么？如何从必要条件上预防？

互斥条件：一个资源每次只能被一个进程使用。
请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

3. 索引查询一定有提升吗？

缺点：索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。

（1）在经常查询的列、使用在WHERE子句中的列上创建索引，加快条件的判断速度。

在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；

（2）不适合加索引的地方：

查询中很少使用或参考的列不应创建索引。
只有很少数据值的列也不应增加索引。这是因为由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引并不能明显加快检索速度。

实习项目

4. 项目的QPS大概是多少？

web 端，列表页:240w/d，详情页:3w/d app 端，列表页+详情页:15w/d
峰值 qps=pv / 4w * 2 = 125(预估量)

链接：https://www.nowcoder.com/discuss/713883?source_id=discuss_experience_nctrack&channel=-1

JVM是进程还是线程？

Java 编写的程序都运行在在 Java 虚拟机(JVM)中，每用 java 命令启动一个 java 应用程序，就会启动一个 JVM 进程。在同一个 JVM 进程中，有且只有一个进程，就是它自己。

在这个 JVM 环境中，所有程序代码的运行都是以线程来运行的。JVM 找到程序程序的入口点 main()，然后运行 main()方法，这样就产生了一个线程，这个线程称之为主线程。当 main 方法结束后，主线程运行完成。JVM 进程也随即退出。

所以一个应用程序只对应着一个进程，但是可以包含多个线程。所以 Java 应用程序不存在多进程

3. 线程的同步机制

在需要同步的方法的方法签名中加入synchronized关键字。
使用synchronized块对需要进行同步的代码段进行同步。
使用JDK 5中提供的java.util.concurrent.lock包中的Lock对象。

4. 了解CMS和G1吗

CMS：老年代的收集器，标记-清除算法，分四步，两步执行时间较长的步骤（并发标记，并发清除）运行工作线程一起执行，但只能搭配Serial收集器或者parNew收集器。

初始标记：标记GC Roots直接关联到的对象，这个过程要使得所有工作线程停顿

并发标记：进行GC Roots 整个对象可达性标记，耗时所以和工作线程并发运行

重新标记：工作线程的运行会导致标记发生变动，这一步用于修正标记。

并发清除：开始垃圾回收，可以与工作线程一起执行（所以是标记-清除）

特点：并发操作使得程序变慢；并发阶段产生新的浮动垃圾；因为是标记-清除算法，使得碎片化，出现大对象无法分配从而Full GC，进行碎片整理。

G1：不区分年轻代和老年代，以Region为最小回收单位，通过跟踪每个Region的回收价值大小（即回收所获得空间和回收所需时间的经验值），并维护一个优先级列表。优先回收价值高的Region，流程前三步与CMS相同，最后一步筛选回收。

筛选回收：需暂停用户线程，根据优先级来逐个进行区域的回收。（局部复制，整体又是压缩）

使用标记-整理算法，回收时不会产生可用空间零碎分布的现象。

5. 线程通信机制有哪些，什么情况下使用

wait()、notify()、notifyAll()结合synchronized来实现

int count = 10;
while (count > 0) {
    synchronized (prev) {
        synchronized (self) {
            System.out.println(name);
            count--;
            self.notifyAll(); //唤醒其他线程竞争self锁，注意此时self锁并未立即释放。
        }
        System.out.println(name + "释放" + self);
        // 最后一次打印，通知其它线程自己释放锁
        // 重点：不是最后一次 就wait，等待别个线程来notify自己
        if (count == 0) {
            prev.notifyAll();
        } else {
            try {
                // 立即释放锁，进入wait阻塞唤醒
                prev.wait();
                System.out.println(name + "唤醒并且获得" + prev + "之后");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

    }

}

条件对象：Condition，Condition和ReentrantLock重入锁来进行有选择性的通知

@Override
public void run() {
    try {
        lock.lock();

        for (int i = 0; i < 10; i++) {
            while (state % 3 != 0){//注意这里是不等于0，也就是说没轮到该线程执行，之前一直等待状态
                System.out.println("A阻塞等待");
                A.await(); //该线程A将会释放lock锁，构造成节点加入等待队列并进入等待状态
            }
            System.out.println("A");
            state++;
            B.signal(); // A执行完唤醒B线程
        }

    } catch (InterruptedException e) {
        e.printStackTrace();
    } finally {
        lock.unlock();
    }
}

链接：https://www.nowcoder.com/discuss/173506?type=post&order=time&pos=&page=2&ncTraceId=&channel=-1&source_id=search_post_nctrack

线程的状态，wait和block的区别

block的话，synchronized会导致线程进入Blocked阻塞获取锁状态

Waiting线程被其他线程调用Object.notify()唤醒之后，才有机会重新获取cpu时间片来继续执行。重新获取对象上的锁的时候也会进入Blocked状态

thrift优势在哪里呢，你说用了rpc，有什么优势呢

thrift

thrift跨语言，基于idl文件来生成代码，适用于公司内的各套技术栈，其次呢为了追求性能吧

为了保证框架的高性能，没有使用反射机制，运行性能上，kite框架在设计的时候就考虑了性能问题，框架全体代码都避免了使用反射，使用代码生成来，因此框架整体性能是和原生Thrift性能一样的。

图示低可信度描述已自动生成

序列化，默认使用的是thrift的二进制序列化；传输层的话默认使用的buffer传输

每个方法抽象成EndPoint。一次RPC调用是两个EndPoint的关系整合了多种中间件，实现公司内部的服务需求，中间件处理输入端点和输出端点，在微服务架构中，RPC调用的服务的注册发现，降级，重试，断路器机制等都会通过Middleware来实现。实现组件化的效果，和业务EndPoint解耦。

底层实际上调用的时候有request和response的封装，作用是：可以通过这些方法来获取RPC调用过程中传递的字段。例如调用方和服务方的id，服务集群的名称

RPC框架的好处在于，首先就是长链接，不必每次通信都要像http一样去开启连接和关闭连接，减少了网络开销；

长连接好处：避免频繁创建连接，避免资源消耗，在高并发，高流量下不使用长连接会使大多数服务处于timewait阶段

其次就是RPC框架一般都有注册中心，有丰富的监控管理；发布、下线接口、动态扩展等，对调用方来说是无感知、统一化的操作。restful使用http协议实现，而rpc则不一定使用http，一般比较常用的是tcp， RPC 可以获得更好的性能（省去了 HTTP 报头等一系列东西）,TCP更加高效，而HTTP在实际应用中更加的灵活。

Reentrantlock

非公平锁：获取时直接尝试cas，如果没有获取失败就变为获取，里面的话也是先尝试一下再加入队列中等待

公平锁：获取时也是如果前面没有等待的节点也是直接cas操作获取锁，如果当前锁持有的是自身，就重入的state++

![image-20210831102821726](/Users/bytedance/Library/Application Support/typora-user-images/image-20210831102821726.png)