数据结构
数组
代码语言：txt复制哈希表
代码语言：txt复制**哈希表**可以弥补**数组*的一些缺点，所以我们就可以在数组的基础上做一些改动，来实现哈希表。树
img树的种类
无序树
树的任意节点的子节点没有顺序关系。
有序树
树的任意节点的子节点有顺序关系。
字典树
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。 它有3个基本性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。
线索二叉树
在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
二叉树
树的任意节点至多包含两棵子树。 二叉树遍历: 二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。 二叉树的访问次序可以分为四种： 前序遍历 中序遍历 后序遍历 层次遍历
img霍夫曼树
带权路径最短的二叉树称为哈夫曼树或最优二叉树。
二叉查找树（二叉搜索树、二叉排序树、BST）这几个都是别名
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 任意节点的左、右子树也分别为二叉查找树； 没有键值相等的节点。
平衡二叉树
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是BST。
AVL树
在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。 AVL树本质上还是一棵二叉搜索树，它的特点是： 1.本身首先是一棵二叉搜索树。 2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。 也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。 使用场景： AVL树适合用于插入删除次数比较少，但查找多的情况。 也在
Windows进程地址空间管理中得到了使用 旋转的目的是为了降低树的高度，使其平衡
红黑树
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求: 性质1. 节点是红色或黑色。 性质2. 根节点是黑色。 性质3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 使用场景： 红黑树多用于搜索,插入,删除操作多的情况下 红黑树应用比较广泛： 1. 广泛用在
C的STL中。map和set都是用红黑树实现的。 2. 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。 3.epoll在内核中的实现，用红黑树管理事件块 4.nginx中，用红黑树管理timer等
伸展树
伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。 在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法， 在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。 它的优势在于不需要记录用于平衡树的冗余信息。
替罪羊树
替罪羊树是计算机科学中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平摊最坏时间复杂度是O(log n)，搜索节点的最坏时间复杂度是O(log n)。 在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足max(size(son_L),size(son_R))>alpha*size(this)的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。替罪羊树替罪羊树是一棵自平衡二叉搜索树，由ArneAndersson提出。替罪羊树的主要思想就是将不平衡的树压成一个序列,然后暴力重构成一颗平衡的树。
B-tree（B树）
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树： 1、根结点至少有两个子女； 2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1； 3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ； 4、所有的叶子结点都位于同一层。
B树(B-Tree)是一种自平衡的树,它是一种多路搜索树（并不是二叉的），能够保证数据有序。同时它还保证了在查找、插入、删除等操作时性能都能保持在
O(logn)，为大块数据的读写操作做了优化,同时它也可以用来描述外部存储(支持对保存在磁盘或者网络上的符号表进行外部查找)
B 树
B 树是B树的一种变形形式，B 树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B 树定义如下: (1)每个结点至多有m个子女； (2)除根结点外，每个结点至少有m/2个子女，根结点至少有两个子女； (3)有k个子女的结点必有k个关键字。 B 树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。 更适合文件索引系统 原因： 增删文件（节点）时，效率更高，因为B 树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率 使用场景： 文件系统和数据库系统中常用的B/B 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如： Windows：HPFS 文件系统 Mac：HFS，HFS 文件系统 Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统 数据库：ORACLE，MYSQL，SQLSERVER 等中 B树：有序数组 平衡多叉树 B 树：有序数组链表 平衡多叉树
B*树
B树是B 树的变体，在B 树的非根和非叶子结点再增加指向兄弟的指针；B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B 树的1/2）。 B 树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B 树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针； B树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针； 所以，B*树分配新结点的概率比B 树要低，空间使用率更高；
树的遍历
img先序遍历：FCADBEHGM
后序遍历：ABDCHMGEF
中序遍历：ACBDFHEMG
层序遍历：FCEADHGBM，层序遍历一般很少用。先序遍历：先访问根节点，再访问左子树，最后访问右子树。
后序遍历：先左子树，再右子树，最后根节点。
中序遍历：先左子树，再根节点，最后右子树。
层序遍历：每一层从左到右访问每一个算法
复杂度分析
时间复杂度：
空间复杂度：
算法题
数组
链表
两两翻转链表
树
二叉树的序列化和反序列化
排序
img递归
代码语言：txt复制广度(BFS)深度(DFS)优先搜索
代码语言：txt复制广度优先算法的核心思想是：
从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。
这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。计算机网络
网络模型（七层|五层|四层）
七层模型从上到下依次是：
- 应用层：协议有：HTTP FTP TFTP SMTP SNMP DNS TELNET HTTPS POP3 DHCP
- 表示层：数据的表示、安全、压缩。格式有，JPEG、ASCll、DECOIC、加密格式等
- 会话层：建立、管理、终止会话。对应主机进程，指本地主机与远程主机正在进行的会话
- 传输层：定义传输数据的协议端口号，以及流控和差错校验。协议有：TCP UDP，数据包一旦离开网卡即进入网络传输层
- 网络层：进行逻辑地址寻址，实现不同网络之间的路径选择。协议有：ICMP IGMP IP（IPV4 IPV6） ARP RARP
- 数据链路层：建立逻辑连接、进行硬件地址寻址、差错校验等功能。将比特组合成字节进而组合成帧，用MAC地址访问介质，错误发现但不能纠正。
- 物理层：建立、维护、断开物理连接。
除了标准的OSI七层模型以外，常见的网络层次划分还有TCP/IP四层协议以及TCP/IP五层协议
查看源图像
查看源图像TUP & UDP
在这里插入图片描述用户数据报协议 UDP（User Datagram Protocol）
代码语言：txt复制是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部），支持一对一、一对多、多对一和多对多的交互通信。
特性
- 无连接：不需要先建立连接（如三次握手）
- 尽最大努力交付（不可靠交付）
- 面向报文。对于应用层交付下来的报文，不作另外的处理，只添加了头部就向下交付到网络层。因此，UDP报文数据不能太长也不能太短，会造成IP分片过多或资源浪费。
- 没有拥塞控制。 不会因网络的堵塞导致发送的速率降低。因此会用在很多的实时应用中。
- 首部开销小，只有8字节。
在这里插入图片描述传输控制协议 TCP（Transmission Control Protocol）
代码语言：txt复制是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块），每一条 TCP 连接只能是点对点的（一对一）。
特性
- 面向连接，要经过三次握手确定端对端都能接收和发送消息
- 可靠交付。保证无差错、不丢失、不重复、不乱序
- 双全工通信。也就是每一端都有发送和接收缓冲区，应用层在自己合适的时候对缓冲区进行读写
- 面向字节流。流 其实就是一个数据序列，在这里连续的消息是连在一起的，需要接收方知道怎么去辨别。
首部固定部分各字段意义如下：
1） 源端口和目的端口 各占2个字节，分别写入源端口和目的端口。
2） 序号 占4字节。序号范围是【0，2^32 - 1】，共2^32（即4294967296）个序号。序号增加到2^32-1后，下一个序号就又回到0。也就是说，序号使用mod 2^32运算。TCP是面向字节流的。在一个TCP连接中传送的字节流中的每一个字节都按顺序编号。整个要传送的字节流的起始序号必须在连接建立时设置。首部中的序号字段值则是指的是本报文段所发送的数据的第一个字节的序号。例如，一报文段的序号是301，而接待的数据共有100字节。这就表明：本报文段的数据的第一个字节的序号是301，最后一个字节的序号是400。显然，下一个报文段（如果还有的话）的数据序号应当从401开始，即下一个报文段的序号字段值应为401。这个字段的序号也叫“报文段序号”。
3） 确认号 占4字节，是期望收到对方下一个报文段的第一个数据字节的序号。例如，B正确收到了A发送过来的一个报文段，其序号字段值是501，而数据长度是200字节（序号501~700），这表明B正确收到了A发送的到序号700为止的数据。因此，B期望收到A的下一个数据序号是701，于是B在发送给A的确认报文段中把确认号置为701。注意，现在确认号不是501，也不是700，而是701。
总之：若确认号为= N，则表明：到序号N-1为止的所有数据都已正确收到。
4） 数据偏移 占4位，它指出TCP报文段的数据起始处距离TCP报文段的起始处有多远。这个字段实际上是指出TCP报文段的首部长度。由于首部中还有长度不确定的选项字段，因此数据偏移字段是必要的，但应注意，“数据偏移”的单位是32位字（即以4字节的字为计算单位）。由于4位二进制数能表示的最大十进制数字是15，因此数据偏移的最大值是60字节，这也是TCP首部的最大字节（即选项长度不能超过40字节）。
5） 保留 占6位，保留为今后使用，但目前应置为0 。
下面有6个控制位，用来说明本报文段的性质。
6） 紧急URG（URGent） 当URG=1时，表明紧急指针字段有效。它告诉系统此报文段中有紧急数据，应尽快发送（相当于高优先级的数据），而不要按原来的排队顺序来传送。例如，已经发送了很长的一个程序要在远地的主机上运行。但后来发现了一些问题，需要取消该程序的运行，因此用户从键盘发出中断命令。如果不使用紧急数据，那么这两个字符将存储在接收TCP的缓存末尾。只有在所有的数据被处理完毕后这两个字符才被交付接收方的应用进程。这样做就浪费了很多时间。
当URG置为1时，发送应用进程就告诉发送方的TCP有紧急数据要传送。于是发送方TCP就把紧急数据插入到本报文段数据的最前面，而在紧急数据后面的数据仍然是普通数据。这时要与首部中紧急指针（Urgent Pointer）字段配合使用。
7） 确认ACK（ACKnowledgment） 仅当ACK = 1时确认号字段才有效，当ACK = 0时确认号无效。TCP规定，在连接建立后所有的传送的报文段都必须把ACK置为1。
8） 推送 PSH（PuSH） 当两个应用进程进行交互式的通信时，有时在一端的应用进程希望在键入一个命令后立即就能收到对方的响应。在这种情况下，TCP就可以使用推送（push）操作。这时，发送方TCP把PSH置为1，并立即创建一个报文段发送出去。接收方TCP收到PSH=1的报文段，就尽快地（即“推送”向前）交付接收应用进程。而不用再等到整个缓存都填满了后再向上交付。
9） 复位RST（ReSeT） 当RST=1时，表名TCP连接中出现了严重错误（如由于主机崩溃或其他原因），必须释放连接，然后再重新建立传输连接。RST置为1还用来拒绝一个非法的报文段或拒绝打开一个连接。
10） 同步SYN（SYNchronization） 在连接建立时用来同步序号。当SYN=1而ACK=0时，表明这是一个连接请求报文段。对方若同意建立连接，则应在响应的报文段中使SYN=1和ACK=1，因此SYN置为1就表示这是一个连接请求或连接接受报文。
11） 终止FIN（FINis，意思是“完”“终”） 用来释放一个连接。当FIN=1时，表明此报文段的发送发的数据已发送完毕，并要求释放运输连接。
12） 窗口 占2字节。窗口值是【0，2^16-1】之间的整数。窗口指的是发送本报文段的一方的接受窗口（而不是自己的发送窗口）。窗口值告诉对方：从本报文段首部中的确认号算起，接收方目前允许对方发送的数据量（以字节为单位）。之所以要有这个限制，是因为接收方的数据缓存空间是有限的。总之，窗口值作为接收方让发送方设置其发送窗口的依据。
例如，发送了一个报文段，其确认号是701，窗口字段是1000.这就是告诉对方：“从701算起，我（即发送方报文段的一方）的接收缓存空间还可接受1000个字节数据（字节序号是701~1700），你在给我发数据时，必须考虑到这一点。”
总之：窗口字段明确指出了现在允许对方发送的数据量。窗口值经常在动态变化。
13） 检验和 占2字节。检验和字段检验的范围包括首部和数据这两部分。和UDP用户数据报一样，在计算检验和时，要在TCP报文段的前面加上12字节的伪首部。伪首部的格式和UDP用户数据报的伪首部一样。但应把伪首部第4个字段中的17改为6（TCP的协议号是6）；把第5字段中的UDP中的长度改为TCP长度。接收方收到此报文段后，仍要加上这个伪首部来计算检验和。若使用TPv6,则相应的伪首部也要改变。
14） 紧急指针 占2字节。紧急指针仅在URG=1时才有意义，它指出本报文段中的紧急数据的字节数（紧急数据结束后就是普通数据） 。因此，在紧急指针指出了紧急数据的末尾在报文段中的位置。当所有紧急数据都处理完时，TCP就告诉应用程序恢复到正常操作。值得注意的是，即使窗口为0时也可以发送紧急数据。
15） 选项 长度可变，最长可达4字节。当没有使用“选项”时，TCP的首部长度是20字节。TCP和UDP的区别
代码语言：txt复制TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接。
TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付。
Tcp通过校验和，重传控制，序号标识，滑动窗口、确认应答实现可靠传输。如丢包时的重发控制，还可以对次序乱掉的分包进行顺序控制。
UDP具有较好的实时性，工作效率比TCP高，适用于对高速传输和实时性有较高的通信或广播通信。
每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信。
TCP对系统资源要求较多，UDP对系统资源要求较少。TCP 的三次握手和四次挥手
代码语言：txt复制TCP 是一种面向连接的单播协议，在发送数据前，通信双方必须在彼此间建立一条连接。所谓的“连接”，其实是客户端和服务器的内存里保存的一份关于对方的信息，如 IP 地址、端口号等。
TCP 可以看成是一种字节流，它会处理 IP 层或以下的层的丢包、重复以及错误问题。在连接的建立过程中，双方需要交换一些连接的参数。这些参数可以放在 TCP 头部。
TCP 提供了一种可靠、面向连接、字节流、传输层的服务，采用三次握手建立一个连接；采用四次挥手来关闭一个连接。说一下 TCP 粘包是怎么产生的？
代码语言：txt复制①. 发送方产生粘包
采用TCP协议传输数据的客户端与服务器经常是保持一个长连接的状态（一次连接发一次数据不存在粘包），双方在连接不断开的情况下，可以一直传输数据；但当发送的数据包过于的小时，那么TCP协议默认的会启用Nagle算法，将这些较小的数据包进行合并发送（缓冲区数据发送是一个堆压的过程）；这个合并过程就是在发送缓冲区中进行的，也就是说数据发送出来它已经是粘包的状态了。
②. 接收方产生粘包
接收方采用TCP协议接收数据时的过程是这样的：数据到底接收方，从网络模型的下方传递至传输层，传输层的TCP协议处理是将其放置接收缓冲区，然后由应用层来主动获取（C语言用recv、read等函数）；这时会出现一个问题，就是我们在程序中调用的读取数据函数不能及时的把缓冲区中的数据拿出来，而下一个数据又到来并有一部分放入的缓冲区末尾，等我们读取数据时就是一个粘包。（放数据的速度 > 应用层拿数据速度） TCP如何保证可靠性
代码语言：txt复制1. 校验和
TCP检验和的计算与UDP一样，在计算时要加上12byte的伪首部，检验范围包括TCP首部及数据部分，但是UDP的检验和字段为可选的，而TCP中是必须有的。计算方法为：在发送方将整个报文段分为多个16位的段，然后将所有段进行反码相加，将结果存放在检验和字段中，接收方用相同的方法进行计算，如最终结果为检验字段所有位是全1则正确（UDP中也是全为1则正确），否则存在错误。
2. 确认应答与序列号
TCP将每个数据包都进行了编号，这就是序列号。
序列号的作用：
a、保证可靠性（当接收到的数据总少了某个序号的数据时，能马上知道）
b、保证数据的按序到达
c、提高效率，可实现多次发送，一次确认
d、去除重复数据
数据传输过程中的确认应答处理、重发控制以及重复控制等功能都可以通过序列号来实现
TCP通过确认应答机制实现可靠的数据传输。在TCP的首部中有一个标志位——ACK，此标志位表示确认号是否有效。接收方对于按序到达的数据会进行确认，当标志位ACK=1时确认首部的确认字段有效。进行确认时，确认字段值表示这个值之前的数据都已经按序到达了。而发送方如果收到了已发送的数据的确认报文，则继续传输下一部分数据；而如果等待了一定时间还没有收到确认报文就会启动重传机制。
序列号错误示意图
3. 超时重传
当报文发出后在一定的时间内未收到接收方的确认，发送方就会进行重传（通常是在发出报文段后设定一个闹钟，到点了还没有收到应答则进行重传）。
一种情况是发送包丢失了，其基本过程如下：
发送包丢失导致的超时
另一种情况是ACK 丢失，过程如下：
ACK 丢失导致的超时
当接收方接收到重复的数据时就将其丢掉，重新发送ACK。而要识别出重复的数据，前面提到的序列号就起作用了。
重传时间的确定：
重传时间的确定：报文段发出到收到应答中间有一个报文段的往返时间RTT，显然超时重传时间RTO会略大于这个RTT，TCP会根据网络情况动态的计算RTT，即RTO是不断变化的。在Linux中，超时以500ms为单位进行控制，每次判定超时重发的超时时间都是500ms的整数倍。其规律为：如果重发一次仍得不到应答，就等待2500ms后再进行重传，如果仍然得不到应答就等待4500ms后重传，依次类推，以指数形式递增，重传次数累计到一定次数后，TCP认为网络或对端主机出现异常，就会强行关闭连接。
4. 连接管理
连接管理机制即TCP建立连接时的三次握手和断开连接时的四次挥手。
5. 流量控制
接收端处理数据的速度是有限的，如果发送方发送数据的速度过快，导致接收端的缓冲区满，而发送方继续发送，就会造成丢包，继而引起丢包重传等一系列连锁反应。
因此TCP支持根据接收端的处理能力，来决定发送端的发送速度，这个机制叫做流量控制。
在TCP报文段首部中有一个16位窗口长度，当接收端接收到发送方的数据后，在应答报文ACK中就将自身缓冲区的剩余大小，放入16窗口大小中。这个大小随数据传输情况而变，窗口越大，网络吞吐量越高，而一旦接收方发现自身的缓冲区快满了，就将窗口设置为更小的值通知发送方。如果缓冲区满，就将窗口置为0，发送方收到后就不再发送数据，但是需要定期发送一个窗口探测数据段，使接收端把窗口大小告诉发送端。
流量控制示意图
注意：窗口大小不受16位窗口大小限制，在TCP首部40字节选项中还包含一个窗口扩大因子M，实际窗口大小是窗口字段的值左移M位。
6. 拥塞控制
流量控制解决了两台主机之间因传送速率而可能引起的丢包问题，在一方面保证了TCP数据传送的可靠性。然而如果网络非常拥堵，此时再发送数据就会加重网络负担，那么发送的数据段很可能超过了最大生存时间也没有到达接收方，就会产生丢包问题。
为此TCP引入慢启动机制，先发出少量数据，就像探路一样，先摸清当前的网络拥堵状态后，再决定按照多大的速度传送数据。
此处引入一个拥塞窗口：
发送开始时定义拥塞窗口大小为1；每次收到一个ACK应答，拥塞窗口加1；而在每次发送数据时，发送窗口取拥塞窗口与接送段接收窗口最小者。
慢启动：在启动初期以指数增长方式增长；设置一个慢启动的阈值，当以指数增长达到阈值时就停止指数增长，按照线性增长方式增加；线性增长达到网络拥塞时立即“乘法减小”，拥塞窗口置回1，进行新一轮的“慢启动”，同时新一轮的阈值变为原来的一半。
“慢启动”机制可用图表示：
拥塞窗口调整
关于拥塞控制的算法细节，可以参考4. TCP 的那些事儿（下）
6.1. 慢启动
1）连接建好的开始先初始化cwnd = 1，表明可以传一个MSS大小的数据。
2）每当收到一个ACK，cwnd ; 呈线性上升
3）每当过了一个RTT，cwnd = cwnd*2; 呈指数让升
4）还有一个ssthresh（slow start threshold），是一个上限，当cwnd >= ssthresh时，就会进入“拥塞避免算法”（后面会说这个算法）
6.2. 拥塞避免
1）收到一个ACK时，cwnd = cwnd 1/cwnd
2）当每过一个RTT时，cwnd = cwnd 1
这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。很明显，是一个线性上升的算法。
6.3. 快重传
当出现ack超时的时候，需要重传数据包。
sshthresh = cwnd /2
cwnd 重置为 1
进入慢启动过程
TCP认为这种情况太糟糕，反应也很强烈。
快速重传在收到3个duplicate ACK时就开启重传(三次 ack 就认为丢包的原理见关于TCP乱序和重传的问题、TCP 快速重传为什么是三次冗余 ACK)，而不用等到RTO超时。
TCP Reno的实现是：
cwnd = cwnd /2
sshthresh = cwnd
进入快速恢复算法——Fast Recovery
6.4. 快恢复
快速恢复
快速重传和快速恢复算法一般同时使用。快速恢复算法是认为，你还有3个Duplicated Acks说明网络也不那么糟糕，所以没有必要像RTO超时那么强烈。 注意，正如前面所说，进入Fast Recovery之前，cwnd 和 sshthresh已被更新：
cwnd = cwnd /2
sshthresh = cwnd
然后，真正的Fast Recovery算法如下：
cwnd = sshthresh 3 * MSS （3的意思是确认有3个数据包被收到了）
重传Duplicated ACKs指定的数据包
如果再收到 duplicated Acks，那么cwnd = cwnd 1
如果收到了新的Ack，那么，cwnd = sshthresh ，然后就进入了拥塞避免的算法了。
如果你仔细思考一下上面的这个算法，你就会知道，上面这个算法也有问题，那就是——它依赖于3个重复的Acks。注意，3个重复的Acks并不代表只丢了一个数据包，很有可能是丢了好多包。但这个算法只会重传一个，而剩下的那些包只能等到RTO超时，于是，进入了恶梦模式——超时一个窗口就减半一下，多个超时会超成TCP的传输速度呈级数下降，而且也不会触发Fast Recovery算法了。
通常来说，正如我们前面所说的，SACK或D-SACK的方法可以让Fast Recovery或Sender在做决定时更聪明一些，但是并不是所有的TCP的实现都支持SACK（SACK需要两端都支持），所以，需要一个没有SACK的解决方案。而通过SACK进行拥塞控制的算法是FACK（可参见关于TCP乱序和重传的问题）HTTP & HTTPS
HTTP是什么
代码语言：txt复制HTTP（超文本传输协议）是一个基于请求与响应模式的、无状态的、应用层的协议，常基于TCP的连接方式HTTP 常见的状态码，有哪些？
imgHTTPS是什么
代码语言：txt复制基于HTTP的缺点
- 通信使用明文不加密，内容可能被窃听
- 不验证通信方身份，可能遭到伪装
- 无法验证报文完整性，可能被篡改
HTTPS就是HTTP加上SSL加密处理（一般是SSL安全通信线路） 认证 完整性保护操作系统
CPU
代码语言：txt复制进程、线程、协程的概念
代码语言：txt复制进程：
是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念，竞争计算机系统资源的基本单位。
线程：
是进程的一个执行单元，是进程内科调度实体。比进程更小的独立运行的基本单位。线程也被称为轻量级进程。
协程：
是一种比线程更加轻量级的存在。一个线程也可以拥有多个协程。其执行过程更类似于子例程，或者说不带返回值的函数调用。进程和线程的区别
代码语言：txt复制地址空间：线程共享本进程的地址空间，而进程之间是独立的地址空间。
资源：线程共享本进程的资源如内存、I/O、cpu等，不利于资源的管理和保护，而进程之间的资源是独立的，能很好的进行资源管理和保护。
健壮性：多进程要比多线程健壮，一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。
执行过程：每个进程有一个程序运行的入口、顺序执行序列和程序入口，执行开销大。线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，执行开销小
切换时：进程切换时，消耗的资源大，效率高。所以涉及到频繁的切换时，使用线程要好于进程。同样如果要求同时进行并且又要共享某些变量的并发操作，只能用线程不能用进程协程和线程的区别
代码语言：txt复制协程避免了无意义的调度，由此可以提高性能，但程序员必须自己承担调度的责任。同时，协程也失去了标准线程使用多CPU的能力。
线程
相对独立
有自己的上下文
切换受系统控制；
协程
相对独立
有自己的上下文
切换由自己控制，由当前协程切换到其他协程由当前协程来控制。何时使用多进程，何时使用多线程？
代码语言：txt复制对资源的管理和保护要求高，不限制开销和效率时，使用多进程。
要求效率高，频繁切换时，资源的保护管理要求不是很高时，使用多线程。为什么会有线程？
代码语言：txt复制每个进程都有自己的地址空间，即进程空间，在网络或多用户换机下，一个服务器通常需要接收大量不确定数量用户的并发请求，为每一个请求都创建一个进程显然行不通（系统开销大响应用户请求效率低），因此操作系统中线程概念被引进。Liunx
Linux什么命令可以改变文件的属性？
代码语言：txt复制Linux chattr命令用于改变文件属性。
这项指令可改变存放在ext2文件系统上的文件或目录属性，这些属性共有以下8种模式：
a：让文件或目录仅供附加用途。
b：不更新文件或目录的最后存取时间。
c：将文件或目录压缩后存放。
d：将文件或目录排除在倾倒操作之外。
i：不得任意更动文件或目录。
s：保密性删除文件或目录。
S：即时更新文件或目录。
u：预防意外删除。Linux哪个命令可以查看线程？
代码语言：txt复制方法一：PS
在ps命令中，“-T”选项可以开启线程查看。下面的命令列出了由进程号为<pid>的进程创建的所有线程。
1.$ ps -T -p <pid>
方法二： Top
top命令可以实时显示各个线程情况。要在top输出中开启线程查看，请调用top命令的“-H”选项，该选项会列出所有Linux线程。在top运行时，你也可以通过按“H”键将线程查看模式切换为开或关。
1.$ top -H
要让top输出某个特定进程<pid>并检查该进程内运行的线程状况：
2.$ top -H -p <pid>
方法三： Htop
一个对用户更加友好的方式是，通过htop查看单个进程的线程，它是一个基于ncurses的交互进程查看器。该程序允许你在树状视图中监控单个独立线程。
要在htop中启用线程查看，请开启htop，然后按<F2>来进入htop的设置菜单。选择“设置”栏下面的“显示选项”，然后开启“树状视图”和“显示自定义线程名”选项。按<F10>退出设置。
