大厂面试题集合之蚂蚁一面

二叉搜索树和平衡二叉树有什么关系?

平衡二叉树也叫做平衡二叉搜索树,是二叉搜索树的升级版,二叉搜索树是指节点左边的所有节点都比该节点小,节点右边的节点都比该节点大,而平衡二叉搜索树是在二叉搜索的基础上还规定了节点左右两边的子树高度差的绝对值不能超过1

强平衡二叉树和弱平衡二叉树有什么区别

强平衡二叉树AVL树,弱平衡二叉树就是我们说的红黑树。

  1. AVL树比红黑树对于平衡的程度更加严格,在相同节点的情况下,AVL树的高度低于红黑树
  2. 红黑树中增加了一个节点颜色的概念
  3. AVL树的旋转操作比红黑树的旋转操作更耗时

B树和B+树的区别,为什么MySQL使用B+树

B树的特点:

  1. 节点排序
  2. 一个节点可以存多个元素,多个元素也排序了

B+树的特点:

  1. 拥有B树的特点
  2. 叶子节点之间有指针
  3. 非叶子节点的元素在叶子节点上都冗余了,也就是叶子节点中存储了所有的元素,并且排好顺序

MySQL索引使用的是B+树,因为索引是用来加快查询的,而B+树通过对数据进行排序所以是可以提高查询速度的,然后通过一个节点中可以存储多个元素,从而可以使得B+树的高度不会太高,在MySQL中InnoDB页就是一个B+树节点,一个InnoDB页默认16kb,所以一般情况下一颗两层的B+树可以存储2000万行左右的数据,然后通过利用B+树叶子节点存储了所有数据并且进行了排序,并且叶子节点之间有指针,可以很好的支持全表扫描,范围查找等SQL语句。

epoll和poll的区别

  1. select模型:使用的是数组来存储Socket连接文件描述符,容量是固定的,需要通过轮询来判断是否发生了IO事件
  2. poll模型:使用的是链接来存储Socket连接文件描述符,容量是不固定的,同样需要通过轮询来判断是否发生了IO事件
  3. epoll模型:epoll和poll是完全不同的,epoll是一种事件通知模型,当发生了IO事件时,应用程序才进行IO操作,不需要poll模型那样主动去轮询

简述线程池原理,知道FixedThreadPool用的阻塞队列是什么嘛?

线程池内部是通过队列+线程实现的,当我们利用线程池执行任务的时候:

  1. 如果此时线程池中的数量小于corePoolSize,即使线程池中的线程都处于空闲状态,也要创建新的线程来处理被添加的任务。
  2. 如果此时线程池中的数量等于corePoolSize,但是缓冲队列workQueue未满,那么任务被放入缓冲队列中。
  3. 如果此时线程池中的数量大于等于corePoolSize,缓冲队列workQueue已满,并且线程池中的数量小于maximumPoolSize,则会创建新的线程来处理被添加的任务。
  4. 如果此时线程池中的数量大于corePoolSize,缓冲队列workQueue已满,并且线程池中的数量等于maximumPoolSize,那么通过handler所指定的策略来处理此任务。
  5. 当线程池中的线程数量大于corePoolSize时,如果某线程空闲时间超过keepAliveTime,线程将被终止。这样,线程池可以动态的调整池中的线程数。

FixedThreadPool代表的是定长线程池,底层用的是LinkedBlockingQueue,表示无界的阻塞队列。

Synchronized和ReentranLock的区别知道嘛?

  1. Synchronized是一个关键字,ReetrantLock是一个Java类。
  2. Synchronized会自动地加锁与释放锁,ReetrantLock需要程序员的手动加锁和释放锁。
  3. Synchronized的底层是JVM层面的锁,ReentranLock是API层面的锁。
  4. Synchronized是非公平锁,ReentrantLock可以选择公平锁或非公平锁。
  5. Synchronized锁的是对象,锁信息保存在对象头中,ReetrantLock通过代码中的int类型的state标识来标识锁的状态。
  6. Synchronized底层有一个锁升级的过程。

Sychronized的自旋锁、偏向锁、轻量级锁、重量级锁,分别介绍和联系

  1. 偏向锁:在锁对象的对象头中记录一下当前获取到该锁的线程ID,该线程下次如果又来获取该锁就可以直接获取到了
  2. 轻量级锁:由偏向锁升级而来,当一个线程获取到锁后,此时这把锁是偏向锁,此时如果有第二个线程来竞争锁,偏向锁就会升级为轻量级锁,之所以叫轻量级锁,是为了和重量级锁区分开来,轻量级锁底层是通过自旋来实现的,并不会阻塞线程
  3. 如果自旋次数过多仍然没有获取到锁,则会升级为重量级锁,重量级锁会导致线程阻塞
  4. 自旋锁:自旋锁就是线程在获取锁的过程中,不会去阻塞线程,也就无所谓唤醒线程,阻塞和唤醒这两个步骤都是需要操作系统去进行的,比较消耗时间,自旋锁是线程通过CAS获取预期的一个标记,如果没有获取到,则继续循环获取,如果获取到了则表示获取到了锁,这个过程线程一直在运行中,相对而言没有使用太多的操作系统资源,比较轻量。

HTTPS是如何保证安全传输的

Https通过使用对称加密、非对称加密、数字证书等方式来保证数据的安全传输。

  1. 客户端向服务端发送数据之前,需要先建立TCP连接,所以需要先建立TCP连接,建立完TCP连接后,服务端会先给客户端发送公钥,客户端拿到公钥后就可以用来加密数据了,服务端到时候接收到数据就可以用私钥解密数据,这种就是通过非对称加密来传输数据。
  2. 不过非对称加密对比对称加密要慢,所以不能直接使用非对称加密来传输数据,所以可以通过非对称加密的方式来传输对称加密的密钥,之后就可以使用对称加密来传输请求数据了。
  3. 但是仅仅通过非对称加密+对称加密还不足以能保证数据传输的绝对安全性,因为服务端向客户端发送公钥时,可能会被截取。
  4. 所以为了安全的传输公钥,需要用到数字证书,数字证书具有公信力、大家都认可的,服务端向客户端发送公钥时,可以把公钥和服务端相关信息通过Hash算法生成消息摘要,再通过数字证书提供的私钥对消息摘要进行加密生成数字签名,在把没进行Hash算法之前的信息和数字签名已经形成数字证书。最后把数字证书发送给客户端,客户端收到数字证书之后,就会通过数字证书提供的公钥来解密数字证书,从而得到非对称加密要用到的公钥。
  5. 在这个过程中,就算有中间人拦截到服务器发送出来的数字证书,虽然它可以解密得到非对称加密要使用的公钥,但是中间人时没办法伪造数字证书发送给客户端的,因为客户端上内嵌的数字证书时全球具有公信力的。某个网站如果要支持https,都是需要申请数字证书的私钥的,中间人如果要生成能被客户端解析的数字证书,也是要申请私钥的,所以是比较安全了。

本文福利, 免费领取C/C++ 开发学习资料包、技术视频/代码,1000道大厂面试题,内容包括(C++基础,网络编程,数据库,中间件,后端开发/音视频开发/Qt开发/游戏开发/Linuxn内核等进阶学习资料和最佳学习路线)↓↓↓↓↓↓见下面↓↓文章底部点击免费领取↓↓