数据库

1.聊一聊事务

在MySQL中，事务是一个最小的不可分割的工作单元。事务能够保证一个业务的完整性。

事务具有四个基本特征，分别是原子性（atomicity），一致性（consistency），隔离性（isolation），持久性（duration），简称ACID。

比如我们的银行转账：在数据库中要执行两条语句，一个用户A加钱，一个用户B减钱。这就是一个不可分割的事务。要么两条语句都执行成功，要么同时失败。这就体现了原子的性质。如果只有一条执行成功，会出现前后不一致的现象。另外事务还有一个性质，是隔离性。通常来说，隔离性是当多个用户并发访问数据库的时候，执行自己的事务的时候不能被其他事务所干扰。通常来说，一个事务所作的修改在最终提交之前是不可见的。

隔离性也分为各种级别：Read Uncommitted(读取未提交)：最低的隔离级别，什么都不需要做，如果有多个事务，那么任意事务都可以看见其他事务的未提交数据。这样会导致脏读显现，A开启一个事务操作，操作转账给B之后未提交，B一方查询到帐了，A回滚，B钱没了。

Read Committed（读取提交内容）：只有在事务提交后，其更新结果才会被其他事务看见，可以解决脏读的问题。但是依然会出现问题，一个用户对表多次读取的时候，发现读取的数据不一致，产生困惑，这也叫做不可重读读现象。

Repeated Read(可重复读）：在一个事务中，对于同一份数据的读取结果总是相同的，无论是否有其他事务对这份数据进行操作，以及这个事务是否提交。可以解决脏读，不可重复读，这就可能产生幻读现象。小张和小王同时开启事务对表进行操作，小张插入一条数据，无论小张是否执行commit，在小王这边都不会查询到小张的事务记录，只会查询到自己所处事务的记录，小王插入一条主键相同的数据，提示错误，冗余插入，给小王带来疑惑，我这表查询没有这条数据啊，幻读。一个事务的提交数据，不能被其他事务读取到。

Serialization（可串行化）：事务串行化执行，隔离级别最高，牺牲了系统的并发性。可以解决并发事务的所有问题，串行化的意思就是：假设所有的事务都放在一个串行的队列中，那么所有的事务都按照固定顺序执行，执行完一个事务后再继续执行下一个事务的写入操作（这意味着队列中同时只能执行一个事务的读写操作）。小张写数据的时候，我这边阻塞，等小张写完数据，小王才能执行操作。

事务的最后一条性质：持久性，持久性是指一个事务一旦被提交了，那么对数据库中的数据的改变就是永久性，即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。

2.数据库的三大范式

第一范式：数据表中的所有字段都是不可分割的原子值。只要字段值还可以继续拆分，就不满足第一范式。

范式设计的越详细，对某些实际操作可能会更好。但并非都有好处，需要对项目的实际情况进行设定。

第二范式：必须满足在第一范式的前提下，其他列都必须完全依赖于主键列，如果出现不完全依赖，只可能发生在联合主键的情况下。

第三范式：必须在满足第二范式的前提下，除了主键列之外，其他列之间不能有传递关系。

我的理解是，尽量将字段分成原子值，每个字段之间的关系都是正交的，减少冗余，新增，修改，删除变少。

对查询不友好。

3.数据库是怎么实现的？

事务是一组逻辑操作的组合。实现事务就是要保证可靠性和并发隔离ACID。这些主要靠日志恢复和并发控制完成的。

日志恢复：数据库里有两个日志，一个是redo log，一个是undo log。redo log记录的是已经成功提交的事务操作信息，用来恢复数据，保证事务的持久性。undo log记录的是事务修改之前的数据信息，用来回滚数据，保证事务的原子性。

并发控制：并发控制主要靠读写锁和MVCC(多版本并发控制)来实现。读写锁包括共享锁和排他锁。保证事务的隔离性，MVCC通过为数据添加时间戳来实现。（MVCC只在REPEATABLE READ 和 READ COMMITTED两个隔离级别下工作，其他的隔离级别都和MVCC不兼容，因为READ UNCOMMITTED总是读取最新的数据行，而不是符合当前事务版本的数据行，而SERIALIZABLE 会对所有读取到的行都加锁。）MVCC解决在REPEATABLE READ和READ COMMITTED两个隔离级别下读同一行和写同一行的两个事务的并发。

4.数据库的锁的种类和加锁方式

以MySQL为例

按照类型来分有乐观锁和悲观锁

根据粒度分有行级锁，页级锁，表级锁（粒度一个比一个大）（仅BDB，Berkeley Database支持页级锁）

根据作用来有共享锁（读锁）和排他锁（写锁）。

什么是共享锁和排他锁？

共享锁是读操作的时候创建的锁，一个事务对数据加上共享锁之后，其他事务只能对数据再加共享锁，不能进行写操作，直到释放所有的共享锁。

排他锁：是写操作时创建的锁，事务对数据加上排他锁之后其他事务都不能对数据加任何的锁（即其他数据不能在访问该数据）。

乐观锁和悲观锁

一般的数据库都会支持并发操作，在并发操作中为了避免数据冲突，所以需要对数据上锁，乐观锁和悲观锁就是两种不同的上锁方式。

悲观锁假设数据在并发操作中一定发生冲突，所以在数据开始读取的时候就把数据锁住。而乐观锁则是假设数据一般情况下不会发生冲突，所以在数据提交更新的时候，才会检测数据是否冲突。

悲观锁的实现：悲观锁有行级锁和页级锁两种形式。行级锁对正在使用的单条数据进行锁定，事务完成后释放该行数据。而页级锁则对整张表进行锁定，事务正在对该表进行访问的时候不允许其他事务并行访问。

悲观锁要求在整个过程中一直与数据库有一条连接，因为上一个事务完成后才能进行下一个事务，所以这个过程是串行化的。

乐观锁有三种常用的实现形式：

一种是在执行事务时把整个数据都拷贝到应用中，在数据更新提交的时候比较数据库中的数据与新数据，如果两个数据一模一样则表示没有冲突可以直接提交，如果有冲突就要交给业务逻辑去解决。
一种是使用版本戳来对数据进行标记，数据每发生一次修改，版本号就增加1。某条数据在提交的时候，如果数据库中的版本号和自己一致，就说明数据没有被修改，否则就认为是过期的数据需要处理。
最后一种采用时间戳对数据最后修改的时间进行标记。

MySQL

1.说一下MySQL执行一条查询语句中的内部执行过程？

连接器：客户端首先通过连接器连接到MySQL服务器

缓存：连接器经过权限验证后，先查询到先前是否执行过此语句（有缓存），若有则返回缓存数据，若无则进入分析器。

分析器：分析器会对查询语句进行语法分析和语义分析，判断SQL语法是否正确，如果查询语法错误则直接返回给客户端错误信息，如果语法正确则进入优化器。

优化器：优化器是对查询语句进行优化处理，例如一个表里面有多个索引，优化器会判断哪个索引效果更好。

执行器：优化器执行完就进入执行器，执行器就开始执行语句进行查询比对了，直到查询到满足条件的所有数据，然后进行返回。

2.MySQL的优化

高频访问：

分表分库：将数据库表进行水平拆分，减少表的长度。

增加缓存：在web和DB之间加上一层缓存层

增加数据库的索引：在合适的字段上加上索引，解决高频访问的限制。

并发优化：

主从读写分离：只在主服务器上写，从服务器上读

负载均衡集群：通过集群或者分布式的方式解决并发压力

3.从MySQL数据库引擎介绍，innoDB和myisam的特点和区别、

InnoDB ： InnoDB是MySQL的默认引擎，支持事务和外键，支持容灾恢复。适合更新频繁和多并发的表，行级锁

MyISAM ： 插入和查询速度比较高，支持大文件，但不支持事务，适合在web和数据仓库场景下使用，表级锁

MEMORY ：memory将表中的数据保存在内存里，适合数据比较小而且频繁访问的场景。

CSV

blackhole

索引

索引的优缺点，什么时候使用索引，什么时候不能使用索引？

什么时候适合使用索引

经常搜索的列上简历索引
作为主键的列上需要建索引
经常需要连接where的列上
经常需要排序的列
进场需要范围查找列

哪些列不适合建立索引

很少查询的列
更新很频繁的列
数据的可取值比较少的列

索引的底层实现

数据库的索引是用B+树来实现的
B+树是一种特殊的平衡多路树，是B树的优化改进版本，他把所有的数据都存放在叶子节点上，中间节点保存的是索引。这样一来相对于B树来说，减少了数据对中间节点的空间占用，使得中间节点可以存放更多的指针，使得树变得更矮，深度更小，从而减少查询的磁盘IO次数，提高查询效率。另一个是由于叶子节点之间有指针连接，所以可以进行范围查询，方便区间访问。
而红黑树是二叉的，它的深度相对于B+树来说更大，更大的深度意味者查找的次数更多，更频繁的磁盘IO，所以红黑树更适合在内存中进行查找。

B树和B+树的二点区别

关键字的数量不同：B+树中分支节点有m个关键字，其叶子节点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是只拥有m-1个关键字。

存储的位置不同：B+树中的数据存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点上，并不仅仅存储在叶子结点。

分支结点的构造不同：B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘的偏移量），也就是说内部节点仅仅包含索引的信息。

查询不同:B树在找到具体的数值之后则结束。而B+树则需要通过索引找到叶子节点中的数据才结束，也就是说B+树的搜索过程中走了一条从根节点到叶子节点的路径。

索引最左前缀、最左匹配

假如我们对a,b,c三个字段建立了联合索引，在联合索引中，从最左边的字段开始，任何连续的索引都能匹配上，当遇到范围查询的时候就停止。比如对于联合索引index（a,b,c），能匹配a,ab,abc三组索引。并且对查询时字段的顺序没有限制，也就是a,b,c;b,a,c;c,a,b;c,b,a;都可以匹配。

匹配列前缀

select * from staffs where id like 'A%';//前缀都是排好序的，使用的都是联合索引
select * from staffs where id like '%A%';//全表查询
select * from staffs where id like '%A';//全表查询

注意：

如果建立(a,b)顺序的索引，我们的条件只有b=xxx，是匹配不到(a,b)索引的；但是如果查询条件是a = 1 and b = 2或者b=2 and a=1就可以，因为优化器会自动调整a,b的顺序，并不需要严格按照索引的顺序来；再比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，因为c字段是一个范围查询，它之后的字段会停止匹配。

在c的范围中，d是无序的。

数据库和数据仓库的区别

数据库与数据仓库的区别实际讲的是OTLP和OLAP的区别

操作性处理，叫联机事务处理OLTP（On-Line Transaction processing ）也可以称面向交易的处理系统，它是针对具体业务在数据库联机的日常操作，通常对少数记录进行查询，修改。用户较为关心操作的响应时间，数据的安全性，完整性和并发支持的用户数等问题。传统过的数据库系统作为数据管理的主要手段，主要用于操作性处理。

分析性处理，叫联机分析处理OLAP(On_line Analytical processing)，一般针对某些主题的历史数据进行分析，支持管理决策。

数据仓库的出现并不是取代数据库。

数据库是面向事务的设计，数据仓库是为了数据而设计。
数据一般存储业务数据，数据仓库存储的一般是历史数据。
数据库设一是尽量避免冗余，一般针对某一业务应用进行设计，比如一张简单的user表，记录用户名，密码等简单数据即可，符合业务应用，但是不符合分析。数据仓库在设计时有意引入冗余，依照分析需求，分析维度，分析指标进行设计。
数据库是为了捕获数据而设计，数据仓库是为了分析数据而设计。

以银行业务为例，数据库是事务系统的数据平台，客户在银行做的每笔交易都会写入数据库，这里可以简单地理解为用数据库记账，数据仓库是分析系统的数据平台，它从事务系统获取数据，并作汇总，加工，为决策者提供决策的依据。比如，某银行某分行一个月发生多少交易，该分行一个月发生多少交易，该分行当前存款余额是多少。如果存款又多，消费交易又多，那么该地区就有必要设立ATM了。

显然，银行的交易量是巨大的，通常以百万甚至千万次来计算，事务系统是实时的，这就要求时效性。客户存一笔钱需要几十秒是无法忍受的，这就要求数据库只能存储很短一段时间的数据，而分析系统是事后的，它要提供关注时间段内所有的有效数据。这些数据是海量的，汇总计算来起来要慢一些。但是只要能够提供有效的分析数据就达到目的了。

结构化数据库和非结构化数据库

在信息社会，信息可分为两大类。一类信息能够用数据或统一的结构加以表示，我们称之为结构化数据。如数字，符合，而另一类信息无法用数字或者统一的结构来表示，如文本，图像，声音，网页等，我们称之为非结构化数据。结构化数据属于非结构化数据，是非结构化数据的特例。

随着网络技术的发展，也别是Internet和Intranet技术的飞速发展，使得非结构化数据的数量日趋增大，这时，主要用于管理结构化数据的关系数据库的局限性暴露的越来越明显。因而，数据库技术相应的进入了“后关系数据库时代”，发展进入基于网络应用的非结构化数据库时代。所谓的非结构化数据库，是指数据的变长记录由若干个不可重复和可重复的字段组成，而每个字段又可由若干个不可重复和可重复的子字段组成。简单的来说，非结构化数据库就是字段可变的数据库。

目前有两大类型的数据库，一种是结构化SQL数据库，一种是非结构化NOSQL数据库。

比拼1：数据的组织形式

SQL，顾名思义是结构化查询语言，它的数据都是结构化的。这个需要在最初创建数据库的时候要做好设计，这个设计一旦定型之后，再修改的话就会比较麻烦。当然如果设计做的好的话，也就无需修改了。所以机构化数据最大的一个工作就是表的设计。这是在使用这种数据库的时候，开发工作中的重中之重。

结构化数据的另一个体现就是各种数据之间的关系，比如说1对1的关系，1对多的关系，多对多的关系。另一个体现就是数据的定义严格，在一个表中只能存放一种表数据，也就是说，你的每一行数据都要遵循这个表的定义。在这个表里的每一行数据都要遵循这个表内定义好的数据类型，不能够存放一些所谓非定义的数据，否则出错。

而NOSQL数据库不需要结构化的数据设计。这样，它的容错性就很强。也不存在太严格的设计，以后的扩展和修改都比较容易。

NOSQL数据库里面不存在关系这个概念，如果想实现关系，比如说1对 1，1对多，多对多，你需要用程序来实现，而不是数据库本身实现。另外一个是一个表中可以存放不同类型的数据，简单的说就是每一行数据可以不遵循统一的定义。

比拼2：原子操作

所谓原子操作，就是指一个操作要么成功，要么失败，没有半途而终的。假设说一个处理订单的操作中存在5个步骤，你处理一个订单，提交订单，开始计算数据，随后写入数据库五个表然后，才返回成功，如果有一个失败，那就返回失败。返回失败就意味着撤回之前所有的操作。

这种原子操作在SQL数据库中非常容易实现，它本身就存在这样的机制叫做事务处理机制。这也是我们选择SQL数据库的一个重要参考指标。只要我们在处理数据的过程中存在这样的操作，要么成功，要么失败，那么我们首先要选择的就是SQL数据库。

然而在NOSQL数据库中不存在这样的机制。但是这里追求数据的统一性，比如说你有很多个数据集，这里不称之为数据表了。一旦有一部分修改，你必须更新所有的包含这类数据数据集。

比拼3：效率方面

结构化数据库有很多方式可以提高数据的处理效率，比如说创建索引，使用存储程序stored procedure，一些架构如entity framework，hibernate。但是因为结构化数据库天然的追求数据的完整性，所以他在效率方面还是存在一些瓶颈的。

然而NOSQL非结构化数据库就不存在这样的问题。因为他关心的就是快速的写入数据查询数据。虽然有一些数据的冗余，但是它的写入和查询速度都非常快，尤其是在处理巨量数据的时候，这个优势特别明显，但是如果数据集之间的耦合性非常强的话，因为要做到数据的统一，你需要不停的写入多个相关的数据集，这样也会大大降低效率。

比拼4：扩展潜力

横向扩展和纵向扩展的区别

横向扩展是指用多台服务器服务一个数据库，这种扩展的好处是没有极限，这个对于结构化数据来说，几乎是不可能的。非结构化数据库就可以做到横向扩展。

纵向扩展是指通过提高硬件性能软件性能来提高整体服务器的性能。这种扩展的劣势就是总会达到极限，当然这种扩展对于结构化数据库和非结构化数据库都是适用的。

小结：哪个更好？

这两个数据库的设计初衷是不一样的

结构化数据库的目标是追求数据库的完整性，但是对单机服务器的性能要求比较高。非结构化数据库的设计，追求的是读写的效率和可扩展性，可以实现多机的协作，但是又不注重数据操作的完整性。同时会产生大量的冗余数据。

选择

目前许多大型互联网都会选择MySQL+NOSQL的组合方案，因为SQL和NOSQL都拥有各自的优缺点。

关系型数据库适合存储结构化数据，比如：用户的账号，地址

这些数据通常需要做结构化查询，比如join 这个时候，关系型数据库就要胜出一筹。
这些数据的规模和增长速度通常是可以预期的
事务性，一致性，适合存储比较复杂的数据

NOSQL适合存储非结构化数据，比如文章，评论

这些数据通常用于模糊处理，例如全文搜索，机器学习，适合存储较为简单的数据。

这些数据是海量的，并且增长速度是难以预期的。

按照key获取数据效率很高，但是对于join或者其他结构化查询的支持就比较差。

数据库比较

操作系统

1.进程，线程

进程和线程的区别和联系

拥有资源：进程是资源分配的基本单位，线程是CPU分配和调度的基本单位。进程再执行过程中拥有独立的内存单元，而多个线程共享进程的内存。（资源分配给进程，同一进程的所有线程共享该进程的所有资源，同一个进程的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫做运行时段，用来存放所有的局部变量和临时变量。
调度：线程是实现独立调度的基本单位。在同一进程中，线程的切换不会引起进程的切换，从一个进程中的线程切换到另一个进程的线程的时候，会引起进程切换。
系统开销：由于创建或者撤销进程时，系统都要为之分配或回收资源。如内存空间。I/O设备等。所付出的开销远远大于创建或撤销线程的开销。类似的，在进行进程切换时，涉及当前执行进程的CPU环境的保存以及新调度进程CPU环境的设置。而线程间的切换只需保存和设置少量的寄存器内容，开销很小。
通信：线程间可以通过直接读写同一个进程中的数据进行通信，但是进程通信需要借助IPC(Inter_process).

进程之间的通信方式

进程之间的通信方式主要分为6种。管道，信号量，消息队列，信号，共享内存，套接字。

管道：

管道是半双工的，双方需要通信的时候，需要建立两个管道。管道的实质是一个内存缓冲区，进程以先进先出的方式从缓冲区种获取数据：管道的一端的进程顺序地将进程数据写入缓冲区，另一端地进程则顺序地读取数据，该缓冲区可以看作是一个循环队列，读和写的位置都是自动增加的，一个数据只能被读一次，读出以后在缓冲区都不复存在了。当缓冲区读空或者写满时，就唤醒等待队列中的进程继续读写，管道是最容易实现的。

信号量：

信号量是一个计数器，可以用来控制多个进程对共享资源的访问。信号量只有等待和发送两种操作，等待P(sv),就是将其值减1或者挂起进程，发送V(sv)就是将其值加1 或者将进程恢复运行。

信号：

信号是linux系统中用于进程之间通信或操作的一种机制，信号可以在任何时候发送给另一个进程，而无需知道进程的状态，如果进程并未处于执行状态，则该信号就有由内核保存起来，直到该进程恢复执行并传递给他为止。如果一个信号被进程设置为阻塞状态，则该信号的传递被延迟，直到阻塞被取消时才传递给进程。信号是开销最小的。

共享内存

共享内存允许两个或者多个进程共享一个给定的存储区，这一段存储区可以被两个或者两个以上的进程映射至自身的地址空间中，就像由malloc()分配的内存一样使用。一个进程写入共享内存的信息，可以被其他使用这个共享内存的进程，通过一个简单的内存读取读出，从而实现了进程间的通信。共享内存的效率最高，缺点是没有提供同步机制，需要用锁等其他机制进行同步。

消息队列：

消息队列就是一个消息的链表，是一系列保存在内核中消息的列表。用户进程可以向消息队列添加消息，也可以向消息队列读取信息。消息队列与管道通信相比，其优势是对每个消息指定特定的消息类型，接收的时候不需要按照队列次序，而是可以根据自定义条件来接收特定类型的消息。

可以把消息看作一个记录，具有特定的格式以及特定的优先级。对消息队列有写权限的进程可以向消息队列中按照一定的规则添加新消息，对消息队列有读权限的进程可以从消息队列总读取信息。

套接字

套接口也是一种进程间的通信，与其他通信机制不同的是，他可用于不同设备及其间的进程通信。

进程调度方法

先来先服务（FCFS）：按照作业到达任务队列的顺序调度FCFS是非抢占式的，易于实现，效率不高，性能不好，有利于长作业（CPU繁忙）而不利于短作业（I/O繁忙）
短作业优先（SHF）：次从队列里选择预计时间最短的作业运行。SJF是非抢占式的，优先照顾短作业，具有很好的性能，降低平均等待时间，提高吞吐量。但是不利于长作业，长作业可能一直处于等待状态，出现饥饿现象；完全未考虑作业的优先紧迫程度，不能用于实时系统。
最短剩余时间优先：该算法首先按照作业的服务时间挑选最短的作业运行，在该作业运行期间，一旦有新作业到达系统，并且该新作业的服务时间比当前运行作业的剩余服务时间短，则发生抢占；否则，当前作业继续运行。该算法确保一旦新的短作业或短进程进入系统，能够很快得到处理。
时间片轮转用于分时系统的进程调度。基本思想：系统将CPU处理时间划分为若干个时间片（q），进程按照到达先后顺序排列。每次调度选择队首的进程，执行完1个时间片q后，计时器发出时钟中断请求，该进程移至队尾。以后每次调度都是如此。该算法能在给定的时间内响应所有用户的而请求，达到分时系统的目的。
优先级调度：为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
多级反馈队列：时间片轮转算法对于需要运行较长时间的进程很不友好，假设有一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。因此发展出了多级反馈队列的调度方式。
多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个就绪队列，每个队列时间片大小都不同，例如：1, 2, 4, 8, … 这样呈指数增长。如果进程在第一个队列没执行完，就会被移到下一个队列。
在这种情况下，一个需要 100 个时间片才能执行完的进程只需要交换 7 次就能执行完 (1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 > 100）。

进程执行的过程

进程执行的过程主要分为三大步骤：编译，链接，和装入。

编译：将源代码编译成若干个模块、

链接：将编译后的模块和所需的库函数进行链接。

链接包括三种形式：静态链接，装入时动态链接（将编译后的模块在链接时一边链接一边装入），运行时动态链接（在执行时才把需要的模块进行链接）

装入：将模块装入内存运行

将进程装入内存时，通常使用分页技术，将内存分成固定大小的页，进程分为固定大小的块，加载时将进程的块装入页中，并使用页表记录，减少外部碎片。

通常操作系统还会使用虚拟内存技术将磁盘作为内存的扩充。

多线程和多进程的选择

频繁修改：需要频繁创建和销毁优先使用多线程

计算量：需要大量计算的优先使用多线程，因为需要消耗大量的CPU资源且切换频繁，所以多线程好一些。

相关性：任务间相关性比较强的用多线程，相关性比较弱的用多进程。因为线程之间的数据共享和同步比较简单。

多分布：可能要扩展到多机分布的用多进程，多核分布的用多线程。

协程

协程和微线程是一个东西。

大多数web服务跟互联网服务本质上大部分都是IO密集型服务。IO密集型服务的瓶颈不在于CPU处理速度，而在于尽可能快速的完成高并发，多连接下的数据读写，以前有两种解决方案。

多进程:存在频繁调度切换问题，同时还会存在每个进程资源不共享的问题，需要额外引入进程间通信机制来解决。

多线程：高并发场景下的大量IO等待会导致多线程被频繁挂起和切换，非常消耗系统资源，同时多线程访问共享资源存在竞争问题。

协程就是子程序在执行时中断并转去执行别的子程序，在适当的时候又返回来执行。

这种子程序间的跳转不是函数调用，也不是多线程执行，所以省去了线程切换的开销，效率很高，并且不需要多线程间的锁机制，不会发生变量写冲突。

协程运行在线程之上，当一个协程执行完成后，可以选择主动让出，让另一个协程运行在当前线程之上。协程并没有增加线程数量，只是在线程的基础上通过分时复用的方式运行多个协程，而且协程的切换在用户态完成。切换的代价比线程从用户态到内核态的代价小很多，一般在python，go中会涉及协程的知识，尤其是现在高性能的脚本go。

协程的底层实现

协程进行中断跳转时将函数的上下文存放在其他位置中，而不是存放在函数堆栈里，当处理完其他事情跳转回来的时候，取回上下文继续执行原来的函数。

进程的状态

执行：进程分到CPU时间片，可以执行

就绪：进程已经就绪，只要分配到CPU时间片，随时可以执行

阻塞：有IO时间或者其他资源等待处理

2.多线程相关

多线程线程同步

线程之间通信的两个基本问题是互斥和同步。

线程同步是指线程之间所具有的一种制约关系，一个线程的执行依赖另一个线程的消息，当它没有得到另一个线程的消息时应等待，直到消息到达时才被唤醒。
线程互斥是指对于共享的操作系统资源（指的是广义的”资源”，而不是Windowsli的.res文件，譬如全局变量就是一种共享资源），在各线程访问时的排它性。当有若干个线程都要使用某一共享资源时，任何时刻最多只允许一个线程去使用，其它要使用该资源的线程必须等待，直到占用资源者释放该资源。

C++11多线程之条件变量

条件变量是线程的另外一种有效的同步机制。这些同步对象为线程提供了交互的场所（一个线程给另外一个或者多个线程发送消息），我们指定在条件变量这个地方发生，一个线程用于修改这个变量使其满足其他线程继续往下执行的条件，**其他线程则等待接收条件已经发生改变的信号**，当条件变量同互斥锁一起使用时，条件变量允许线程以一种无竞争的方式等待任意条件发生。
为何引入条件变量
前一章介绍了多线程并发访问共享数据时遇到的数据竞争问题，我们通过互斥锁保护共享数据，保证多线程对共享数据的访问同步有序。但如果一个线程需要等待一个互斥锁的释放，该线程通常需要轮询该互斥锁是否已被释放，我们也很难找到适当的轮训周期，如果轮询周期太短则太浪费CPU资源，如果轮询周期太长则可能互斥锁已被释放而该线程还在睡眠导致发生延误。
这就引入了条件变量来解决该问题：条件变量使用“通知—唤醒”模型，生产者生产出一个数据后通知消费者使用，消费者在未接到通知前处于休眠状态节约CPU资源；当消费者收到通知后，赶紧从休眠状态被唤醒来处理数据，使用了事件驱动模型，在保证不误事儿的情况下尽可能减少无用功降低对资源的消耗。

多线程互斥

同步机制：

事件
信号量
互斥量
临界区

多线程如何保证线程安全

线程安全就是多线程访问时，采用了加锁机制，当一个线程访问该类的某个数据时，进行保护，其他进程不能进行访问直到该线程读取完，其他线程才可以使用。不会出现数据不一致或者数据污染。

说说线程同步方式有哪些？（线程安全性）
线程间的同步方式包括互斥锁、信号量、条件变量、读写锁：
互斥锁：采用互斥对象机制，只有拥有互斥对象的线程才可以访问。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。
信号量：计数器，允许多个线程同时访问同一个资源。
条件变量：通过条件变量通知操作的方式来保持多线程同步。
读写锁：读写锁与互斥量类似。但互斥量要么是锁住状态，要么就是不加锁状态。读写锁一次只允许一个线程写，但允许一次多个线程读，这样效率就比互斥锁要高。

互斥锁的简单实现：

实现mutex最重要的就是实现lock()和unlock()方法。我们保存一个全局变量flag，flag=1表明该锁已经锁住，flag=0表明没有锁住。

实现lock()时，使用一个while循环不断检测flag是否等于1，如果等于1就一直循环，然后将flag设置为1，unlock()方法将flag设置为0

static int flag = 0;
void lock(){
    while(TestAndSet(&flag,1) == 1);
}
void unlock(){
    flag = 0;
}

int TestAndSet(int *ptr,int new){
    int old = *ptr;
    *ptr = new;
    return old;
}

如何保证线程安全以是否需要同步手段分类：

1、互斥同步（阻塞同步）
互斥同步是最常见的一种并发正确性保障手段。同步是指在多线程并发访问共享数据时，保证共享数据在同一时刻只被一个线程使用（同一时刻，只有一个线程在操作共享数据）。而互斥是实现同步的一种手段，临界区、互斥量和信号量都是主要的互斥实现方式。因此，在这4个字里面，互斥是因，同步是果；互斥是方法，同步是目的。
互斥同步最主要的问题就是进行线程阻塞和唤醒所带来的性能问题，因此这种同步也成为阻塞同步。从处理问题的方式上说，互斥同步属于一种悲观的并发策略，总是认为只要不去做正确地同步措施（例如加锁），那就肯定会出现问题，无论共享数据是否真的会出现竞争，它都要进行加锁。
非阻塞同步
随着硬件指令集的发展，出现了基于冲突检测的乐观并发策略，通俗地说，就是先进行操作，如果没有其他线程争用共享数据，那操作就成功了；如果共享数据有争用，产生了冲突，那就再采用其他的补偿措施。（最常见的补偿错误就是不断地重试，直到成功为止），这种乐观的并发策略的许多实现都不需要把线程挂起，因此这种同步操作称为非阻塞同步。

线程池原理

传统多线程方案中我们采用的服务器模型则是一旦接受到请求之后，即创建一个新的线程，由该线程执行任务。任务执行完毕后，线程退出，这就是是“即时创建，即时销毁”的策略。尽管与创建进程相比，创建线程的时间已经大大的缩短，但是如果提交给线程的任务是执行时间较短，而且执行次数极其频繁，那么服务器将处于不停的创建线程，销毁线程的状态。
线程池采用预创建的技术，在应用程序启动之后，将立即创建一定数量的线程(N1)，放入空闲队列中。这些线程都是处于阻塞（Suspended）状态，不消耗CPU，但占用较小的内存空间。当任务到来后，缓冲池选择一个空闲线程，把任务传入此线程中运行。当N1个线程都在处理任务后，缓冲池自动创建一定数量的新线程，用于处理更多的任务。在任务执行完毕后线程也不退出，而是继续保持在池中等待下一次的任务。当系统比较空闲时，大部分线程都一直处于暂停状态，线程池自动销毁一部分线程，回收系统资源。

3.Linux的I/O模型介绍

1.IO过程包括两个阶段

内核从IO设备读取数据进程从内核复制数据

阻塞：调用IO操作的时候，如果缓冲区空或者已经满了，调用的进程或者线程就会处于阻塞状态直到IO可用并完成数据拷贝。

非阻塞：调用IO操作的时候，内核会马上返回结果，如果IO不可用，会返回错误，这种方式下进程需要不断轮询直到IO可用为止，但是当进程从内核拷贝数据时是阻塞的。

IO多路复用就是同时监听多个描述符，一旦某个描述符IO就绪（读就绪或者写就绪），就能够通知进程进行相应的操作。否则就将进程阻塞在select或者epoll语句上。

同步IO :同步IO模型包括阻塞IO，非阻塞IO和IO多路复用。特点就是当进程从内核复制数据的时候都是阻塞的。

异步IO：检测IO是否可用和进程拷贝数据的两个阶段都是不阻塞的，进程可以做其他事情，当IO完成后内核会发给进程一个信号。

2.EPOLL的介绍和了解

Epoll是Linux进行IO多路复用的一种方式，用于在一个线程中监听多个IO源，在IO源可用的时候返回并进行操作。它的特点就是基于事件驱动，性能很高。

epoll将文件描述符拷贝到内核空间后，使用红黑树进行维护。同时向内核注册每个文件描述符的回调函数，当某个文件描述符可读可写的时候，将这个文件描述符加入到就绪链表当中，并唤起进程，返回就绪链表到用户空间，由用户程序进行处理。

epoll有三个系统调用：epoll_create(),epoll_ctrl,epoll_wait()

epoll_create()函数在内核中初始化一个eventpoll对象，同时初始化红黑树和就绪链表。

epoll_ctl()：用于监听文件描述符并进行管理。将文件描述符插入红黑树，或者从红黑树删除，这个过程的事件复杂度是logn，同时向内核注册文件描述符的回调函数。

epoll_wait()：会将进程放到eventpoll等待队列中，将进程阻塞，当某个文件描述符IO可用时，内核通过回调函数将该文件描述符放到就绪链表中，epoll_wait()会将就绪链表中的文件描述符返回到用户空间里。

首先创建一个epoll对象，然后使用epoll_ctl对这个对象进行操作（添加、删除、修改），把需要监控的描述符加进去，这些描述符将会以epoll_event结构体的形式组成一颗红黑树，接着阻塞在epoll_wait，进入大循环，当某个fd上有事件发生时，内核将会把其对应的结构体放入一个链表中，返回有事件发生的链表。

epoll为什么高效：
（1）select，poll实现需要自己不断轮询所有fd集合，直到设备就绪，期间可能要睡眠和唤醒多次交替。而epoll只要判断一下就绪链表是否为空就行了，这节省了大量的CPU时间。
（2）select，poll每次调用都要把fd集合从用户态往内核态拷贝一次，并且要把当前进程往设备等待队列中挂一次，而epoll只要一次拷贝，而且把当前进程往等待队列上挂也只挂一次，这也能节省不少的开销。

3.select poll epoll区别

（1）select==>时间复杂度O(n)
select的方法介绍：select把所有监听的文件描述符拷贝到内核中，挂起进程。当某个文件描述符可读或可写的时候，中断程序唤起进程，select将监听的文件描述符再次拷贝到用户空间，然select后遍历这些文件描述符找到IO可用的文件。下次监控的时候需要再次拷贝这些文件描述符到内核空间。select支持监听的描述符最大数量是1024.
它仅仅知道了，有I/O事件发生了，却并不知道是哪那几个流（可能有一个，多个，甚至全部），我们只能无差别轮询所有流，找出能读出数据，或者写入数据的流，对他们进行操作。所以select具有O(n)的无差别轮询复杂度，同时处理的流越多，无差别轮询时间就越长。
缺点是：
1、单个进程可监视的fd数量被限制，即能监听端口的大小有限。
一般来说这个数目和系统内存关系很大，具体数目可以cat /proc/sys/fs/file-max察看。32位机默认是1024个。64位机默认是2048.
2、对socket进行扫描时是线性扫描，即采用轮询的方法，效率较低：
当套接字比较多的时候，每次select()都要通过遍历FD_SETSIZE个Socket来完成调度,不管哪个Socket是活跃的,都遍历一遍。这会浪费很多CPU时间。如果能给套接字注册某个回调函数，当他们活跃时，自动完成相关操作，那就避免了轮询，这正是epoll与kqueue做的。
3、需要维护一个用来存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大
（2）poll==>时间复杂度O(n)
poll使用链表保存文件描述符，其他的跟select没有什么不同。
poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，但是它没有最大连接数的限制，原因是它是基于链表来存储的.
缺点：
1、大量的fd的数组被整体复制于用户态和内核地址空间之间，而不管这样的复制是不是有意义。
（3）epoll==>时间复杂度O(1)
epoll可以理解为event poll，不同于忙轮询和无差别轮询，epoll会把哪个流发生了怎样的I/O事件通知我们。所以我们说epoll实际上是事件驱动（每个事件关联上fd）的，此时我们对这些流的操作都是有意义的。（复杂度降低到了O(1)）
epoll将文件描述符拷贝到内核空间后使用红黑树进行维护，同时向内核注册每个文件描述符的回调函数，当某个文件描述符可读可写的时候，将这个文件描述符加入到就绪链表里，并唤起进程，返回就绪链表到用户空间。
epoll的优点：
1、没有最大并发连接的限制，能打开的FD的上限远大于1024（1G的内存上能监听约10万个端口）；
2、效率提升，不是轮询的方式，不会随着FD数目的增加效率下降。只有活跃可用的FD才会调用callback函数；
即Epoll最大的优点就在于它只管你“活跃”的连接，而跟连接总数无关，因此在实际的网络环境中，Epoll的效率就会远远高于select和poll。
3、内存拷贝，利用mmap()文件映射内存加速与内核空间的消息传递；即epoll使用mmap减少复制开销。

4.epoll的ET模式和LT模式

ET是边缘触发模式，在这种模式下，只有当描述符从未就绪变成就绪时，内核才会通过epoll进行通知。然后直到下一次变成就绪前，不会再次重复通知。也就是说，如果一次就绪通知之后不对这个描述符进行IO操作导致他变成未就绪，内核也不会发送就绪通知。优点就是只通知一次，减少内核资源浪费，效率高。缺点就是不能保证数据的完整性，有些数据来不及读取可能就会无法取出。

LT是水平触发模式，在这个模式下如果文件描述符IO就绪，内核就会进行通知，如果不对它进行IO操作，只要还有未操作的数据，内核就会进行通知，如果不对它进行IO操作，只要还有未操作的数据，会不停的从内核空间切换到用户空间，资源严重浪费。

5.coredump是什么，怎么才能coredump？

coredump是程序由于异常或者bug在运行时异常退出或者终止，在一定的条件下生成的一个叫做core的文件，这个core文件会记录程序在运行时的内存，寄存器状态，内存指针，和函数堆栈信息等等。对这个文件进行分析可以定位到程序异常的时候对应的堆栈调用信息。

coredump产生的条件：

shell资源控制限制，ulimit-c命令查看shell执行程序时的资源，如果未0，则不会产生coredump。可以用ulimit -c unlimited去设置为不限大小。
读写越界，包括数组访问越界，指针指向错误的内存，字符串读写越界。
使用了线程不安全的函数，读写未加锁保护
错误使用指针转换、
堆栈溢出

6、tcpdump常用命令

用简单的话来定义tcpdump，就是：dump the traffic on a network，根据使用者的定义对网络上的数据包进行截获的包分析工具。 tcpdump可以将网络中传送的数据包的“头”完全截获下来提供分析。它支持针对网络层、协议、主机、网络或端口的过滤，并提供and、or、not等逻辑语句来帮助你去掉无用的信息

STL

C++的STL介绍

C++ STL从广义上来讲包括三类：算法，容器和迭代器

算法包括排序，复制等常用算法，以及不同容器特定的算法。

容器就是数据的存放形式，包括序列式容器和关联式容器，序列式容器就是list和vector等，关联式容器就是set，map等。

迭代器就是在不暴露容器内部结构的情况下，对容器进行遍历。

STL源码中hash表的实现

STL中的hash表就是unordered_map。使用的是哈希进行实现（注意与map的区别）。它记录的键是元素的哈希值，通过对比元素的哈希值来确定元素的值。

unordered_map的底层实现是hashtable，采用开链法（也就是桶）来解决哈希冲突，默认的桶的大小是10。

解决哈希冲突的方式

开放地址方法：
当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
（1）线性探测
按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。　
（2）再平方探测
按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。
（3）伪随机探测
按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。
链式地址法（HashMap的哈希冲突解决方法）
对于相同的值，使用链表进行连接。使用数组存储每一个链表。
优点：
（1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
（2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
（4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
缺点：
指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。
再哈希法：当发生哈希冲突时使用另一个哈希函数计算地址值，直到冲突不再发生。这种方法不易产生聚集，但是增加计算时间，同时需要准备许多哈希函数。
建立公共溢出区：采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突，再采用处理冲突方法处理。

STL中unordered_map和map的区别

unordered_map是用哈希实现的，占用内存比较多，查询速度快，是常数时间复杂度，它内部是无序的，需要实现==操作符。

map底层是红黑树实现的，插入删除查询时间复杂度都是logn，它的内部是有序的，因此需要实现操作符<.

STL中vector的实现

STL的vector是封装了动态数组的顺序容器。不过与动态数组不同的是，vector可以根据需要自动扩大容器的大小。具体策略是每次容量不够用时重新申请一块大小为原来容量两倍的内存，将原容器的元素拷贝至新容器，并释放原空间，返回新空间的指针。

在原来空间不够存储新值时，每次调用push_back都会重新分配新的空间以满足新数据的添加操作。如果在程序中频繁进行这种操作，还是比较耗能的。

vector使用的注意及其原因

如果需要频发插入，最好先指定vector的大小，因为vector在容器的大小不够用的时候会重新申请一块大小为原容器两倍的空间，并将容器的元素拷贝到新容器中，并释放原空间，这个过程是十分耗时和耗内存的。频繁调用push_back()会使得程序花费很多时间在vector扩容上，会变得很慢，这种情况可以考虑使用list。

C++中vector和list的区别

vector和数组类似，拥有一段连续的内存空间。vector申请的是一段连续的内存，当插入新的元素内存不够时，通常以2倍重新申请更大的一块内存，将原来的元素拷贝过去，释放旧空间。因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。

list是由双向链表实现的，因此内存空间是不连续的，只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为O(n),但由于链表的特点，能高效的进行插入和删除。

vector拥有一段连续的内存空间，能够很好的支持随机存取，因此vector::iterator 支持“+”，“+=”，“<”等操作符。list的内存空间是不连续的，不支持随机访问，因为ilst::iterator不支持“+”，“+=”，“<”等操作符。

总之，如果需要高效的随机存取，而不在乎插入和删除的效率，使用vector;
如果需要大量的插入和删除，而不关心随机存取，则应使用list。

string的底层实现

string继承自basic_string，其实是对char进行了封装，封装的string包含了char数组，容量和长度等等属性。

string可以进行动态扩展，在每次扩展的时候，另外申请一块原空间大小两倍的空间，然后将源字符串拷贝过去，并加上新增内容。

set，map和vector的插入复杂度

map，set，multimap and multiset

上述四种容器采用了红黑树实现，红黑树是平衡二叉树的一种，不同操作的时间复杂度近似为：

插入: O(logN)
查看:O(logN)
删除:O(logN)
hash_map, hash_set, hash_multimap, and hash_multiset
上述四种容器采用哈希表实现，不同操作的时间复杂度为：
插入:O(1)，最坏情况O(N)。
查看:O(1)，最坏情况O(N)。
删除:O(1)，最坏情况O(N)。
vector的复杂度
查看：O（1）
插入：O（N）
删除：O（N）
list复杂度
查看：O（N）
插入：O（1）
删除：O（1）

set,map的插入复杂度就是红黑树的插入复杂度，是log(N)。
unordered_set,unordered_map的插入复杂度是常数，最坏是O(N).
vector的插入复杂度是O(N),最坏的情况下（从头插入）就要对所有其他元素进行移动，或者扩容重新拷贝

set是一种关联式容器，特性如下：

set底层以红黑树为底层容器；（底层实现：红黑树）
所得元素的只有key没有value，value就是key；
不允许出现键值重复；
所有元素都会被自动排序
不能通过迭代器来改变set的值，因为set的值就是键

map是一种关联式容器，特性如下：

map以红黑树作为底层容器（底层实现：红黑树）
所有元素都是键key+值value存在
不允许键key重复
所有元素是通过键进行自动排序的
map的键是不能修改的，但是其键对应的值是可以修改的

unordered_map

底层实现：哈希表

map和set为什么要用红黑树实现

红黑树是一种二叉查找树，但在每个节点上增加一个存储为用于表示节点的颜色，可以是红或者黑。通过对任何一条从根到叶子节点的路径上各个节点的着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因此，红黑树是一种弱平衡树，但又相对与要求严格的AVL树来说，他的旋转次数较少，所以对于搜索，插入，删除操作比较多的情况下，通常使用红黑树。

STL里迭代器失效的情况

对于序列式容器(如vector,deque)，序列式容器就是数组式容器，删除当前的iterator会使后面所有元素的iterator都失效。这是因为vector,deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。
对于关联容器(如map, set,multimap,multiset)，删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响。
对于链表式容器(如list)，删除当前的iterator，仅仅会使当前的iterator失效，这是因为list之类的容器，使用了链表来实现，插入、删除一个结点不会对其他结点造成影响。

vector用swap来缩减空间

vector<int> v1;
for(int i=0;i<10000;i++)
	v1.push_back(1);
cout<<"size:"<<v1.size()<<endl;
cout<<"capacity:"<<v1.capacity()<<endl;

//size:10000
//capacity :12138

vector<int>(v1).swap(v1);
//vector<int>(v1)代表用v1初始化一个临时对象；
//.swap(v1)代表将之前的临时对象和v1交换
cout<<"size:"<<v1.size()<<endl;
cout<<"capacity:"<<v1.capacity()<<endl;

//size:10000
//capacity :10000

计算机网络基础

计算机体系模型

各层模型：

七层模型：物理层，数据链路层，网络层，传输层，会话层，应用层

tcp/ ip 四层模型：网络接口层网络层传输层应用层

五层模型：物理层数据链路层网络层传输层应用层

各层常用的协议：

网络层：IP ICMP ARP RARP OSPF IPX RIP IGRP

传输层： TCP UDP

应用层：DNS Telnet SMTP HTTP

展开讲讲各个协议的作用

IP (Internet Protocol 网际协议)是为计算机网络相互连接进行通信而设计的协议。

ARP (Address Resolution Protocol 地址协议)

ICMP(Internet Control Message Protocol 网际控制报文协议)

ICMP 是TCP/IP 模型中网络层的重要成员，ping 和 tracert 是两个常用的网络管理命令。

ping ：用来测试网络可达性

traceroute（路由追踪）：用来检测发出数据包的主机到目标主机之间所经过的网关数量的工具。

IGMP (internet Group Management Protocol)网际组管理协议

路由协议的了解与介绍。

内部网关协议IGP包括RIP，OSPF，和外部网关协议EGP和BGP。

内部网关协议分类：

距离矢量路由协议：

距离矢量是指以距离和方向构成的矢量来通告路由信息。距离按跳数等度量来定义，方向则是下一跳的路由器或送出接口。距离矢量协议通常使用贝尔曼-福特 (Bellman-Ford) 算法来确定最佳路径。尽管贝尔曼-福特算法最终可以累积足够的信息来维护可到达网络的数据库，但路由器无法通过该算法了解网际网络的确切拓扑结构。路由器仅了解从邻近路由器接收到的路由信息。
距离矢量协议适用于以下情形：
（1）网络结构简单、扁平，不需要特殊的分层设计。
（2）管理员没有足够的知识来配置链路状态协议和排查故障。
（3）特定类型的网络拓扑结构，如集中星形（Hub-and-Spoke）网络。
（4）无需关注网络最差情况下的收敛时间。
链路状态路由协议

配置了链路状态路由协议的路由器可以获取所有其它路由器的信息来创建网络的“完整视图”（即拓扑结构）。并在拓扑结构中选择到达所有目的网络的最佳路径（链路状态路由协议是触发更新，就是说有变化时就更新）。
链路状态协议适用于以下情形：
（1）网络进行了分层设计，大型网络通常如此。
（2）管理员对于网络中采用的链路状态路由协议非常熟悉。
（3）网络对收敛速度的要求极高。
RIP：路由信息协议(Route Information Protocol)”的简写，主要传递路由信息，通过每隔30秒广播一次路由表，维护相邻路由器的位置关系，同时根据收到的路由表信息使用动态规划的方式计算自己的路由表信息。RIP是一个距离矢量路由协议,最大跳数为16跳,16跳以及超过16跳的网络则认为目标网络不可达。
OSPF:OSPF(Open Shortest Path First开放式最短路径优先）是一个内部网关协议(Interior Gateway Protocol，简称IGP），用于在单一自治系统（autonomous system,AS）内决策路由。是对链路状态路由协议的一种实现，隶属内部网关协议（IGP），故运作于自治系统内部

ping的过程

ping通过ICMP协议来进行工作。ICMP：网络报文控制协议

首先，ping命令会构建一个ICMP请求数据包，然后由ICMP协议将这个数据包连同目的IP地址，源IP地址一起交给IP协议；
然后IP协议会构建一个IP数据包并在映射表中查找目的IP对应的MAC地址，将其交给数据链路层。
数据链路层会构建一个数据帧，附上源mac地址和目的mac地址发送出去；
目的主机收到数据帧后，会检查数据包上的mac地址和本机mac地址是否相符，如果相符，就把其中的信息提取出来交给IP协议，IP协议提取信息后交给ICMP协议，然后构建一个ICMP应答包，用相同的过程发回去。

DNS的工作过程和原理

DNS解析方式有两种。递归查询和迭代查询

递归查询：用户先向本地域名服务器查询，如果本地域名服务器的缓存没有IP地址映射记录，就向根域名服务器查询，根域名服务器就会向顶级域名服务器查询，顶级域名服务器向权限域名服务器查询，查到结果依次返回。

迭代查询：用户向本地域名服务器查询，如果没有缓存，本地域名服务器会向根域名服务器查询，根域名服务器返回顶级域名服务器的地址，本地域名服务器再向顶级域名服务器查询，得到权限域名服务器的地址，本地域名服务器再向权限域名服务器查询得到结果。

IP寻址的过程（ARP协议工作）

IP寻址的工作原理，（包括本地网络寻址和非本地网络寻址）

本地网络寻址：
本地网络实现IP 寻址，也就是我们所说的同一网段通信过程，现在我们假设有2个主机，他们是属于同一个网段。主机A和主机B，首先主机A通过本机的hosts表或者wins系统或dns系统先将主机B的计算机名转换为ip地址，然后用自己的 ip地址与子网掩码计算出自己所出的网段，比较目的主机B的ip地址与自己的子网掩码，发现与自己是出于相同的网段，于是在自己的ARP缓存中查找是否有主机B 的mac地址，如果能找到就直接做数据链路层封装并且通过网卡将封装好的以太网帧发送有物理线路上去：如果arp缓存中没有主机B的的mac地址，主机A将启动arp协议通过在本地网络上的arp广播来查询主机B的mac地址，获得主机B的mac地址厚写入arp缓存表，进行数据链路层的封装，发送数据。
非本地网络寻址：不同的数据链路层网络必须分配不同网段的Ip地址并且由路由器将其连接起来。主机A通过本机的hosts表或wins系统或dns系统先主机B的计算机名转换为IP地址，然后用自己的Ip地址与子网掩码计算出自己所处的网段，比较目的目的主机B的Ip地址，发现与自己处于不同的网段。于是主机A将知道应该将次数据包发送给自己的缺省网关，即路由器的本地接口。主机A在自己的ARP缓存中查找是否有缺省网关的MAC地址，如果能够找到就直接做数据链路层封装并通过网卡将封装好的以太网数据帧发送到物理线路上去，如果arp缓存表中没有缺省网关的Mac地址，主机A将启动arp协议通过在本地网络上的arp广播来查询缺省网关的mac地址，获得缺省网关的mac地址后写入arp缓存表，进行数据链路层的封装，发送数据。数据帧到达路由器的接受接口后首先解封装，变成ip数据包，对ip 包进行处理，根据目的Ip地址查找路由表，决定转发接口后做适应转发接口数据链路层协议帧的封装，并且发送到下一跳路由器，次过程继续直至到达目的的网络与目的主机。

TCP拥塞控制，算法名字（极其重要）

防止过多的数据注入到网络中，这样可以是网络中的路由器或者链路不致过载，拥塞控制是控制发送者的流量。拥塞控制有四种算法：慢启动，拥塞避免，快速重传、快速恢复。
发送方发送方维持一个拥塞窗口 cwnd ( congestion window )的状态变量。拥塞窗口的大小取决于网络的拥塞程度，并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口和接受窗口的较小值。

慢启动：思路是当主机开始发送数据时，先以较小的拥塞窗口进行发送，然后每次翻倍。即，由小到大（指数级别）增加拥塞窗口的大小。此外，为了防止拥塞窗口cwnd增长速度过快引起网络堵塞，还需设置一个慢启动阈值ssthresh状态变量，当拥塞窗口大于阈值ssthresh时，停止使用慢启动改用拥塞避免算法。
拥塞避免： 让拥塞窗口cwnd慢慢增大，即每经过一个往返时间RTT就让发送方的拥塞窗口cwnd加一。
快速重传： 当发送端连续收到三个重复的ack时，表示该数据段已经丢失，需要重发。此时慢启动阈值ssth变为原来一半，拥塞窗口cwnd变为ssth，然后+1+1的发（每一轮rtt+1）。
快速恢复： 当超过设定时间没有收到某个报文段的ack时，表示网络拥塞，慢启动阈值ssth变为原来一半，拥塞窗口cwnd=1，进入慢启动阶段。

流量控制，采用滑动窗口法存在的问题

定义：流量控制即让发送方发送速率不要过快，让接收方有来得及接收，可以通过TCP报文中的窗口大小字段来控制发送方的发送窗口不大于接收方发回的窗口大小，这样就可以实现流量控制
可能存在的问题： 特殊情况下，接收方没有足够的缓存可以使用，就会发送零窗口大小的报文，此时发送方接收到这个报文后，停止发送。过了一段时间，接收方有了足够的缓存，开始接收数据了，发送了一个非零窗口的报文，这个报文在传输过程中丢失，那么发送方的发送窗口一直为零导致死锁发生。
解决方法： 为了解决这个问题，TCP为每一个连接设定一个持续计时器（persistence timer），只要TCP的一方接收到了对方的零窗口通知，就会启动这个计时器，周期性的发送零窗口探测报文段，对方在确认这个报文时给出现在的窗口大小。（注意：TCP规定，即便是在零窗口状况下，也必须接收以下几种报文段：零窗口探测报文、确认段报文、携带紧急数据的报文段）。
在什么情况下会减慢拥塞窗口增长的速度
1. 到达慢开始门限ssthresh，采用拥塞避免算法；
2. 出现丢包现象，就进入快速恢复；
3. 当连续收到三个重复确认，进入快速重传。

TCP滑动窗口协议

详见：TCP-IP详解：滑动窗口（Sliding Window）
TCP的滑动窗口协议用来控制发送方和接收方的发送速率，避免拥塞的发生。滑动窗口即接收方缓冲区的大小，用来告知发送方对它的接收还有多大的缓存空间。在接收方的滑动窗口已知的情况下，当接收方确认了连续的数据序列之后，发送方的滑动窗口向后滑动，发送下一个数据序列。

TCP的粘包和避免

粘包：因为TCP减少额外开销，采取的是流传输，所以接收端在一次接收的时候有可能一次接收多个包。而TCP粘包就是发送方的若干个数据报到达接收方的时候粘成了一个包，多个包首尾相接无法区分。

导致TCP粘包的原因有三方面：

发送端等待缓冲区满才进行发送，导致粘包
接收方来不及接收缓冲区内的数据，造成粘包
由于TCP协议在发送较小的数据包的时候，会将几个包合成一个包后发送

避免粘包的措施：

发送定长包。如果每个消息的大小都是一样的，那么在接收对方只要累计接收数据，直到数据等于一个定长的数值的时候，将他作为一个消息。

包头加上包体长度。包头是定长的4个字节。说明了包体的长度。接受对等方先接收包头长度，依据包头长度来接收包体。

在数据包之间设置边界，如添加特殊符号\r\n 标记。FTP协议是这么做的。但问题在于如果数据正文中也含有\r\n ，则会误判消息的边界。

使用更加复杂的应用层协议。

TCP封包和拆包

封包：封包就是在发送数据报的时候为每个TCP数据包加上一个包头，将数据报分为包头和包体两个部分。包头是一个固定长度的结构体，里面包含数据包的总长度。

拆包：接收方在接收到报文后提取包头中的长度信息进行截取。

http协议

网页的解析过程与实现方法

浏览器解析服务器响应过程：

首先是html文档解析，浏览器会将html文档生成分析树，也就是DOM树，它由DOM元素以及属性结点组成。

然后浏览器加载过程中如果遇到了外部的css文件或者图片资源，还会另外发送请求来获取css文件和资源，这个请求通常是异步的，不会影响html文档的加载。

如果浏览器在加载时遇到js文件，则会挂起渲染的线程，等js文件加载分析完毕才恢复html的渲染线程。

然后是css解析，将css文件解析为样式表来渲染dom树。

在浏览器中输入url后执行的全部过程

首先是域名解析，客户端使用dns协议将url解析为对应的IP地址。
然后建立TCP连接，客户端与服务器端通过三次握手来建立TCP连接。
接着是http连接，客户端向服务器发送http连接请求，（http连接无需额外连接，直接通过已经建立的TCP连接发送）
服务器对客户端发来的http请求进行处理，并返回响应。
客户端接收http响应时，将结果渲染展示给用户。

网络分片的原因

因为在链路层中帧的大小通常有限制，如在以太网中最大大小（MTU）就是1500字节。如果IP数据包加上头部后超过1500字节，就需要分片。

IP分片和完整IP报文拥有差不多的IP头。16位ID域对于每个分片都是一致的，这样才能在重新组装时识别出来来自同一报文的分片。在IP头中，16标识号唯一记录了一个IP包的ID，具有同一ID的IP分片将会重新组装起来，而13位片位移则记录了某IP分片相对整体某IP分片相对整个IP包的位置，而这两个标志中间的三位标志则标志着该分片后是否还有新的分片。这三个标志就组成了IP分片的所有信息。接收方就可以利用这些信息对IP数据进行重新组织。

http协议和TCP的区别和联系

联系：http是建立在TCP基础上的，当浏览器需要从服务器获取网页数据时，会发出一次http请求。http会通过TCP建立从客户端到服务端的连接通道，当本次请求的数据传输完毕后，http会立即断开TCP连接，这个过程非常短暂。

区别：两个协议位于不同的层次。tcp协议是传输层的，定义了数据传输和连接的规范。http协议是应用层的，定义了数据的内容的规范。

http/1.0和http :1.1的区别

HTTP协议老的标准是http/1.0 ,目前最通用的标准是 HTTP/1.1 。

HTTP1.0 只保持短暂的连接，浏览器的每次请求都需要与服务器建立一个 TCP 连接，但是最新的http/1.0加入了长连接，只需要在客户端给服务器发送的http报文头部加入Connection :keep-alive
HTTP 1.1 支持持久连接，默认进行持久连接，在一个 TCP 连接上可以传送多个 HTTP 请求和响应，减少了建立和关闭连接的消耗和延迟。

http请求的方法

HTTP的请求方法包括GET、POST、PUT、DELETE四种基本方法。
GET和POST的区别：
1. get方法不会修改服务器上的资源，它的查询是没有副作用的，而post有可能会修改服务器上的资源
2. get可以保存为书签，可以用缓存来优化，而post不可以
3. get把请求附在url上，而post把参数附在http包的包体中
4. 浏览器和服务器一般对get方法所提交的url长度有限制，一般是1k或者2k，而对post方法所传输的参数大小限制为80k到4M不等
5. post可以传输二进制编码的信息，get的参数一般只支持ASCII

http状态码含义

-200 - 请求成功
-301 - 资源（网页等）被永久转移到其它URL
-404 - 请求的资源（网页等）不存在
-500 - 内部服务器错误
-400 - 请求无效
-403 - 禁止访问

http和https的区别，由http升级为https需要做哪些操作

区别：

http 是超文本传输协议，信息是明文传输， https 则是具有安全性的 ssl 加密传输协议
http 和 https 使用的是完全不同的连接方式，用的端口也不一样，前者是 80 ，后者是 443
http 的连接很简单，是无状态的； HTTPS 协议是由 SSL+HTTP 协议构建的可进行加密传输、身份认证的网络协议，比http 协议安全。
https 协议需要到 ca 申请证书，一般免费证书较少，因而需要一定费用

http2.0的改动

多路复用允许同时通过单一的http/2连接发起多重的请求-响应消息。

多禁止分帧：在应用层http/2和传输层TCP/UDP 之间增加一个二进制分帧层，将所有传输的信息分割成更小的消息和帧，并对他们采用二进制格式的编码，其中http 1.x的首部信息会被封装到header frame，而相应的request body则封装到data frame里面。二进制分帧主要作用是二进制鲁棒性高，增强了通信的稳定性。首部压缩：http1.x的header由于cookie和user agent很容易膨胀，而且每次都要重复发送。http2.0 encoder来减少需要传输的header大小。

服务端推送：

http2.0能通过push的方式将客户端需要的内容先推送出去。

https的具体实现

SSL是传输层协议

https包括非对称加密和对称加密两个阶段，在客户端和服务器建立连接的时候，使用非对称加密，连接建立以后使用的是对称加密。

客户端使用https的URL访问web服务器，要求与服务器建立SSL连接。

服务器接收到客户端请求后，发送一份公钥给客户端，私钥自己保存。

客户端收到公钥后，将自己生成的对称加密的会话密钥进行加密，并传给网站。

网站收到密文后，用私钥解密出会话密钥。

web服务器利用会话密钥加密与客户端之间的通信，这个过程称为对称加密的过程。

注意：服务器第一次传给客户端的公钥其实是CA对网站信息进行加密的数字证书。

设计模式

工厂方法模式总结

如果Jungle想玩棒球（Baseball），只需要增加一个棒球工厂（BaseballFacory），然后在客户端代码中修改具体工厂类的类名，而原有的类的代码无需修改。由此可看到，相较简单工厂模式，工厂方法模式更加符合开闭原则。工厂方法是使用频率最高的设计模式之一，是很多开源框架和API类库的核心模式。

优点：

工厂方法用于创建客户所需产品，同时向客户隐藏某个具体产品类将被实例化的细节，用户只需关心所需产品对应的工厂；
工厂自主决定创建何种产品，并且创建过程封装在具体工厂对象内部，多态性设计是工厂方法模式的关键；
新加入产品时，无需修改原有代码，增强了系统的可扩展性，符合开闭原则。
缺点：

添加新产品时需要同时添加新的产品工厂，系统中类的数量成对增加，增加了系统的复杂度，更多的类需要编译和运行，增加了系统的额外开销；
工厂和产品都引入了抽象层，客户端代码中均使用的抽象层（AbstractFactory和AbstractSportProduct ），增加了系统的抽象层次和理解难度。
适用环境：

客户端不需要知道它所需要创建的对象的类；
抽象工厂类通过其子类来指定创建哪个对象（运用多态性设计和里氏代换原则）

STL

map和set

map和set都是C++关联容器，其底层实现都是红黑树。由于map和set所开放的各种操作接口，红黑树也都提供了，所以几乎所有map和set的操作行为，都是转调红黑树的操作行为。

map和set的区别在于：

map中的元素是键值对key-value。关键字起到了索引的作用，值则表示与索引相关联的数据，set与之相对就是关键字的简单集合，set中每个元素只包含一个关键字。

set的迭代器是const，不允许修改元素的值。map允许修改value，但不允许修改key。其原因是因为map和set是根据关键字排序来保证具有有序性，如果修改key，首先需要删除key，然后调节平衡，再插入修改后的键值，调节平衡。如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置为const，不允许修改迭代器的值，而map迭代器则不允许修改key值吗，允许修改value值。

map支持下标操作，set不支持下标操作。mao可以用key做下标，map的下标运算符[]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped_type类型默认值的元素至map中，因此下标运算符[]在map应用中需要慎用。只希望确定某个元素是否存在而不希望插入元素时也不应该使用。mapped_type类型没有默认值也不应该使用。如果find能解决尽量用find。

allocator

STL的分配器用于封装STL容器在内存管理上的底层细节。在C++中，其内存配置和释放如下。

new运算分为两个阶段：

数组array和list区别

信号量操作

sem_init

信号量的数据类型为结构sem_t ,它的本质上是一个长整型的树，函数sem_init()用来初始化一个信号量，它的原型为：

extern int sem_init__P((sem_t *__Sem,int __pshared,unsigned int __value));

sem为指向信号量结构的指针，pshared不为0时此信号量在进程间共享，否则只能为当前进程的所有线程共享，value给出了信号量的初始值。

sem_post

函数sem_post(sem_t * sem)用来增加信号量的值，当有线程阻塞在这个信号量上时，调用这个函数会使其中一个线程不再阻塞，选择机制同样是由线程的调度策略决定的。

sem_wait

函数sem_wait(sem_t * sem)被用来阻塞当前线程直到信号量sem的值大于0，解除阻塞后将sem的值减1，表明公共资源经使用后减少。函数sem_trywait(sem_t * sem)是函数sem_wait()的非阻塞版本，它直接将信号量sem的值-1。

sem_destroy

函数sem_destroy(sem_t * sem)用来释放信号量sem

define

#include<bits/stdc++.h>
#define N 6
#define M (N+N)
using namespace std;
int main(){
    int p = M * M ;
    cout << p << endl;
    return 0;
}
//结果144
#define M N+N
//去掉括号结果 6+6*6+6 =48

结构体

结构体大小也遵循内存对齐原则。

#include<bits/stdc++.h>
using namespace std;
struct BOOK
{
    int id;
    char name[20];
};
 
int main(){
    struct BOOK a = {3,"活着"};
    struct BOOK c;
    struct BOOK d;
    strcpy(c.name, "死了");
    struct BOOK b = a;
    cout << b.id << b.name << endl;
    cout << c.id << c.name << endl;
    
    cout << d.id << d.name << endl;

    return 0;
}
//
3活着  直接赋值正确
0死了   id未赋值 id值不确定 字符数组赋值字符串的时候要使用strcpy
2      未赋值,id随机 ，字符数组为空
结构体大小24

布尔

这里（x>y>z）从左往右计算 x>y 为真等于1 ，1>z 为假 false = 0

#include<bits/stdc++.h>
using namespace std;

int main(){
    int x = 3, y = 2, z = 1;
    int ret;
    ret = (x > y > z);
    cout << ret << endl;

    return 0;
}
//0

#if和#ifdef和#ifndef

#define XXX 0
 
// 第一段条件编译
#ifdef XXX
  逻辑1
#else
  逻辑2
#endif
 
// 第二段条件编译
#if XXX
  逻辑1
#else
  逻辑2
#endif

答案：

第一段条件编译逻辑1会被编译进去，因为宏被定义

第二段条件编译逻辑2会被编译进去，因为xxx为0，判断逻辑真假

#if既关心宏是否定义，又关心宏的逻辑的真假
#ifdef(#if defined())、#ifndef(#if !defined())仅仅关心宏是否被定义，不关心宏的逻辑真假

#ifdef 和#ifndef

// 如果定义了macro_name宏就编译代码段1
#ifdef macro_name　　 
    代码段1
#else　　 
    代码段2
#endif
 
// 等价于上面的条件编译指令，如果未定义macro_name宏，就编译代码段1
#ifndef macro_name
    代码段2
#else
    代码段1
#endif

定义优先级

对于int * pa[5]; 的描述，正确的是？（）

pa是一个具有5个元素的指针数组，每个元素是一个int类型的指针；

pa[5]表示某个数组的第5个元素的值；

pa是一个指向数组的指针，所指向的数组是5个int类型的元素；

pa是一个指向某个数组中第5个元素的指针，该元素是int类型的变量；

选项为A 。

解析

看定义记得注意优先级，  int pa[5]，首先[]优先级比*高，所以pa与[]先结合，pa[5]表明pa是一个数组，大小是5，既然知道pa是数组了，接下来就是确认数组元素了，int *表明数组元素是指针; 

int（* p）[5]，首先()优先级比[]高，所以pa先与*结合，*pa表明pa是一个指针，既然知道pa是指针，接下来确认指针指向的数据类型，int [5]表明指针指向大小为5的int型数组。

构造二叉树

前序遍历，中序遍历构造

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
 	TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
    TreeNode(int x,TreeNode *left,TreeNode *right):val(x),left(left),right(right){}
    
};

class Solution{
public:
    TreeNode *buildTree(vector<int> &preorder,vector<int>inorder){
        //迭代法 辅助栈
        if(!preorder.size()){
            return nullptr;
        }
        stack<TreeNode *>st;
        TreeNode *root  = preorder[0];
        st.push(root);
        int inordernum = 0;
        for(int i = 1;i<preorder.size();i++){
            TreeNode *node = st.top();
            if(node->val != inorder[inordernum]){
                node->left = new TreeNode(preorder[i]);
            }
            else{
                while(!st.empty() && st.top()->val == inorder[inordernum]){
                    node = st.top();
                    st.pop();
                    ++inordernum;
                }
                node->right = new TreeNode(preorder[i]);
                st.push(node->right);
            }
        }
        return root;
    }
}

数据库外键主键

CREATE TABLE student(
	sid int NOT NULL AUTO_INCREMENT,
    sname varchar(20) NOT NULL,
    gender varchar(10) NOT NULL,
    PRIMARY KEY(sid)
);
CREATE TABLE course(
	cid int NOT NULL AUTO_INCREMENT,
    cname varchar(20) NOT NULL,
    PRIMARY KEY(cid)
);
CREATE TABLE mark(
	mid int NOT NULL AUTO_INCREMENT,
    sid int NOT NULL,
    cid int NOT NULL,
    PRIMARY KEY(mid),
    FOREIGN KEY(sid) REFERENCES student(sid),
    FOREIGN KEY(cid) REFERENCES course(cid)
);

类构造函数

省略部分代码

// main.cpp
#include "Line.h"
int main()
{
    Line *p = new Line(1, 2, 3, 4);

    cout << "sizeof (p) = " << sizeof (p) << endl;
    cout << "sizeof (Line) = " << sizeof (Line) << endl;
    Point *m = new Point(6, 7);
    Point *n = new Point(8, 9);
    Point aa(1, 2);
    Point bb(3, 4);
    cout << "________________" << endl;
    Point nn(2, 3);
    Point mm = nn;
    cout << "______________________________________" << endl;
    Line li(aa,bb);
    
    Line *q = new Line(m->getX(), m->getY(), n->getX(), n->getY());

    delete p;
    p = nullptr;
    delete q;
    q = nullptr;
    return 0;
}

yxy@ubuntu:~/Linux/construt$ ./main
Point(int x = 1, int y = 2)
Point(int x = 3, int y = 4)
拷贝构造函数 值拷贝
Line(int aX, int aY, int bX, int bY)
sizeof (p) = 8
sizeof (Line) = 16
Point(int x = 6, int y = 7)
Point(int x = 8, int y = 9)
Point(int x = 1, int y = 2)
Point(int x = 3, int y = 4)
________________
Point(int x = 2, int y = 3)
Point(const Point &p:(2, 3)
______________________________________
Point(const Point &p:(1, 2)
Point(const Point &p:(3, 4)
拷贝构造函数 对象拷贝
Line(const Point & pA, const Point &pB)
Point(int x = 6, int y = 7)
Point(int x = 8, int y = 9)
拷贝构造函数 值拷贝
Line(int aX, int aY, int bX, int bY)
~Line()
~Point():(3, 4)
~Point():(1, 2)
~Line()
~Point():(8, 9)
~Point():(6, 7)
~Line()
~Point():(3, 4)
~Point():(1, 2)
~Point():(2, 3)
~Point():(2, 3)
~Point():(3, 4)
~Point():(1, 2)

浅拷贝深拷贝

拷贝构造函数进行的是浅拷贝

析构函数释放内存进行了两次

#include"Array.h"
Array::Array(int count){
    this->count = count;
    Arr = new int[count];
    cout<<"Array()"<<endl;

}
Array::Array(const Array &arr){
    this->count  = arr.count;
    this->Arr = arr.Arr;
    cout<<"Array(const Array &arr)"<<endl;
}
// 析构函数
Array:: ~Array() {
        delete [] Arr;
        Arr = nullptr;
        cout << "~Array(): " << count << endl;
}
void Array:: printAddress() {
        cout << "address: " << Arr << endl;
}
void Array ::setCount(int count) { this->count = count; }
int Array :: getCount() { return count; }

/*
Array()
Array(const Array &arr)
address: 0x614c20
address: 0x614c20
~Array(): 5
*/

//Error in `./main': double free or corruption (fasttop): 0x0000000000614c20 ***

改进：进行深拷贝

方法先申请内存，再赋值

Array(const Array & arr) {
    // 浅拷贝
    this->count = arr.count;
    // 浅拷贝正确用法
    this->Arr = new int[count];
    for (int i = 0; i < count; i++) {
        this->Arr[i] = arr.Arr[i];
    }
    cout << "Array(const Array & arr)" << endl;
}
/*
Array()
Array(const Array &arr)
address: 0x614c20
address: 0x615050
~Array(): 5
~Array(): 5
*/

如果不实现拷贝构造函数，系统将自动生成，并且只能做浅拷贝。
如果类中存在申请内存操作时一定要重载拷贝构造函数。
类中存在指针数据成员时需要使用深拷贝。

指针常量和常量指针

常量指针：

int const * p 和 const int * p相同, * p的值不可以改变，但是可以改变指针的指向的地址。

指针常量：

int * const p ,指针p的地址不可以改变，但可以改变 * p的值。

#include<iostream>
#include<typeinfo>
using namespace std;
int main(){
    const int a = 5;
    /*int *p = &a;
    error:  invalid conversion from ‘const int*’ to ‘int*
    */
    int b = 8;
    int &&c = 9;
    const int *p = &a; //常量指针 不能赋值，可以改变指向地址  p指向常量a的地址是可以的

    int *q = (int *)&a;

    int * const r = &b; //指针常量一般可以赋值 不可以改变指针的地址 
    
    c = 12;  //右值引用的值改变了 
    *r = 11;   //指针常量可以赋值
    *r = c;  //右值引用 c是int类型的值 c==9
    cout << "类型" << typeid(r).name() << "," << typeid(c).name() << endl;
    cout << sizeof(c) << endl;   //c是int类型右值引用 类型大小为4
    cout << sizeof(&c) << endl;   //c是int类型指针 类型大小为8

    /* 
        *p = 10;
    error:  assignment of read-only location * p
    */

    cout << "*p=" << *p << endl;
    cout << "*q=" << *q << endl;
    cout << "*r=" << *r << endl;
    return 0;
}

面试问题总结

Typora激活

2022-05-13 工具

工具

笔试问题总结

2021-10-18 秋季招聘

笔试问题总结