后端开发、C++开发面经分类整理

博主秋招参加了字节百度腾讯B站虾皮美团等多个大厂的秋招,均已得到offer。现将参与的多轮面试中被问到的基础类问题进行分类整理,也欢迎大家补充!
我投递的主要是后端开发工程师、C++开发等,感觉遇到的问题大致可以归纳为以下几类,图里展开的都是多次被问到的重点问题:

后端开发、C++开发面经分类整理_第1张图片

文章目录

    • 存储
      • MySQL
        • 查询
          • 说出两种搜索引擎
          • 一条select的执行过程
          • mysql的join 外连接 内连接 左连接
          • 表太长了条件太多怎么增加查询速度
          • 查询太慢了
          • SQL注入有了解吗
        • 索引
          • 索引存储结构
          • 聚集索引 非聚集索引
          • 覆盖索引
          • 联合索引的好处
          • 联合索引 最左前缀匹配 原则 abcd四列,对ab做联合索引,各种情况会不会走索引 有没有可能走一个字段不走其他的
          • 索引失效
          • 什么样的适合建索引
          • 建索引一定会快吗
          • 如何知道命中了索引
        • 事务 锁
          • **数据库实现ACID:**
        • 并发事务带来的问题
          • 事务隔离级别
          • 数据库怎么持久化?写一个事务时怎么保证持久化是原子性的
          • 数据库断电,重启的时候能正常恢复从前的状态码?它怎么直到需要恢复呢 用的什么log 为什么需要多个而不是1个log呢,需要写多份才行吗?
          • repeateable下会出现什么问题,不提升级别的情况下,如何避免这些问题? / repeatable怎么避免幻读
          • GAP锁有可能会出现什么问题
          • MVCC
          • mysql锁粒度
          • 如何安全修改一行数据
          • 持久化
          • crash-safe
          • 断电恢复
          • 日志相关
          • mysql怎么进行主从备份
        • 二阶段提交
      • Redis
        • 数据类型及结构
          • ordered_set的底层结构
          • 再哈希
        • 应用相关
          • redis有哪几种持久化的方式 两个同时开启的话,做数据恢复的时候优先走哪个方式
          • redis实现分布式锁
          • Redis怎么做消息队列
          • redis分布式锁 setnx 和redisson有什么区别,后者的优点是啥
    • 语言
      • C++
        • C++和C的区别
        • C++空类大小是多大,加了构造函数析构函数呢
        • C++类型安全吗
          • C++ 四种强制类型转换
        • 左值右值
          • std::move是干啥用的
          • 右值引用是为了解决什么问题
        • 指针
          • 如果指针是万能的,为什么还要出现引用呢
          • 浅拷贝 深拷贝
          • 智能指针是为了解决什么问题
          • 智能指针如何管理内存
          • 智能指针有几种
          • unique ptr 如何实现只保证有一个
          • shared_ptr是怎么实现管理内存的
          • 为什么要有weak_ptr
          • 如何用C++实现引用计数智能指针
          • 如何用C++实现weak_ptr 怎么知道还有没有在引用的
        • 虚函数
          • 虚函数调用过程
          • C++虚函数是怎么实现的
          • C++如何实现多态
          • C++的析构函数为什么要定义为虚函数
          • 为什么有虚基类:
          • 虚函数指针是每个对象都有的吗,虚函数表呢
        • 关键字
          • map unordered_map
          • inline是干嘛的 怎么减小开销
          • vector
          • new 和malloc有什么区别
          • malloc和free是怎么分配内存和释放内存的
          • new delete malloc free 区别 能混用吗
          • main函数执行结束后 当前这个进程是否就结束退出了 退出之前会做什么事请 在执行main函数的第一行代码之前,C++中会做哪些事情
          • extern "C"是干什么用的
          • C++中static的变量会存到哪 static怎么用
          • NULL和Nullptr什么区别 为什么后者可以表示空指针
          • C++中的volatile
        • 新特性
        • 为什么C++性能更高
      • Java
        • JVM
          • gc是怎么判断一个对象可不可回收的/如何进行内存回收
          • gc root对象有哪些
          • 反射
          • static变量有什么特点 什么时候要用static关键字
          • java中double 和float的变量有什么区别 占几个字节
          • java中的final关键字是干吗用的
          • seriable关键字
          • JVM内存
        • Collections
          • hashMap怎么实现
        • SpringBoot
          • spring里两个主要概念 IOC AOP的理解
          • 介绍一下spring boot的依赖注入
        • 并发
          • 多线程有什么好处 线程池有什么好处
          • 同步锁与互斥锁 自旋锁 读写锁
          • 乐观锁 悲观锁
          • volatile 的三个特点
          • volatile与synchronize有什么不同
          • 什么时候用线程池
          • 多线程进程池的那几个参数
          • 怎么实现阻塞队列 有读有写
          • 有了synchronize为啥还要加可重入锁等 可重入锁是解决什么问题
          • concurrentHashMap是线程安全的吗?怎么上锁的?加锁的粒度是多少
          • CAS
          • java中原子类了解吗
      • Python
        • python的垃圾回收机制了解吗
        • Python支持多线程高并发吗
      • Go
        • Go的优点
        • C++ Java Go Python有什么区别
        • 从编译的角度看,这几种语言的差别在哪
    • 操作系统
      • 进程线程协程
        • 进程和线程的区别
        • 通信机制
          • 线程同步的方式:
          • 进程间通信的方式:
        • 协程
          • 协程有什么不足
        • 调度
        • 特殊进程
          • 守护进程 僵尸进程 孤儿进程
      • IO模型
        • IO多路复用是什么
        • 为什么要有IO多路复用
        • IO多路复用的三种实现方式
        • 阻塞IO 非阻塞IO
      • Linux指令
        • top命令里的load average
      • 内存、CPU
        • 字节序大端 小端
          • 判断大端小端
        • 什么是死锁 死锁的条件
        • 如何避免死锁
        • 什么是内存泄漏
        • 内存分区
        • 动态链接静态链接
        • 程序编译到运行的过程都有哪些
        • 为什么要区分内核态和用户态
        • CPU执行一条指令的过程
        • 页面置换算法
    • 网络
      • 层级结构
        • ping是哪个协议
        • HTTP 状态码
        • HTTP长连接段连接
        • HTTP 1.0 1.1 的主要区别 2.0有什么新特点 3.0呢
        • HTTPS的对称和非对称加密各自的优缺点
        • https TLS加密的三次握手过程
        • cookie session
        • DNS 解析:
      • TCP-UDP
        • TCP UDP的区别
        • 握手挥手
          • 可以省略第三次握手吗
          • 可以改成4次握手吗
          • 握手过程中可以携带数据吗
          • SYN泛洪攻击
          • 4次挥手的时候time_wait是干啥的
          • time wait等待的时间是多少
          • 2msl时间是多长
          • time_wait过多
        • TCP如何保证通信可靠性
          • 粘包
          • 怎么判断网络是否出现了拥塞?有了解过其他的拥塞控制算法吗
        • 应用
          • socket
      • 性能指标
    • 分布式
      • Kafka
        • kafka为什么快
        • kafka怎么保证数据不丢失
        • kafka基本架构了解吗》kafka消费者消费失败了会怎么样?有出现消费和生产监控不一样的情况吗
      • CAP
      • 分布式锁
      • RPC
        • thrift
        • 开发一个RPC的话 dubbo spring cloud之类,需要哪些基本的组件
        • 客户端怎么发现服务;用什么做服务发现 怎么做服务发现; zookeeper是怎么是实现的(树桩结构)
      • 负载均衡
        • 怎么增加一个服务的高并发和容灾性?突然大量请求过来了可以怎么处理
    • 数据结构
      • 红黑树
        • 红黑树的5个特点
        • 红黑树VS二叉搜索树
        • 红黑树插入删除
      • 哈希
        • 哈希冲突的解决
        • 内存中的堆与数据结构中的堆是一回事吗
      • 稳定的排序方式
      • arrylist和linkedlist有什么区别,查询时间复杂度
      • 简单介绍一下HashMap,怎么做到O(1)的时间复杂度去查找的;hash和equal 不一样的对象算出来的hash一样 会出现什么情况; 哈希冲突了会怎么样
      • 跳表
        • 为什么redis用跳表而不是红黑树
    • 其他
      • 汉字编码
      • 人在上海 请求北京机房的服务,会经过哪些过程?不能所有请求都打到一台机器上,怎么做负载均衡?
      • android为什么比ios卡
      • django一个请求过来 生命周期如何
      • 从浏览器输入地址后到返回经历的过程
      • git rebase git merge

存储

MySQL

MySQL的问题其实主要涉及两个方面:

  1. 查询相关
    基本的查询语法比如连接排序分组;为了提升查询效率的索引,索引的存储结构(B+树)、索引的分类、索引是否能生效等衍生问题
  2. 事务相关
    为了保证ACID四个属性涉及到的锁、MVCC和各个日志。

查询

说出两种搜索引擎

搜索引擎: innodb mylsam

一条select的执行过程

link
后端开发、C++开发面经分类整理_第2张图片

mysql的join 外连接 内连接 左连接

https://blog.csdn.net/plg17/article/details/78758593

  • 内连接:组合两个表中的记录,返回两个表的交集
    • 左连接:左表的全都有,右表的只有符合的,不足的地方补充null

    • 右连接:左边只有符合的,右边的表全显示

    • mysql当前不支持全外连接

表太长了条件太多怎么增加查询速度
  • 可以试试联合索引
  • like太慢可以试试全文索引 全文索引在大量的数据面前,能比 like + % 快 N 倍,速度不是一个数量级
  • 全文索引有自己的语法格式,使用 match 和 against 关键字
  • 对于字段比较多的表,如果有些字段的使用频率很低,可以将这些字段分离出来形成新表。
  • 将一个大的查询分解为多个小查询是很有必要的,可以对每一个表进行一次单表查询,然后将查询结果在应用程序中进行关联
查询太慢了
  • 一直很慢
    • 是不是没用到索引
  • 偶尔慢
    • 是不是在刷新脏表
SQL注入有了解吗
  • 是网站中存在较多的也较简单的漏洞,主要是程序对用户输入数据的合法性没有判断,导致攻击者可以在应用程序中事先定义好的sql语句中添加额外的sql语句,实现非法操作

  • 简单说就是在用户输入的字符串中加入SQL语句,如果不检查后端就会认为这是正常的SQL进行执行

  • 比如恶意拼接
    避免SQL注入

  • 过滤输入内容,校验字符串 比如正则函数

  • 参数化查询 设计与数据库连接并访问数据时,在需要填入数值的地方用parameter来给值 这样数据库服务器不会将参数的内容视为SQL语句的一部分来处理

  • 好好测试

  • 敏感数据最好加密,不要直接明文保护

索引

索引是关系型数据库中给数据库表中一列或多列的值排序后的存储结构

索引存储结构

InnoDB存储引擎是 B+ 树索引组织的,所以数据即索引,索引即数据
为什么用B+树

  • B+树非叶子节点只存储key值,而B-树存储key值和data值,这样B+树每次读取时可以读取到更多的key值
  • mysql进行区间访问时,由于B+树叶子节点之间用指针相连,只需要遍历所有的叶子节点即可;而B-树则需要中序遍历那样遍历
  • B+树非叶子节点只存储key值,而B-树存储key值和data值,导致B+树的层级更少,查询效率更高
  • B+树所有关键词地址都存在叶子节点上,所以每次查询次数都相同,比B-树稳定

B 树& B+树两者有何异同呢?

  • B 树的所有节点既存放键(key) 也存放 数据(data),而 B+树只有叶子节点存放 key 和 data,其他内节点只存放 key。
  • B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
  • B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找,可能还没有到达叶子节点,检索就结束了。而 B+树的检索效率就很稳定了,任何查找都是从根节点到叶子节点的过程,叶子节点的顺序检索很明显。

为什么不用哈希表:

  • 哈希冲突
  • 不支持顺序和范围查询
聚集索引 非聚集索引

聚集索引和非聚集索引的根本区别是表记录的排列顺序和与索引的排列顺序是否一致

  • 聚集索引:

    • 存放的物理顺序和列中的顺序一样
    • 索引和数据一起放 优点是定位到节点就能找到数据,缺点是数据要有序,维护成本高
    • 聚集索引表记录的排列顺序和索引的排列顺序一致,所以查询效率快,只要找到第一个索引值记录,其余就连续性的记录在物理也一样连续存放
    • 只要索引是相邻的,那么对应的数据一定也是相邻地存放在磁盘上的。
    • 也叫一级/主键索引
    • 如果一个主键被定义了,那么这个主键就是作为聚集索引
    • 如果没有主键被定义,那么该表的第一个唯一非空索引被作为聚集索引
    • 聚集索引在一个表中只能有一个
    • 优点:查询非常快;缺点:依赖有序的数据;更新代价大
  • 非聚集索引:

    • 只放索引,可能需要2次回表
    • 也叫二级索引(唯一 普通 前缀)
    • 非聚集索引的叶子层并不和实际数据页相重叠,而采用叶子层包含一个指向表中的记录在数据页中的指针方式
    • 优点:更新代价小 缺点:可能二次回表;也得是有序数据
  • 聚集索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点,只不过有一个指针指向对应的数据块

  • 非聚集索引的键值在逻辑上也是连续的,但是表中的数据在存储介质上的物理顺序是不一致的,即记录的逻辑顺序和实际存储的物理顺序没有任何联系。索引的记录节点有一个数据指针指向真正的数据存储位置。非聚集索引第一次只能查到记录对应的主键值 , 再使用主键的值通过聚集索引查找到需要的数据

  • 主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚集索引(clustered index)。

    非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。

覆盖索引

索引字段就是要查的数据,不需要回表,查的那个值刚好是索引

联合索引的好处
  • 减少开销:建一个联合索引(col1,col2,col3),实际相当于建了(col1),(col1,col2),(col1,col2,col3)三个索引
  • 更容易索引覆盖
  • 效率高

联合索引:
1、需要加索引的字段,要在where条件中
2、数据量少的字段不需要加索引
3、如果where条件中是OR关系,加索引不起作用
4、符合最左原则
将区分度高的字段放到前面

联合索引 最左前缀匹配 原则 abcd四列,对ab做联合索引,各种情况会不会走索引 有没有可能走一个字段不走其他的

https://zhuanlan.zhihu.com/p/115778804
最左前缀匹配原则:**在MySQL建立联合索引时会遵守最左前缀匹配原则,即最左优先,在检索数据时从联合索引的最左边开始匹配。

值得注意的是,当遇到范围查询(>、<、between、like)就会停止匹配

  • 而你对(a,b,c,d)建立索引,where后条件为

    a = 1 and b = 2 and c > 3 and d = 4
    

    那么,a,b,c三个字段能用到索引,而d就匹配不到。因为遇到了范围查询

MySQL创建联合索引的规则是首先会对联合索引的最左边第一个字段排序,在第一个字段的排序基础上,然后在对第二个字段进行排序.所以b=2这种查询条件没有办法利用索引

MySQL中有查询优化器explain,所以sql语句中字段的顺序不需要和联合索引定义的字段顺序相同,查询优化器会判断纠正这条SQL语句以什么样的顺序执行效率高,最后才能生成真正的执行计划,所以不论以何种顺序都可使用到联合索引

索引失效
  • 索引列上的操作 计算 函数 类型转换
  • 不等于无法用
  • is null is not null可能不能用
  • like匹配不能用
  • 字符串不加单引号 索引失效
什么样的适合建索引
  • 不为Null
  • 频繁查询
  • 经常做条件
  • 频繁要排序、连接

经常更新的最好别用;多建立联合索引而不是单索引;避免冗余;字符串上可以用前缀索引

建索引一定会快吗

索引优缺点:

优点

  • 使用索引可以大大加快 数据的检索速度(大大减少检索的数据量), 这也是创建索引的最主要的原因。
  • 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。

缺点

  • 创建索引和维护索引需要耗费许多时间。当对表中的数据进行增删改的时候,如果数据有索引,那么索引也需要动态的修改,会降低 SQL 执行效率。
  • 索引需要使用物理文件存储,也会耗费一定空间。

大多数情况下,索引查询都是比全表扫描要快的。但是如果数据库的数据量不大,那么使用索引也不一定能够带来很大提升。

表太太大了建索引开销也很大

如何知道命中了索引

explain一条命令 type里可以看到 比如all是遍历全表才找到 index用了索引

possible_keys 指出能用哪个索引 key现实实际用到的索引,没有就是Null

事务 锁

事务是逻辑上的一组操作,要么都执行,要么都不执行

  1. 原子性Atomicity) : 事务是最小的执行单位,不允许分割。事务的原子性确保动作要么全部完成,要么完全不起作用;
  2. 一致性Consistency): 执行事务前后,数据保持一致,例如转账业务中,无论事务是否成功,转账者和收款人的总额应该是不变的;
  3. 隔离性Isolation): 并发访问数据库时,一个用户的事务不被其他事务所干扰,各并发事务之间数据库是独立的;
  4. 持久性Durability): 一个事务被提交之后。它对数据库中数据的改变是持久的,即使数据库发生故障也不应该对其有任何影响。
数据库实现ACID:

MySQL InnoDB 引擎使用 redo log(重做日志) 保证事务的持久性,使用 undo log(回滚日志) 来保证事务的原子性

MySQL InnoDB 引擎通过 锁机制MVCC 等手段来保证事务的隔离性( 默认支持的隔离级别是 REPEATABLE-READ )。

保证了事务的持久性、原子性、隔离性之后,一致性才能得到保障。

并发事务带来的问题

在典型的应用程序中,多个事务并发运行,经常会操作相同的数据来完成各自的任务(多个用户对同一数据进行操作)。并发虽然是必须的,但可能会导致以下的问题。

  • 脏读(Dirty read): 当一个事务正在访问数据并且对数据进行了修改,而这种修改还没有提交到数据库中,这时另外一个事务也访问了这个数据,然后使用了这个数据。因为这个数据是还没有提交的数据,那么另外一个事务读到的这个数据是“脏数据”,依据“脏数据”所做的操作可能是不正确的。
  • 丢失修改(Lost to modify): 指在一个事务读取一个数据时,另外一个事务也访问了该数据,那么在第一个事务中修改了这个数据后,第二个事务也修改了这个数据。这样第一个事务内的修改结果就被丢失,因此称为丢失修改。 例如:事务 1 读取某表中的数据 A=20,事务 2 也读取 A=20,事务 1 修改 A=A-1,事务 2 也修改 A=A-1,最终结果 A=19,事务 1 的修改被丢失。
  • 不可重复读(Unrepeatable read): 指在一个事务内多次读同一数据。在这个事务还没有结束时,另一个事务也访问该数据。那么,在第一个事务中的两次读数据之间,由于第二个事务的修改导致第一个事务两次读取的数据可能不太一样。这就发生了在一个事务内两次读到的数据是不一样的情况,因此称为不可重复读。
  • 幻读(Phantom read): 幻读与不可重复读类似。它发生在一个事务(T1)读取了几行数据,接着另一个并发事务(T2)插入了一些数据时。在随后的查询中,第一个事务(T1)就会发现多了一些原本不存在的记录,就好像发生了幻觉一样,所以称为幻读。
事务隔离级别
  • READ-UNCOMMITTED(读取未提交): 最低的隔离级别,允许读取尚未提交的数据变更,可能会导致脏读、幻读或不可重复读
  • READ-COMMITTED(读取已提交): 允许读取并发事务已经提交的数据,可以阻止脏读,但是幻读或不可重复读仍有可能发生
  • REPEATABLE-READ(可重复读): 对同一字段的多次读取结果都是一致的,除非数据是被本身事务自己所修改,可以阻止脏读和不可重复读,但幻读仍有可能发生
  • SERIALIZABLE(可串行化): 最高的隔离级别,完全服从 ACID 的隔离级别。所有的事务依次逐个执行,这样事务之间就完全不可能产生干扰,也就是说,该级别可以防止脏读、不可重复读以及幻读

MySQL InnoDB 存储引擎的默认支持的隔离级别是 REPEATABLE-READ(可重读)

数据库怎么持久化?写一个事务时怎么保证持久化是原子性的

为了实现事务的原子性和持久性,mysql引入了undoredo日志.undo日志记录的是修改前的值.由于undo日志会被清理掉,不能保证事务的持久性,因此才需要引入redo日志来保证事务的持久性。redo日志记录的是修改后最新的数据和冗余的undo日志.redo日志必须先于数据写入磁盘(即步骤8和步骤9的顺序不能改变)。因为如果不这样,在数据提交之后再写redo日志,一旦redo日志的写入过程出现异常,将无法保证持久性。未提交的事务回滚了的事务也会计入redo日志。

数据库断电,重启的时候能正常恢复从前的状态码?它怎么直到需要恢复呢 用的什么log 为什么需要多个而不是1个log呢,需要写多份才行吗?
  • 恢复时,先根据redo重做所有事务(包括未提交和回滚了的)

    • 再根据undo回滚未提交的事务。

    • 当数据修改时,InnoDB除了修改Buffer Pool中的数据,还会在redo log 记录这次操作,并保证redo log早于对应的页面落盘(一般在事务提交的时候),也就是常说的WAL。若MySQL突然宕机了且还没有把数据刷回磁盘,重启后,MySQL会通过已经写入磁盘的redo log来恢复没有被刷新到磁盘的数据页。
      在任何情况下,InnoDB启动时都会尝试执行recovery操作。在恢复过程中,需要redo log参与,而如果还开启了binlog,那就还需要binlog、undo log的参与。因为有可能数据已经写入binlog了,但是redo log还没有刷盘的时候数据库就奔溃了(事务是InnoDB引擎的特性,修改了数据不一定提交了,而binlog是MySQL服务层的特性,修改数据就会记录了),这时候就需要redo log,binlog和undo log三者的参与来判断是否有还没提交的事务,未提交的事务进行回滚或者提交操作。
      ————————————————
      版权声明:本文为CSDN博主「X先生说」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
      原文链接:https://blog.csdn.net/u013314679/article/details/109389649

repeateable下会出现什么问题,不提升级别的情况下,如何避免这些问题? / repeatable怎么避免幻读

幻读
Gap锁 MVCC

  • 快照读时 通过MVCC 事务会读取版本号<=当前版本号的数据,这时就算另一个事务插入一个数据,并立马提交,新插入这条数据的版本号会比读取事务的版本号高,因此读取事务读的数据还是不会变 (一般简单的select是快照读
  • 当前读时,通过next-key lock 就是行锁+GAP间隙锁 (一般插入更新删除用当前读)
GAP锁有可能会出现什么问题

死锁

  • GAP锁锁住的位置,也不是记录本身,而是两条记录之间的GAP。 在可能发生幻读的地方加上GAP
MVCC

多版本并发控制。

普通select触发 多版本并发控制,主要为了提高并发 不用锁来实现

快照读

  • 当前读 读的都是当前最新的版本 会堆当前读取的数据加锁,是悲观锁的一种操作

  • 快照读 基于MVCC 读的不一定是当前版本

  • MVCCC是“维持一个数据的多个版本,使读写操作没有冲突”的一个抽象概念,这个概念的具体实现就是快照读

  • mvcc为解决读写冲突的无锁并发控制,为事务分配单向增长的时间戳,为每个数据修改保存一个版本,版本与事务时间戳相关联。读操作只读取该事务开始前的数据库快照 解决脏读 幻读 不可重复读等事务隔离问题 可以结合悲观锁或者乐观锁

  • 主要实现原理依靠版本链 undo日志 read view等

mysql锁粒度
  • 为啥要用锁:保持数据一致性
  • InnoDB存储引擎的两种锁:表级锁和行级锁,默认行级锁
  • 表级锁并发低,适合更新少的;行级锁并发高,但开销大会出现死锁

粒度:

  • 表锁
  • 行锁
  • 页锁

行锁:(建立在索引上,没有则退化为表锁)

  • Gap 锁
  • record
  • next_key

RECORDLOCK就是锁住某一行记录;而GAPLOCK会锁住某一段范围中的记录;NEXT-KEYLOCK则是前两者加起来的效果。

  • 共享 也就是读锁,多个事务都能读,不能写
  • 排他 写锁 只能有一个事务有锁
  • 意向 InnoDB自己加的,不需要用户干预,不会与行级的读写锁互斥,而是兼容的(表)

只有通过索引查询数据,才会用到行级锁,其他是表级锁

增删查改时匹配的条件没有索引时,会用到表级锁。

如何安全修改一行数据
  • 悲观锁: 本质是当前只有一个线程执行操作,排斥外部请求的修改。遇到加锁的状态,就必须等待。结束了唤醒其他线程进行处理
  • 乐观锁:一般是通过版本号
  • FIFO先进队列:请求按顺序放到队列里
持久化

数据库怎么持久化:

对于持久性(durability)是这样定义的:事务一旦提交,则其所有的修改将会保存到数据库当做。即使此时系统崩溃,修改的数据也不会丢失

我们知道数据是存储在磁盘当中的,如果每一次数据修改操作都要写进磁盘,然后磁盘找到对应的那一条记录,然后再去更新。整个过程看下来IO成本、查询成本都非常高。

为了解决这个问题,MySQL采用了一种叫WAL(Write Ahead Logging)提前写日志的技术。意思就是说,发生了数据修改操作先写日志记录下来,等不忙的时候再持久化到磁盘。这里提到的日志就是redo log。

为了实现事务的原子性和持久性,mysql引入了undoredo日志.undo日志记录的是修改前的值.由于undo日志会被清理掉,不能保证事务的持久性,因此才需要引入redo日志来保证事务的持久性。redo日志记录的是修改后最新的数据和冗余的undo日志.redo日志必须先于数据写入磁盘(即步骤8和步骤9的顺序不能改变)。因为如果不这样,在数据提交之后再写redo日志,一旦redo日志的写入过程出现异常,将无法保证持久性。未提交的事务回滚了的事务也会计入redo日志。

crash-safe
  • redo log 物理日志 记录数据库物理页的修改
    • 每条 redo 记录由“表空间号+数据页号+偏移量+修改数据长度+具体修改的数据”组成
  • undo log 逻辑日志 用于回滚
断电恢复
  • 恢复时,先根据redo重做所有事务(包括未提交和回滚了的)
  • 再根据undo回滚未提交的事务

当数据修改时,InnoDB除了修改Buffer Pool中的数据,还会在redo log 记录这次操作,并保证redo log早于对应的页面落盘(一般在事务提交的时候),也就是常说的WAL。若MySQL突然宕机了且还没有把数据刷回磁盘,重启后,MySQL会通过已经写入磁盘的redo log来恢复没有被刷新到磁盘的数据页。
在任何情况下,InnoDB启动时都会尝试执行recovery操作。在恢复过程中,需要redo log参与,而如果还开启了binlog,那就还需要binlog、undo log的参与。因为有可能数据已经写入binlog了,但是redo log还没有刷盘的时候数据库就奔溃了(事务是InnoDB引擎的特性,修改了数据不一定提交了,而binlog是MySQL服务层的特性,修改数据就会记录了),这时候就需要redo log,binlog和undo log三者的参与来判断是否有还没提交的事务,未提交的事务进行回滚或者提交操作。

日志相关

MySQL 日志 主要包括错误日志、查询日志、慢查询日志、事务日志、二进制日志几大类。其中,比较重要的还要属二进制日志 binlog(归档日志)和事务日志 redo log(重做日志)和 undo log(回滚日志)

https://snailclimb.gitee.io/javaguide/#/docs/database/mysql/MySQL%E4%B8%89%E5%A4%A7%E6%97%A5%E5%BF%97

binlog的作用只要是主从复制 和数据的增量恢复

mysql怎么进行主从备份
  • binlog

  • 主服务器在做数据库操作的时候将所有的操作通过日志记录在binlog里面,有专门的文件存放。如localhost-bin.000003,这种,从服务器 和主服务配置好关系后,通过I/O线程获取到这个binlog文件然后写入到从服务器的relaylog(中继日志)中,然后从服务器执行从服务器中的sql语句进行数据库的同步。

二阶段提交

  • redo是两阶段提交,来保证redo和Binlog的数据一致性 prepre commit

  • 先落日志,然后再写磁盘,也就是write-ahead logging

    后端开发、C++开发面经分类整理_第3张图片

    两阶段提交的第一阶段 (prepare阶段):写rodo-log 并将其标记为prepare状态。

    两阶段提交的第二阶段(commit阶段):写bin-log 并将其标记为commit状态。

    如果你根本不需要binlog带给你的特性(比如数据备份恢复、搭建MySQL主从集群),那你根本就用不着让MySQL写binlog,也用不着什么两阶段提交。

    只用一个redolog就够了。无论你的数据库如何crash,redolog中记录的内容总能让你MySQL内存中的数据恢复成crash之前的状态。

    两阶段提交的主要用意是:为了保证redolog和binlog数据的安全一致性。只有在这两个日志文件逻辑上高度一致了。你才能放心地使用redolog帮你将数据库中的状态恢复成crash之前的状态,使用binlog实现数据备份、恢复、以及主从复制。而两阶段提交的机制可以保证这两个日志文件的逻辑是高度一致的。没有错误、没有冲突。

    其实总的来说,不论mysql什么时刻crash,最终是commit还是rollback完全取决于MySQL能不能判断出binlog和redolog在逻辑上是否达成了一致。只要逻辑上达成了一致就可以commit,否则只能rollback。

    当MySQL写完redolog并将它标记为prepare状态时,并且会在redolog中记录一个XID,它全局唯一的标识着这个事务。而当你设置sync_binlog=1时,做完了上面第一阶段写redolog后,mysql就会对应binlog并且会直接将其刷新到磁盘中。

    下图就是磁盘上的row格式的binlog记录。binlog结束的位置上也有一个XID。

    只要这个XID和redolog中记录的XID是一致的,MySQL就会认为binlog和redolog逻辑上一致。就上面的场景来说就会commit,而如果仅仅是rodolog中记录了XID,binlog中没有,MySQL就会RollBack

Redis

数据类型及结构

redis有哪几种数据类型

  • string key:value 可以是json;计数功能
  • set 无序 唯一 类似hashset,主要用于一些去重的场景
  • list 比较接近linkedList, 可以用于做秒杀 在秒杀前将本场秒杀的商品放到list中,因为list的pop操作是原子性的,所以即使有多个用户同时请求,也是依次pop,list空了pop抛出异常就代表商品卖完了
  • hash 相当于hashMap 数组+链表,常用于保存结构体
  • ordered_set 可以给每个value一个score zset用跳表来实现 经常用于各种热门排序

字符串(是二进制安全的,不受任何终止字符的影响 没用C的字符串,而是自己构建的简单动态字符串SDS 一个结构体 有长度 有char buf[] 有free的大小 可以常量获得字符串长度 ) 哈希(通过自建的字典来实现 key是唯一的,通过key来进行查找修改) list(双向链表) set ordered set bitmaps

ordered_set的底层结构

跳表

再哈希

当哈希表保存的键值对太多或太少时,就要通过rehash(重新散列)来对哈希表进行响应的扩展或者收缩 扩展的话,会基于原来的哈希表创建一个大一倍的,重新利用上面的哈希算法计算索引值,讲键值对放到新的哈希表上,所有键值对都迁完后,释放原来哈希表的内存空间 用拉链法解决哈希冲突

  • 渐进式rehash 扩容收缩可能不是一次集中完成的,如果键值对非常非常多,可能就要渐进式rehash,渐进期间字典的增删查改可能要在两个哈希表上,但是增加是在新表上

应用相关

redis有哪几种持久化的方式 两个同时开启的话,做数据恢复的时候优先走哪个方式
  • RDB 快照 存储到磁盘上 对于 RDB 方式,redis 会单独创建(fork)一个子进程来进行持久化,而主进程是不会进行任何 IO 操作的,这样就确保了 redis 极高的性能 如果需要大规模恢复,对完整性要求不高性能要求高的话,可以rdb
  • AOF 修改过redis的指令存下来

其实 RDB 和 AOF 两种方式也可以同时使用,在这种情况下,如果 redis 重启的话,则会优先采用 AOF 方式来进行数据恢复,这是因为 AOF 方式的数据恢复完整度更高。

redis实现分布式锁

link

Redis怎么做消息队列
  • Redis实现轻量级的消息队列与消息中间件相比,没有高级特性也没有ACK保证,无法做到数据不重不漏,如果业务简单而且对消息的可靠性不是那么严格可以尝试使用。
  • 用redis的List结构 ,相当于队列 有push和pop操作
  • 提供生产消费模式(push pop)和发布订阅模式(pub sub,可以生产者和消费之一对多)
redis分布式锁 setnx 和redisson有什么区别,后者的优点是啥

语言

  • 面向对象与面向过程有什么区别:

面向过程以过程为中心,主要是分解步骤,然后一步步调用函数

面向对象会把客观世界中的事务抽象为对象,具有属性和方法,以对象的角度来描述和分析问题,使得计算机系统能与真实世界的物体相统一
- 面向过程:性能高 但不好维护复用可扩展
- 面向对象:易维护易扩展易复用,不过性能比面向过程低

  • 继承和多态是什么

继承:对象的一个新类可以从现有的类中派生出来,可以获得基类的成员变量和方法,增加了可重用。可以使用基类的所有功能,还可以在这个基础上扩展

多态:简单说就是父类指针可以指向子类,通过父类指针能调用到子类的成员函数

C++

C++和C的区别

面向过程面向对象
new malloc

C++空类大小是多大,加了构造函数析构函数呢

空类 sizeof大小位1
有虚函数的,就会有一个虚函数指针,32位上4字节,64位上8字节;单纯普通函数不占大小,构造函数 析构函数等成员函数均不影响类的大小

  • 有数据成员时 会对齐大小 (提高读取效率)
  • 静态成员不占类的大小
  • 普通类的继承,类的大小为本身数据成员大小+基类数据成员大小

默认构造函数 默认拷贝构造函数 默认析构函数 默认复制运算符 取址运算符 取址运算符const

C++类型安全吗

*C/C++不是类型安全的语言*

  • 类型安全指同一段内存再不同的地方,会被强制要求使用相同的办法来解释 类型安全意味着编译器将在编译时验证类型 如果尝试将错误的类型分配给变量,则抛出错误
  • Java是类型安全的 除非强制类型转换
  • C语言不是,同一段内存可以用不同的数据类型来解释,1用int就是1 用Bool就是true
C++ 四种强制类型转换
  • static_cast
    • 最常用,能做基础类型之间的转换;子类转成父类也是安全的
  • dynamic_cast
    • 可以动态的较为安全的把指向基类的指针指向子类,会做运行时安全检查,转化失败会返回null或者抛出异常。且基类中得有虚函数,否则编译不过
    • 不能用于基本类型的转化
  • reinterpret_cast
    • 可以把指针转换成整数,也可以把整数转化为指针
    • 可以改变指针或引用的类型
  • const_cast
    • 修改类型的const或volatile属性,一般作用于指针

左值右值

等号左边,可以取地址、有名字的是左值;反之,不能取地址,没有名字的是右值。 int a = b+c &a是可以的,不能&(b+c)

  • C++ 11中,右值又分为纯右值和将亡值,纯右值就是上面的右值,将亡值是跟右值引用相关的表达式,通常是将要被移动的。比如返回右值引用 T&&的函数返回值、std::move 的返回值,或者转换为 T&&的类型转 换函数的返回值。将亡值可以理解为通过“盗取”其他变量内存空间的方式获取到的值。 在确保其他变量不再被使用、或即将被销毁时,通过“盗取”的方式可以避免内存空间 的释放和分配,能够延长变量值的生命期
  • 左值引用就是正常的引用一个变量;右值引用是对右值做引用,因为右值通常也没名字,只能通过右值引用来。左值引用是具名变量值的别名,而右值引用则是不具名(匿名) 变量的别名。左值引用通常也不能绑定到右值,

  • 要绑定左值到右值引用,需要std::move将左值转化为右值
    blog

std::move是干啥用的
  • 左值转化为右值,返回传入参数的右值引。
  • 将对象的状态或者所有权从一个对象转移到另一个对象,只是转移,没有内存的搬迁或者内存拷贝,性能好
右值引用是为了解决什么问题
  • 移动引用和完美转发

  • 移动语义:对象的资源所有权转移,不用深拷贝一个,再销毁原来的

  • 完美转发:通过一个函数将参数继续转交给另一个函数处理,保持参数原有特征。

指针

如果指针是万能的,为什么还要出现引用呢

指针太灵活,容易出问题,也存在安全性问题,内存管理问题

java中用引用,可以看作是对指针的封装

浅拷贝 深拷贝

基本数据类型是没什么差别的。

**浅拷贝只复制指向某个对象的指针,而不复制对象本身,新旧对象还是共享同一块内存。但深拷贝会另外创造一个一模一样的对象,新对象跟原对象不共享内存,修改新对象不会改到原对象。

智能指针是为了解决什么问题

如果用完忘记delete可能会出现内存泄漏问题。智能指针的作用是进行内存管理,利用析构函数将内存释放

智能指针如何管理内存

智能指针,可以管理动态内存分配。交给类来管理,通过析构函数来释放,因为类变量是局部作用域,离开后会自动调用析构函数,即使出现异常析构函数也会执行,因为类变量是保存在栈上的

智能指针有几种

有三种智能指针,unique_ptr, shared_ptr和weak_ptr

  • unique_ptr:仅有一个实例拥有内存所有权

    • std::unique_ptr<Fraction> f1{ new Fraction{ 3, 5 } };
          cout << *f1 << endl; // output: 3/5
                              
          std::unique_ptr<Fraction> f2; // 初始化为nullptr
                              
          // f2 = f1 // 非法,不允许左值赋值
          f2 = std::move(f1);  // 此时f1转移到f2,f1变为nullptr
      
  • shared_ptr:可以有多个,指向同一个内存,引用计数,每用一次,内部的引用计数+1,析构一次-1,减到0时删除

  • weak_ptr:最大作用是协助shared_ptr工作,像旁观者一样观测资源使用情况,但它本身不会让引用计数增加。可以用lock()来获得一个可用的shared_ptr对象。弱引用能检测到所管理的对象是否已经被释放, 从而避免访问非法内存

    • 共享指针可能出现死锁没有调用析构函数出现内存泄露的问题。std::weak_ptr可以包含由std::shared_ptr所管理的内存的引用。但是它仅仅是旁观者,并不是所有者。那就是std::weak_ptr不拥有这块内存,当然不会计数,也不会阻止std::shared_ptr释放其内存。但是它可以通过lock()方法返回一个std::shared_ptr对象,从而访问这块内存。这样我们可以用std::weak_ptr来解决上面的“循环引用”问题
unique ptr 如何实现只保证有一个
  • 它是一个局部变量,所以退出函数时唯一指针会自动销毁,无论退出是正常的还是由于异常导致的

  • 当对象的唯一指针unique_ptr被销毁时,对象将自动销毁

  • C++11 标准中的 unique_ptr 模板类没有提供拷贝构造函数,只提供了移动构造函数

shared_ptr是怎么实现管理内存的

http://c.biancheng.net/view/7898.html

  • 引用计数
  • 拷贝一个shared_ptr引用计数+1, 引用计数为0 的时候,对象被析构
为什么要有weak_ptr

blog1
blog2
避免出现循环引用
循环引用会导致资源没法正常释放。当pa,pb构造时,他们的引用计数为1,接下来由于循环引用,导致两者的引用计数为2,离开作用域后,引用计数都为1,因此不释放资源。这就是循环引用导致的后果。

  • 可以把其中一个改成weak_ptr 这样不增加引用,就能解决循环依赖的问题了

  • shared_ptr a; shared_ptr b; a中有shared_ptr b; b中有weak_ptr指向a, 这样a b就算互相指着也不会循环依赖了

如何用C++实现引用计数智能指针

原文链接

  • 简单来说,智能指针是一个类,它对普通指针进行封装,使智能指针类对象具有普通指针类型一样的操作。具体而言,复制对象时,副本和原对象都指向同一存储区域,如果通过一个副本改变其所指的值,则通过另一对象访问的值也会改变.所不同的是,智能指针能够对内存进行自动管理,避免出现悬垂指针等情况。

  • shared_ptr 采取一种 “自动的引用计数管理” 的方法来控制一个 “对象实例” 的安全释放,当然说是 “自动引用计数管理” 但主要是依靠来自 “C/C++” 编译器本身的特性完成的,我们知道C/C++对象若在 “函数栈上分配”的话,到该函数的 “}” 的位置,编译器会在build 时由编译器生成调用 “栈上对象” 的析构函数,而 shared_ptr 自动管理 “引用计数” 便是依靠的这种特性

如何手动实现一个shared_ptr 引用计数存到哪里

  • 指向相同资源的所有 shared_ptr 共享“引用计数管理区域”,并采用原子操作保证该区域中的引用计数值被互斥地访问。“引用计数管理区域”是指通过 new 创建的 sp_counted_impl_p 或 sp_counted_impl_pd 对象,在创建成功后立即由其基类指针指向它,而该基类指针被 shared_ptr 间接持有。
    ————————————————
    版权声明:本文为CSDN博主「学无止境丶」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/qq_29108585/article/details/78027867
    shared_ptr在其内部,给每个资源都维护了着一份计数,用来记录该份资源被几个对象共享
    智能指针对象中引用计数是多个智能指针对象共享的,两个线程中智能指针的引用计数同时++或–,这个操作不是原子的,引用计数原来是1,++了两次,可能还是2.这样引用计数就错乱了。会导致资源未释放或者程序崩溃的问题。所以智能指针中引用计数++、–是需要加锁的,也就是说引用计数的操作是线程安全的

    • 当创建类的新对象时,初始化指针,并将引用计数设置为1
    • 当对象作为另一个对象的副本时,复制构造函数复制副本指针,并增加与指针相应的引用计数(加1)
    • 使用赋值操作符对一个对象进行赋值时,处理复杂一点:先使左操作数的指针的引用计数减1(为何减1:因为指针已经指向别的地方),如果减1后引用计数为0,则释放指针所指对象内存。然后增加右操作数所指对象的引用计数(为何增加:因为此时做操作数指向对象即右操作数指向对象)。
    • 析构函数:调用析构函数时,析构函数先使引用计数减1,如果减至0则delete对象
  • 还要在类里重载一些指针运算符

如何用C++实现weak_ptr 怎么知道还有没有在引用的

观察者模式

虚函数

虚函数调用过程
C++虚函数是怎么实现的

虚函数的作用主要是实现多态

每个有虚函数的类都有虚函数表 指针指向虚函数表 虚函数表中有实际的函数的地址(函数指针) 一个类一个虚函数表 继承了的类有自己的虚函数表

根据指针找到自己的虚函数表,根据虚函数表中函数的地址来调用实际的函数

C++如何实现多态
  • 静态多态:函数重载
  • 动态多态:虚函数
C++的析构函数为什么要定义为虚函数

当基类指针指向派生类的时候,若基类析构函数不声明为虚函数,在析构时,只会调用基类而不会调用派生类的析构函数,从而导致内存泄露。

为什么有虚基类:

方块派生的问题, BC都继承A, D继承BC,那调用func的时候到底调用谁。

一种方法是明显的指明,B::func();

另一种方法就是虚基类

方法1中,调用D,会先调用A, 然后B; 然后A,然后C,最后D

方法2中,B:virtual A; C:virtual A D:public B,C,相当于直到了A是B C 共有得,顺序就变成了: A-》B-> C

按照最后一个派生类调用的构造函数为准,也就是如果D自己没改得话,那就输出C中得改动

虚函数指针是每个对象都有的吗,虚函数表呢

每个类中都有一个虚表(一维数组)。每个对象都有一个指向虚表的指针(对象地址的前四个字节就是指向虚表的指针)。虚表存的是虚函数地址。

虚函数表存放在常量中

虚函数表是针对类的,一个类的所有对象的虚函数表都一样

每个对象内部都保存一个指向该类虚函数表的指针vptr,每个对象的vptr的存放地址都不一样,但是都指向同一虚函数表
为什么不把虚函数指针放到类里

- > 因为Base *可能指向Derived,对象里得记录对象类型,否则通过Base *调用虚函数不知道该调用谁。
  >
  > 在“更加面向对象”的语言里,这个指针通常是一个指向“类对象”的普通指针。C++里类不是对象,所以vptr直接指向vtbl提高效率。

关键字

map unordered_map

unordered_map底层实现:
map的实现原理就是红黑树 每个节点到叶子节点最大树高不超过1 是平衡二叉树。查找的时间复杂度是O(lgn),但是插入和删除要维持红黑树的自平衡,所以效率较低。但是有序
>
> unordered_map 底层使用hashtable+buket的实现原理,hashtable可以看作是一个数组 或者vector之类的连续内存存储结构(可以通过下标来快速定位时间复杂度为O(1))处理hash冲突的方法就是在相同hash值的元素位置下面挂buket(桶),

inline是干嘛的 怎么减小开销

内联函数

  • 做了函数展开,所以减少了压栈出栈的时间

  • 内联函数的原理是,在编译期间,对调用内联函数的地方的代码替换成函数 代码。内联函数对于程序中需要频繁使用和调用的小函数非常有用。

    相当于不用执行进入函数的步骤,直接执行函数体

  • //虚函数是不能inline的,因为编译期间还不能确定

  • inline相对宏的优点

    • 会进行类型的检查
  • 字节序 大小端

#define 定义的常数,没有类型,只在预处理阶段起作用,没有类型检查

  • 宏提供了一种机制,能够使你在编译期替换代码中的符号或者语句。当你的代码中存在大量相似的、重复的代码时,使用宏可以极大的减少代码量,便于书写。
  • 使用#define定义
vector
  • vector的底层实现

连续内存,可以说是数组的形式。有三个迭代器指针,分别指向起始字节、最后一个元素的末尾字节 和 整个vector占用内存空间的末尾字节。

扩容时完全弃用这一块,申请更大的,然后按顺序把旧的迁到新内存,再释放旧的内存。

  • Vector的迭代器失效的情况
  • for 循环用erase删除的时候迭代器会失效,需要erase之后递增iterator,因为传给erase的是iter的一个副本,iter++才是下一个有效的迭代器。

迭代器失效: 1)扩容时,会释放掉这部分,再申请个新的,原来的iter若不更新就会失效(当然底层是会更新的) 2)insert delete时可能出现偏差,比如it_begin后插入一个,虽然it_begin不变,it_end原来指的那个可能变成倒数第二个

new 和malloc有什么区别
  • new delete是C++关键字,malloc free是库函数
  • 使用new操作符申请内存分配时无需指定内存大小,编译器会根据类型计算;malloc需要显示指出
  • new成功时返回对象类型的指针,类型与对象匹配,所以New是渡河类型安全的;malloc返回的是void* ,一般需要强制类型转化
  • new内存分配失败抛出异常,malloc失败返回NULL;
  • new会申请内存,然后调用类型的构造函数,初始化成员变量,最后返回指定类型的指针;delete会调用析构函数;而malloc free是库函数,只能动态的申请和释放内存
malloc和free是怎么分配内存和释放内存的

释放后标志位变化,其他程序就可以来分配这块空间了,此时原来的指针变成了无效指针,得置为空

new delete malloc free 区别 能混用吗

对于基本类型而言,没有区别。根据需要new和malloc可以混用,new[]和malloc可以混用,delete、delete[]和free可以混用。
对于构造函数没有作用的类,new和malloc可以混用。
对于构造函数有作用的类,如果想混用,需要显式调用构造函数的逻辑实现。
对于没有显式定义析构函数的类,delete、delete[]和free可以混用。
对于显式定义析构函数的类,delete[]和new[]必须配套使用,delete和free如果想混用,free需要显式调用析构函数。
————————————————
版权声明:本文为CSDN博主「木凡辰」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_44844115/article/details/99433233

main函数执行结束后 当前这个进程是否就结束退出了 退出之前会做什么事请 在执行main函数的第一行代码之前,C++中会做哪些事情

在执行main函数的前后 有哪些初始化 最后要做什么事请

  • main函数执行之前: ELF的.init段

    • 全局对象的构造函数,对象的空间分配和赋初值
    • 全局变量、静态变量初始化
  • main函数执行之后:

    • 释放资源 全局对象的析构函数
  • 一个典型程序的大致运行步骤:

    • 操作系统创建进程后,把控制权交到程序入口
    • 入口函数对运行库和程序运行环境进行初始化,包括堆 IO 线程 全局变量构造等
    • 完成初始化后,调用Main函数
    • main函数执行完毕后,返回到入口函数,进行全局变量析构、关闭IO等
extern "C"是干什么用的
  • 在 C++中调用 C 库函数,就需要在 C++程序中用 extern “C”声明要引用的 函数。

  • extern的用法:

    • 修饰变量声明
      • 比如A文件中要引用B中的变量v,可以在A中extern int v
    • 修饰函数声明
      • 类似上面,A中用B的函数func,在A中extern这个函数
    • 用于C或C++的引用规范
      • 比如在 C++中调用 C 库函数,就需要在 C++程序中用 extern “C”声明要引用的 函数。这是给链接器用的,告诉链接器在链接的时候用 C 函数规范来链接。主要原 因是 C++和 C 程序编译完成后在目标代码中命名规则不同
    C++中static的变量会存到哪 static怎么用
  • 控制变量的存储方式和可见性:全局静态变量只能在本文件中可见,普通全局变量在整个项目中可见;在类中修饰的成员变量和函数可以直接通过类名来访问到,所有对象共享

  • 静态变量放在全局存储区,即使是静态局部变量也是。程序运行时初始化,程序结束才销毁

  • 全局存储区分为DATA段和BSS段,DATA段放初始化的,BSS段放未初始化的,自动标0

  • (1)在修饰变量的时候,static 修饰的静态局部变量只执行初始化一次,而且延长了局部变量的生命周期,直到程序运行结束以后才释放。
  • (2)static 修饰全局变量的时候,这个全局变量只能在本文件中访问,不能在其它文件中访问,即便是 extern 外部声明也不可以。
  • (3)static 修饰一个函数,则这个函数的只能在本文件中调用,不能被其他文件调用。static 修饰的变量存放在全局数据区的静态变量区,包括全局静态变量和局部静态变量,都在全局数据区分配内存。初始化的时候自动初始化为 0。
  • (4)不想被释放的时候,可以使用static修饰。比如修饰函数中存放在栈空间的数组。如果不想让这个数组在函数调用结束释放可以使用 static 修饰。
  • (5)考虑到数据安全性(当程序想要使用全局变量的时候应该先考虑使用 static)。
    img
NULL和Nullptr什么区别 为什么后者可以表示空指针
  • nullptr是C++11版本中新加入的,它的出现是为了解决NULL表示空指针在C++中具有二义性的问题

  • 在C语言中,NULL通常被定义为:#define NULL ((void *)0), 但是C++是强类型语言,void*不能隐式转换成其他类型的指针,所以在C++中NULL实际是0

  • 但是用NULL表示0,在函数重载的时候会出问题 也就是NULL代替空指针void*在C++中有二义性问题

    • void func(void* i)
      {
      cout << “func1” << endl;
      }

      void func(int i)
      {
      cout << “func2” << endl;
      }

      void main(int argc,char* argv[])
      {
      func(NULL); —> func2
      func(nullptr); ----->func1
      getchar();

      }

  • 为解决这个问题,C++11中引入nullptr

C++中的volatile

volatile声明的变量表示可以被一些编译器未知的因素更改,编译时对此处不做优化处理,每次用到都要从内存中去读取变量的值

比如:

  • 中断程序中修改的,供其他程序查看的变量
  • 多任务下,各任务共享的标志

新特性

浅谈C++11新特性

为什么C++性能更高

编译型语言

Java

JVM

gc是怎么判断一个对象可不可回收的/如何进行内存回收

引用计数和可达性分析

  • 引用计数:给对象维护一个引用计数器,有地方引用时就计数器+1,引用失效-1,当为0 的时候就可以回收了 (不过不能解决循环引用问题)
  • 可达性分析:从 GC Root对象开始,向下搜索,当一个对象到GC root没有引用链,说明不可用
gc root对象有哪些

栈里引用的对象;方法区内类的静态属性引用的对象;方法去常量引用的对象 本地方法栈中JNI(即一般说的Native方法)引用的对象

反射

反射是java提供的一个重要功能,可以在运行时检查类、接口、方法和变量等信息,无需知道类的名字,方法名等。还可以在运行时实例化新对象,调用方法以及设置和获取变量值。

反射,在运行时,获取到与类型紧密相关的TypeInfo对象,其中保存了类型的丰富信息,包括类型名称、字段信息、成员函数信息、接口信息等众多重要信息,某种意义上讲,反射可视为富虚函数表指针

例子:大家如果接触过spring,会发现当你配置各种各样的bean时,是以配置文件的形式配置的,你需要用到哪些bean就配哪些,spring容器就会根据你的需求去动态加载,你的程序就能健壮地运行。

Java的反射机制是在编译并不确定是哪个类被加载了,而是在程序运行的时候才加载、探知、自审。使用在编译期并不知道的类。这样的特点就是反射。
自己理解:反射关键就是编译时不确定,要到运行时才确定,运行时获得对象 变量或方法等

为什么C++中没有反射:
坚持零开销,不为用不到的特性付出任何代价,不管这个代价有多小,也不管是怎样的语言特性,都不会妥协。然后再看看java下的反射操作,编译器会登记类型的一切信息,包括全部字段的详细信息,全部方法的详细信息,全部接口的详细信息等,不管猿猴是否需要,就算是临时辅助类,甚至是虚拟机生成的匿名类,完全压根就看不到其反射信息在代码上的作用,都会一一备案 (也就是说C++觉得开销大,没必要,所以不实现 但是感觉虚函数的这个动态动态有点这个意思了 或者templet

链接

static变量有什么特点 什么时候要用static关键字

方便在没有创建对象的情况下进行调用(方法/变量)。

static 成员变量和方法是属于类的;

static 代码块不需要程序主动调用,在JVM加载类时系统会执行 static 代码块,因此在static 代码块中可以做一些类成员变量的初始化工作。

Java中的static关键字不会影响到变量或者方法的作用域

java中double 和float的变量有什么区别 占几个字节

float 4个字节 double 8个字节

java中的final关键字是干吗用的
  • final修饰的变量为常量 只能赋值一次
  • 修饰引用变量时 引用的地址不变 final声明变量时,要求全部字母大写
  • 修饰的方法不可被重写
  • 修饰的类不能被继承
seriable关键字
JVM内存

堆 栈 PC 方法区 直接内存 1.8后移动到了直接内存中(元空间)

  • 多个线程共享进程的堆和方法区等,但是有自己的虚拟机栈 本地方法栈和PC
  • PC为啥是私有的:通过改变PC来读取指令,实现代码的流程控制;多线程时PC用于记录当前线程执行的位置,切换回来的时候知道运行到哪了 私有主要是为了线程切换后能恢复到正确的执行位置
  • 堆是进程中最大的一块内存,主要用于存放新创建的对象,方法去主要用于村房已经被加载的类信息、常量 静态变量 JIT等

Collections

hashMap怎么实现

hash_num = hash(key) &(length-1) 算出的这个值就是Index,把node(key value)放到对应的index处就行;如果已经有了,可以放个链表

SpringBoot

spring里两个主要概念 IOC AOP的理解
  • https://www.cnblogs.com/xdp-gacl/p/4249939.html

  • **Ioc—Inversion of Control,即“控制反转”,不是什么技术,而是一种设计思想。**在Java开发中,Ioc意味着将你设计好的对象交给容器控制,而不是传统的在你的对象内部直接控制。
    AOP https://blog.csdn.net/qukaiwei/article/details/50367761

  • https://blog.csdn.net/m0_37125796/article/details/86484701

介绍一下spring boot的依赖注入

并发

多线程有什么好处 线程池有什么好处
  • 高并发高可用性
  • 减少创建销毁的开销;提高响应速度;提高线程的客观理性

线程池,本质上是一种对象池,用于管理线程资源。
在任务执行前,需要从线程池中拿出线程来执行。
在任务执行完成之后,需要把线程放回线程池。
通过线程的这种反复利用机制,可以有效地避免直接创建线程所带来的坏处。

好处:

降低资源的消耗。线程本身是一种资源,创建和销毁线程会有CPU开销;创建的线程也会占用一定的内存。

提高任务执行的响应速度。任务执行时,可以不必等到线程创建完之后再执行。

提高线程的可管理性。线程不能无限制地创建,需要进行统一的分配、调优和监控

  • 后端开发、C++开发面经分类整理_第4张图片
同步锁与互斥锁 自旋锁 读写锁

关于“互斥”和“同步”的概念

答案很清楚了,互斥就是线程A访问了一组数据,线程BCD就不能同时访问这些数据,直到A停止访问了
同步就是ABCD这些线程要约定一个执行的协调顺序,比如D要执行,B和C必须都得做完,而B和C要开始,A必须先得做完。
这是两种典型的并发问题。恰当的使用锁,可以解决同步或者互斥的问题。 —博客

  • 互斥锁 同步锁:
    • 互斥锁是保证一次只能有一个线程去访问资源比如Mutex;同步则主要是为了协调多个线程间的合作,按预定的次序去完成,比如信号量
    • 互斥锁:访问共享资源前加锁,访问完成后释放锁;加锁后其他试图获得资源的线程会被阻塞
  • 读写锁:多个读者可以同时读;写者必须互斥(也不能同时读写);写者先于读者 --> 主要是提高了读的并发性,适合读次数比写多的情况
  • 自旋锁:互斥量阻塞后休眠让出CPU,而自旋锁阻塞后不会让出CPU,会一直忙等待直到得到锁。对于锁持有的时间比较短的更合适。
    • 自旋锁:当线程尝试去获取锁但是已经被占用的时候,会循环等待尝试获取锁,不会放出cpu。
    • 如果持有锁的thread短时间内就会放出资源,那等待的线程就不用频繁做用户态和内核态之间的切换,减少开销
    • 适合锁的竞争不激烈,且占用锁时间非常短的代码块来说性能提升很多
      自旋锁指的是,线程在没有获得锁时,不是被直接挂起,而是执行一个空循环(自旋)。默认是循环10次。
自旋锁的目的也就是为了减少线程被挂起的几率,因为线程的挂起和唤醒也都是耗资源的操作自适应自旋锁

自适应自旋锁是对自锁锁的一种优化。当一个线程自旋后成功获得了锁,那么下次自旋的次数就会增加。因为虚拟机认为,既然上次自旋期间成功拿到了锁,那么后面的自旋会有很大几率拿到锁。相反,如果对于某个锁,很少有自旋能够成功获得的,那么后面就会减少自旋次数,甚至省略掉自旋过程,以免浪费处理器资源。
  • 锁消除

    锁消除指的是,在编译期间利用“逃逸分析技术”分析出那些不存在竞争却加了锁的代码的锁失效。这样就减少了锁的请求与释放操作,因为锁的请求与释放都会消耗系统资源。

乐观锁 悲观锁
  • 悲观锁:悲观态度,认为别人会修改数据,所以上来先加锁,其他线程就无法使用。传统关系型数据库中常用,比如行锁,表锁等,java中synchronized reentrantlock都是悲观锁;
    • 适合冲突比较多的情况 写比较多的情况
  • 乐观锁:乐观态度,认为别人不会改数据,所以先不加锁,更新的时候再检查数据有没有被改动过,要是被改了就重新试
    • 适合读多写少冲突少的情况
    • 一般两种实现方式:CAS和版本号
      • 版本号:数据表中额外加一个字段表示版本号,读的时候连版本号一起读,更新的时候检查一下版本号是否发生了变化,没变再更新,然后版本号+1
      • CAS:这个有三个操作数,需要读写的内存值V、进行比较的值A、拟写入的值B,只有V==A的时候,以原子的方式去用B更新V,否则不执行(一般会自旋重试)
    • 乐观锁的缺点:
      • ABA:一开始是A,改成了B,又改回了A,其实改过了,但是CAS会认为没改过
      • 循环等待时间长的话CPU开销大
      • 只能保证1个共享变量的原子操作 --> JDK 1.5后 可以把多个变量放在1个对象里来CAS
volatile 的三个特点
  • 原子性
    • 一个操作或多个操作,要么全部执行,要么都不执行 比如i=9
  • 可见性
    • 多个线程访问同一个变量时,一个线程修改了这个值,其他的线程也能看到; 每次读都是从内存中读进来,每次写完都更新到内存中
  • 有序性
    • 程序执行的顺序按照代码的先后顺序执行,防止出现指令重排比如双重校验锁的单例模式
volatile与synchronize有什么不同
  • volatile本质是在告诉jvm当前变量在寄存器(工作内存)中的值是不确定的,需要从主存中读取; synchronized则是锁定当前变量,只有当前线程可以访问该变量,其他线程被阻塞住。
  • volatile仅能使用在变量级别;synchronized则可以使用在变量、方法、和类级别的
  • volatile仅能实现变量的修改可见性,不能保证原子性;而synchronized则可以保证变量的修改可见性和原子性
  • volatile不会造成线程的阻塞;synchronized可能会造成线程的阻塞。
  • volatile标记的变量不会被编译器优化;synchronized标记的变量可以被编译器优化
什么时候用线程池

降低资源消耗。通过重复利⽤已创建的线程降低线程创建和销毁造成的消耗。 提⾼响应速度。当任务到达时,任务可以不需要的等到线程创建就能⽴即执⾏。 提⾼线程的可管理性。线程是稀缺资源,如果⽆限制的创建,不仅会消耗系统资源,还会降 低系统的稳定性,使⽤线程池可以进⾏统⼀的分配,调优和监控

  • 当线程涉及到频繁的创建于销毁时,适合使用线程池。
多线程进程池的那几个参数
  • corePoolSize : 核⼼线程数线程数定义了最⼩可以同时运⾏的线程数量。
  • maximumPoolSize : 当队列中存放的任务达到队列容量的时候,当前可以同时运⾏的线程数 量变为最⼤线程数。
  • workQueue : 当新任务来的时候会先判断当前运⾏的线程数量是否达到核⼼线程数,如果达 到的话,新任务就会被存放在队列中
  • keepAliveTime :当线程池中的线程数量⼤于 corePoolSize 的时候,如果这时没有新的任务 提交,核⼼线程外的线程不会⽴即销毁,⽽是会等待,直到等待的时间超过了 keepAliveTime 才会被回收销毁
怎么实现阻塞队列 有读有写
  • wait notify
  • countdown lock
  • 可重入锁
有了synchronize为啥还要加可重入锁等 可重入锁是解决什么问题
  • 可重入锁,指的是以线程为单位,当一个线程获取对象锁之后,这个线程可以再次获取本对象上的锁,而其他的线程是不可以的。

    synchronized 和 ReentrantLock 都是可重入锁。

    可重入锁的意义之一在于防止死锁。

    实现原理实现是通过为每个锁关联一个请求计数器和一个占有它的线程。当计数为0时,认为锁是未被占有的;线程请求一个未被占有的锁时,JVM将记录锁的占有者,并且将请求计数器置为1 。

    如果同一个线程再次请求这个锁,计数器将递增;

    每次占用线程退出同步块,计数器值将递减。直到计数器为0,锁被释放。

  • ReentrantLock有锁等待超时;Synchronized没有。

    3.ReentrantLock有中断锁;Synchronized没有。

    4.ReentrantLock有多条件变量锁;Synchronized没有。

  • synchronize问题:如果我们的程序使用synchronized关键字发生了死锁时,synchronized关键是是无法破坏“不可剥夺”这个死锁的条件的。这是因为synchronized申请资源的时候, 如果申请不到, 线程直接进入阻塞状态了, 而线程进入阻塞状态, 啥都干不了, 也释放不了线程已经占有的资源。

  • Lock是一个接口,而synchronized是关键字。
    synchronized会自动释放锁,而Lock必须手动释放锁。
    Lock可以让等待锁的线程响应中断,而synchronized不会,线程会一直等待下去。
    通过Lock可以知道线程有没有拿到锁,而synchronized不能。
    Lock能提高多个线程读操作的效率。
    synchronized能锁住类、方法和代码块,而Lock是块范围内的

  • reentrantlock:

    1.等待可中断,持有锁的线程长期不释放的时候,正在等待的线程可以选择放弃等待,这相当于Synchronized来说可以避免出现死锁的情况。通过lock.lockInterruptibly()来实现这个机制。

        2.公平锁,多个线程等待同一个锁时,必须按照申请锁的时间顺序获得锁,Synchronized锁非公平锁,ReentrantLock默认的构造函数是创建的非公平锁,可以通过参数true设为公平锁,但公平锁表现的性能不是很好。
                                            
         3.锁绑定多个条件,一个ReentrantLock对象可以同时绑定对个对象。ReenTrantLock提供了一个Condition(条件)类,用来实现分组唤醒需要唤醒的线程们,而不是像synchronized要么随机唤醒一个线程要么唤醒全部线程。
    

    ReenTrantLock的实现是一种自旋锁,通过循环调用CAS操作来实现加锁。它的性能比较好也是因为避免了使线程进入内核态的阻塞状态。

concurrentHashMap是线程安全的吗?怎么上锁的?加锁的粒度是多少
  • ConcurrentHashMap采取了“锁分段”技术来细化锁的粒度:把整个map划分为一系列被成为segment的组成单元,一个segment相当于一个小的hashtable。这样,加锁的对象就从整个map变成了一个更小的范围——一个segment。ConcurrentHashMap线程安全并且提高性能原因就在于:对map中的读是并发的,无需加锁;只有在put、remove操作时才加锁,而加锁仅是对需要操作的segment加锁,不会影响其他segment的读写,由此,不同的segment之间可以并发使用,极大地提高了性能。

  • 在 Java 8 之后, JDK 却弃用了这个策略,重新使用了 synchronized+cas.

    • 加入多个分段锁浪费内存空间。
    • 生产环境中, map 在放入时竞争同一个锁的概率非常小,分段锁反而会造成更新等操作的长时间等待。
    • 为了提高 GC 的效率
CAS

CAS是英文单词Compare And Swap的缩写,翻译过来就是比较并替换。

CAS机制当中使用了3个基本操作数:内存地址V,旧的预期值A,要修改的新值B。更新一个变量的时候,只有当变量的预期值A和内存地址V当中的实际值相同时,才会将内存地址V对应的值修改为B

java中原子类了解吗
  • Java提供了两种方式来处理线程安全的问题。第一种是互斥同步(悲观锁),第二种是采用非阻塞式同步(乐观锁)
  • Atomic系列类原理都是CAS操作
  • 由Atomic可知,这些类提供的操作是不可中断的。即使是在多个线程一起执行的时候,一个操作一旦开始,就不会被其他线程干扰
  • 整形 长整型 布尔 整形数组 长整型数组 引用类型数组

Python

python的垃圾回收机制了解吗

python采用的是引用计数机制为主,标记-清除和**分代收集(隔代回收)**两种机制为辅的策略。

  • 引用计数法机制的原理是:每个对象维护一个ob_ref字段,用来记录该对象当前被引用的次数,每当新的引用指向该对象时,它的引用计数ob_ref加1,每当该对象的引用失效时计数ob_ref减1,一旦对象的引用计数为0,该对象立即被回收,对象占用的内存空间将被释放。它的缺点是需要额外的空间维护引用计数,这个问题是其次的,不过最主要的问题是它不能解决对象的“循环引用”,

    • 分代回收是一种以空间换时间的操作方式,Python将内存根据对象的存活时间划分为不同的集合,每个集合称为一个代,Python将内存分为了3“代”,分别为年轻代(第0代)、中年代(第1代)、老年代(第2代),他们对应的是3个链表,它们的垃圾收集频率随着对象存活时间的增大而减小。
    • 新创建的对象都会分配在年轻代,年轻代链表的总数达到上限时,Python垃圾收集机制就会被触发,把那些可以被回收的对象回收掉,而那些不会回收的对象就会被移到中年代去,依此类推,老年代中的对象是存活时间最久的对象,甚至是存活于整个系统的生命周期内。
  • 有三种情况会触发垃圾回收:

    1. 调用gc.collect(),需要先导入gc模块。
    2. gc模块的计数器达到阈值的时候。
    3. 程序退出的时候。

    而gc模块的一个主要功能就是解决循环引用的问题。

    从根对象(root object)出发,沿着有向边遍历对象,可达的(reachable)对象标记为活动对象,不可达的对象就是要被清除的非活动对象。根对象就是全局变量、调用栈、寄存器

  • 标记清除(Mark—Sweep)』算法是一种基于追踪回收(tracing GC)技术实现的垃圾回收算法。它分为两个阶段:第一阶段是标记阶段,GC会把所有的『活动对象』打上标记,第二阶段是把那些没有标记的对象『非活动对象』进行回收。

Python支持多线程高并发吗

支持 有thread和threading模块,一个是源生模块,threading是扩展模块,在thread基础上进行了封装及改进

Go

Go的优点

Go被很多人誉为“互联网时代的C语言”,位解决大型系统开发中的问题,支持并发,规范统一,比较简单。支撑面向对象,但不支持继承,重点是接口

  • Go提供语言层面对并发的支持,goroutine;Go也是自己管理内存的

  • 相对于 C/C++ 来讲,Go语言拥有清晰的依赖管理和全自动的垃圾回收机制;相对于 Java 来讲,Go语言拥有简明的类型系统、函数式编程范式和先进的并发编程模型。

    最大的优势在于具有较高的生产效率、先进的依赖管理和类型系统,以及原生的并发计算支持

C++ Java Go Python有什么区别

  • C++兼容C,还是可以面向过程的,但Java纯面向对象;C++内存要自己管理,Java自动垃圾回收;C++有指针,Java没有指针,只有引用的概念;C++会编译成机器码,但Java是字节码,然后在虚拟机上解释执行,跨平台性更好;Python是面向对象的 解释型的;GO不是面向对象的,支持封装,不支持继承多态,但是接口很灵活
    • 除了C++都是内存自动管理
    • C++是强类型语言,Python则不需要显式地声明出变量类型,是动态类型;C++是编译型语言,Python是解释型;C++效率高,Python效率低一些; Python有很多很丰富的第三方库;C++主要用大括号,Python中主要用:和缩进来控制; Python也是内存自动管理,C++手动管理内存;GO也是静态强类型语言,同时GO也是编译型语言
    • Python没有提供内置的并发,而Go有;GO在进行变量声明时,需要在变量前加***var***关键字;Go也是静态强类型语言,编译型,有垃圾回收(后台有个守护进程来监控对象); Go 谈不上是面向对象还是面向过程的; Python是有面向对象支持的;Python不太支持高并发,但是也行

内存分配上有什么区别

  • C++自己管理内存
  • Java Python Go都是自动内存管理

从编译的角度看,这几种语言的差别在哪

  • GO也是编译型语言 C++是编译型
  • Java是有编译有解释 Python是解释

操作系统

进程线程协程

进程和线程的区别

进程:资源管理的最小单位 线程:系统调度的最小单位

进程间是独立的,切换的开销比较大;同一个进程内的线程共享进程内的资源,线程间的切换开销较小

线程共享本进程的资源,如内存\IO CPU 等,对java而言,共享堆、方法区 直接内存

线程内部有独立的PC 和栈

通信机制

线程同步的方式:

临界区 互斥量 信号量 事件

进程间通信的方式:

管道 消息队列 信号 信号量 共享内存 socket

  • 管道 匿名管道只能有亲缘关系的 命名管道允许无亲缘关系的进程间通信
  • 消息队列 克服了信号传递信息少、管道只能字节流的缺点 可以自定义消息类型
  • 信号 比较复杂,用于通知某进程事件已经发生
  • 信号量 计数器 控制多个进程对共享资源的访问
  • 共享内存 映射一段能被其他进程访问的内存,是最快的,一般需要和其他方式一起实现同步
  • sockets 不同机器上的进程通信
    共享内存:速度最快 多个进程可以共享同一块物理内存。将同一段物理内存连接到自己的地址空间中(虚拟地址MMU机制,看到的地址并不一样,转换之后才是一样的)。

共享内存并没有提供同步机制,所以需要其他机制比如信号量

  • 每个进程有自己的PCB进程控制块和地址空间,有与之对应的页表,负责将进程的虚拟地址和物理地址做映射,通过内存管理单元进行管理。两个不同的虚拟地址通过页表映射到物理空间的同一区域,指向共享内存
    img
    对于同一个共享内存,实现采用的是引用计数原理,进程进入+1 离开-1 不为0的话不能删除的

  • 为什么共享内存快:就两次复制 A对内存 B对内存,直接操作内存,所以快

协程

线程的问题:

我们知道操作系统在线程等待IO的时候,会阻塞当前线程,切换到其它线程,这样在当前线程等待IO的过程中,其它线程可以继续执行。当系统线程较少的时候没有什么问题,但是当线程数量非常多的时候,却产生了问题。一是系统线程会占用非常多的内存空间,二是过多的线程切换会占用大量的系统时间

  • 协程运行在线程之上,当一个协程执行完成后,可以选择主动让出,让另一个协程运行在当前线程之上。协程并没有增加线程数量,只是在线程的基础之上通过分时复用的方式运行多个协程

  • 没有线程切换的开销,不需要多线程的锁,因为一个线程能启动多个协程

  • 协程, 我们又称为微线程,协程它不像线程和进程那样,需要进行系统内核上的上下文切换,协程的上下文切换是由开发人员决定的。

协程是一种用户级的轻量级线程。协程拥有自己的寄存器上下文和栈。协程调度切换时,将寄存器上下文和栈保存到其他地方,在切回来的时候,恢复先前保存的寄存器上下文和栈。
link
协程的切换在用户态完成,切换的代价比线程从用户态到内核态的代价小很多
协程只有和异步IO结合起来,才能发挥最大的威力

协程有什么不足
  • 程的概念最核心的点其实就是函数或者一段程序能够被挂起(说暂停其实也没啥问题),待会儿再恢复
  • 无法使用 CPU 的多核。协程的本质是个单线程,它不能同时用上单个 CPU 的多个核,协程需要和进程配合才能运行在多
    CPU上。
  • 要用非阻塞代码

调度

也叫CPU调度算法

面向用户的准则:周转时间短 响应时间快 优先级等

面向系统的准则:吞吐量高 CPU利用率搞 资源平衡利用等

  • 先来先服务
  • 最短作业优先
  • 高相应比优先 权衡短作业和长作业 (等待时间+要求服务时间)/要求服务时间
  • 时间片轮转 古老简单公平 通常时间片未20ms到50ms
  • 最高优先级
    • 静态优先级(创建进程时已经确定优先级) 动态优先级(动态调整 比如运行时间增加就降低优先级 等待时间增加就升高优先级)
    • 抢占式 非抢占式
    • 可能最低优先级的一直得不到执行
  • 多级反馈队列

特殊进程

pipe匿名管道是亲缘进程通信,祖父和孙子能通信吗?父进程挂了,祖父和孙子还能通信吗

守护进程 僵尸进程 孤儿进程

IO模型

IO多路复用是什么

一种同步IO模型,一个进程/线程监视多个文件描述符看是否可以执行IO操作;一旦某个文件句柄就绪,就能够通知应用程序进行相应的读写操作,没有文件句柄就绪时会阻塞应用程序,交出CPU。

多路指网络连接,复用指用同一个线程。

文件描述符:file descriptor 用于表述指向文件的引用

为什么要有IO多路复用

  • 用更少的资源做更多的事,线程切换是很耗资源的
  • 没有IO多路复用时,一般是BIO和NIO。BIO无法处理并发,请求数增加就需要很多线程,开销很大;NIO则是一直轮询,浪费CPU

IO多路复用的三种实现方式

  • select poll epoll 本质都是同步IO
    • select调用 会返回就绪fd的数目,然后可以判断每个fd看有没有读写事件发生
    • epoll中每一个epoll对象有一个独立的eventpoll结构体,用于存放epoll_ctl方法向epoll对象中添加进来的事件;epoll_wait检查是否有事件发生时,只需要去检查对象中的rdlist双链表;
      • epoll_create创建一个ep对象,把所有要监听的socket放到对象中
      • epoll_ctl:把socket增加、删除到红黑树
      • epoll_wait:检测可读队列,没有可读socket则堵塞进程
      • epoll只能工作在linux下
    • select缺点:单个进程打开的FD有限;每次调用都需要把fd集合从用户态拷贝到内核态,开销大;对socket扫描是线性扫描,用轮询,效率低
    • poll和select相比,只是没有fd限制,其他一样
  • epoll 的两种模式:
  • LT 默认模式 只要fd还有数据可读,每次epoll_wait都会返回它的事件
  • ET 高速模式,只提示一次,直到下次再有数据流入前都不提示。所以ET下读一个fd就要把buffer读完

水平触发:如果文件描述符已经就绪可以非阻塞的执行IO操作了,此时会触发通知.允许在任意时刻重复检测IO的状态.select,poll就属于水平触发.

边缘触发:如果文件描述符自上次状态改变后有新的IO活动到来,此时会触发通知.在收到一个IO事件通知后要尽可能多的执行IO操作,因为如果在一次通知中没有执行完IO那么就需要等到下一次新的IO活动到来才能获取到就绪的描述符.信号驱动式IO就属于边缘触发.

  • epoll中LT是水平触发(defaul),ET是边沿触发(只能开启unblok模式)
    • LT时,内核告诉你一个fd是否就绪了,就算不做操作或者没有读写完,还会继续通知你
    • ET 是高速的,只支持非阻塞。fd从未就绪变成就绪,内核就会告诉你,不读完也不会告诉你了,除非有新的IO进来
  • epoll的应用:
    redis nginx

阻塞IO 非阻塞IO

阻塞IO:fd上没有数据可读或者没有空间可写,就卡在那了(卡在调用函数哪里),直到有数据可读或者有空间可写。

  • 非阻塞IO:不管可不可以读写,都会立即返回,返回成功说明操作完成了,不成为会有状态码。

Linux指令

  • top: 动态的现实CPU 内存使用情况等

  • PS: 当前进程情况的快照

  • uname:查看操作系统

  • df -h 查看各分区使用情况

  • fdisk -l:查看所有分区

  • free -m 查看内存使用量和交换区使用量

  • ipconfig:查看所有网络接口的属性

  • ls pwd mkdir cp mv top ps zip unzip tar scp ssh cat more

  • 调试工具:
    pstack pdb

top命令里的load average

load average分别代表最近一分钟、最近5分钟、最近15分钟的负载

  • Linux top命令的load average满负荷是cpu核心的个数,实际上应该比满负荷的值要小,不然会影响性能。如果负载超过cpu核心数的话,则说明系统超负荷运行。而负载最大值和并发执行的线程数有关,大小基本和并发执行的线程数一致。如果是单核CPU,负载等于1就是满负荷运转了,如果是四核、甚至更多核心的CPU,负载大于1这说明系统当前负载很小,不需要过多关心
    作者:jerrik
    link

内存、CPU

字节序大端 小端

大于一个字节类型的数据在内存中的存放顺序
大端模式才是我们直观上认为的模式,高位字节排放在内存的低地址端
blog

判断大端小端
//大端小端判断
//方法1
int check_end(){
	long long x = 3;
	auto ans = 1 & x;
	if(ans == 1){
		return 0;
	}else{
		return 1;
	}
}

也可以用Union

// 代码1
union test {
    int a;
    char b;
} c;

int main(int argc, char const *argv[])
{
    c.a = 1;
    cout << (c.b & 1 ? "小端" : "大端") << endl;
    return 0;
}

什么是死锁 死锁的条件

死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去

互斥 占有且等待 不可抢占 循环等待

如何避免死锁

顺序加锁; 可抢占; 一次性申请所有的资源

什么是内存泄漏

申请了但没释放

  • 内存泄露:申请了内存,但是之后没释放。多次内存泄露哦可能就会造成内存溢出
  • 内存溢出:OOM 内存不够用了,需要的比已有的内存大

内存分区

堆 栈 全局(DATA放初始化过的全局和静态 BSS放未初始化的) 常量 代码区

动态链接静态链接

动态链接和静态链接有什么不同和优缺点,实践中用过吗

  • https://blog.csdn.net/kang___xi/article/details/80210717

  • 静态链接:程序执行之前完成所有的组装,加载到内存运行前将所有要用到的目标文件合在一起,内存中同一个文件可能存在多个副本。

    动态链接:运行的时候需要什么再加载

  • 静态链接的优点是简单速度快,问题:

    • 占用空间 同一个模块被多个模块链接时,内存中有多个副本
    • 不好更新 更新的时候整个程序要重新链接
    • –>为了解决这两个问题,就出现了动态链接
  • linux上的.so文件 windows的.dll文件 就是动态链接库。DLL不必包含在最终的EXE文件中。 优点是节省空间,容易更新。缺点是把链接推迟到了程序运行时,每次执行程序都要链接,性能会有一定损失

  • 动态链接库的两种链接方法:

    • 装载时动态链接:编译之前就要直到要调用哪些
    • 运行时动态链接:运行时决定要调用哪个函数

程序编译到运行的过程都有哪些

为什么要区分内核态和用户态

  • 为了保证系统不被应用程序破坏。用户态相较来说有较低的执行权限,一些危险又高级的特权指令用户态不能执行,只允许操作系统用
  • 处于用户态时,进程能访问的内存空间和对象受到限制;内核态的能访问所有的
  • 用户态切到内核态的方法:中断 异常 系统调用
  • 内核态到用户态:设置程序状态字
    两者切换耗时:

需要保存上下文,进行栈的转换,保存用户态的状态,包括寄存器等,然后到内核态,回来之后还要恢复

//mutex加锁解锁也是要到内核态的https://www.jianshu.com/p/5725db8f07dc

CPU执行一条指令的过程

  • 取址 译码 执行 访存取数 结果写回
  • 取址:将一条指令从贮存中取到寄存器中 PC用来指示当前指令在主存中的位置
  • 译码:识别出指令类别和操作数
  • 执行:常常涉及到计算单元
  • 存取:根据指令地址码,得到操作数在主存中的

页面置换算法

  • 最佳页面置换算法
  • 先进先出
  • 最近最久未使用 LRU
  • 时钟页面置换
  • 最不常用置换

网络

层级结构

后端开发、C++开发面经分类整理_第5张图片
后端开发、C++开发面经分类整理_第6张图片
link

ping是哪个协议

ICMP
ICMP 面向无连接,用于在IP主机、路由器之间传递控制消息,属于网络层协议

HTTP 状态码

1xx 信息性状态码 接受的请求正在处理

2xx 成功 请求正常处理完

3xx 重定向 需要进行附加操作以完成请求 (301资源移动到新的URL)

4xx 客户端错误 (404 请求资源不存在 400 客户端请求的语法错误 )

5xx服务器错误 (500 服务器内部错误)

HTTP长连接段连接

博客

HTTP 1.0 1.1 的主要区别 2.0有什么新特点 3.0呢

  • HTTP 1.0 短连接 HTTP1.1 长连接 HTTPS做了SSL(运行在TCP上)或TSL的加密,端口是443
  • HTTP2.0 支持铭文传输 基于二进制格式解析 支持多路复用
  • HTTP3.0 基于UDP 有助于切换网络时保持连接,适合于现在移动网络的情况,基于TCP的话,切换网络后IP会变,之前的连接没法保持,而基于UDP的QUIC协议,可以内建不同的连接标识方法,在网络完成切换后恢复与服务器之前的连接

HTTPS的对称和非对称加密各自的优缺点

  • 对称加密快速简单 效率高
  • 对称加密安全 密钥越大加密越强,但加密和解密的过程就越慢

https TLS加密的三次握手过程

  • http://www.ruanyifeng.com/blog/2014/02/ssl_tls.html

  • SSL/TLS协议的基本思路是采用公钥加密法
    公钥加密计算量太大,如何减少耗用的时间?

    • 解决方法:每一次对话(session),客户端和服务器端都生成一个"对话密钥"(session key),用它来加密信息。由于"对话密钥"是对称加密,所以运算速度非常快,而服务器公钥只用于加密"对话密钥"本身,这样就减少了加密运算的消耗时间。
    • 后端开发、C++开发面经分类整理_第7张图片

cookie session

  • cookie保存用户信息,保存在客户端 下次client向server发送请求的时候会带上cookie 一般用于会话状态管理(用户登录状态 等) 个性化设置 浏览器行为跟踪

  • session是服务器端记录用户的状态,保存在服务器端,在整个用户会话中一直存在下去 客户端关闭了session超时了一般就会失效 更安全

  • token主要是前后端分离的,前端的请求头里会加上token

  • 为啥要有:

    • HTTP是无状态的,要让知道现在是谁在什么操作,需要cookie和session。
    • 第一次登录时服务器生成session,将session ID返回给浏览器放到cookie里,以后再访问会带着这个cookie,从中取出sessionID来找到session
  • 要是禁用了cookie呢:

    • 再请求中带上seesionID 比如拼在url上
    • token 第一次登录时将返回的token存起来放到客户端,以后带上这个token
  • 分布式session

    • nginx代理,将请求按IP hash分配,同一IP固定访问一个后台服务器
    • session复制,广播给其他节点
    • 共享session,用缓存中间件来统一管理

DNS 解析:

  • 首先,在本地域名服务器中根据域名查询IP地址,如果没有找到的情况下,本地域名服务器会向根域名服务器发送一个请求。

    如果根域名服务器也不存在该域名时,本地域名会向com顶级域名服务器(TLD)发送一个请求,依次类推下去。

    直到最后本地域名服务器得到google的IP地址并把它缓存到本地,供下次查询使用。


    DNS是通过UDP传送。其实,有时候也是通过TCP来传送。那么什么时候用TCP,什么时候用UDP?很简单,当response的packet大于512字节时,就用TCP,反之,则用UDP。

TCP-UDP

TCP UDP的区别

  • TCP:面向连接 可靠 保证顺序 对系统资源的要求多
  • UDP:非连接的 不可靠 不保证顺序 更快 更简单

握手挥手

握手
握手过程:
在 socket 编程中,客户端执行 connect() 时。将触发三次握手。
后端开发、C++开发面经分类整理_第8张图片

可以省略第三次握手吗

不能
第三次握手是为了防止失效的请求连接到达服务器,让服务器错误的打开连接
假如客户端发出了连接请求,但因为网络波动导致服务器并没有收到来自客户端的请求连接,于是客户端又重发了一次连接请求,客户端和服务器经过两次握手就建立好连接。双方开始传输数据,数据传输完成以后,双方断开连接。过一段时间后,原本在网络传输中搁置的连接请求到达了服务器。服务器以为是客户端又发出来一次新的连接请求,于是就向客户端发送确认报文段,同意建立连接(两次握手只需要服务器发出确认报文段,就建立好连接)。此时服务器一直在等待客户端发送的数据,一直浪费着系统资源。
————————————————
版权声明:本文为CSDN博主「‍oOoOoOooOO」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/LOOKTOMMER/article/details/121243476

可以改成4次握手吗

可以
TCP三次握手原本应该是"四次握手",但是中间的同步报文段SYN和应答报文ACK是可以合在一起的,这两个操作在时间上是同时发送的。

当客户端的到达同步报文段SYN到达服务器的时候,服务器的内核就会第一时间进行应答报文段ACK, 同时也会第一时间发起同步报文段SYN,这两件事情同时触发,于是就没必要分成两次传输,直接一步到位。分成两次反而会更浪费系统资源(需要进行两次的封装和分用)。
————————————————
版权声明:本文为CSDN博主「‍oOoOoOooOO」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/LOOKTOMMER/article/details/121243476

握手过程中可以携带数据吗

第三次可以,这时对服务器而言已经建立好连接了。前面就携带的话更容易受到泛洪攻击而且处理速度慢

SYN泛洪攻击

SYN泛洪攻击利用的是TCP的三次握手机制,攻击端利用伪造的IP地址向服务器发出请求,而被服务器发出的响应响应将永远发送不到目的地,那么就会触发服务器的超时重传机制等待客户端的响应(客户端的IP地址不存在,根本不会进行响应)。那么被服务器在等待关闭这个连接的过程中消耗了资源,如果有成千上万的这种连接,主机资源将被耗尽,从而达到攻击的目的。

措施:

    降低SYN timeout时间

    采用SYN cookie设置

    增加半连接数

    合理地采用防火墙等外部网络安全设施

方法1:开启SYN cookie 客户端发送SYN,服务器不会立刻建立连接,而是生成一个cookie一起发送给客户端,客户端再次返回ACK后,核验cookie值,验证成功才创建TCP分配资源 类似的是SYN cache 用专用的HASH中保存这种半连接信息,直到收到正确的ACK再分配TCB 都属于延缓TCB分配方法
方法2: SYN Proxy 防火前确定连接的安全后,再进行连接

挥手过程:
后端开发、C++开发面经分类整理_第9张图片
挥手

4次挥手的时候time_wait是干啥的

保证客户端最后发送的ACK能够到达服务器,帮助其正常关闭
防止已失效的连接请求报文段出现在本连接中

time wait等待的时间是多少

2MSL(Maximum Segment LifeTime)
它是任何报文在网络上存在的最长时间,超过这个时间的报文将被丢弃。

因为TCP协议是基于IP协议(位于IP协议的上一层),IP数据报中有限制其生存时间的TTL字段,是IP数据报可以经过的最大路由器的个数,每经过处理它的路由,TTL就会减一。TTL为 0 时还没有到达目的地的数据报将会被丢弃,同时发送 ICMP 报文通知源主机。

MSL的单位为时间,TTL的单位为跳转数。所以MSL应该大于等于TTL变为0的时间,以确保报文已被丢弃。

TIME_WAIT等待的2MSL时间,可以理解为数据报一来一回所需要的最大时间。

2MSL时间是从客户端接收到FIN后发送ACK开始计时的。如果在这个时间段内,服务器没有收到ACK应答报文段,会重发FIN报文段,如果客户端收到了FIN报文段,那么2MSL的时间将会被重置。如果在2MSL时间段内,没有收到任何数据报,客户端则会进入CLOSE状态。
————————————————
版权声明:本文为CSDN博主「‍oOoOoOooOO」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/LOOKTOMMER/article/details/121307137

2msl时间是多长

1分钟

time_wait过多

只有主动发起断开请求的一方才会进入TIME_WAIT状态
过多会占用系统资源;端口号无法释放,若占据太多则无法

最好的办法是尽量让客户端主动断开连接,除非遇到一些异常情况,如客户端协议错误、客户端超时等

  • 调整系统内核参数,比如开启重用 、开启sockets的快速回收等 net.ipv4.tcp_tw_reuse = 1,允许对处于TIME_WAIT的socket用于建立新的连接
  • 改成长连接

TCP如何保证通信可靠性

TCP的可靠性传输是如何保证的

流量控制 blog 滑动窗口
拥塞控制 blog 慢启动、拥塞避免、快重传、快恢复
超时重传 停止等待ARQ blog
确认应答+序列号

  • 接收方收到报文就会确认(累积确认:对所有按序接收的数据的确认)TCP给发送的每一个包进行编号,接收方对数据包进行排序,把有序数据传送给应用层。

校验和等 blog

  • 发送的数据包的二进制相加然后取反,目的是检测数据在传输过程中的任何变化。如果收到段的检验和有差错,TCP将丢弃这个报文段和不确认收到此报文段。

TCP 的流量控制窗口:

  • 发送方和接收方是一样大的,窗口为0时就不发送了,但不会一直等待,而是主动探测 (发送的时候也是,怀疑对方挂了不会一直等待,而是主动探测 比如长连接丹迪断不断
粘包
  • TCP粘包是指发送方发送的若干包数据到接收方接收时粘成一包。发送方等缓冲区满了再发送、以及接收方不及时接收缓冲区的包,会导致粘包
  • 若传输的数据未不带结构的连续流数据,比如文件,就不用分开;但一般带结构的数据都要分包
  • 针对TCP没有保护消息边界:发送固定长度的消息;把消息的尺寸和消息一块发送;使用特殊标记来区分
  • UDP是面向报文的,有消息边界
怎么判断网络是否出现了拥塞?有了解过其他的拥塞控制算法吗
  • 判断:没有按时收到确认;收到3次重复确认

应用

UDP:适用于实时性很高,对数据准确性不是特别高的场合。比如QQ聊天 在线视频 网络语音电话; 不能容忍延时的游戏,比如多人动作类,射击对战,其实可以UDP的;而纸牌这种,对延时没感觉,就TCP

socket

套接字 IP地址和端口

socket编程核心就包括:建立连接 发送数据 以及接收数据

  • 服务器:创建socket对象,用指定的端口号和IP建立end point对象,bind()绑定,listen()监听socket,接到客户端连接后,用socket对象的accept方法创建一个新的用于和客户端通信的socket对象,通信结束关闭socket

  • 客户端:创建socket对象, connect连接服务器的socket对象, send recieve接收消息

  • 连接过程主要是TCP三次握手;通信时服务端客户端都可以用read() write()函数

性能指标

QPS

分布式

Kafka

kafka为什么快

  • kafka的写入是顺序写入(减少了随机IO的寻址时间) 还会利用内存映射文件memory mapped files(省去了用户空间到内核空间复制的开销);
  • zero copy 文件数据copy到内核缓冲区,再从内核缓冲区拷贝到socket相关缓冲区
  • 批量压缩

kafka怎么保证数据不丢失

  • 生产者,回调函数看发送成功了没;添加重试次数;leader和follower都接收到才算发送成功
  • 消费者:关闭自动提交offset,真正消费完消息后再自己手动提交offset
  • kafka:partition多个副本,生产者和消费者只和leader交互,leader挂了可以重新选取

kafka基本架构了解吗》kafka消费者消费失败了会怎么样?有出现消费和生产监控不一样的情况吗

  • 消费失败了重试一下,可以把消费的数据存下来,写数据库或者写文件都行,后面再手动处理一下也行

CAP

CAP** 也就是 Consistency(一致性)Availability(可用性)Partition Tolerance(分区容错性)

  • 当发生网络分区的时候,如果我们要继续服务,那么强一致性和可用性只能 2 选 1。也就是说当网络分区之后 P 是前提,决定了 P 之后才有 C 和 A 的选择。
  • 比如 ZooKeeper、HBase 就是 CP 架构,Cassandra、Eureka 就是 AP 架构

分布式锁

多机环境中,不同机器不同进程下保证线程的安全性,需要分布式锁

常见的分布式锁方案:

  • 基于数据库
    • mysql唯一索引 加锁;完全利用现有数据库;还是可能死锁开销大
  • 基于分布式系统
    • 基于zookeeper 需要单独维护一套zookeeper集群
  • 基于缓存
    • 基于redis命令,加锁setnx解锁delete 不过也可能死锁
  • redisson分布式锁

分布式锁的四个条件:

  • 互斥性,任意时候,只有一个客户端能持有锁
  • 不会死锁。即使一个客户端持锁期间崩溃了没有主动解锁,也能保证后续其他客户端能加锁
  • 加锁解锁的是同一个客户端
  • 具有容错性,大多数redis节点正常运行,客户端就能获取和释放锁
    分布式事务**
    • https://zhuanlan.zhihu.com/p/263555694
    • 本地事务依赖数据库本身提供的事务特性来实现
    • 典型的场景就是微服务架构:微服务之间通过远程调用完成事务操作

RPC

项目中用的RPC是基于thrift的

thrift

thrift是基于TCP的(HTTP)

开发一个RPC的话 dubbo spring cloud之类,需要哪些基本的组件

  • 微服务架构(Microservice Architecture)是一种架构概念,旨在通过将功能分解到各个离散的服务中以实现对解决方案的解耦

    • 必须组件:注册中心,后台服务(Provider)
    • 非必须组件:配置中心,熔断,限流,链路跟踪,路由

客户端怎么发现服务;用什么做服务发现 怎么做服务发现; zookeeper是怎么是实现的(树桩结构)

  • zookeeper 利用zookeeper,实现服务端注册、客户端自动发现
  • 服务注册和发现需要一个位置固定或提供了固定域名的ServiceRegistry服务。服务发现包括Client-Side的服务发现和Server-Side的服务发现两种方式。发现的方式可以是主动到ServiceRegistry查询,也可以由ServiceRegistry通知到Client。在使用Client-Side Discovery时,Client会发现服务的所有实例,并根据LB策略选择一个实例发起请求。
  • 客户端发现模式通过客户端组件根据负载均衡算法决定相应服务实例的网络位置,也就是说,客户端组件保存有服务端所有实例的服务注册表,调用发生时,根据负载均衡算法,从服务注册表中选择一个网络位置,向服务端发起请求,完成调用。
  • 服务端发现模式是有一个单独的服务发现组件,这个实例持有服务注册表,同时也起到负载均衡器的作用,客户端调用服务端时,直接调用服务发现实例,通过服务实例代理到后端服务实例中,所以服务端发现模式也被称为代理模式
  • 目前常用的服务注册表有:Eureka、etcd、Consul、Zookeeper,Kibernetes

负载均衡

怎么增加一个服务的高并发和容灾性?突然大量请求过来了可以怎么处理

  • 以下是我想到的:
  • 加机器 部署集群; 甚至多机房; 数据库备份 数据库加缓存提高并发;大服务拆开成多个微服务; 限流操作/ 扩容; 设置请求超时和重复次数; IO多路复用 线程池; 服务降级,减少性能损耗;过滤无效请求;请求排队后台异步处理;

数据结构

红黑树

红黑树的5个特点

https://zhuanlan.zhihu.com/p/273829162 这个讲得好
二叉搜索树的一个高级版本
增删查改效率是O(logn)

红黑树是一种二叉搜索树,满足左子树<根节点<右子树

红黑树的节点只能是红色或者黑色,根节点为黑色

红节点的子节点只能是黑色

叶节点都是黑色(null的叶子节点)

任意节点到null的所有路径经过的黑点节点数都相同 (保证了没有一条路径比其他路径长两倍,基本平衡)

红黑树VS二叉搜索树

二叉搜索树在插入完全有序的情况下会退化成一条,插入删除查找变成O(n);红黑树最差也是O(logn);平衡二叉树是左右子树树高的差不超过1,但整体效率上还是不如红黑树

红黑树的查询性能略微逊色于AVL树,因为其比AVL树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较,但是,红黑树在插入和删除上优于AVL树,AVL树每次插入删除会进行大量的平衡度计算,而红黑树为了维持红黑性质所做的红黑变换和旋转的开销,相较于AVL树为了维持平衡的开销要小得多

红黑树插入删除

红黑树 插入最多两次旋转就平衡(一次插入最多2次旋转,是父红叔不红,插入子节点与父节点不在同一边时); 删除最多三次旋转就平衡https://www.jianshu.com/p/ab90c2ec07e4

哈希

哈希冲突的解决

哈希的操作时间复杂度是O(1)

哈希冲突:根据key的结果计算位置时,发现那个位置已经有数了

解决哈希冲突常用的四种方法:

1)开放定址

冲突了,沿着计算的位置向前向后再找,知道找到一个空的,比如线性就是往后一个个找,二次就左右跳着找

2)拉链

HasMap常用,冲突了就下面接链表

3)再哈希

多个hash函数,冲突了换下一个,不会很聚集,不过计算时间会多一点

4)公共溢出区

哈希表和一个用来溢出的表,冲突了就放到溢出区

  • 插入删除时的时间复杂度:O(logn)

内存中的堆与数据结构中的堆是一回事吗

link

  • 数据结构中的堆(Heap)是一类数据结构,它们拥有树状结构,且能够保证父节点比子节点大(或小)。当根节点保存堆中最大值时,称为大根堆;反之,则称为小根堆。
    二叉堆(Binary Heap)是最简单、常用的堆,是一棵符合堆的性质的完全二叉树。它可以实现 [公式] 地插入或删除某个值,并且 [公式] 地查询最大(或最小)值。 https://zhuanlan.zhihu.com/p/187618450-

稳定的排序方式

冒泡排序 插入排序 归并排序

arrylist和linkedlist有什么区别,查询时间复杂度

  • arraylist是动态数组,linkedlist是链表,随机访问arraylist更优O(1),linkedlist要O(n);新增删除用链表更快

简单介绍一下HashMap,怎么做到O(1)的时间复杂度去查找的;hash和equal 不一样的对象算出来的hash一样 会出现什么情况; 哈希冲突了会怎么样

key算出hash code 可以直接找到索引下标

哈希冲突:拉链 开放寻址 多个hash函数再哈希 公共溢出区

跳表

时间O(logn) 空间 O(n)

跳表在原有的有序 链表上增加了多级索引,通过索引来实现快速查找。
1、首先在最高级索引上查找最后一个小于当前查找元素的位置
2、调到次高级索引继续查找,直到调到最底层为止,如果查找元素存在的话,此刻已经十分接近要查找的元素的位置了

Skip List–跳表(全网最详细的跳表文章没有之一)

为什么redis用跳表而不是红黑树

因为查找一定范围内的数据跳表效率更高,定位到节点遍历链表就行了

其他

汉字编码

  • gbk unicode utf8
    • unicode规定必须用两个字节来表示字符
    • utf8是每次传输8为 utf16是每次16,utf8是互联网上使用最广的一种unicode实现方式,是变长的编码方式,可以用1-4字节表示一个符号,在ascii范围内就用1个字节。unicode一个中文字符占2个字节,utf8一个中文占3个字节。从unicode到utf8之间要通过一些算法和规则来转换

人在上海 请求北京机房的服务,会经过哪些过程?不能所有请求都打到一台机器上,怎么做负载均衡?

android为什么比ios卡

  • 苹果的硬件是自己的,可以做更多优化;安卓是跨平台的,机型丰富,要考虑对不同硬件的兼容支持
  • 应用设计上的一些 后台服务策略不一样 安卓是支持后台服务的

django一个请求过来 生命周期如何

  • \1. 当用户在浏览器中输入url时,浏览器会生成请求头和请求体发给服务端 请求头和请求体中会包含浏览器的动作(action),这个动作通常为get或者post,体现在url之中.

    1. url经过Django中的wsgi,再经过Django的中间件,最后url到过路由映射表,在路由中一条一条进行匹配, 一旦其中一条匹配成功就执行对应的视图函数,后面的路由就不再继续匹配了.
    2. 视图函数根据客户端的请求查询相应的数据.返回给Django,然后Django把客户端想要的数据做为一个字符串返回给客户端.
    3. 客户端浏览器接收到返回的数据,经过渲染后显示给用户.

从浏览器输入地址后到返回经历的过程

  • www.cnblogs.com/confach/p/10050013.html

  • 总的来说:

    1. DNS查询
    2. TCP连接
    3. 发送HTTP请求
    4. Server处理HTTP请求并返回HTTP报文
    5. 浏览器解析并render页面
    6. HTTP连接断开

git rebase git merge

链接:https://www.jianshu.com/p/c17472d704a0

你可能感兴趣的