c++
2020-05-18 11:49:29 16 举报AI智能生成
C++是一种通用的编程语言，支持过程化编程、面向对象编程和泛型编程。它被广泛用于开发软件，包括桌面应用程序、游戏、浏览器和其他系统软件。C++的设计目标是提供一种能以高效、便携的方式编译和执行低级存储器访问的编程语言。 C++语言的主要特点包括：强大的性能，与硬件的直接交互能力，以及高度的可移植性。此外，C++还提供了一些高级特性，如异常处理、命名空间、模板等，使得程序员能够更有效地编写复杂的程序。 尽管C++是一种强大的编程语言，但它也有一些缺点。例如，由于其复杂性和灵活性，学习和掌握C++可能需要大量的时间和精力。此外，C++的错误处理机制可能会使调试变得困难。
作者其他创作
大纲/内容
stl标准库及相关算法
容器（container）
顺序容器
vector(向量)
特征
1.维护一段连续的内存空间，具有固定的起始地址，因而能非常方便地进行随机存取，即 [] 操作符
2.被插入的内存空间不够时，需要重新申请一块足够大的内存并进行内存拷贝，vector每次扩容为原来的两倍，
对小对象来说执行效率高，但如果遇到大对象，执行效率就低了
对小对象来说执行效率高，但如果遇到大对象，执行效率就低了
list（链表）
STL为链表提供的默认容器是class list<>双向链表容器list
List容器的内部结构完全迥异于array、vector，List对象自身提供了两个指针，用来指向第一个和最后一个元素（便于快速找到链表首结点与尾结点，从链表首位插入、删除结点比较高效），每个元素都有两个指针分别指向其前一个元素与后一个元素。如果想要插入新元素、移除指定元素，只需要操作对应的指针即可
list容器由于使用了指针存储元素间的指向关系，相比array和vector等顺序表容器，可以更高效的插入与删除元素。由于不要求元素间连续存储，自然也不需要类似vector的容量调整、空间重分配的操作。同样的，list容器放弃了元素间的邻接关系，自然就不支持下标访问与随机访问了，对链表元素的排序就很不方便（可以在链表插入新元素时，按顺序插入到指定位置，使其插入新元素前后都保持有序状态）
List容器的内部结构完全迥异于array、vector，List对象自身提供了两个指针，用来指向第一个和最后一个元素（便于快速找到链表首结点与尾结点，从链表首位插入、删除结点比较高效），每个元素都有两个指针分别指向其前一个元素与后一个元素。如果想要插入新元素、移除指定元素，只需要操作对应的指针即可
list容器由于使用了指针存储元素间的指向关系，相比array和vector等顺序表容器，可以更高效的插入与删除元素。由于不要求元素间连续存储，自然也不需要类似vector的容量调整、空间重分配的操作。同样的，list容器放弃了元素间的邻接关系，自然就不支持下标访问与随机访问了，对链表元素的排序就很不方便（可以在链表插入新元素时，按顺序插入到指定位置，使其插入新元素前后都保持有序状态）
deque（队列）
特征
1.Deque容器是由一组独立区块（individual blocks，一般一个区块大小为512字节）构成的，第一个区块朝某方向扩展，
最后一个区块朝另一个方向扩展。（如果把两个Vector起点拼接到一起，两个Vector分别能向其中一端变长扩展，组合起来不就可以实现双向变长扩展。）
最后一个区块朝另一个方向扩展。（如果把两个Vector起点拼接到一起，两个Vector分别能向其中一端变长扩展，组合起来不就可以实现双向变长扩展。）
2.（避免扩容时元素的复制，就需要再增加新的地址空间后，能把原地址空间与新地址空间（可称为“区块”）连接起来，每当一端扩容时，再找一个新的独立区块连接到原区块后面）为了管理分段空间deque容器引入了Map数组（可看作多个独立区块的中央控制器），Map是一块连续地址空间，其中每个元素是指向各个独立区块的指针，这些独立区块是deque存储数据的主体，deque容器每创建一个独立区块，都将该区块的首地址存入Map数组的相应数据项中
随机访问的设计
deque容器要想实现对分段连续地址空间的随机访问，迭代器的设计就比Vector复杂得多。在Map和deque块的结构之下，deque使用了两个迭代器M_start和M_finish，对首个deque块和末deque块进行控制访问。迭代器iterator共有4个变量域，包括M_first、M_last、M_cur和M_node。M_node存放当前deque块的Map数据项地址，M_first和M_last分别存放该deque块的首尾元素的地址（M_last实际存放的是deque块的末尾字节的地址），M_cur则存放当前访问的deque双端队列的元素地址。
建议
由于deque容器的迭代器比vector容器的迭代器复杂很多，所以通过deque容器的元素访问和迭代器操作会比vector慢一些。所以C++ Standard建议：如非必要（比如需要经常在首尾两端插入或移除元素，或及时释放不再使用的元素等），优先选择使用Vector容器。
应用场景
比如排队购票系统，对排队者的存储可以采用deque， 支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动 大量的数据，速度慢。
vector与deque的比较
一：vector.at()比deque.at() 效率高，比如vector.at(0)是固定的，deque的开始位置 却是不固定的。
二：如 果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
三：deque支持头部的快速插入与快速移除，这是deque的优点。
二：如 果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
三：deque支持头部的快速插入与快速移除，这是deque的优点。
array（C++11）
Forward List（C++11）
STL既然提供了双向链表容器list，有没有提供单向链表容器呢？之前觉得单向链表的使用不如双向链表那么方便，所以并没有为单向链表单独提高一个容器，从C++11开始才为单向链表专门提供了一个容器forward list，<forward_list>其内部是以singly linked list管理元素的。forward list容器内元素的逻辑结构如下图示（== forward list前向链表== ，即往前面靠近首结点的地方插入移除元素比较高效，省去了不少遍历时间）：
Forward List可以看作一个行为受限的List，只能单向前进，不能走回头路。凡是List不支持的功能，Forward List也不支持。那么，既然已经有了List，为了又提供了一个更鸡肋的Forward List呢？
C++ standard这样描述forward list
我们希望forward list和你自己手写的C-style singly linked
list相较之下没有任何空间或时间上的额外开销，任何性质如果与这个目标相抵触，我们就放弃该性质
由此可见，forward list相比list的优势就是内存占用更少，运行效率更高。凡事有收益就有代价，forward list相较list有着诸多约束，比如只能前向遍历，没有提供指向最后一个元素的指针，自然也不提供在链表末尾插入或删除元素的操作。
class forward_list<>容器跟list容器类似，也提供链表的拼接、合并、反序、移除重复元素等。同样的，forward_list也不适用于算法库中的排序函数，容器自身提供了用于内部元素排序的成员函数forward_list::sort
Forward List可以看作一个行为受限的List，只能单向前进，不能走回头路。凡是List不支持的功能，Forward List也不支持。那么，既然已经有了List，为了又提供了一个更鸡肋的Forward List呢？
C++ standard这样描述forward list
我们希望forward list和你自己手写的C-style singly linked
list相较之下没有任何空间或时间上的额外开销，任何性质如果与这个目标相抵触，我们就放弃该性质
由此可见，forward list相比list的优势就是内存占用更少，运行效率更高。凡事有收益就有代价，forward list相较list有着诸多约束，比如只能前向遍历，没有提供指向最后一个元素的指针，自然也不提供在链表末尾插入或删除元素的操作。
class forward_list<>容器跟list容器类似，也提供链表的拼接、合并、反序、移除重复元素等。同样的，forward_list也不适用于算法库中的排序函数，容器自身提供了用于内部元素排序的成员函数forward_list::sort
关联容器
set（集合）
有序集合
set
Multiset
特征
根据特定的排序准则，自动将元素排序，都是使用红黑树作为其实现的底层数据结构。两者的不同之处在于Multiset使用多重集合，允许元素重复，而Set需要满足元素互异性，每个元素只能出现一次。
红黑树实现，插入、删除、查找元素比较高效，且能实现自动排序。但是自动排序也给Set和Multiset带来一个限制：你不能直接改变元素值，因为这样会打乱原本正确的顺序。因此，要改变元素值，必须先删除旧元素，再插入新元素
无序集合Unordered_set
Unordered Set/Multiset，为了能提供尽可能高的访问效率，都使用hash table作为其实现的底层数据结构.对于每个将被存放的value，hash function会把它映射到hash table内某个bucket(slot)中，每个bucket管理一个单向linked list，内含所有“会造成hash function产生相同数值”的元素。
Unordered Set/Multiset容器使用链表法避免散列冲突。对于每个将被存放的value，hash function会把它映射到hash table内某个bucket(slot)中，每个bucket管理一个单向linked list，内含所有“会造成hash function产生相同数值”的元素
Unordered Set/Multiset容器使用链表法避免散列冲突。对于每个将被存放的value，hash function会把它映射到hash table内某个bucket(slot)中，每个bucket管理一个单向linked list，内含所有“会造成hash function产生相同数值”的元素
其基本原理是：使用一个下标范围比较大的数组来存储元素。把关键字Key通过一个固定的算法函数即所谓的哈希函数（散列函数）转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的list空间里。也可以简单的理解为，按照关键字key为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。
原文链接：https://blog.csdn.net/weixin_41413441/article/details/81607221
原文链接：https://blog.csdn.net/weixin_41413441/article/details/81607221
map（映射）
有序MAP
map
优点
对于map，其底层是基于红黑树实现的，优点如下：
1)有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
2)map的查找、删除、增加等一系列操作时间复杂度稳定，都为logn
1)有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
2)map的查找、删除、增加等一系列操作时间复杂度稳定，都为logn
缺点
缺点如下：
1）查找、删除、增加等操作平均时间复杂度较慢，与n相关
1）查找、删除、增加等操作平均时间复杂度较慢，与n相关
Multimap
无序MAP
Unordered_map
优点
对于unordered_map来说，其底层是一个哈希表，优点如下：
查找、删除、添加的速度快，时间复杂度为常数级O(c)
查找、删除、添加的速度快，时间复杂度为常数级O(c)
缺点
缺点如下：
因为unordered_map内部基于哈希表，以（key,value）对的形式存储，因此空间占用率高
Unordered_map的查找、删除、添加的时间复杂度不稳定，平均为O(c)，取决于哈希函数。极端情况下可能为O(n)
因为unordered_map内部基于哈希表，以（key,value）对的形式存储，因此空间占用率高
Unordered_map的查找、删除、添加的时间复杂度不稳定，平均为O(c)，取决于哈希函数。极端情况下可能为O(n)
为何map和set的插入删除效率
要比其他序列容器高？
要比其他序列容器高？
对于关联容器而言，不需要做内存拷贝和内存移动。map和set容器内的所有元素都是以节点方式来存储的，其节点结构和链表类似，指向父节点和子节点。
因此，在插入的时候只需要稍作变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍作变换后吧指向删除节点的节点的指针指向其他的节点就可以了。
这其中，只涉及到指针的转换，而没有涉及到内存的移动。
因此，在插入的时候只需要稍作变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍作变换后吧指向删除节点的节点的指针指向其他的节点就可以了。
这其中，只涉及到指针的转换，而没有涉及到内存的移动。
容器适配器
栈stack
先进后出
队列queue
优先级队列priority_queue
迭代器（iterator）
vector::iterator 和 array::iterator 可以满足到连续迭代器。
deque::iterator 可以满足到随机访问迭代器（记得它的内存只有部分连续）。
list::iterator 可以满足到双向迭代器（链表不能快速跳转）。
forward_list::iterator 可以满足到前向迭代器（单向链表不能反向遍历）。
deque::iterator 可以满足到随机访问迭代器（记得它的内存只有部分连续）。
list::iterator 可以满足到双向迭代器（链表不能快速跳转）。
forward_list::iterator 可以满足到前向迭代器（单向链表不能反向遍历）。
算法（algorithm）
数据结构与算法
二分查找法
整个查找过程就是通过比较中间值大小，从而在其左部分或右部分查找，其实也是一个递归的过程，可通过递归实现，通常思维思考起来更容易，只是性能上会略差（常数级别）
二叉搜索树（Binary Sort Tree）
特征
- 二分搜索树本质上是一棵二叉树。
- 每个节点的键值大于左孩子
- 每个节点的键值小于右孩子
- 以左右孩子为根的子树仍为二分搜索树
遍历
前序遍历
先访问当前节点，再依次递归访问左右子树
中序遍历
先递归访问左子树，再访问自身，再递归访问右子树
是按照从小到大的顺序进行打印的，所以在进行实际应用时，可使用二分搜索输的中序遍历将元素按照从小到大顺序输出。其原因与二分搜索树定义相关的！
后序遍历
先递归访问左右子树，再访问自身节点
析构释放思想
通过后序遍历来删除节点。先判断节点是否为空，若不为空，则先删除掉其左孩子，再删除掉右孩子，最后毫无顾虑了，删除掉自身。
优势
使得我们在此二叉树上查找某个值就很方便了，从根节点开始，若要寻找的值小于根节点的值，则在左子树上去找，反之则去右子树查找，知道找到与值相同的节点。插入节点也是一样的道理，从根节点出发，所要插入的值，若小于根节点则去左子树寻找该节点所对应的位置，反之去右子树寻找，直到找到该节点合适的位置。
完全二叉树
定义
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，
当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树
除了最后一层外，以上层数的节点都必须存在并且狐妖集中在左侧。
当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树
除了最后一层外，以上层数的节点都必须存在并且狐妖集中在左侧。
特征
它的左孩子序列号都是本身序列号的 2倍
它的右孩子序列号都是本身序列号的 2倍+1
它的右孩子序列号都是本身序列号的 2倍+1
二叉堆（Binary Heap）(最大堆)
定义
在二叉树上任何一个子节点都不大于其父节点。
必须是一棵完全的二叉树，即除了最后一层外，以上层数的节点都必须存在并且狐妖集中在左侧。
必须是一棵完全的二叉树，即除了最后一层外，以上层数的节点都必须存在并且狐妖集中在左侧。
插入元素
移除元素
应用
堆排序
二叉平衡查找树（AVL）
特征
- 左子树与右子树高度之差的绝对值不超过1
- 树的每个左子树和右子树都是AVL树
- 每一个节点都有一个平衡因子（balance factor），任一节点的平衡因子是-1、0、1（每一个节点的平衡因子 = 右子树高度 - 左子树高度）
四种节点调平方式(A为参照节点)
LL旋转
当x位于A的左子树的左子树上时，执行LL旋转
LR旋转
当x位于A的左子树的右子树上时，执行LR旋转
RR旋转
当x位于A的右子树的右子树上时，执行RR旋转
RL旋转
当x位于A的右子树的左子树上时，执行RL旋转
定义
任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树
平衡多路查找树（B-Tree）
B+树
B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的
红黑树
背景
平衡二叉树是严格按照规定执行，每次的插入，删除，都就会引发树的调整．调整的多了，自然会影响树的效率
红黑树设计的是让整棵树左右看起来比较“对称”、比较“平衡”，整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
红黑树可以看作是二叉搜索树和AVL树的一个折中，维持平衡的同时也不需要花太多时间维护数据结构的性质。红黑树在很多地方都有应用
红黑树设计的是让整棵树左右看起来比较“对称”、比较“平衡”，整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
红黑树可以看作是二叉搜索树和AVL树的一个折中，维持平衡的同时也不需要花太多时间维护数据结构的性质。红黑树在很多地方都有应用
为什么红黑树是近似平衡的
将红色节点从红黑树中去掉，之前的二叉树就变成了四叉树，四叉树根本不会高于 log2n
红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开．红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n。仅仅大了一倍
特征
- 性质1. 节点是红色或黑色；
性质2. 根节点是黑色；
性质3 每个叶节点（指树的末端的NIL指针节点或者空节点）是黑色的；
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)；
性质5. 从任一节点到其每个尾端NIL节点或者NULL节点的所有路径都包含相同数目的黑色节点。
（注：上述第3、5点性质中所说的NIL或者NULL结点，并不包含数据，只充当树的路径结束的标志，即此叶结点非常见的叶子结点）
插入
红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上
特殊情况
如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。
如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。
删除
初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足最后一条定义的要求，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点
应用
- C++的STL，map和set都是用红黑树实现的。
- 著名的linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块。
- epoll在内核中的实现，用红黑树管理事件块。
- nginx用红黑树管理timer等。
- Java的TreeMap实现。
Btree 索引
m-way查找树
m-way查找树是是一种树形的存储结构
特征
- 每个节点存储的key数量小于m个
- 每个节点的度小于等于m
- 节点key按顺序排序
- 子树key值要完全小于、大于或介于父节点之间
Btree查找树（多路查找树）
Btree是一种平衡的m-way查找树，它可以利用多个分支节点（子树节点）来减少查询数据时所经历的节点数，从而达到节省存取时间的目的
特征
- 每个节点的key数量小于m个（与m-way相同）
- 除根节点和叶子节点的其他节点存储key的个数必须大于等于m/2
- 所有叶子节点都处于同一层，也就是说所有叶节点具有相同的深度h（树的高度，也意味着树是平衡的）
Btree的查找
必须从根节点开始采用二分法查找，所以时间复杂度为O（logn）
Btree的插入
为了保证树的平衡，如果带插入节点的key数量小于m-1个，则直接插入（不会违反第一条特性），否则，需要将该节点分为两部分，再执行该操作
为什么使用Btree结构
为了达到降低磁盘I/O的目的
索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。
索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。（换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。）
索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。（换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。）
磁盘按需读取，要求每次都会预读的长度一般为页的整数倍， 数据库系统将一个节点的大小设为等于一个页，这样每个节点的元素数据只需要一次I/O就可以完全载入
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O
把B-tree中的m值设的非常大，就会让树的高度降低，有利于一次完全载入
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O
把B-tree中的m值设的非常大，就会让树的高度降低，有利于一次完全载入
应用
文件系统和数据库系统中常用的B/B+ 树，它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作
举例2-3树
定义：多路查找树中的每一个结点都具有两个或者三个孩子我们称之为2-3树
2-3树的所有叶子都在同一层次。
B+tree查找树
B+tree是基于Btree的变体，与Btree不同之处在于以下
- 非叶子节点的key个数等于m
- 每个节点的下级指针为n个（n为关键字个数，而不是n+1个）
- 为所有叶子节点增加一个链指针（注意链上的数据是有序的）
- 所有key都存在叶子节点中
散列表hash table
散列函数
散列函数在散列表中起着非常关键的作用，完成将关键字key映射为散列表元素下标的作用
如何解决散列冲突
开放寻址法（open addressing）
核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？我先讲一个比较简单的探测方法，线性探测（Linear Probing）：当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止，进行插入。
延伸方法
对于开放寻址冲突解决方法，除了线性探测方法之外，还有另外两种比较经典的探测方法，二次探测（Quadratic probing）和双重散列（Double hashing）。
- 所谓二次探测，跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+22…
- 所谓双重散列，意思就是不只要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。
优缺点
开放寻址法的优点：开放寻址法不像链表法，需要拉很多链表。散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。链表法包含指针，序列化起来就没那么容易。
开放寻址法的缺点：用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
总结一下，当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
开放寻址法的缺点：用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
总结一下，当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
链表法（chaining）
链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。在散列表中，
每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中
每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中
当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，
所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除
所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除
优缺点
链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好
链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对 CPU 缓存是不友好的，这方面对于执行效率也有一定的影响
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用跳表或红黑树代替链表。
如何设计散列函数
数据分析法
比如处理手机号码，因为手机号码前几位重复的可能性很大，但是后面几位就比较随机，我们可以取手机号的后四位作为散列值
取模法
如何实现 Word 拼写检查功能。这里面的散列函数，我们就可以这样设计：将单词中每个字母的ASCll 码值“进位”相加，然后再跟散列表的大小求余、取模，作为散列值
散列表的装载因子
当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。探测法装载因子不能超过1
装载因子的计算公式是：
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
如何进行动态扩容
背景
装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。
对于支持动态扩容的散列表，插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，散列表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)。
实际上，对于动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多。如果我们对空间消耗非常敏感，我们可以在装载因子小于某个值之后，启动动态缩容。当然，如果我们更加在意执行效率，能够容忍多消耗一点内存空间，那就可以不用费劲来缩容了。
当散列表的装载因子超过某个阈值时，就需要进行扩容。装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。
实际上，对于动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多。如果我们对空间消耗非常敏感，我们可以在装载因子小于某个值之后，启动动态缩容。当然，如果我们更加在意执行效率，能够容忍多消耗一点内存空间，那就可以不用费劲来缩容了。
当散列表的装载因子超过某个阈值时，就需要进行扩容。装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。
排序算法
选择排序
算法思想
选择排序的实现思想较为简单，例如有一组不规则数字排序{8,6,2,3,1,5,7,4}，需要将它们从小到大进行排序。
- 首先在数组中找出第一名的位置（即最小的数字 1），将它与目前数组中第一名（即数字8）进行交换。
- 此时数组中第一个位置已是最小数字，接着在其余位置中找寻最小数字，与其数组中目前的第二个位置进行交换。
- 后面过程依次类推，直到剩下最后一个位置，已无需排序，已为最大值。
时间复杂度
O(n^2)
插入排序
算法思想
插入排序的思想同生活中整理扑克牌顺序有些类似，将后面的牌按照大小顺序插入到前面来。{8,6,2,3,1,5,7,4}
- 首先第一个元素8，由于它的位置是第一个，所以保持不动。
- 继续看第二个位置的元素是6，比前面的元素8小，两者交换位置。
- 继续看第三个元素2，比第二个元素8小，交换位置，此时元素2是第二个位置，再同第一个元素6进行比较，比它小继而交换位置。
- 后面过程依次类推。
时间复杂度
O(n^2) 但插入排序的内循环在满足条件的情况下是可以提前结束的！而选择排序必须遍历每一次循环
冒泡排序
算法思想
从数组的第一个位置开始两两比较array[index]和array[index+1]，如果array[index]大于array[index+1]则交换array[index]和array[index+1]的位置，止到数组最后一个元素比较完
给定一个数组，我们把数组里的元素通通倒入到水池中，这些元素将通过相互之间的比较，按照大小顺序一个一个地像气泡一样浮出水面。
在进行新一轮的比较中，判断一下在上一轮比较的过程中有没有发生两两交换，如果一次交换都没有发生，就证明其实数组已经排好序了。
在进行新一轮的比较中，判断一下在上一轮比较的过程中有没有发生两两交换，如果一次交换都没有发生，就证明其实数组已经排好序了。
代码示例
void sort(int[] nums) {
//定义一个布尔变量 hasChange，用来标记每轮遍历中是否发生了交换
boolean hasChange = true;
//每轮遍历开始，将 hasChange 设置为 false
for (int i = 0; i < nums.length - 1 && hasChange; i++) {
hasChange = false;
//进行两两比较，如果发现当前的数比下一个数还大，那么就交换这两个数，同时记录一下有交换发生
for (int j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
hasChange = true;
}
}
}
}
//定义一个布尔变量 hasChange，用来标记每轮遍历中是否发生了交换
boolean hasChange = true;
//每轮遍历开始，将 hasChange 设置为 false
for (int i = 0; i < nums.length - 1 && hasChange; i++) {
hasChange = false;
//进行两两比较，如果发现当前的数比下一个数还大，那么就交换这两个数，同时记录一下有交换发生
for (int j = 0; j < nums.length - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
hasChange = true;
}
}
}
}
希尔排序
算法思想
希尔排序，整体思路就是插入排序衍生，插入排序中是每个元素和之前1个元素进行比较，而希尔排序是每个元素和之前的t个元素进行比较，t从一个大值慢慢缩小成1，无序数组渐变为有序数组，时间复杂度发送质变！
时间复杂度为O(n^(3/2))
归并排序
算法思想
- 首先将数组对半划分，分别对左、右边的数组进行排序。
- 还要分别继续划分左、右边的数组，将左边的数组继续对半划分…
- 一直这样划分直到划分的“左边”或“右边”只剩下两个元素，对每一个小部分进行排序。
- 小部分排序完后，进行向上归并，即与旁边的“小组”进行归并（注意：此时各小组的排序已经完成，需要做的步骤是将其归并！），层层往上，直到由多个小组归并成一个大组，归并完成，排序也完成。
O(n*logn)
优化
近乎有序的情况概率较大，此时插入排序有优势。
对左右两个部分进行了递归之后，没有考虑两部分的大小问题，一律进行归并过程。事实上有可能出现正好左部分的最后一个值（即最大值）小于右部分的第一个值（即最小值），这样其实整个数组是有序的，无需再进行归并过程，直接跳过即可。
快速排序
算法思想
- 则每次从当前考虑的数组中选择一个元素，以这个元素为基点，进行处理将此基点放到数组中的合适位置，使得左边的其它元素比此元素小，右边的其它元素比此元素大。
- 之后对左、右边这2个子数组分别使用快速排序的思路进行排序，逐渐递归下去完成整个排序过程。
优化
在原有快速排序中，是固定使用最左侧元素作为标志元素，而希望是尽可能地使用整个数组中间的元素，也许不能准确地定位此中间元素。
双路快速排序法
三路快速排序法
堆排序
二叉堆（Binary Heap
在二叉树上任何一个子节点都不大于其父节点。
必须是一棵完全的二叉树，即除了最后一层外，以上层数的节点都必须存在并且狐妖集中在左侧。
必须是一棵完全的二叉树，即除了最后一层外，以上层数的节点都必须存在并且狐妖集中在左侧。
c++11/14新特性
语言可用性的强化
nullptr 与 constexpr
nullptr 出现的目的是为了替代 NULL。在某种意义上来说，传统 C++ 会把 NULL、0 视为同一种东西，这取决于编译器如何定义 NULL，有些编译器会将 NULL 定义为 ((void*)0)，有些则会直接将其定义为 0。导致函数重载时调用错误
constexpr,C++ 11 提供了 constexpr 让用户显式的声明函数或对象构造函数在编译器会成为常数，这个关键字明确的告诉编译器应该去验证 len_foo 在编译器就应该是一个常数
类型推导
auto
auto自动类型推导，但 不能用于函数传参,还不能用于推导数组类型，最常使用于迭代器推导
（从C++14 开始，还有函数的返回类型推导），不再需要程序员手工声明。但需要说明的是，auto 并没有改变 C++ 是静态类型语言这一事实——使用 auto 的变量（或函数返回值）的类型仍然是编译时就确定了，只不过编译器能自动帮你填充而已。
decltype
decltype 关键字是为了解决 auto 关键字只能对变量进行类型推导的缺陷而出现的。decltype(表达式)
decltype 的用途是获得一个表达式的类型，结果可以跟类型一样使用。它有两个基本用
法：
decltype(变量名) 可以获得变量的精确类型。
decltype(表达式) （表达式不是变量名，但包括 decltype((变量名)) 的情况）可
以获得表达式的引用类型；除非表达式的结果是个纯右值（prvalue），此时结果仍然是值类型。
法：
decltype(变量名) 可以获得变量的精确类型。
decltype(表达式) （表达式不是变量名，但包括 decltype((变量名)) 的情况）可
以获得表达式的引用类型；除非表达式的结果是个纯右值（prvalue），此时结果仍然是值类型。
从 C++14 开始，函数的返回值也可以用 auto 或 decltype(auto) 来声明了。同样的，
用 auto 可以得到值类型，用 auto& 或 auto&& 可以得到引用类型；而用
decltype(auto) 可以根据返回表达式通用地决定返回的是值类型还是引用类型
用 auto 可以得到值类型，用 auto& 或 auto&& 可以得到引用类型；而用
decltype(auto) 可以根据返回表达式通用地决定返回的是值类型还是引用类型
区间迭代
如对数组进行遍历，for(auto &x : array)
初始化列表
C++11 首先把初始化列表的概念绑定到了类型上，并将其称之为 std::initializer_list，允许构造函数或其他函数像参数一样使用初始化列表，这就为类对象的初始化与普通数组和 POD 的初始化方法提供了统一的桥梁，A a {1, 1.1}; // 统一的初始化语法
模板增强
类型别名模板
传统 C++中，typedef 可以为类型定义一个新的名称，但是却没有办法为模板定义一个新的名称。因为，模板不是类型，且typedef 定义别名的语法是：typedef 原名称 新名称;
typedef int (*process)(void *); // 定义了一个返回类型为 int，参数为 void* 的函数指针类型，名字叫做 process
using process = int(*)(void *); // 同上, 更加直观
using process = int(*)(void *); // 同上, 更加直观
可以指定默认模板参数
在 C++11 中提供了一种便利，可以指定模板的默认参数
如：template<typename T = int, typename U = int>
auto add(T x, U y) -> decltype(x+y) {
return x+y;
}
auto add(T x, U y) -> decltype(x+y) {
return x+y;
}
变长参数模板
在 C++11 之前，无论是类模板还是函数模板，都只能按其指定的样子，接受一组固定数量的模板参数；而 C++11 加入了新的表示方法，允许任意个数、任意类别的模板参数，同时也不需要在定义时将参数的个数固定。
参数解包
1. 递归模板函数解包
不断递归的向函数传递模板参数，进而达到递归遍历所有模板参数的目的，但需要定义一个终止递归函数进行处理函数
2. 转发用法 初始化列表展开
typename... Args 声明了一系列的类型——class... 或 typename... 表示后面的标识符代表了一系列的类型。
Args&&... args 声明了一系列的形参 args，其类型是 Args&&。
forward<Args>(args)... 会在编译时实际逐项展开 Args 和 args ，参数有多少项，展开后就是多少项。
Args&&... args 声明了一系列的形参 args，其类型是 Args&&。
forward<Args>(args)... 会在编译时实际逐项展开 Args 和 args ，参数有多少项，展开后就是多少项。
template <>
inline unique_ptr<vector<int>>
make_unique(int&& arg1, int&& arg2) {
return unique_ptr<vector<int>>( new vector<int>(
forward<int>(arg1),
forward<int>(arg2)));
}
inline unique_ptr<vector<int>>
make_unique(int&& arg1, int&& arg2) {
return unique_ptr<vector<int>>( new vector<int>(
forward<int>(arg1),
forward<int>(arg2)));
}
forward<Args>(args)... 为每一项可变模板参数都以同样的形式展开。项
数也允许为零，那样，我们在调用构造函数时也同样没有任何参数。
数也允许为零，那样，我们在调用构造函数时也同样没有任何参数。
面向对象增强
委托构造
C++ 11 引入了委托构造的概念，这使得构造函数可以在同一个类中一个构造函数调用另一个构造函数，从而达到简化代码的目的
继承构造
在传统 C++ 中，构造函数如果需要继承是需要将参数一一传递的，这将导致效率低下。C++ 11 利用关键字 using 引入了继承构造函数的概念，using Base::Base; // 继承构造
显式虚函数重载， override 和 final
当重载虚函数时，引入 override 关键字将显式的告知编译器进行重载，编译器将检查基函数是否存在这样的虚函数，否则将无法通过编译
final 则是为了防止类被继续继承以及终止虚函数继续重载引入的。
显式禁用默认函数
在传统 C++ 中，如果程序员没有提供，编译器会默认为对象生成默认构造函数、复制构造、赋值算符以及析构函数。另外，C++ 也为所有类定义了诸如 new delete 这样的运算符。当程序员有需要时，可以重载这部分函数
编译器产生的默认构造函数与用户定义的构造函数无法同时存在。若用户定义了任何构造函数，编译器将不再生成默认构造函数，但有时候我们却希望同时拥有这两种构造函数，这就造成了尴尬。
C++11 提供了上述需求的解决方案，允许显式的声明采用或拒绝编译器自带的函数。例如：class Magic {
public:
Magic() = default; // 显式声明使用编译器生成的构造
Magic& operator=(const Magic&) = delete; // 显式声明拒绝编译器生成构造
Magic(int magic_number);
}
C++11 提供了上述需求的解决方案，允许显式的声明采用或拒绝编译器自带的函数。例如：class Magic {
public:
Magic() = default; // 显式声明使用编译器生成的构造
Magic& operator=(const Magic&) = delete; // 显式声明拒绝编译器生成构造
Magic(int magic_number);
}
强类型枚举
C++ 11 引入了枚举类（enumaration class），并使用 enum class 的语法进行声明
如：
enum class new_enum : unsigned int {
value1,
value2,
value3 = 100,
value4 = 100
};
enum class new_enum : unsigned int {
value1,
value2,
value3 = 100,
value4 = 100
};
这样定义的枚举实现了类型安全，首先他不能够被隐式的转换为整数，同时也不能够将其与整数数字进行比较，更不可能对不同的枚举类型的枚举值进行比较。但相同枚举值之间如果指定的值相同
类数据成员的默认初始化
C++11 增加了一个语法，允许
在声明数据成员时直接给予一个初始化表达式。这样，当且仅当构造函数的初始化列表中不
包含该数据成员时，这个数据成员就会自动使用初始化表达式进行初始化
在声明数据成员时直接给予一个初始化表达式。这样，当且仅当构造函数的初始化列表中不
包含该数据成员时，这个数据成员就会自动使用初始化表达式进行初始化
语言运行期的强化
Lambda 表达式
[捕获列表](参数列表) mutable(可选) 异常属性 -> 返回类型 {
// 函数体
}
// 函数体
}
泛型 Lambda (C++ 14)
auto 关键字不能够用在参数表里，这是因为这样的写法会与模板的功能产生冲突。但是 Lambda 表达式并不是普通函数，所以 Lambda 表达式并不能够模板化。这就为我们造成了一定程度上的麻烦：参数表不能够泛化，必须明确参数表类型。
幸运的是，这种麻烦只存在于 C++11 中，从 C++14 开始，Lambda 函数的形式参数可以使用 auto 关键字来产生意义上的泛型
幸运的是，这种麻烦只存在于 C++11 中，从 C++14 开始，Lambda 函数的形式参数可以使用 auto 关键字来产生意义上的泛型
函数对象包装器
std::function
C++11 std::function 是一种通用、多态的函数封装，它的实例可以对任何可以调用的目标实体进行存储、复制和调用操作
std::function<int(int)> func2 = [&](int value) -> int {
return 1+value+important;
};
return 1+value+important;
};
std::bind/std::placeholder
std::bind 则是用来绑定函数调用的参数的，它解决的需求是我们有时候可能并不一定能够一次性获得调用某个函数的全部参数，通过这个函数，我们可以将部分调用参数提前绑定到函数身上成为一个新的对象，然后在参数齐全后，完成调用
如：int foo(int a, int b, int c) {
;
}
int main() {
// 将参数1,2绑定到函数 foo 上，但是使用 std::placeholders::_1 来对第一个参数进行占位
auto bindFoo = std::bind(foo, std::placeholders::_1, 1,2);
// 这时调用 bindFoo 时，只需要提供第一个参数即可
bindFoo(1);
}
;
}
int main() {
// 将参数1,2绑定到函数 foo 上，但是使用 std::placeholders::_1 来对第一个参数进行占位
auto bindFoo = std::bind(foo, std::placeholders::_1, 1,2);
// 这时调用 bindFoo 时，只需要提供第一个参数即可
bindFoo(1);
}
右值引用
左值(lvalue, left value)
右值(rvalue, right value)，右边的值，是指表达式结束后就不再存在的临时对象
对标准库的扩充: 新增容器
std::array
std::array 保存在栈内存中，相比堆内存中的 std::vector，我们就能够灵活的访问这里面的元素，从而获得更高的性能；同时正式由于其堆内存存储的特性，有些时候我们还需要自己负责释放这些资源
使用std::array能够让代码变得更加现代，且封装了一些操作函数，同时还能够友好的使用标准库中的容器算法等等，比如 std::sort
std::array 会在编译时创建一个固定大小的数组，std::array 不能够被隐式的转换成指针，使用 std::array 很简单，只需指定其类型和大小即可
std::forward_list
std::forward_list 使用单向链表进行实现，提供了 O(1) 复杂度的元素插入，不支持快速随机访问（这也是链表的特点），也是标准库容器中唯一一个不提供 size() 方法的容器。当不需要双向迭代时，具有比 std::list 更高的空间利用率
std::unordered_set
传统 C++ 中的有序容器 std::map/std::set，这些容器内部通过红黑树进行实现，插入和搜索的平均复杂度均为 O(log(size))。在插入元素时候，会根据 < 操作符比较元素大小并判断元素是否相同，并选择合适的位置插入到容器中。当对这个容器中的元素进行遍历时，输出结果会按照 < 操作符的顺序来逐个遍历。
而无序容器中的元素是不进行排序的，内部通过 Hash 表实现，插入和搜索元素的平均复杂度为 O(constant)，在不关心容器内部元素顺序时，能够获得显著的性能提升。
C++11 引入了两组无序容器：std::unordered_map/std::unordered_multimap 和 std::unordered_set/std::unordered_multiset
而无序容器中的元素是不进行排序的，内部通过 Hash 表实现，插入和搜索元素的平均复杂度为 O(constant)，在不关心容器内部元素顺序时，能够获得显著的性能提升。
C++11 引入了两组无序容器：std::unordered_map/std::unordered_multimap 和 std::unordered_set/std::unordered_multiset
std::tuple
元组基本操作
关于元组的使用有三个核心的函数：
std::make_tuple: 构造元组
std::get: 获得元组某个位置的值
std::tie: 元组拆包
std::make_tuple: 构造元组
std::get: 获得元组某个位置的值
std::tie: 元组拆包
运行期索引
std::get<> 依赖一个编译期的常量，所以下面的方式是不合法的：
int index = 1;
std::get<index>(t);
copy
那么要怎么处理？答案是，标准库做不到。这里介绍一个使用 boost::variant 配合变长模板参数的黑魔法：
提示：使用 boost 只是暂时性的解决方案，variant 已在 C++17 中被纳入标准库 std::variant
int index = 1;
std::get<index>(t);
copy
那么要怎么处理？答案是，标准库做不到。这里介绍一个使用 boost::variant 配合变长模板参数的黑魔法：
提示：使用 boost 只是暂时性的解决方案，variant 已在 C++17 中被纳入标准库 std::variant
元组合并与遍历
合并两个元组，这可以通过 std::tuple_cat 来实现
对标准库的扩充: 智能指针和引用计数
RAII 与引用计数
智能指针借用了RAII技术（Resource Acquisition Is Initialization—使用类来封装资源，在构造函数中完成资源的分配和初始化，在析构函数中完成资源的清理，可以保证正确的初始化和资源释放）对普通指针进行封装，达到智能管理动态内存释放的效果。同样的，C++也针对lock与unlock引入了智能锁lock_guard与unique_lock，同样使用了RAII技术对普通锁进行封装，达到智能管理互斥锁资源释放的效果
智能指针借用了RAII技术（Resource Acquisition Is Initialization—使用类来封装资源，在构造函数中完成资源的分配和初始化，在析构函数中完成资源的清理，可以保证正确的初始化和资源释放）对普通指针进行封装，达到智能管理动态内存释放的效果。同样的，C++也针对lock与unlock引入了智能锁lock_guard与unique_lock，同样使用了RAII技术对普通锁进行封装，达到智能管理互斥锁资源释放的效果
对标准库的扩充: 正则表达式
正则表达式描述了一种字符串匹配的模式。一般使用正则表达式主要是实现下面三个需求：
检查一个串是否包含某种形式的子串；
将匹配的子串替换；
从某个串中取出符合条件的子串。
检查一个串是否包含某种形式的子串；
将匹配的子串替换；
从某个串中取出符合条件的子串。
C++11 提供的正则表达式库操作 std::string 对象，模式 std::regex (本质是 std::basic_regex)进行初始化，通过 std::regex_match 进行匹配，从而产生 std::smatch （本质是 std::match_results 对象）
对标准库的扩充: 语言级线程支持
std::thread
std::mutex/std::unique_lock
std::future/std::packaged_task
std::condition_variable
std::mutex/std::unique_lock
std::future/std::packaged_task
std::condition_variable
std::thread 用于创建一个执行的线程实例，所以它是一切并发编程的基础，使用时需要包含头文件，它提供了很多基本的线程操作，例如get_id()来获取所创建线程的线程 ID，例如使用 join() 来加入一个线程等等
其它杂项
noexcept 的修饰和操作
C++11 将异常的声明简化为以下两种情况：
函数可能抛出任何异常
函数不能抛出任何异常
并使用 noexcept 对这两种行为进行限制，例如：
void may_throw(); // 可能抛出异常
void no_throw() noexcept; // 不可能抛出异常
使用 noexcept 修饰过的函数如果抛出异常，编译器会使用 std::terminate() 来立即终止程序运行。
noexcept 还能用作操作符，用于操作一个表达式，当表达式无异常时，返回 true，否则返回 false
函数可能抛出任何异常
函数不能抛出任何异常
并使用 noexcept 对这两种行为进行限制，例如：
void may_throw(); // 可能抛出异常
void no_throw() noexcept; // 不可能抛出异常
使用 noexcept 修饰过的函数如果抛出异常，编译器会使用 std::terminate() 来立即终止程序运行。
noexcept 还能用作操作符，用于操作一个表达式，当表达式无异常时，返回 true，否则返回 false
字面量
C++11 提供了原始字符串字面量的写法，可以在一个字符串前方使用 R 来修饰这个字符串，同时，将原始字符串使用括号包裹
c++17扩展
非类型模板参数的 auto
std::variant<>
c++17/20新标准
c++17
C++17 是继 C++14 之后，C++ 编程语言 ISO/IEC 标准的下一次修订的非正式名称
编译选项：-std=c++17
如g++ future.cpp -std=c++17 -pthread
如g++ future.cpp -std=c++17 -pthread
if constexpr，能减少不少模板代码， 代码简洁性好了很多
结构化绑定 (Structured Binding)：for (auto [key,value] : my_map) {…}；
lambda的功能更加丰富，参数都能支持自动推导了
pair和tuple的结构化绑定，简直不要太舒服
类模板参数规约 (Class Template Argument Deduction)：用 pair p{1, 2.0}; 替代 pair<int, double>{1, 2.0};；
新支持的folding特性，更是对c++11中可变长参数模板的一次升级，能减少不少不必要的重复代码
折叠表达式 (fold expressions)：用于可变的模板；
另外一块就是pararrel STL了，很多算法都支持多线程并行了， 甚至矢量化，不过要使用的话还是要链接一些外部的一些库，比如intel tbb
内联变量 (inline variables)：允许在头文件中定义变量；
关键字
1.1 constexpr
扩展constexpr使用范围，可用于if语句中，也可用于lambda表达式中。这样if条件确定，else语句就可以不用编译了
1.2 static_assert
扩展static_assert用法，静态断言的显示文本可选。
1.3 auto
扩展auto的推断范围
1.4 typename
扩展用法，允许出现在模板的模板的参数中。
1.5 inline
扩展用法，可用于定义内联变量，功能与内联函数相似。inline可避免函数或变量多重定义的问题，如果已定义相同的函数或变量（且该函数或变量声明为inline），编译器会自动链接到该函数或变量
2 语法
2.1 折叠表达式
用于变长参数模板的解包，只支持各种运算符（和操作符），分左、右折叠
2.2 结构化绑定
用一对包含一个或多个变量的中括号，表示结构化绑定，但是使用结构化绑定时，须用auto关键字，即绑定时声明变量
2.3 允许非类型模板参数进行常量计算
非类型模板参数可传入类的静态成员
2.4 条件分支语句初始化
在if和switch中可进行初始化
2.5 聚合初始化
在初始化对象时，可用花括号进行对其成员进行赋值
2.6 嵌套命名空间
简化多层命名空间的写法
2.7 lambda表达式捕获*this的值
lambda表达式可捕获*this的值，但this及其成员为只读
2.8 枚举[类]对象的构造
可以给枚举[类]对象赋值
2.9 十六进制单精度浮点数字面值
2.10 基于对齐内存的动态内存分配
谈到动态内存分配，少不了new和delete运算符，新标准中的new和delete运算符新增了按照对齐内存值来分配、释放内存空间的功能（即一个新的带对齐内存值的new、delete运算符重载）
2.12 模板类的模板参数自动推导
2.15 改写与继承构造函数
2.17 用auto作为非类型模板参数
当模板参数为非类型时，可用auto自动推导类型
3 宏
3.1 __has_include
判断有没有包含某文件
4 属性
4.1 fallthrough
用于switch语句块内，表示会执行下一个case或default
4.2 nodiscard
可用于类声明、函数声明、枚举声明中，表示函数的返回值没有被接收，在编译时会出现警告。
4.3 maybe_unused
可用于类、typedef、变量、非静态数据成员、函数、枚举或枚举值中。用于抑制编译器对没用实体的警告。即加上该属性后，对某一实体不会发出“没有用”的警告。
C++20的四大新特性
概念（concept）
范围库（Ranges Library）
协程（Coroutines）
模块（Module）
modules不用说，提速编译，简化远古include结构，真正的模块化
还有其他一些小功能
各种constexpr。std::string也能constexpr，还有什么constexpr dynamic_cast，这魔法真够黑的。来跟我念，动态类型转换的常量表达式，无法想象这是拿来干嘛的。c++已经上天了。std::format。c++终于有format了。一个语言30年了才有format你敢信。过程好比单身30年，30年啊，stream撸到怀疑人生。什么<iomanip>、setprecision，这设计出来存心找碴的？operator<=>（飞碟operator，三向比较）。貌似挺有用，只是这符号不是特别喜欢，有向rust靠拢的趋势。std::span。现在已经有gsl::span了，标准化了比较顺手。大小从index_type换成了size_type，我觉的蛮好的，和stl统一。char8_t。utf8专属类型，与char不能混用，编译器层面的支持。蛮好的，utf一家整整齐齐了。heterogeneous lookup。之前map支持transparent comparator，现在unordered_map也有相应功能了，很方便。
链接：https://www.zhihu.com/question/362881111/answer/949909598
链接：https://www.zhihu.com/question/362881111/answer/949909598
内存管理
C++内存模型，内存分配方式是什么
在C++中，内存区分为5个区，分别是堆、栈、自由存储区、全局/静态存储区、常量存储区。malloc在堆上分配的内存，使用free释放内存，而new所申请的内存则是在自由存储区上，使用delete来释放，不过这只是表象。进一步来讲，基本上所有的C++编译器默认使用堆来实现自由存储，即缺省的全局运算符new和delete也会按照malloc和free的方式来被实现，这时藉由new运算符分配的对象，说它在堆上也对，说它在自由存储区上也正确。
所以，new所申请的内存区域在C++中称为自由存储区，如果是通过malloc实现的，那么他也是在堆上的。
所以，new所申请的内存区域在C++中称为自由存储区，如果是通过malloc实现的，那么他也是在堆上的。
设计一个内存池
内存池的原理
内存池的思想是，在真正使用内存之前，预先申请分配一定数量、大小预设的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存，当内存释放后就回归到内存块留作后续的复用，使得内存使用效率得到提升，一般也不会产生不可控制的内存碎片。
算法原理
- 预申请一个内存区chunk，将内存中按照对象大小划分成多个内存块block
- 维持一个空闲内存块链表，通过指针相连，标记头指针为第一个空闲块
- 每次新申请一个对象的空间，则将该内存块从空闲链表中去除，更新空闲链表头指针
- 每次释放一个对象的空间，则重新将该内存块加到空闲链表头
- 如果一个内存区占满了，则新开辟一个内存区，维持一个内存区的链表，同指针相连，头指针指向最新的内存区，新的内存块从该区内重新划分和申请
虚拟内存
虚拟内存中，允许将一个作业分多次调入内存，需要时就调入，不需要的就先放在外存。因此，虚拟内存的实需要建立在离散
分配的内存管理方式的基础上
分配的内存管理方式的基础上
虚拟内存的实现有以下三种方式
#请求分页存储管理
#请求分段存储管理
#请求段页式存储管理
#请求分段存储管理
#请求段页式存储管理
虚拟内存的意义：
一，虚拟内存可以使得物理内存更加高效。虚拟内存使用置换方式，需要的页就置换进来，不需要的置换出去，使得内存中只保存了需要的页，提高了利用率，也避免了不必要的写入与擦除；
二，使用虚拟地址可以使内存的管理更加便捷。在程序编译的时候就会生成虚拟地址，该虚拟地址并不是对应一个物理地址，使得也就极大地减少了地址被占用的冲突，减少管理难度；
三，为了安全性的考虑。在使用虚拟地址的时候，暴露给程序员永远都是虚拟地址，而具体的物理地址在哪里，这个只有系统才了解。这样就提
高了系统的封装性。
二，使用虚拟地址可以使内存的管理更加便捷。在程序编译的时候就会生成虚拟地址，该虚拟地址并不是对应一个物理地址，使得也就极大地减少了地址被占用的冲突，减少管理难度；
三，为了安全性的考虑。在使用虚拟地址的时候，暴露给程序员永远都是虚拟地址，而具体的物理地址在哪里，这个只有系统才了解。这样就提
高了系统的封装性。
c++基础
c++各知识点总结
友元函数和友元类
友元函数是可以直接访问类的私有成员的非成员函数。它是定义在类外的普通函数，它不属于任何类，但需要在类的定义中加以声明，声明时只需在友元的名称前加上关键字friend，其格式如下：
friend 类型 函数名(形式参数);
friend 类型 函数名(形式参数);
基础面试
智能指针
智能指针的设计指导思想raii
智能指针的线程安全性
unique的T[]偏特化
T[]偏特化说到C++模板的偏序原则，说到msvc、gcc、clang的array decay的偏序规则不一致，说到C++模板实例化原理（名称查找、参数推导、参数替换、重载决议），SFINAE，模板元编程
内存模型
建议使用make shared因为make shared的内存模型可能是control block和对象连在一起的、control block为什么要有weak ref count
堆栈的分配
虚拟地址，exec加载，动态链接库，mmap，堆的实现（freelist、分配一块大的33页（好像是、记不住了）、直接mmap），再展开可以说页表、tlb、tlb刷新，进程切换（switch mm、switch to、系统调用int 80过程、调用约定，fork把子进程tss的rax设置为0所以子进程fork返回0），带进程id的tlb，ipc
shared from this的设计思路crtp
crtp说到多态和system F。爬一遍lambda cube，说到dependent type以及C++阉割版的非类型模板参数。再说到递归，为什么system F里的递归就比stlc里的和谐，强在哪。
分类
c++11之前的auto_ptr
使用方式： auto const ptr = std::auto_ptr<int>(new int);
缺陷：auto_ptr重载了等号操作符，控制权可以随便转换，但是只有一个在用，用起来会受到诸多限制，转换之后，旧指针就不能用了
c++11新加的unique_ptr
使用方式：unique_ptr<Base1> base1(new Base1);
unique_ptr<Base1> base2;//但是不能用拷贝构造和等号赋值把base1赋值给base2了
unique_ptr<Base1> base2;//但是不能用拷贝构造和等号赋值把base1赋值给base2了
优势：unique_ptr中的拷贝构造和赋值操作符被删除了，所以也就意味着，他和auto_ptr有区别，控制权唯一，不能随意转换。用法都差不多
左右值引用
左值指的是既能够出现在等号左边也能出现在等号右边的变量
只能出现在等号右边的变量(或表达式)
左值的声明符号为”&”， 为了和左值区分，右值的声明符号为”&&”，两个引号&&是C++ 11提出的一个新的引用类型。记住，这是一个新的类型。默念10次吧
右值引用的意义
直观意义：为临时变量续命，也就是为右值续命，因为右值在表达式结束后就消亡了，如果想继续使用右值，那就会动用昂贵的拷贝构造函数。（关于这部分，推荐一本书《深入理解C++11》）
右值引用是用来支持转移语义的。转移语义可以将资源 ( 堆，系统对象等 ) 从一个对象转移到另一个对象，这样能够减少不必要的临时对象的创建、拷贝以及销毁，能够大幅度提高 C++ 应用程序的性能。临时对象的维护 ( 创建和销毁 ) 对性能有严重影响。
右值引用是用来支持转移语义的。转移语义可以将资源 ( 堆，系统对象等 ) 从一个对象转移到另一个对象，这样能够减少不必要的临时对象的创建、拷贝以及销毁，能够大幅度提高 C++ 应用程序的性能。临时对象的维护 ( 创建和销毁 ) 对性能有严重影响。
C++11 std::move和std::forward
定义
一个声明的右值引用其实是一个左值。这就为我们进行参数转发（传递）造成了问题：
std::move和std::forward本质就是一个转换函数，std::move执行到右值的无条件转换，std::forward执行到右值的有条件转换，在参数都是右值时，二者就是等价的。其实std::move和std::forward就是在C++11基本规则之上封装的语法糖。
std::move和std::forward本质就是一个转换函数，std::move执行到右值的无条件转换，std::forward执行到右值的有条件转换，在参数都是右值时，二者就是等价的。其实std::move和std::forward就是在C++11基本规则之上封装的语法糖。
智能指针借用了RAII技术（Resource Acquisition Is Initialization—使用类来封装资源，在构造函数中完成资源的分配和初始化，在析构函数中完成资源的清理，可以保证正确的初始化和资源释放）对普通指针进行封装，达到智能管理动态内存释放的效果。同样的，C++也针对lock与unlock引入了智能锁lock_guard与unique_lock，同样使用了RAII技术对普通锁进行封装，达到智能管理互斥锁资源释放的效果
你要记住的是
std::move执行到右值的无条件转换。就其本身而言，它没有move任何东西。
std::forward只有在它的参数绑定到一个右值上的时候，它才转换它的参数到一个右值。
std::move和std::forward在运行期都没有做任何事情。
std::forward只有在它的参数绑定到一个右值上的时候，它才转换它的参数到一个右值。
std::move和std::forward在运行期都没有做任何事情。
shared_ptr
特征：内存添加了一个引用计数，每shared_ptr一次，引用计数+1；每次调用析构函数，引用计数减一。直到最后一个智能指针删除，才会释放内存。
注意事项
其实就是和unique_ptr一样可以通过move来切换控制权，这个时候是切换，不是共享了。
2、接下来，还有两个函数：
其实auto_ptr也有，只是一样，没必要截图了）也就是说，auto_ptr和unique_ptr都可以通过move函数转换成shared_ptr类型，当然，一样是切换控制权的形式，即旧的置空。
用法如下：
auto_ptr<Base1> base1(new Base1);
shared_ptr<Base1> base2=move(base1);
2、接下来，还有两个函数：
其实auto_ptr也有，只是一样，没必要截图了）也就是说，auto_ptr和unique_ptr都可以通过move函数转换成shared_ptr类型，当然，一样是切换控制权的形式，即旧的置空。
用法如下：
auto_ptr<Base1> base1(new Base1);
shared_ptr<Base1> base2=move(base1);
weak_ptr
定义
std::weak_ptr是解决shared_ptr循环依赖的问题。解决野指针问题的一个很好的方法。通过使用原始指针，不可能知道引用的数据是否已被释放。相反，通过std::shared_ptr管理数据std::weak_ptr并向用户提供数据，用户可以通过调用expired()或检查数据的有效性lock()。你不能std::shared_ptr单独做到这一点，因为所有std::shared_ptr实例共享数据的所有权，在删除所有实例之前，数据不会std::shared_ptr被删除
优势
weak_ptr用于解决”引用计数”模型循环依赖问题，weak_ptr指向一个对象，并不增减该对象的引用计数器。weak_ptr用于配合shared_ptr使用，并不影响动态对象的生命周期，即其存在与否并不影响对象的引用计数器
作用
weak_ptr更像是shared_ptr的助手：
1、他不像其余三种，可以通过构造函数直接分配对象内存；他必须通过shared_ptr来共享内存。
2、没有重载opreator*和->操作符，也就意味着即使分配到对象，他也没法使用该对象
3、不主动参与引用计数，即，share_ptr释放了，那么weak_ptr所存的对象也释放了。
4、使用成员函数use_count()可以查看当前引用计数，expired()判断引用计数是否为空。
5、weak_ptr观测shared_ptr智能指针，并且在需要时候通过lock函数返回一个shared_ptr智能指针
1、他不像其余三种，可以通过构造函数直接分配对象内存；他必须通过shared_ptr来共享内存。
2、没有重载opreator*和->操作符，也就意味着即使分配到对象，他也没法使用该对象
3、不主动参与引用计数，即，share_ptr释放了，那么weak_ptr所存的对象也释放了。
4、使用成员函数use_count()可以查看当前引用计数，expired()判断引用计数是否为空。
5、weak_ptr观测shared_ptr智能指针，并且在需要时候通过lock函数返回一个shared_ptr智能指针
头文件：#include <memory>
智能指针线程安全问题
高质量面试题
C++为什么要有class？
类是C++用来实现OOP封装、继承和多态的核心机制。C++用虚函数实现多态，用RAII（和析构，异常机制）实现自动资源管理，用拷贝和移动定义资源的复制和转移，进而用隐式成员（Rule of 5，析构，拷贝构造，拷贝赋值，移动构造，移动赋值）来帮助用户省去手写冗余代码，最终达到不多写一个字的资源管理。如果说面向对象的概念已经有些过时了，资源管理却是永不过时的，也是C++从机制上不同于C的最主要一点。有些人写的糟糕C++代码其实是把写面向过程套了一层class的皮、滥用多态让代码纠缠不清、最终既不仅没有简化逻辑，也没有简化资源管理。
为什么在C++里面，一个类的成员函数不能既是 template 又是 virtual 的
原因如下：因为C++ 的编译与链接模型是"分离"的(至少是部分原因吧)
- 从Unix/C开始，==一个C/C++ 程序就可以被分开编译，然后用一个linker链接起来==。这种模型有一个问题，就是==各个编译单元可能对另一个编译单元一无所知==。
- 一个 function template最后到底会被 实例为多少个函数，要等整个程序(所有的编译单元)全部被编译完成才知道。
- 同时，virtual function的实现大多利用了一个"虚函数表"的东西，这种实现中，一个类的内存布局(或者说虚函数表的内存布局)需要在这个类编译完成的时候就被完全确定。
所以，由上面的矛盾可知，C++ 的 member function 不能既是 template 又是 virtual 的
- 从Unix/C开始，==一个C/C++ 程序就可以被分开编译，然后用一个linker链接起来==。这种模型有一个问题，就是==各个编译单元可能对另一个编译单元一无所知==。
- 一个 function template最后到底会被 实例为多少个函数，要等整个程序(所有的编译单元)全部被编译完成才知道。
- 同时，virtual function的实现大多利用了一个"虚函数表"的东西，这种实现中，一个类的内存布局(或者说虚函数表的内存布局)需要在这个类编译完成的时候就被完全确定。
所以，由上面的矛盾可知，C++ 的 member function 不能既是 template 又是 virtual 的
不管是类模板还是函数模板，编译器在看到其定义时只能做最基本的语法检查，真正的类型检查要在实例化（instantiation）的时候才能做
编程思想
OOA
OOP
Object Oriented Programming，OOP，面向对象程序设计
基本原则
OOP 的一条基本原则是计算机程序是由单个能够起到子程序作用的单元或对象组合而成
核心思想
封装
继承
多态
现代C++实战30讲
堆、栈、RAII：C++里该如何管理资源？
堆
C++ 标准里一个相关概念是自由存储区，英文是 free store，特指使用 new 和 delete 来
分配和释放内存的区域。一般而言，这是堆的一个子集：
new 和 delete 操作的区域是 free store
malloc 和 free 操作的区域是 heap
但 new 和 delete 通常底层使用 malloc 和 free 来实现，所以 free store 也是 heap。
分配和释放内存的区域。一般而言，这是堆的一个子集：
new 和 delete 操作的区域是 free store
malloc 和 free 操作的区域是 heap
但 new 和 delete 通常底层使用 malloc 和 free 来实现，所以 free store 也是 heap。
函数如何实现的，包括函数的调用的几种常见调用方式、参数的入栈顺序、内存栈在地址从高向低扩展、栈帧指针和栈顶指针的位置、函数内局部变量在栈中的内存分布、函数调用结束后，调用者和被调用者谁和如何清理栈
自己动手，实现C++的智能指针
智能指针的线程安全问题
右值和移动究竟解决了什么问题？
左值
左值变量有标识符、有地址（类型是右值引用的变量也是一个左值！），可以绑定到左值引用的参数，如 T&。一个常量只能绑定到常左值引
用，如 const T&。
用，如 const T&。
纯右值
纯右值 prvalue 是没有标识符、不可以取地址的表达式，一般也称之为“临时对
象”，如除字符串字面量之外的字面量，如 42、true
象”，如除字符串字面量之外的字面量，如 42、true
C++ 对临时对象有特殊的生命周期延长规则。这条规则是：
如果一个 prvalue 被绑定到一个引用上，它的生命周期则会延长到跟这个引用变量一样
长。
如果一个 prvalue 被绑定到一个引用上，它的生命周期则会延长到跟这个引用变量一样
长。
std::move(ptr) 将亡值
作用是把一个左值引用强制转换成一个右值引用，而并不改变其内容。
从实用的角度，在我们这儿 std::move(ptr1) 等价
于 static_cast<smart_ptr<shape>&&>(ptr1)。因此，std::move(ptr1) 的结果
是指向 ptr1 的一个右值引用
从实用的角度，在我们这儿 std::move(ptr1) 等价
于 static_cast<smart_ptr<shape>&&>(ptr1)。因此，std::move(ptr1) 的结果
是指向 ptr1 的一个右值引用
std::move(ptr1) 看作是一个有名字的右值。为了跟无名的纯右值 prvalue
相区别，C++ 里目前就把这种表达式叫做 xvalue。跟左值 lvalue 不同，xvalue 仍然是不
1314151617181920 { ptr_ = other.ptr_; if (ptr_) { shared_count_ = other.shared_count_; other.ptr_ = nullptr; } } 复制代码
12 smart_ptr<shape> ptr1{new circle()}; smart_ptr<shape> ptr2 = std::move(ptr1);
能取地址的
相区别，C++ 里目前就把这种表达式叫做 xvalue。跟左值 lvalue 不同，xvalue 仍然是不
1314151617181920 { ptr_ = other.ptr_; if (ptr_) { shared_count_ = other.shared_count_; other.ptr_ = nullptr; } } 复制代码
12 smart_ptr<shape> ptr1{new circle()}; smart_ptr<shape> ptr2 = std::move(ptr1);
能取地址的
生命期延长规则只对 prvalue 有效，而对 xvalue 无效。如果由于
某种原因，prvalue 在绑定到引用以前已经变成了 xvalue，那生命期就不会延长。不注意
这点的话，代码就可能会产生隐秘的 bug
某种原因，prvalue 在绑定到引用以前已经变成了 xvalue，那生命期就不会延长。不注意
这点的话，代码就可能会产生隐秘的 bug
引用坍缩和完美转发
1. 是不是看到 T&，就一定是个左值引用？
2. 是不是看到 T&&，就一定是个右值引用？
对于前者的回答是“是”，对于后者的回答为“否”
2. 是不是看到 T&&，就一定是个右值引用？
对于前者的回答是“是”，对于后者的回答为“否”
如果 T 是左值引用，那 T&& 的结果仍然是左值引用——即 type& && 坍缩成了
type&。
如果 T 是一个实际类型，那 T&& 的结果自然就是一个右值引用。
type&。
如果 T 是一个实际类型，那 T&& 的结果自然就是一个右值引用。
std::forward
为在 T 是模板参数时，T&& 的作用主要是保持值类别进行转发，它有个名字就叫“转发
引用”（forwarding reference）。因为既可以是左值引用，也可以是右值引用，它也曾
经被叫做“万能引用”（universal reference）
引用”（forwarding reference）。因为既可以是左值引用，也可以是右值引用，它也曾
经被叫做“万能引用”（universal reference）
完美转发，使其左值的仍然是左值，右值的仍然是右值。这个功能在 C++ 标准库中已经提供
了，叫 std::forward。（类型是右值引用的变量也是一个左值，右值引用变量仍然会匹配到左值引用上去，因此使用forward可以使右值仍然为右值）它和 std::move 一样都是利用引用坍缩机制来实现
了，叫 std::forward。（类型是右值引用的变量也是一个左值，右值引用变量仍然会匹配到左值引用上去，因此使用forward可以使右值仍然为右值）它和 std::move 一样都是利用引用坍缩机制来实现
变长模板：forward<Args>(args)... 会在编译时实际逐项展开 Args 和 args ，参数有多少
项，展开后就是多少项。
项，展开后就是多少项。
函数式编程：一种越来越流行的编程范式
特点：会影响函数结果的只是函数的参数，没有对环境的依赖
返回的结果就是函数执行的唯一后果，不产生对环境的其他影响
返回的结果就是函数执行的唯一后果，不产生对环境的其他影响
高阶函数
既然函数（对象）可以被传递、使用和返回，自然就有函数会接受函数作为参数或者把函数
作为返回值，这样的函数就被称为高阶函数
作为返回值，这样的函数就被称为高阶函数
常见的三个：map（映射）、reduce（归并）和 filter（过
滤）。
滤）。
Map 在 C++ 中的直接映射是 transform（在 <algorithm> 头文件中提供）。它所做的
事情也是数学上的映射，把一个范围里的对象转换成相同数量的另外一些对象。这个函数的
基本实现非常简单，但这是一种强大的抽象，在很多场合都用得上。
事情也是数学上的映射，把一个范围里的对象转换成相同数量的另外一些对象。这个函数的
基本实现非常简单，但这是一种强大的抽象，在很多场合都用得上。
Reduce 在 C++ 中的直接映射是 accumulate（在 <numeric> 头文件中提供）。它的功
能是在指定的范围里，使用给定的初值和函数对象，从左到右对数值进行归并。在不提供函
数对象作为第四个参数时，功能上相当于默认提供了加法函数对象，这时相当于做累加；提
供了其他函数对象时，那当然就是使用该函数对象进行归并了。
能是在指定的范围里，使用给定的初值和函数对象，从左到右对数值进行归并。在不提供函
数对象作为第四个参数时，功能上相当于默认提供了加法函数对象，这时相当于做累加；提
供了其他函数对象时，那当然就是使用该函数对象进行归并了。
Filter 的功能是进行过滤，筛选出符合条件的成员。它在当前 C++（C++20 之前）里的映
射可以认为有两个：copy_if 和 partition。这是因为在 C++20 带来 ranges 之前，在
C++ 里实现惰性求值不太方便。上面说的两个函数里，copy_if 是把满足条件的元素拷贝
到另外一个迭代器里；partition 则是根据过滤条件来对范围里的元素进行分组，把满足
条件的放在返回值迭代器的前面。另外，remove_if 也有点相近，通常用于删除满足条件
的元素。它确保把不满足条件的元素放在返回值迭代器的前面（但不保证满足条件的元素在
函数返回后一定存在），然后你一般需要使用容器的 erase 成员函数来将待删除的元素真
正删除。
射可以认为有两个：copy_if 和 partition。这是因为在 C++20 带来 ranges 之前，在
C++ 里实现惰性求值不太方便。上面说的两个函数里，copy_if 是把满足条件的元素拷贝
到另外一个迭代器里；partition 则是根据过滤条件来对范围里的元素进行分组，把满足
条件的放在返回值迭代器的前面。另外，remove_if 也有点相近，通常用于删除满足条件
的元素。它确保把不满足条件的元素放在返回值迭代器的前面（但不保证满足条件的元素在
函数返回后一定存在），然后你一般需要使用容器的 erase 成员函数来将待删除的元素真
正删除。
三大主流编译器
GCC
GNU(Gnu's Not Unix)编译器套装(GNU Compiler Collection，GCC)，指一套编程语言编译器
GCC支持的语言：原名为GNU C语言编译器(GNU C Compiler)，因为它原本只能处理C语言。GCC在发布后很快地得到扩展，变得可处理C++。之后也变得可处理Fortran、Pascal、Objective-C、Java、Ada，Go与其他语言
GCC特性：除支持C/C++/ Objective-C/Objective-C++语言外，还是支持Java/Ada/Fortran/Go等；当前的Clang的C++支持落后于GCC；支持更多平台；更流行，广泛使用，支持完备。
传统静态编译器 流程分别
由三个组件来完成具体工作，分别为前端、优化器和后端
由三个组件来完成具体工作，分别为前端、优化器和后端
Clang
Clang：是一个C、C++、Objective-C和Objective-C++编程语言的编译器前端。它采用了底层虚拟机(LLVM)作为其后端。它的目标是提供一个GNU编译器套装(GCC)的替代品
Clang性能：测试证明Clang编译Objective-C代码时速度为GCC的3倍，还能针对用户发生的编译错误准确地给出建议。
Clang特性：编译速度快；内存占用小；兼容GCC；设计清晰简单、容易理解，易于扩展增强；基于库的模块化设计，易于IDE集成；出错提示更友好。
LLVM
LLVM项目是一系列分模块、可重用的编译工具链。它提供了一种代码良好的中间表示(IR)，
LLVM实现上可以作为多种语言的后端
LLVM实现上可以作为多种语言的后端
流程：编译前端将源码编译成LLVM中间格式的文
件，然后使用LLVM Linker进行链接。Linker执行大量的链接时优化，特别是过程间优化。链接得到的LLVM code最终会被翻译成特定平台的机器码
件，然后使用LLVM Linker进行链接。Linker执行大量的链接时优化，特别是过程间优化。链接得到的LLVM code最终会被翻译成特定平台的机器码
LLVM IR提供三种格式
内存里面的IR模型，存储在磁盘上的二进制
格式，存储在磁盘上的文本可读格式
格式，存储在磁盘上的文本可读格式
MSVC
编译器编程
我们下面看一个源自实际项
目的例子。需求是，我们希望快速地计算一串二进制数中 1 比特的数量。举个例子，如果
我们有十进制的 31 和 254，转换成二进制是 00011111 和 11111110，那我们应该得到 5
+ 7 = 12。
显然，每个数字临时去数肯定会慢，我们应该预先把每个字节的 256 种情况记录下来。因
而，如何得到这些计数值是个问题。在没有编译期编程时，我们似乎只能用另外一个程序先
行计算，然后把结果填进去——这就很不方便很不灵活了。有了编译期编程，我们就不用
写死，而让编译器在编译时帮我们计算数值。
利用 constexpr 函数，我们计算单个数值完全没有问题
目的例子。需求是，我们希望快速地计算一串二进制数中 1 比特的数量。举个例子，如果
我们有十进制的 31 和 254，转换成二进制是 00011111 和 11111110，那我们应该得到 5
+ 7 = 12。
显然，每个数字临时去数肯定会慢，我们应该预先把每个字节的 256 种情况记录下来。因
而，如何得到这些计数值是个问题。在没有编译期编程时，我们似乎只能用另外一个程序先
行计算，然后把结果填进去——这就很不方便很不灵活了。有了编译期编程，我们就不用
写死，而让编译器在编译时帮我们计算数值。
利用 constexpr 函数，我们计算单个数值完全没有问题
c++多线程并发,异常处理
线程并发与进程并发？
进程：资源分配的基本单位，也是程序运行的单位。用户运行自己的程序，系统就创建一个进程，并为它分配资源，包括各种表格、内存空间、磁盘空间、I／O设备等。然后，把该进程放人进程的就绪队列。进程调度程序选中它，为它分配CPU以及其它有关资源，该进程才真正运行。所以，进程是系统中的并发执行的单位。
线程：执行处理器调度的基本单位。一个进程由一个或多个线程构成,各线程共享相同的代码和全局数据,但各有其自己的堆栈。由于堆栈是每个线程一个,所以局部变量对每一线程来说是私有的。由于所有线程共享同样的代码和全局数据,它们比进程更紧密,比单独的进程间更趋向于相互作用,线程间的相互作用更容易些,因为它们本身就有某些供通信用的共享内存：进程的全局数据。
多线程问题
为什么要使用多线程？
通过设置正确个数的线程来最大化程序的运行速度，
充分的利用 CPU 和 I/O 的利用率
充分的利用 CPU 和 I/O 的利用率
并发编程适用于什么场景
CPU密集型程序
由于是单核 CPU，所有线程都在等待 CPU 时间片。按照理想情况来看，四个线程执行的时间总和与一个线程5独自完成是相等的，实际上我们还忽略了四个线程上下文切换的开销
所以，单核CPU处理CPU密集型程序，这种情况并不太适合使用多线程
所以，单核CPU处理CPU密集型程序，这种情况并不太适合使用多线程
如果是多核CPU 处理 CPU 密集型程序，我们完全可以最大化的利用 CPU 核心数，应用并发编程来提高效率
四核cpu创建四个线程，每个线程都有 CPU 来运行，并不会发生等待 CPU 时间片的情况，也没有线程切换的开销。理论情况来看效率提升了 4 倍
四核cpu创建四个线程，每个线程都有 CPU 来运行，并不会发生等待 CPU 时间片的情况，也没有线程切换的开销。理论情况来看效率提升了 4 倍
I/O密集型程序
进行 I/O 操作时，CPU是空闲状态，所以我们要最大化的利用 CPU，不能让其是空闲状态
比如：CPU操作耗时固定，将 I/O 操作耗时变为 CPU 耗时的 3 倍，你会发现，CPU又有空闲了，这时你就可以新建线程 4，来继续最大化的利用 CPU。
比如：CPU操作耗时固定，将 I/O 操作耗时变为 CPU 耗时的 3 倍，你会发现，CPU又有空闲了，这时你就可以新建线程 4，来继续最大化的利用 CPU。
总结：线程I/o操作等待时间所占比例越高，需要越多线程；线程CPU时间所占比例越高，需要越少线程。
创建多少线程合适？
对于 CPU 密集型来说，理论上 线程数量 = CPU 核数（逻辑）就可以了
I/O密集型程序创建多少个线程合适？
一个CPU核心的最佳线程数：最佳线程数 = (1/CPU利用率) = 1 + (I/O耗时/CPU耗时)
如CPU耗时1，io耗时2，最佳线程数3
多个核心，那么 I/O 密集型程序的最佳线程数就是
最佳线程数 = CPU核心数 * (1/CPU利用率) = CPU核心数 * (1 + (I/O耗时/CPU耗时))
面试会怎样问线程个数？
假如几乎全是 I/O耗时，所以纯理论你就可以说是 2N（N=CPU核数），当然也有说 2N + 1的，（我猜这个 1 也是 backup）
我怎么知道具体的 I/O耗时和CPU耗时呢？
有很多 APM （Application Performance Manager）工具可以帮我们得到准确的数据，学会使用这类工具，也就可以结合理论，在调优的过程得到更优的线程个数了
小问一
假设要求一个系统的 TPS（Transaction Per Second 或者 Task Per Second）至少为20，然后假设每个Transaction由一个线程完成，继续假设平均每个线程处理一个Transaction的时间为4s，如何设计线程数，20/（1/4）=80
但是，这是因为没有考虑到CPU数目。家里又没矿，一般服务器的CPU核数为16或者32，如果有80个线程，那么肯定会带来太多不必要的线程上下文切换开销（希望这句话你可以主动说出来），这就需要调优了，来做到最佳 balance
小问二
计算操作需要5ms，DB操作需要 100ms，对于一台 8个CPU的服务器，怎么设置线程数呢？
线程数 = 8 * (1 + 100/5) = 168 (个)
增加CPU核数一定能解决问题吗？
有一个阿姆达尔定律，cpu核心取向无穷大，程序串行百分比为5%，提升的效率最多二十倍
总结
多线程不一定就比单线程高效，比如大名鼎鼎的 Redis （后面会分析），因为它是基于内存操作，这种情况下，单线程可以很高效的利用CPU。而多线程的使用场景一般时存在相当比例的I/O或网络操作
灵魂追问
我们已经知道创建多少
个线程合适了，为什么
还要搞一个线程池出来？
个线程合适了，为什么
还要搞一个线程池出来？
手动创建线程有什么缺点？
不受控风险
频繁创建开销大
频繁创建开销大
如死锁的问题，系统资源 有限，当系统运行起来，所有线程都在疯狂抢占资源，无组织无纪律，混乱场面可想而知（出现问题，自然也就不可能轻易的发现和解决），过多的线程自然也会引起上下文切换的开销
创建一个线程都要做哪些事情？为什么说频繁的创建线程开销很大？
多线程通常要注意共享变量问题，为什么局部变量就没有线程安全问题呢？
进程
cpu在切换程序的时候，如果不保存上一个程序的状态（也就是我们常说的context--上下文），直接切换下一个程序，就会丢失上一个程序的一系列状态，于是引入了进程这个概念，用以划分好程序运行时所需要的资源。因此进程就是一个程序运行时候的所需要的基本资源单位（也可以说是程序运行的一个实体）。
线程
cpu切换多个进程的时候，会花费不少的时间，因为切换进程需要切换到内核态，而每次调度需要内核态都需要读取用户态的数据，进程一旦多起来，cpu调度会消耗一大堆资源，因此引入了线程的概念，线程本身几乎不占有资源，他们共享进程里的资源，内核调度起来不会那么像进程切换那么耗费资源。
协程
协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈。因此，协程能保留上一次调用时的状态（即所有局部状态的一个特定组合），每次过程重入时，就相当于进入上一次调用的状态，换种说法：进入上一次离开时所处逻辑流的位置。线程和进程的操作是由程序触发系统接口，最后的执行者是系统；协程的操作执行者则是用户自身程序，goroutine也是协程。
cpu在切换程序的时候，如果不保存上一个程序的状态（也就是我们常说的context--上下文），直接切换下一个程序，就会丢失上一个程序的一系列状态，于是引入了进程这个概念，用以划分好程序运行时所需要的资源。因此进程就是一个程序运行时候的所需要的基本资源单位（也可以说是程序运行的一个实体）。
线程
cpu切换多个进程的时候，会花费不少的时间，因为切换进程需要切换到内核态，而每次调度需要内核态都需要读取用户态的数据，进程一旦多起来，cpu调度会消耗一大堆资源，因此引入了线程的概念，线程本身几乎不占有资源，他们共享进程里的资源，内核调度起来不会那么像进程切换那么耗费资源。
协程
协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈。因此，协程能保留上一次调用时的状态（即所有局部状态的一个特定组合），每次过程重入时，就相当于进入上一次调用的状态，换种说法：进入上一次离开时所处逻辑流的位置。线程和进程的操作是由程序触发系统接口，最后的执行者是系统；协程的操作执行者则是用户自身程序，goroutine也是协程。
进程间各通信方式？
进程间通信：共享内存、套接字、管道、消息队列、信号
无名管道
单向性半双工通信
父子进程之间
没有名字
父子进程之间
没有名字
有名管道
有名字
可以在无亲缘关系的进程间通信
可以在无亲缘关系的进程间通信
消息队列
IPC进程间通信需要指定关键字key，然后关键字由内核变换成标识符
消息队列是消息的链接表 ,存放在内核中并由消息队列标识符标识。我们将称消息队列为“队列”，其标识符为“队列 I D”。 m s g g e t用于创建一个新队列或打开一个现存的队列。 m s g s n d用于将新消息添加到队列尾端
可以指定消息类型，然后接收特定类型的消息
信号量
本质上是一个计数器，它不以传送数据为主要目的，
它主要是用来保护共享资源（信号量也属于临界资源），使得资源在一个时刻只有一个进程独享。
它主要是用来保护共享资源（信号量也属于临界资源），使得资源在一个时刻只有一个进程独享。
两种操作
等待信号
发送信号
二元信号量（特殊的互斥锁）
二元信号量（Binary Semaphore）是最简单的一种锁（互斥锁），它只用两种状态：占用与非占用。所以它的引用计数为1。
进程获得共享资源的方式
（1）测试控制该资源的信号量
（2）信号量的值为正，进程获得该资源的使用权，进程将信号量减1，表示它使用了一个资源单位
（3）若此时信号量的值为0，则进程进入挂起状态（进程状态改变），直到信号量的值大于0，若进程被唤醒则返回至第一步。
注：信号量通过同步与互斥保证访问资源的一致性。
（2）信号量的值为正，进程获得该资源的使用权，进程将信号量减1，表示它使用了一个资源单位
（3）若此时信号量的值为0，则进程进入挂起状态（进程状态改变），直到信号量的值大于0，若进程被唤醒则返回至第一步。
注：信号量通过同步与互斥保证访问资源的一致性。
共享内存
共享内存就是允许两个或多个进程共享一定的存储区，因为数据不需要在客户机和服务器端之间复制，数据直接写到内存，不用若干次数据拷贝，所以这是最快的一种IPC。
注：共享内存没有任何的同步与互斥机制，所以要使用信号量来实现对共享内存的存取的同步。
注：共享内存没有任何的同步与互斥机制，所以要使用信号量来实现对共享内存的存取的同步。
原理
共享内存的大致原理就是让两个进程地址通过页表映射到同一片物理地址以便于通信
缺点
共享内存也并不完美，共享内存并未提供同步机制
多线程并发编程
< thread > : 提供线程创建及管理的函数或类接口；它是一切并发编程的基础
< mutex > : 为线程提供获得独占式资源访问能力的互斥算法，保证多个线程对共享资源的互斥访问；
（互斥锁)mutex
为了获得独占式的资源访问能力，相应的线程必须锁定(lock) mutex，这样可以防止其他线程也锁定mutex，直到第一个线程解锁(unlock) mutex。
2个互斥锁变种
智能指针借用了RAII技术（Resource Acquisition Is Initialization—使用类来封装资源，在构造函数中完成资源的分配和初始化，在析构函数中完成资源的清理，可以保证正确的初始化和资源释放）对普通指针进行封装，达到智能管理动态内存释放的效果。同样的，C++也针对lock与unlock引入了智能锁lock_guard与unique_lock，同样使用了RAII技术对普通锁进行封装，达到智能管理互斥锁资源释放的效果
std::lock_guard
析构时自动释放锁，所有权不可转移，对象生存期内不允许手动加锁和释放锁
std::adopt_lock
std::adopt_lock
std::unique_lock
在对象析构时如果持有锁会自动释放锁，所有权可以转移。对象生命期内允许手动加锁和释放锁
std::adopt_lock 和std::defer_lock std::try_to_lock
std::adopt_lock 和std::defer_lock std::try_to_lock
（递归锁）std::recursive_mutex
所谓递归锁，就是在同一线程上该锁是可重入的(允许在同一时间多次被同一线程获得其lock)，对于不同线程则相当于普通的互斥锁.。其典型应用是：函数捕获一个lock并调用另一函数而后者再次捕获相同的lock。
std::timed_mutex
额外允许你传递一个时间段或时间点，用来定义多长时间内它可以尝试捕获一个lock。为此它提供了try_lock_for(duration)和try_lock_until(timepoint)。
std::recursive_timed_mutex
允许同一线程多次取得其lock，且可指定期限。
< condition_variable > : (条件锁)允许一定量的线程等待（可以定时）被另一线程唤醒，然后再继续执行；
注意事项：
- 在管理互斥锁的时候，使用的是std::unique_lock而不是std::lock_guard，而且事实上也不能使用std::lock_guard。这需要先解释下wait()函数所做的事情，可以看到，在wait()函数之前，使用互斥锁保护了，如果wait的时候什么都没做，岂不是一直持有互斥锁？那生产者也会一直卡住，不能够将数据放入队列中了。所以，wait()函数会先调用互斥锁的unlock()函数，然后再将自己睡眠，在被唤醒后，又会继续持有锁，保护后面的队列操作。lock_guard没有lock和unlock接口，而unique_lock提供了，这就是必须使用unique_lock的原因；
2. 使用细粒度锁unique_lock,可以提前unlock，尽量减小锁的范围，在notify_one()的时候，不需要处于互斥锁的保护范围后，就可以在作用域结束之前可以将锁unlock()。
< future > : 提供了一些工具来获取异步任务（即在单独的线程中启动的函数）的返回值，并捕捉其所抛出的异常；
获取被调用者的执行结果或状态的方式
使用全局变量与条件变量传递结果
条件变量具有“通知–唤醒”功能，可以把执行结果或执行状态放入一个全局变量中，当被调用者执行完任务后，通过条件变量通知调用者结果或状态已更新，可以使用了
虽然也实现了获取异步任务执行结果的功能，但需要的全局变量较多，多线程间的耦合度也较高，编写复杂程序时容易引入bug
通过共享状态
这里的共享状态是保证返回值或异常在线程间正确传递的关键，
被调用线程可以通过改变共享状态通知调用线程返回值或异常已写入完毕，可以访问或操作了
被调用线程可以通过改变共享状态通知调用线程返回值或异常已写入完毕，可以访问或操作了
怎么为一个线程提供一个包含共享状态的对象呢？这就需要借助std::promise< T >类模板实现了
std::promise< T >构造时，产生一个未就绪的共享状态（包含存储的T值和是否就绪的状态）。可设置T值，set_value()公用接口，并让状态变为ready。也可以通过产生一个future对象获取到已就绪的共享状态中的T值
std::future< T >在多个线程等待时，只有一个线程能获取等待结果。当需要多个线程等待相同的事件的结果(即多处访问同一个共享状态)，需要用std::shared_future< T >来替代std::future < T >，std::future< T >也提供了一个将future转换为shared_future的方法f.share()，但转换后原future状态失效。这有点类似于智能指针std::unique_ptr< T >与std::shared_ptr< T >的关系
使用std::packaged_task< Func >与future传递结果
除了为一个任务或线程提供一个包含共享状态的变量，还可以直接把共享状态包装进一个任务或线程中。这就需要借助std::packaged_task< Func >来实现了
std::packaged_task< Func >构造时绑定一个函数对象，也产生一个未就绪的共享状态。通过thread启动或者仿函数形式启动该函数对象。但是相比promise，没有提供set_value()公用接口，而是当执行完绑定的函数对象，其执行结果返回值或所抛异常被存储于能通过 std::future 对象访问的共享状态中
使用async传递结果
std::future std::async(std::launch policy, Func, Args…)
std::async是一个函数而非类模板，其函数执行完后的返回值绑定给使用std::async的std::futrue对象
示例说明
示例很简单，大致步骤为：
（链接有示例源码）
（链接有示例源码）
- 调用异步函数async创建异步对象，返回结果为future类型
- 合适的时候使用异步对象返回的future方法检测异步任务执行进度
- 检测任务执行成功后，使用future的get方法获取异步任务执行结果
<atomic >（原子锁） :无锁编程 为细粒度的原子操作（不能被处理器拆分处理的操作）提供组件，允许无锁并发编程。
原子操作可以实现自旋锁（spinlock）
在任一时刻最多只能有一个持有者，但如果资源已被占用，互斥锁会让资源申请者进入睡眠状态，
而自旋锁不会引起调用者睡眠，会一直循环判断该锁是否成功获取
而自旋锁不会引起调用者睡眠，会一直循环判断该锁是否成功获取
实现方式
头文件：<linux\spinlock.h>
自旋锁的类型：spinlock_t
相关函数：初始化：spin_lock_init(spinlock_t *x);
spin_lock(x); //只有在获得锁的情况下才返回，否则一直“自旋”
spin_trylock(x); //如立即获得锁则返回真，否则立即返回假
释放锁：spin_unlock(x);
spin_is_locked(x)// 该宏用于判断自旋锁x是否已经被某执行单元保持（即被锁），如果是， 返回真，否则返回假。
注意：自旋锁适合于短时间的的轻量级的加锁机制。
自旋锁的类型：spinlock_t
相关函数：初始化：spin_lock_init(spinlock_t *x);
spin_lock(x); //只有在获得锁的情况下才返回，否则一直“自旋”
spin_trylock(x); //如立即获得锁则返回真，否则立即返回假
释放锁：spin_unlock(x);
spin_is_locked(x)// 该宏用于判断自旋锁x是否已经被某执行单元保持（即被锁），如果是， 返回真，否则返回假。
注意：自旋锁适合于短时间的的轻量级的加锁机制。
临界区（仅Windows平台下可用）
临界区和互斥锁的区别
1、临界区只能用于对象在同一进程里线程间的互斥访问；互斥体可以用于对象进程间或线程间的互斥访问。
2、临界区是非内核对象，只在用户态进行锁操作，速度快；互斥体是内核对象，在核心态进行锁操作，速度慢。
3、临界区和互斥体在Windows平台都下可用；Linux下只有互斥体可用
2、临界区是非内核对象，只在用户态进行锁操作，速度快；互斥体是内核对象，在核心态进行锁操作，速度慢。
3、临界区和互斥体在Windows平台都下可用；Linux下只有互斥体可用
保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。
临界区包含两个操作原语：
EnterCriticalSection（） 进入临界区
LeaveCriticalSection（） 离开临界区
EnterCriticalSection（）语句执行后代码将进入临界区以后无论发生什么，必须确保与之匹配的LeaveCriticalSection（）都能够被执行到。否则临界区保护的共享资源将永远不会被释放。虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。
临界区包含两个操作原语：
EnterCriticalSection（） 进入临界区
LeaveCriticalSection（） 离开临界区
EnterCriticalSection（）语句执行后代码将进入临界区以后无论发生什么，必须确保与之匹配的LeaveCriticalSection（）都能够被执行到。否则临界区保护的共享资源将永远不会被释放。虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。
linux c++ 三种信号量
信号灯(semaphore)，也叫信号量。它是不同进程间或一个给定进程内部不同线程间同步的机制。信号灯包括posix有名信号灯、 posix基于内存的信号灯(无名信号灯)和System V信号灯(IPC对象)
总结:
System V的信号量一般用于进程同步, 且是内核持续的, api为
semget
semctl
semop
Posix的有名信号量一般用于进程同步, 有名信号量是内核持续的. 有名信号量的api为
sem_open
sem_close
sem_unlink
Posix的无名信号量一般用于线程同步, 无名信号量是进程持续的, 无名信号量的api为
sem_init
sem_destroy
总结:
System V的信号量一般用于进程同步, 且是内核持续的, api为
semget
semctl
semop
Posix的有名信号量一般用于进程同步, 有名信号量是内核持续的. 有名信号量的api为
sem_open
sem_close
sem_unlink
Posix的无名信号量一般用于线程同步, 无名信号量是进程持续的, 无名信号量的api为
sem_init
sem_destroy
有名和无名。它们的区别在于，如何被创建和销毁，其他方面则完全相同。无名信号量只存在于内存中，并且规定能够访问该内存的进程才能够使用该内存中的信号量。这就意味着，无名信号量只能被这样两种线程使用：（1）来自同一进程的各个线程（2）来自不同进程的各个线程，但是这些进程映射了相同的内存范围到自己的地址空间。相反，有名信号量则是通过名字访问，因此，来自于任何进程的线程，只要知道该有名信号量的名字都可以访问。
有三种信号量：
1，Posix有名信号量：使用PosixIPC名字标识（通过特定函数，调用一个绝对文件路径名作为参数，返回一个特定标识），可用于进程或线程间通信。
2，Posix基于内存的信号量：存放在共享内存区（进程间共享内存区或者线程间共享内存区），可用于进程或线程间同步。
3，System V信号量：在内核中维护，可用于进程或线程间的同步。
Posix信号量不必在内核中维护的，这不同于systemV信号量。
那么信号量、互斥锁和条件变量之间的差异在哪呢？：
1，互斥锁必须总是由给它上锁的线程解锁，信号量的挂出却不用非得由执行它的等待操作线程执行。
2，互斥锁要么被锁住要么被解开（二值状态，类似于二值信号量）。
1，Posix有名信号量：使用PosixIPC名字标识（通过特定函数，调用一个绝对文件路径名作为参数，返回一个特定标识），可用于进程或线程间通信。
2，Posix基于内存的信号量：存放在共享内存区（进程间共享内存区或者线程间共享内存区），可用于进程或线程间同步。
3，System V信号量：在内核中维护，可用于进程或线程间的同步。
Posix信号量不必在内核中维护的，这不同于systemV信号量。
那么信号量、互斥锁和条件变量之间的差异在哪呢？：
1，互斥锁必须总是由给它上锁的线程解锁，信号量的挂出却不用非得由执行它的等待操作线程执行。
2，互斥锁要么被锁住要么被解开（二值状态，类似于二值信号量）。
读写锁
也称作**共享互斥锁**：当读写锁是读模式锁住时，可以说成是共享模式锁住的；当它是写模式锁住时，可以说成是以互斥模式锁住的
三种状态
- **读模式下加锁状态**：多个线程可以用时占有读模式的读写锁，此时任何试图以写模式对该读写锁加锁的线程都会阻塞，直到所有的线程释放它们的读锁为止（通常这种情况下会阻塞随后的读模式锁请求，从而避免读模式长期占用，而等待的写模式锁请求一直得不到满足）
- **写模式下加锁状态**：一次只有一个线程可以占有写模式的读写锁
- **不加锁状态**
- **写模式下加锁状态**：一次只有一个线程可以占有写模式的读写锁
- **不加锁状态**
应用场景
**读写锁非常适合于对数据结构读的次数远大于写的情况**
屏障
`pthread_join`就是一种屏障，允许一个线程等待，直到另一个线程退出
举例：在允许所有线程继续运行之前，必须到达屏障的线程数目n,初始化屏障线程的数目n，在允许所有线程继续运行之前，必须到达屏障的线程数目。假设主线程希望开启`n`个线程进行排序，每个线程排序数组的一部分，所有`n`个线程排好序后主线程进行归并，那么`count`应该为`n+1`
pthread_barrier_wait 该函数用以表明，线程已完成工作，准备等待所有其他线程赶上来。
死锁的四个必要条件及解决办法
死锁概念及原理
概念：多个并发线程因争夺系统资源而产生相互等待的现象。
死锁 本质原因：
1）、系统资源有限。
2）、线程推进顺序不合理。
死锁 本质原因：
1）、系统资源有限。
2）、线程推进顺序不合理。
四个必要条件
互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
环路等待条件：在发生死锁时，必然存在一个进程--资源的环形链。
请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
环路等待条件：在发生死锁时，必然存在一个进程--资源的环形链。
**屏障是用户协调多个线程并行工作的同步机制。屏障允许每个线程等待，直到所有的合作线程都到达某一点，然后从该点继续执行**
解决死锁
加锁顺序（各线程均按照一定的顺序加锁）
加锁时限（线程尝试获取锁的时候加上一定的时限，超过时限则放弃对该锁的请求，并释放自己占有的锁）
死锁检测（处理：一个可行的做法是释放所有锁，回退，并且等待一段随机的时间后重试）
加锁时限（线程尝试获取锁的时候加上一定的时限，超过时限则放弃对该锁的请求，并释放自己占有的锁）
死锁检测（处理：一个可行的做法是释放所有锁，回退，并且等待一段随机的时间后重试）
*死锁预防：通过设置某些限制条件，去破坏死锁的四个条件中的一个或几个条件，来预防发生死锁。但由于所施加的限制条件往往太严格，因而导致系统资源利用率和系统吞吐量降低。
*死锁避免：允许前三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此死锁避免比死锁预防允许更多的并发。
*死锁检测：不须实现采取任何限制性措施，而是允许系统在运行过程发生死锁，但可通过系统设置的检测机构及时检测出死锁的发生，并精确地确定于死锁相关的进程和资源，然后采取适当的措施，从系统中将已发生的死锁清除掉。
*死锁解除：与死锁检测相配套的一种措施。当检测到系统中已发生死锁，需将进程从死锁状态中解脱出来。常用方法：撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程。死锁检测盒解除有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。
*死锁避免：允许前三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此死锁避免比死锁预防允许更多的并发。
*死锁检测：不须实现采取任何限制性措施，而是允许系统在运行过程发生死锁，但可通过系统设置的检测机构及时检测出死锁的发生，并精确地确定于死锁相关的进程和资源，然后采取适当的措施，从系统中将已发生的死锁清除掉。
*死锁解除：与死锁检测相配套的一种措施。当检测到系统中已发生死锁，需将进程从死锁状态中解脱出来。常用方法：撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程。死锁检测盒解除有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。
利用队列写一个多线程下的生产者和消费者程序，全面考察的多线程的资源同步与竞态问题
线程池的设计
基础概念
当进行并行的任务作业操作时，线程的建立与销毁的开销是，阻碍性能进步的关键，因此线程池，由此产生。使用多个线程，无限制循环等待队列，进行计算和操作。帮助快速降低和减少性能损耗。
线程池的组成
线程池管理器：初始化和创建线程，启动和停止线程，调配任务；管理线程池
工作线程：线程池中等待并执行分配的任务
任务接口：添加任务的接口，以提供工作线程调度任务的执行。
任务队列：用于存放没有处理的任务，提供一种缓冲机制，同时具有调度功能，高优先级的任务放在队列前面
工作线程：线程池中等待并执行分配的任务
任务接口：添加任务的接口，以提供工作线程调度任务的执行。
任务队列：用于存放没有处理的任务，提供一种缓冲机制，同时具有调度功能，高优先级的任务放在队列前面
涉及到的c++11特性
std::vector
std::list
std::thread
std::mutex
std::future
std::condition_variable
std::list
std::thread
std::mutex
std::future
std::condition_variable
代码
Linux gdb调试
常用调试命令
一个强大的UNIX下的程序调试工具，可执行文件中加入源代码的信息，比如可执行文件中第几条机器指令对应源代码的第几行
用gdb调试多进程程序
独调试子进程
设计模式
创建型模式
1. 单例模式（Singleton Pattern）
优点：1.单例模式提供了严格的对唯一实例的创建和访问
2.单例模式的实现可以节省系统资源
2.单例模式的实现可以节省系统资源
缺点：如果某个实例负责多重职责但又必须实例唯一，那单例类的职责过多，这违背了单一职责原则
多线程下需要考虑线程安全机制
单例模式没有抽象层，不方便扩展
多线程下需要考虑线程安全机制
单例模式没有抽象层，不方便扩展
使用场景：系统只需要一个实例对象 某个实例只允许有一个访问接口
2. 抽象工厂模式（Abstract Factory Pattern）
- 创建抽象产品
- 创建具体产品
- 创建抽象工厂
- 创建具体工厂
- 创建客户端
抽象工厂模式出现了 - 将产品归类分组，然后将好几组产品构成一族。每个工厂负责生产一族产品，
而工厂中的每个方法负责生产一种类型的产品。如奥迪工厂可以创建奥迪轿车，SUV，跑车，
可以创建多个奥迪工厂，奔驰工厂，宝宝马工厂来生产各自的汽车。
而工厂中的每个方法负责生产一种类型的产品。如奥迪工厂可以创建奥迪轿车，SUV，跑车，
可以创建多个奥迪工厂，奔驰工厂，宝宝马工厂来生产各自的汽车。
- 优点 ：封装了产品的创建，使得不需要知道具体是哪种产品，只需要知道是哪个工厂即可。
- 可以支持不同类型的产品，使得模式灵活性更强。
- 可以非常方便的使用一族中的不同类型的产品。
- 缺点：结构过于臃肿，如果产品类型较多或产品族较多，会非常难于管理。
- 每次如果添加一组产品，那么所有的工厂类都必须添加一个方法，这样违背了开放-封闭原则。所以一般适用于产品组合产品族变化不大的情况。
适用场景
- 在不必指定产品的具体的情况下，创建多个产品族中的产品对象。如奥迪工厂可以创建奥迪轿车，SUV，跑车，可以创建多个奥迪工厂，奔驰工厂，宝宝马工厂来生产各自的汽车。
抽象工厂模式是指一个工厂服务于一个产品族，一个产品族可能包含多个接口，接口又会包含多个实现类，通过一个工厂就可以把这些绑定在一起，非常方便。
3. 建造者模式（Builder Pattern）
创建过程
- 定义产品类House
- 定义抽象建造者AbstractBuilder
- 定义具体建造者
- 定义指挥者
优点：
- 建造者模式中，客户端不需要知道产品内部组成细节，将产品本身和产品的创建过程分离，使同样的创建过程可以创建不同的产品对象；
- 不同建造者相互独立，并无任何挂链，方便替换。
缺点：
- 建造者模式所创建的产品一般具有较多的共同点，其组成部分相似，如果产品之间的差异性很大，则不适合使用建造者模式，因此其使用范围受到一定的限制。
- 如果产品的内部变化复杂，可能会导致需要定义很多具体建造者类来实现这种变化，导致系统变得很庞大
使用场景：
- 需要生成的产品对象有复杂的内部结构（通常包含多个成员变量）；
- 同一个创建流程适用于多种不同的产品
案例：建造方式，选择不同的开发商，可以建造不同的房子。Jungle想要建造一栋简易的房子（地板、墙和天花板），两个工程师带着各自的方案找上门来，直接给Jungle看方案和效果图。犹豫再三，Jungle最终选定了一位工程师……交房之日，Jungle满意的看着建好的房子
4. 工厂方法模式（Factory Method Pattern）
创建抽象产品
创建具体产品
创建工厂
创建具体工厂
创建具体产品
创建工厂
创建具体工厂
简单工厂模式中，每新增一个具体产品，就需要修改工厂类内部的判断逻辑。
为了不修改工厂类，遵循开闭原则，工厂方法模式中不再使用工厂类统一创建所有的具体产品，
而是针对不同的产品设计了不同的工厂，每一个工厂只生产特定的产品。如奔驰工厂只生产背驰汽车，
不生产背驰自行车。
为了不修改工厂类，遵循开闭原则，工厂方法模式中不再使用工厂类统一创建所有的具体产品，
而是针对不同的产品设计了不同的工厂，每一个工厂只生产特定的产品。如奔驰工厂只生产背驰汽车，
不生产背驰自行车。
优点:
- 工厂方法用于创建客户所需产品，同时向客户隐藏某个具体产品类将被实例化的细节，用户只需关心所需产品对应的工厂；
- 工厂自主决定创建何种产品，并且创建过程封装在具体工厂对象内部，多态性设计是工厂方法模式的关键；
- 新加入产品时，无需修改原有代码，增强了系统的可扩展性，符合开闭原则。
缺点:
- 添加新产品时需要同时添加新的产品工厂，系统中类的数量成对增加，增加了系统的复杂度，更多的类需要编译和运行，增加了系统的额外开销；
- 工厂和产品都引入了抽象层，客户端代码中均使用的抽象层（AbstractFactory和AbstractSportProduct ），增加了系统的抽象层次和理解难度。
适用场景
- 客户端不需要知道它所需要创建的对象的类；
- 抽象工厂类通过其子类来指定创建哪个对象（运用多态性设计和里氏代换原则）
5. 原型模式（Prototype Pattern）
关于克隆方法：浅拷贝/深拷贝
原型模式可以说是“复制”，即克隆，但这个复制不是代码的复制，而是将对象包含的所有属性都创建一份拷贝。但不同的复制操作，可能会产生两种不同的拷贝，即浅拷贝和深拷贝。
浅拷贝
在浅拷贝中，如果原型对象的成员变量是值类型（如int、double、char等基本数据类型），将复制一份给拷贝对象；如果原型对象的成员变量是引用/指针，则将引用/指针指向的地址拷贝一份给拷贝对象，即原型对象和拷贝对象中的成员变量指向同一个地址。
深拷贝
在深拷贝中，无论原型对象中的成员变量是值类型还是指针/引用类型，都将复制一份给拷贝对象。注意，深拷贝中，指针/引用对象也会被拷贝一份给拷贝对象。
原型模式可以说是“复制”，即克隆，但这个复制不是代码的复制，而是将对象包含的所有属性都创建一份拷贝。但不同的复制操作，可能会产生两种不同的拷贝，即浅拷贝和深拷贝。
浅拷贝
在浅拷贝中，如果原型对象的成员变量是值类型（如int、double、char等基本数据类型），将复制一份给拷贝对象；如果原型对象的成员变量是引用/指针，则将引用/指针指向的地址拷贝一份给拷贝对象，即原型对象和拷贝对象中的成员变量指向同一个地址。
深拷贝
在深拷贝中，无论原型对象中的成员变量是值类型还是指针/引用类型，都将复制一份给拷贝对象。注意，深拷贝中，指针/引用对象也会被拷贝一份给拷贝对象。
优点：
- 当创建新的对象实例较为复杂时，原型模式可以简化创建过程，提高创建对象的效率；
- 可扩展：模式中提供了抽象原型类，具体原型类可适当扩展；
- 创建结构简单：创建工厂即为原型对象本身
缺点：
- 深克隆代码较为复杂；
- 每一个类都得配备一个clone方法，且该方法位于类的内部，修改时违背开闭原则；
适用环境：
- 当创建新的对象实例较为复杂时，原型模式可以简化创建过程；
- 结合优点第3条，需要避免使用分层次的工厂类来创建分层次的对象，并且类的实例对象只有一个或很少几个的组合状态，通过复制原型对象得到新实例，比通过使用构造函数创建一个新实例会更加方便。
案例：抄作业
结构型模式
6. 适配器模式（Adapter Pattern）
案例分析只需要提供一个电源转化器即可。该转化器的一端符合俄罗斯标准，可以插到俄罗斯的插座上，
另一端符合中国标准，可以供我们的手机充电器使用。
另一端符合中国标准，可以供我们的手机充电器使用。
优点：
- 可以让任何两个没有关联的类一起运行
- 提高了类的复用
- 增加了类的透明度
- 灵活性好
- 过多地使用适配器，会让系统非常零乱，不利于整体把控。
适用场景
- 当想使用一个已存在的类，而它的接口不符合需求时。
- 你想创建一个可复用的类，该类可以与其他不相关的类或不可预见的类协同工作。
- 你想使用一些已经存在的子类，但是不可能对每一个都进行子类化以匹配它们的接口，对象适配器可以适配它的父接口。
7. 桥接模式（Bridge Pattern）
案例分析：开关和电器。开关是抽象部分，控制着实现部分的电器
电器是现代生活必不可少的东西，几乎每家每户都有，电视、风扇、电灯。。。无论什么电器，都由开关控制。开关种类众多，有拉链式开关、两位开关、调光开关。。。
不管任何时候，都可以在不触及其它东西的情况下更换设备。例如，可以在不更换开关的情况下换掉灯泡，也可以在不接触灯泡或风扇的情况下更换开关，甚至可以在不接触开关的情况下将灯泡和风扇互换。
电器是现代生活必不可少的东西，几乎每家每户都有，电视、风扇、电灯。。。无论什么电器，都由开关控制。开关种类众多，有拉链式开关、两位开关、调光开关。。。
不管任何时候，都可以在不触及其它东西的情况下更换设备。例如，可以在不更换开关的情况下换掉灯泡，也可以在不接触灯泡或风扇的情况下更换开关，甚至可以在不接触开关的情况下将灯泡和风扇互换。
优点：
- 分离抽象和实现部分。桥接模式使用“对象间的关联关系”解耦了抽象和实现之间固有的绑定关系，使得抽象和实现可以沿着各自的维度来变化。所谓抽象和实现沿着各自维度的变化，也就是说抽象和实现不再在同一个继承层次结构中，而是“子类化”它们，使它们各自都具有自己的子类，以便任何组合子类，从而获得多维度组合对象。
- 在很多情况下，桥接模式可以取代多层继承方案，多层继承方案违背了“单一职责原则”，复用性较差，且类的个数非常多，桥接模式是比多层继承方案更好的解决方法，它极大减少了子类的个数。
- 桥接模式提高了系统的可扩展性，在两个变化维度中任意扩展一个维度，都不需要修改原有系统，符合“开闭原则”。
缺点：
- 桥接模式的使用会增加系统的理解与设计难度，由于关联关系建立在抽象层，要求开发者一开始就针对抽象层进行设计与编程。
- 桥接模式要求正确识别出系统中两个独立变化的维度，因此其使用范围具有一定的局限性，如何正确识别两个独立维度也需要一定的经验积累。
适用场景
- 如果一个系统需要在抽象化和具体化之间增加更多的灵活性，避免在两个层次之间建立静态的继承关系，通过桥接模式可以使它们在抽象层建立一个关联关系。
- “抽象部分”和“实现部分”可以以继承的方式独立扩展而互不影响，在程序运行时可以动态将一个抽象化子类的对象和一个实现化子类的对象进行组合，即系统需要对抽象化角色和实现化角色进行动态耦合。
- 一个系统存在多个（≥ 2）独立变化的维度，且这多个维度都需要独立进行扩展。
- 对于那些不希望使用继承或因为多层继承导致系统类的个数急剧增加的系统，桥接模式尤为适用。
8. 装饰者模式（Decorator Pattern）
类结构：
- Component（抽象构件）：给出一个抽象接口，以规范准备接收附加责任的对象。
- ConcreteComponent（具体构件）：定义一个将要接收附加责任的类。
- Decorator（抽象装饰类）：持有一个构件（Component）对象的实例，并实现一个与抽象构件接口一致的接口。
- ConcreteDecorator（具体装饰类）：负责给构件对象添加上附加的责任。
案例分析： 在星巴克购买咖啡时，可以要求在其中加入各种调味品（辅料）。调味品很多，有些不收费（例如：白砂糖、香草粉等），有些则需要额外收费（例如：奶油、摩卡、糖浆等），所以充分利用起来吧！倘若咖啡不带劲，我们想要添加奶油、摩卡和糖浆，这时，就可以利用装饰者模式思想来实现。
调味品可以随便组合，甚至同一调味品可以添加多份（例如：来 三份糖浆）或者同时添加奶、摩卡和糖浆。
调味品可以随便组合，甚至同一调味品可以添加多份（例如：来 三份糖浆）或者同时添加奶、摩卡和糖浆。
优点：
- Decorator 模式与继承关系的目的都是要扩展对象的功能，但是 Decorator 可以提供比继承更多的灵活性。
- 通过使用不同的具体装饰类以及这些装饰类的排列组合，可以创造出很多不同行为的组合。
缺点：
- 这种比继承更加灵活机动的特性，也同时意味着更加多的复杂性。
- 装饰模式会导致设计中出现许多小类，如果过度使用，会使程序变得很复杂。
- 装饰模式是针对抽象构建（Component）类型编程。但是，如果要针对具体构件（ConcreteComponent）编程，应该重新思考应用架构，以及装饰者是否合适。当然也可改变 Component 接口，增加新的公开的行为，实现“半透明”的装饰者模式。在实际项目中要做出最佳选择。
适用场景
- 需要扩展一个类的功能，或给一个类添加附加职责。
- 需要动态的给一个对象添加功能，这些功能可以再动态的撤销。
- 需要增加由一些基本功能的排列组合而产生的非常大量的功能，从而使继承关系变的不现实。
- 当不能采用生成子类的方法进行扩充时。一种情况是，可能有大量独立的扩展，为支持每一种组合将产生大量的子类，使得子类数目呈爆炸性增长。另一种情况可能是因为类定义被隐藏，或类定义不能用于生成子类。
9. 组合模式（Composite Pattern）
Component（抽象构件）：为叶子构件和容器构件对象定义接口，可以包含所有子类共有行为的声明和实现。在抽象构件中，声明了访问及管理子构件的接口（例如：Add()、Remove()、GetChild() 等）。
Leaf（叶子构件）：叶子节点没有子节点。它实现了 Component 中定义的行为，对于访问及管理子构件的接口，可以通过异常等方式进行处理。
Composite（容器构件）：容器节点包含子节点（可以是叶子构件，也可以是容器构件）。它提供了一个集合用于存储子节点，实现了 Component 中定义的行为，包括访问及管理子构件的接口，在其业务方法中可以递归调用其子节点的业务方法。
Leaf（叶子构件）：叶子节点没有子节点。它实现了 Component 中定义的行为，对于访问及管理子构件的接口，可以通过异常等方式进行处理。
Composite（容器构件）：容器节点包含子节点（可以是叶子构件，也可以是容器构件）。它提供了一个集合用于存储子节点，实现了 Component 中定义的行为，包括访问及管理子构件的接口，在其业务方法中可以递归调用其子节点的业务方法。
根据 Component 的定义形式，可将组合模式分为两种形式：
- 透明组合模式
- 安全组合模式
- 在 Component 中定义了用于访问和管理子构建的接口，这样做的好处是确保所有的构件类都有相同的接口。
- 在 Client 看来，Leaf 与 Composite 所提供的接口一致，Client 可以相同地对待所有的对象。
- 在 Component 中不定义任何用于访问和管理子构建的接口，而在 Composite 中声明并实现。
- 这种做法是安全的，因为不需要向 Leaf 提供这些管理成员对象的接口，对于 Leaf 来说，Client 不可能调用到这些接口。
优缺点
优点：
组合模式可以清楚地定义分层次的复杂对象，表示对象的全部或部分层次，它让 Client 忽略了层次的差异，方便对整个层次结构进行控制。
Client 可以一致地使用一个组合结构或其中单个对象，不必关心处理的是单个对象还是整个组合结构，简化了 Client 的代码。
在组合模式中，增加新的叶子构件和容器构件很方便，无须对现有类进行任何修改，符合“开闭原则”。
为树形结构提供了一种灵活的解决方案，通过递归组合容器对象和叶子对象，可以形成复杂的树形结构，但对树形结构的控制却非常简单。
缺点：
使设计变得更加抽象，对象的业务规则如果很复杂，则实现组合模式具有很大挑战性，而且不是所有的方法都与叶子对象子类都有关联。
适用场景
表示对象的“整体-部分”层次结构（树形结构）
希望用户忽略组合对象与单个对象的不同，统一地使用组合结构中的所有对象。
优点：
组合模式可以清楚地定义分层次的复杂对象，表示对象的全部或部分层次，它让 Client 忽略了层次的差异，方便对整个层次结构进行控制。
Client 可以一致地使用一个组合结构或其中单个对象，不必关心处理的是单个对象还是整个组合结构，简化了 Client 的代码。
在组合模式中，增加新的叶子构件和容器构件很方便，无须对现有类进行任何修改，符合“开闭原则”。
为树形结构提供了一种灵活的解决方案，通过递归组合容器对象和叶子对象，可以形成复杂的树形结构，但对树形结构的控制却非常简单。
缺点：
使设计变得更加抽象，对象的业务规则如果很复杂，则实现组合模式具有很大挑战性，而且不是所有的方法都与叶子对象子类都有关联。
适用场景
表示对象的“整体-部分”层次结构（树形结构）
希望用户忽略组合对象与单个对象的不同，统一地使用组合结构中的所有对象。
案例如公司部门分级：总经理 财务 运营 技术 行政等部门
10. 外观模式（Facade Pattern）
- Facade（外观）：模式的核心，被 Client 调用，知晓相关子系统的功能和责任。在正常情况下，它将所有从 Client 发来的请求委派到相应的子系统去，让子系统处理。
- SubSystem（子系统）：可以同时有一个或者多个子系统，子系统可以是一个单独的类或类的集合。每个子系统都可以被 Client 直接调用，或者被 Facade 调用，它处理由 Facade 传过来的请求。子系统并不知道 Facade 的存在，对于子系统而言，Facade 仅仅是另外一个 Client 而已。
案例
外观用户跟踪订单：下订单 –> 订单验证 –> 打包 –> 出货 –> 派送 –> 交付
子系统包含 3 个，订单团队（确认付款、联系供应商）、供应商（确认库存、包装、联系快递）、快递员（分配人员、派送包裹）
子系统包含 3 个，订单团队（确认付款、联系供应商）、供应商（确认库存、包装、联系快递）、快递员（分配人员、派送包裹）
优缺点
优点：
优点：
- 对 Client 屏蔽子系统组件，减少了 Client 处理的对象数目，并使得子系统使用起来更加容易。通过引入外观模式，Client 的代码将变得很简单，与之关联的对象也很少。
- 实现了子系统与 Client 之间的松耦合关系，这使得子系统的组件变化不会影响到调用它的 Client，只需要调整 Facade 即可。
- 降低了大型软件系统中的编译依赖性，并简化了系统在不同平台之间的移植过程，因为编译一个子系统一般不需要编译所有其他的子系统。一个子系统的修改对其他子系统没有任何影响，而且子系统内部变化也不会影响到外观对象。
- 只是提供了一个访问子系统的统一入口，并不影响用户直接使用子系统类。
- 不能很好地限制 Client 使用子系统类，如果对 Client 访问子系统类做太多的限制，则会减少可变性和灵活性。
- 在不引入抽象外观类的情况下，增加新的子系统可能需要修改 Facade 或 Client 的源代码，违背了“开闭原则”。
适用场景
- 当要为一个复杂子系统提供一个简单接口时。该接口可以满足大多数用户的需求，而且用户也可以越过外观类直接访问子系统。
- Client 与多个子系统之间存在很大的依赖性。引入外观类将子系统与 Client 以及其他子系统解耦，可以提高子系统的独立性和可移植性。
- 在层次化结构中，可以使用外观模式定义系统中每一层的入口。层与层之间不直接产生联系，而通过外观类建立联系，降低层之间的耦合度。
11. 享元模式（Flyweight Pattern）
- Flyweight（抽象享元类）：通常是一个抽象类，在抽象享元类中声明了具体享元类公共的方法，这些方法可以向外界提供享元对象的内部数据（内部状态），同时也可以通过这些方法来设置外部数据（外部状态）。
- ConcreteFlyweight（具体享元类）：实现了抽象享元类，其实例称为享元对象；在具体享元类中为内部状态提供了存储空间。通常可以结合单例模式来设计具体享元类，为每一个具体享元类提供唯一的享元对象。
- UnsharedConcreteFlyweight（非共享具体享元类）：并不是所有抽象享元类的子类都需要被共享，不能被共享的子类可设计为非共享具体享元类，当需要一个非共享具体享元类的对象时可以直接通过实例化创建。
- FlyweightFactory（享元工厂类）：用于创建并管理享元对象，它针对抽象享元类编程，将各种类型的具体享元对象存储在一个享元池中，享元池一般设计为一个存储“键值对”的集合（也可以是其他类型的集合），可以结合工厂模式进行设计；当用户请求一个具体享元对象时，享元工厂提供一个存储在享元池中已创建的实例或者创建一个新的实例（如果不存在的话），返回新创建的实例并将其存储在享元池中。
优缺点
优点：
优点：
- 可以极大减少内存中对象的数量，使得相同或相似对象在内存中只保存一份，从而可以节约系统资源，提高系统性能。
- 享元模式的外部状态相对独立，而且不会影响其内部状态，从而使得享元对象可以在不同的环境中被共享。
- 享元模式使得系统变得复杂，需要分离出内部状态和外部状态，这使得程序的逻辑复杂化。
- 为了使对象可以共享，享元模式需要将享元对象的部分状态外部化，而读取外部状态将使得运行时间变长。
适用场景
- 一个系统有大量相同或者相似的对象，造成内存的大量耗费。
- 对象的大部分状态都可以外部化，可以将这些外部状态传入对象中。
- 在使用享元模式时，需要维护一个存储享元对象的享元池，而这需要耗费一定的系统资源。因此，应当在需要多次重复使用享元对象时才值得使用享元模式。
示例 ： CS 将玩家分为“恐怖份子”（Terrorists）与“反恐精英”（Counter Terrorists）两个阵营，每个队伍必须在地图上进行多回合的战斗。在“爆破模式”中，T 阵营的任务是在指定时间内装置 C4 并引爆，而 CT 阵营的任务是拆除被装置的 C4。当玩家请求武器时，系统会为其分配所需的武器。
现在，有 n 个玩 CS 的玩家，如果创建 n 个对象（每个玩家一个），这势必会占用大量内存。为了解决这个问题，可以使用享元模式（减少玩家数量），只需要为恐怖分子和反恐精英创建两个对象，在需要时反复使用即可。
享元对象之所以能做到共享，关键是区分了内部状态和外部状态：
现在，有 n 个玩 CS 的玩家，如果创建 n 个对象（每个玩家一个），这势必会占用大量内存。为了解决这个问题，可以使用享元模式（减少玩家数量），只需要为恐怖分子和反恐精英创建两个对象，在需要时反复使用即可。
享元对象之所以能做到共享，关键是区分了内部状态和外部状态：
- 内部状态（Intrinsic State）：存储在享元对象内部，并且不会随环境改变而改变。因此，内部状态可以共享。
- 这里的“任务”就是两种类型玩家的内部状态，不会随外部环境的变化而变化。无论在任何环境下，T 的任务永远是装置 C4 并引爆，而 CT 的任务永远是拆除 C4。
- 外部状态（Extrinsic State）：随环境改变而改变的、不可以共享的状态。享元对象的外部状态通常由客户端保存，并在享元对象被创建之后，需要使用时再传入到享元对象内部。一个外部状态与另一个外部状态之间是相互独立的。
- 比如“武器”，每个玩家都可以携带自己选择的任何武器。有的玩家用的是 AK-47，有的则用的是沙漠之鹰。
12. 代理模式（Proxy Pattern）
- Subject（抽象主题）：声明了 RealSubject 与 Proxy 的共同接口，定义了某个/些功能。
- RealSubject（真实主题）：通常执行具体的业务逻辑，Proxy 控制对它的访问。
- Proxy（代理）：持有一个 RealSubject 引用（指针），可以在需要时将请求转发给 RealSubject，以此起到代理的作用。
- Client（客户端）：通过 Proxy 间接地与 RealSubject 进行交互。
优缺点
优点：
代理模式能将代理对象与真正被调用的对象分离，在一定程度上降低了系统的耦合度。
在客户端和目标对象之间，代理起到一个中介作用，这样可以保护目标对象。在对目标对象调用之前，代理对象也可以进行其他操作。
缺点：
根据目的和实现方式的不同，代理模式可分为很多种，常见的有：
远程代理（Remote Proxy）
为一个位于不同地址空间的对象提供一个本地代理，对代理的方法调用会导致对远程对象的方法调用。ATM 就是一个例子，ATM 可能会持有（存在于远程服务器中的）银行信息的一个代理对象。
优点：
代理模式能将代理对象与真正被调用的对象分离，在一定程度上降低了系统的耦合度。
在客户端和目标对象之间，代理起到一个中介作用，这样可以保护目标对象。在对目标对象调用之前，代理对象也可以进行其他操作。
缺点：
- 这种模式引入了另一个抽象层，这有时可能是一个问题。如果真实主题被某些客户端直接访问，并且其中一些客户端可能访问代理类，这可能会导致不同的行为。
- 由于在客户端和真实主题之间增加了代理对象，因此有些类型的代理模式可能会造成请求的处理速度变慢。
- 实现代理模式需要额外的工作，有些代理模式的实现非常复杂。
根据目的和实现方式的不同，代理模式可分为很多种，常见的有：
远程代理（Remote Proxy）
为一个位于不同地址空间的对象提供一个本地代理，对代理的方法调用会导致对远程对象的方法调用。ATM 就是一个例子，ATM 可能会持有（存在于远程服务器中的）银行信息的一个代理对象。
- 虚拟代理（Virtual Proxy） 使用虚拟代理，代理可以作为一个（资源消耗较大的）对象的代表。虚拟代理经常延迟对象的创建，直到需要为止。在创建对象之前（及创建对象过程中），虚拟代理也可以作为对象的代理；之后，代理将请求直接委托给 RealSubject。
- 保护代理（Protection Proxy） 根据访问权限，可以使用保护代理来控制对资源的访问。例如，有一个员工对象，保护代理可以允许普通员工调用对象的某些方法，管理员调用其他方法。
- 缓冲代理（Cache Proxy） 为某一个目标操作的结果提供临时的存储空间，以便多个客户端可以共享这些结果。
- 智能引用代理（Smart Reference Proxy）当一个对象被引用时，提供一些额外的操作（例如：将对象被调用的次数记录下来）。
示例：移动公司把充值的职责托付给代理点，代理点代替移动公司充值，客户直接与代理点打交道，而非移动公司。
行为型模式
13. 模版方法模式 （Template Method Pattern）
- 抽象类（AbstractClass）：定义抽象的原语操作，具体的子类将重定义它们以实现一个算法的各步骤。主要是实现一个模板方法，定义一个算法的骨架。该模板方法不仅调用原语操作，也调用定义在 AbstractClass 或其他对象中的操作。
- 具体类（ConcreteClass）：实现原语操作以完成算法中与特定子类相关的步骤。
优缺点
优点：
优点：
- 在父类中形式化地定义一个算法，而由其子类实现细节的处理，在子类实现详细的处理算法时并不会改变算法中步骤的执行次序。
- 模板方法模式是一种代码复用技术，在类库设计中尤为重要，它提取了类库中的公共行为，将公共行为放在父类中，而通过其子类来实现不同的行为，它鼓励我们恰当使用继承来实现代码复用。
- 可实现一种反向控制结构，通过子类覆盖父类的钩子方法来决定某一特定步骤是否需要执行。
- 在模板方法模式中，可以通过子类来覆盖父类的基本方法，不同的子类可以提供基本方法的不同实现，更换和增加新的子类很方便，符合单一职责原则和开闭原则。
- 需要为每一个基本方法的不同实现提供一个子类，如果父类中可变的基本方法太多，将会导致类的个数增加，系统更加庞大，设计也更加抽象，此时，可结合桥接模式来进行设计。
- 对一些复杂的算法进行分割，将算法中固定不变的部分设计为模板方法和父类具体方法，而一些可变的细节由子类实现。
- 各子类中公共的行为应被提取出来并集中到一个公共父类中，以避免代码重复。
- 需要通过子类来决定父类算法中某个步骤是否执行，实现子类对父类的反向控制。
示例：在校招时一般都会采用“宣讲会 -> 接收简历 -> 面试 -> 发放 Offer”这样一套固定流程。其中，各公司宣讲会（宣传企业文化、福利待遇）和接收简历（自带简历）的形式几乎是一样的，不同的是面试和发放 Offer 环节。阿里需要经过一面、二面、三面，并提供30W/年的薪酬；而腾讯则需要一面、二面，并提供25W/年的薪酬。
这里，公司是抽象类，“宣讲会 -> 接收简历 -> 面试 -> 发放 Offer”则是一套固定的模板方法（招聘流程）。具体类由阿里和腾讯表示，不同之处在于面试和发放 Offer 环节，需要它们分别实现。
这里，公司是抽象类，“宣讲会 -> 接收简历 -> 面试 -> 发放 Offer”则是一套固定的模板方法（招聘流程）。具体类由阿里和腾讯表示，不同之处在于面试和发放 Offer 环节，需要它们分别实现。
14. 命令模式（Command Pattern）
Command：定义命令的接口，声明执行的方法。
ConcreteCommand：命令接口实现对象，是“虚”的实现；通常会持有接收者，并调用接收者的功能来完成命令要执行的操作。
Receiver：接收者，真正执行命令的对象。任何类都可能成为一个接收者，只要它能够实现命令要求实现的相应功能。
Invoker：要求命令对象执行请求，通常会持有命令对象，可以持有很多的命令对象。这个是客户端真正触发命令并要求命令执行相应操作的地方，也就是说相当于使用命令对象的入口。
Client：创建具体命令对象，并设置其接收者（注意： 这并非常规意义上的客户端，而是在组装命令对象和接收者。或许，把这个 Client 称为装配者会更好理解，因为真正使用命令的客户端是从 Invoker 来触发执行）。
ConcreteCommand：命令接口实现对象，是“虚”的实现；通常会持有接收者，并调用接收者的功能来完成命令要执行的操作。
Receiver：接收者，真正执行命令的对象。任何类都可能成为一个接收者，只要它能够实现命令要求实现的相应功能。
Invoker：要求命令对象执行请求，通常会持有命令对象，可以持有很多的命令对象。这个是客户端真正触发命令并要求命令执行相应操作的地方，也就是说相当于使用命令对象的入口。
Client：创建具体命令对象，并设置其接收者（注意： 这并非常规意义上的客户端，而是在组装命令对象和接收者。或许，把这个 Client 称为装配者会更好理解，因为真正使用命令的客户端是从 Invoker 来触发执行）。
示例： 根据命令模式，实现一个命令队列，形成一个命令链。
以打车为例，又是滴滴（~O(∩_∩)O~），用户发起一个“打车”命令，司机接单，到达终点时，用户再次发起一个“付款”命令，司机收款。
和上述示例类似， Command 是一个抽象类，将被用作执行命令的接口。其他的 ConcreteCommand 类派生自它，提供了具体的命令（打车/付款）。
以打车为例，又是滴滴（~O(∩_∩)O~），用户发起一个“打车”命令，司机接单，到达终点时，用户再次发起一个“付款”命令，司机收款。
和上述示例类似， Command 是一个抽象类，将被用作执行命令的接口。其他的 ConcreteCommand 类派生自它，提供了具体的命令（打车/付款）。
15. 迭代器模式（Iterator Pattern）
16. 观察者模式（Observer Pattern）
Subject（抽象主题）：跟踪所有观察者，并提供添加和删除观察者的接口。
Observer（抽象观察者）：为所有的具体观察者定义一个接口，在得到主题的通知时进行自我更新。
ConcreteSubject（具体主题）：将有关状态存入各 ConcreteObserver 对象。当具体主题的状态发生任何更改时，通知所有观察者。
ConcreteObserver（具体观察者）：实现 Observer 所要求的更新接口，以便使本身的状态与主题的状态相协调。
Observer（抽象观察者）：为所有的具体观察者定义一个接口，在得到主题的通知时进行自我更新。
ConcreteSubject（具体主题）：将有关状态存入各 ConcreteObserver 对象。当具体主题的状态发生任何更改时，通知所有观察者。
ConcreteObserver（具体观察者）：实现 Observer 所要求的更新接口，以便使本身的状态与主题的状态相协调。
优缺点
优点：
优点：
- 观察者和被观察者是抽象耦合的
- 建立一套触发机制
- 如果一个被观察者对象有很多的直接和间接的观察者，将所有的观察者都通知到会花费很多时间。
- 如果在观察者和观察目标之间有循环依赖的话，观察目标会触发它们之间进行循环调用，可能导致系统崩溃。
- 观察者模式没有相应的机制让观察者知道所观察的目标对象是怎么发生变化的，而仅仅只是知道观察目标发生了变化。
- 有多个子类共有的方法，且逻辑相同。
- 重要的、复杂的方法，可以考虑作为模板方法。
示例： 滴滴：好，第一个月，价格上调至 12.5。。。
过了不久，心里想着：纳尼，都垄断了，还不多涨涨，果断 15.0。。。 然后通知给所有司机。
开始，我们创建了一个主题（滴滴）以及两个观察者（Jack Ma & Pony），通过 attach() 将他们加入至司机行列。调用 setPrice(12.5)，通知他们起步价为 12.5 元。后来呢，司机 Pony 由于种种原因（~O(∩_∩)O~大家都懂得）离职了 - detach() 注销。。。价格再次上调，涨、涨、涨 setPrice(15.0)。
过了不久，心里想着：纳尼，都垄断了，还不多涨涨，果断 15.0。。。 然后通知给所有司机。
开始，我们创建了一个主题（滴滴）以及两个观察者（Jack Ma & Pony），通过 attach() 将他们加入至司机行列。调用 setPrice(12.5)，通知他们起步价为 12.5 元。后来呢，司机 Pony 由于种种原因（~O(∩_∩)O~大家都懂得）离职了 - detach() 注销。。。价格再次上调，涨、涨、涨 setPrice(15.0)。
17. 中介者模式（Mediator Pattern）
- Mediator（抽象中介者）：为 Colleague 对象之间的通信定义接口。
- ConcreteMediator（具体中介者）：实现 Mediator 接口，并需要了解和维护各个 Colleague 对象，负责协调他们之间的通信。
- Colleague（抽象同事类）：定义与其他 Colleague 通信的接口。
- ConcreteColleague （具体同事类）：实现 Colleague 接口，并通过 Mediator 与其他 Colleague 进行沟通。
示例： 中介是对象的通信中心。当房东需要与租客通信时，他们之间不会直接交互，而是通过中介将消息发送给目标对象。
18.备忘录模式 （Memento Pattern）
- Originator（发起人）：负责创建一个 Memento，以记录当前时刻自身的内部状态，并可以使用 Memento 恢复内部状态。Originator 可以根据需要决定 Memento 储存自己的哪些内部状态。
- Memento（备忘录）：负责存储 Originator 对象的内部状态，并可以防止 Originator 以外的其他对象访问备忘录。
- Caretaker（管理者）：负责管理 Memento，但不能对 Memento 的内容进行访问或者操作。
示例： 备忘录模式也提供了时光倒流的机制，将一个对象某个时刻的状态进行备份，当用户后悔（需要返回之前的状态）时，可以把备份调用出来！
19.解释器模式（Interpreter Pattern）
20. 状态模式（State Pattern）
- Context（上下文）：定义一个与 Client 交互的接口。它维护对 ConcreteState 对象的引用，可以用该对象来定义当前状态。
- State（抽象状态）：定义接口，来声明每个 ConcreteState 应该做什么。
- ConcreteState（具体状态）：为 State 中定义的方法提供实现。
示例： 交通信号灯的状态流：红灯 -> 绿灯 -> 黄灯。。。实际上，就是各个状态之间的相互切换，这完全符合状态模式。
21. 策略模式（Strategy Pattern）
- Context（环境角色）：持有一个对 Strategy 的引用，最终给客户端调用。
- Strategy（抽象策略）：定义了一个公共接口，让不同的算法以不同的方式来实现。通过这个接口，Context 可以调用不同的算法。
- ConcreteStrategy（具体策略）：实现 Strategy 定义的接口，提供具体算法的实现。
示例： 要出去玩，有很多种出行方式，自行车、公交车、自驾、地铁、火车、飞机。。。如何选择最合适的呢？
这里的每一种出行方式都是一种具体的策略。如何选择，需要基于成本、便利和时间之间的权衡。
- 如果离家近，又怕堵车，可以骑自行车。
- 如果离家远，但想省钱，早点出发，可以乘公交车。
- 如果有车，并且不介意支付停车费，可以选择自驾。
- 如果没有车，但赶时间，可以乘出租车。
这里的每一种出行方式都是一种具体的策略。如何选择，需要基于成本、便利和时间之间的权衡。
22. 职责链模式 （Chain of Responsibility Pattern）
Handler（抽象处理者）：定义了处理请求所需的接口。
ConcreteHandler（具体处理者）：处理自己负责的请求，如果无法处理，则将请求传递给与之保持联系的后继者（即：successor）。
Client（客户端）：请求的发起者，将访问 Handler 来处理它。
ConcreteHandler（具体处理者）：处理自己负责的请求，如果无法处理，则将请求传递给与之保持联系的后继者（即：successor）。
Client（客户端）：请求的发起者，将访问 Handler 来处理它。
示例： 当员工发出请假请求时，链中的处理者可以对请求作出响应或者将其传递给上级。每个处理者都有自己的一套规则，而这套规则是他们可以批准的。审批流程：经理（1 天及以下） -> 总监（3 天及以下） -> 总裁（7 天为界限）。不同的请假天数由不同的职责人批准
23. 访问者模式 （Visitor Pattern）
Vistor（访问者）：为对象结构中每一个 ConcreteElement 声明一个 visit() 操作，从这个操作的名称或参数类型可以清楚知道需要访问的具体元素的类型。
ConcreteVisitor（具体访问者）：实现每个由 Visitor 声明的操作。
Element（元素）：定义一个 accept() 操作，它通常以一个 Vistor 作为参数。
ConcreteElement（具体元素）：实现 accept() 操作，通过调用 Visitor 的 visit() 方法来实现对元素的访问。
ObjectStructure（对象结构）：能够枚举它的元素，同时提供一个高层的接口，以允许访问者访问它的元素。
ConcreteVisitor（具体访问者）：实现每个由 Visitor 声明的操作。
Element（元素）：定义一个 accept() 操作，它通常以一个 Vistor 作为参数。
ConcreteElement（具体元素）：实现 accept() 操作，通过调用 Visitor 的 visit() 方法来实现对元素的访问。
ObjectStructure（对象结构）：能够枚举它的元素，同时提供一个高层的接口，以允许访问者访问它的元素。
示例： 在访问西安时，访问者会参观各个景点。对于景点来说，无论访问者是谁，它们都是不变的。而作为访问者，不同角色的访问方式也不尽相同，游客只负责旅游 - 吃喝玩乐，而清洁工则需要打扫卫生、清理垃圾。
这里，游客和清洁工是具体访问者，兵马俑、钟楼等景点是具体元素，西安这座城市是结构对象。
这里，游客和清洁工是具体访问者，兵马俑、钟楼等景点是具体元素，西安这座城市是结构对象。
六大设计原则
1 单一职责原则(Single Responsibility Principle - SRP)
一个类，只有一个引起它变化的原因。应该只有一个职责。每一个职责都是变化的一个轴线，如果一个类有一个以上的职责，这些职责就耦合在了一起。这会导致脆弱的设计。当一个职责发生变化时，可能会影响其它的职责。多个职责耦合在一起，会影响复用性。例如：要实现逻辑和界面的分离。
2 开放封闭原则(Open Closed Principle - OCP)
对扩展是开放的，而对修改是封闭的。
对扩展开放，意味着有新的需求或变化时，可以对现有代码进行扩展，以适应新的情况。
对修改封闭，意味着类一旦设计完成，就可以独立完成其工作，而不要对类进行任何修改。
封装变化，是实现开放封闭原则的重要手段，对于经常发生变化的状态一般将其封装为一个抽象。
拒绝滥用抽象，只将经常变化的部分进行抽象，这种经验可以从设计模式的学习与应用中获得。
对扩展开放，意味着有新的需求或变化时，可以对现有代码进行扩展，以适应新的情况。
对修改封闭，意味着类一旦设计完成，就可以独立完成其工作，而不要对类进行任何修改。
封装变化，是实现开放封闭原则的重要手段，对于经常发生变化的状态一般将其封装为一个抽象。
拒绝滥用抽象，只将经常变化的部分进行抽象，这种经验可以从设计模式的学习与应用中获得。
3 里氏替换原则(Liskov Substitution Principle - LSP)
子类可以扩展父类的功能，但不能改变父类原有的功能。它包含以下4层含义：
- 子类可以实现父类的抽象方法，但不能覆盖父类的非抽象方法。
- 子类中可以增加自己特有的方法。
- 当子类的方法重载父类的方法时，方法的前置条件（即方法的形参）要比父类方法的输入参数更宽松。
- 当子类的方法实现父类的抽象方法时，方法的后置条件（即方法的返回值）要比父类更严格。
4 最少知识原则(Least Knowledge Principle - LKP)
最少知识原则又叫迪米特法则。核心思想是：低耦合、高内聚
一个实体应当尽量少的与其他实体之间发生相互作用，使得系统功能模块相对独立。也就是说一个软件实体应当尽可能少的与其他实体发生相互作用。这样，当一个模块修改时，就会尽量少的影响其他的模块，扩展会相对容易，这是对软件实体之间通信的限制，它要求限制软件实体之间通信的宽度和深度。
一个实体应当尽量少的与其他实体之间发生相互作用，使得系统功能模块相对独立。也就是说一个软件实体应当尽可能少的与其他实体发生相互作用。这样，当一个模块修改时，就会尽量少的影响其他的模块，扩展会相对容易，这是对软件实体之间通信的限制，它要求限制软件实体之间通信的宽度和深度。
5 接口隔离原则(Interface Segregation Principle - ISP)
建立单一接口，不要建立庞大臃肿的接口，尽量细化接口，接口中的方法尽量少。
采用接口隔离原则对接口进行约束时，要注意以下几点：
采用接口隔离原则对接口进行约束时，要注意以下几点：
- 接口尽量小，但是要有限度。对接口进行细化可以提高程序设计灵活性是不挣的事实，但是如果过小，则会造成接口数量过多，使设计复杂化。所以一定要适度。
- 为依赖接口的类定制服务，只暴露给调用的类它需要的方法，它不需要的方法则隐藏起来。只有专注地为一个模块提供定制服务，才能建立最小的依赖关系。
- 提高内聚，减少对外交互。使接口用最少的方法去完成最多的事情。
6 依赖倒置原则(Dependence Inversion Principle - DIP)
依赖倒置原则的核心思想是面向接口编程，不应该面向实现（类）编程。
（面向实现强烈的依赖关系将会大大地抑制编程的灵活性和可复用性）
在实际编程中，要做到下面3点：
（面向实现强烈的依赖关系将会大大地抑制编程的灵活性和可复用性）
在实际编程中，要做到下面3点：
- 低层模块尽量都要有抽象类或接口，或者两者都有。
- 变量的声明类型尽量是抽象类或接口。
- 使用继承时遵循里氏替换原则。
参考Spring的工厂接口
客户使用Car的roll方法调用轮胎对应的方法时，不需要知道这个轮胎实例是用什么子类实现的，
他只需要知道定义转动方法的抽象类（JAVA中的interface）的内容就行了
他只需要知道定义转动方法的抽象类（JAVA中的interface）的内容就行了
设计思想
我们怎么优化？有两个方向，一个是ScaleUP，就是把机器的CPU、内存、硬盘跑满，但是一个机器能跑的是有限的。如果做到服务海量用户，ScaleOUT是一定要做到的，就是平行扩容 。区块链架构的性能优化跟其他优化没有什么区别，我们2018年做了一次代码，我们内部有些争议，有些路线的磋商有，些人说重构 就好了，我些处女座的架构师看不下去，要把它重写，最后我们有个妥协，就是重用原来大量的模块，但是把它解耦、模块化，接口编程，同步的、虚拟机的、共识的都是模块，再把这些模块组合起来，拒绝意大利面条式编程，做到隔离、低耦合、高内聚，基于模块化架构做并行化，一个个小积木放那是高内聚，可以在多线程多进程跑，我可以给它加各种各样的策略，非常容易的组合起来，做到交易并行计算、共识并行处理、网络并行传输和编解码。最后一点，把数据高速缓存起来，区块链有个特点，数据一旦生成就不会再改历史数据，它只会新增，我就有很多办法把历史数据，它如果是热点的，比如刚刚产生的仓单或者存证，放在内存里。这要有些策略和技巧，怎么识别哪些是热的、冷的，怎么做RIU、怎么分配大小。这个策略可以从1000提到1万。
网络通信
TCP拥塞控制和流量控制
流量控制
流量控制是端到端的控制，例如A通过网络给B发数据，A发送的太快导致B没法接收(B缓冲窗口过小或者处理过慢)，这时候的控制就是流量控制
原理是通过滑动窗口的大小改变来实现
如何避免零窗口死锁
B向A发送了零窗口的报文段后不久，B的接收缓存又有了一些存储空间。于是B向A发送了rwind=400的报文段，然而这个报文段在传送中丢失了。A一直等待收到B发送的非零窗口的通知，而B也一直等待A发送的数据。这样就死锁了。为了解决这种死锁状态，TCP为每个连接设有一个持续计时器。只要TCP连接的一方收到对方的零窗口通知，就启动持续计时器，若持续计时器设置的时间到期，就发送一个零窗口探测报文段（仅携带1字节的数据），而对方就在确认这个探测报文段时给出了现在的窗口值。
拥塞控制
A与B之间的网络发生堵塞导致传输过慢或者丢包，来不及传输。防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不至于过载
机制
发送报文段速率的确定，既要根据接收端的接收能力，又要从全局考虑不要使网络发生拥塞，这由接收窗口和拥塞窗口两个状态量确定
接收端窗口rwnd（Reciver Window)又称通知窗口（Advertised Window),是接收端根据目前的接收缓存大小所许诺的最新窗口值，是来自接收端的流量控制
拥塞窗口cwnd（Congestion Window)是发送端根据自己估计的网络拥塞程度而设置的窗口值，是来自发送端的流量控制
慢启动原理
1）当主机开始发送数据时，如果立即将较大的发送窗口的全部数据字节都注入到网络中，那么由于不清楚网络的情况，有可能引其网络拥塞
2）比较好的方法是试探一下，即从小到达逐渐增大发送端的拥塞控制窗口数值
3）通常在刚刚开始发送报文段时可先将拥塞窗口cwnd设置为一个最大报文段的MSS（每一个tcp报文的最大值）的数值。现在Google默认建议10个窗口。在每收到一个对新报文段确认后，将拥塞窗口增加至多一个MSS的数值，当rwind足够大的时候，为了防止拥塞窗口cwind的增长引起网络拥塞，还需要另外一个变量—慢开始门限ssthresh
2）比较好的方法是试探一下，即从小到达逐渐增大发送端的拥塞控制窗口数值
3）通常在刚刚开始发送报文段时可先将拥塞窗口cwnd设置为一个最大报文段的MSS（每一个tcp报文的最大值）的数值。现在Google默认建议10个窗口。在每收到一个对新报文段确认后，将拥塞窗口增加至多一个MSS的数值，当rwind足够大的时候，为了防止拥塞窗口cwind的增长引起网络拥塞，还需要另外一个变量—慢开始门限ssthresh
拥塞避免
1）TCP连接初始化，将拥塞窗口设置为1
2）执行慢开始算法，cwind按指数规律增长，知道cwind == ssthreshold开始执行拥塞避免算法，cwnd按线性规律增长
3）当网络发生拥塞，把ssthresh值更新为拥塞前ssthresh值的一半，cwnd重新设置为1，按照步骤（2）执行。
2）执行慢开始算法，cwind按指数规律增长，知道cwind == ssthreshold开始执行拥塞避免算法，cwnd按线性规律增长
3）当网络发生拥塞，把ssthresh值更新为拥塞前ssthresh值的一半，cwnd重新设置为1，按照步骤（2）执行。
快重传
一条TCP连接有时会因等待重传计时器的超时而空闲较长的时间，慢开始和拥塞避免无法很好的解决这类问题，因此提出了快重传和快恢复的拥塞控制方法。
快重传算法并非取消了重传机制，只是在某些情况下更早的重传丢失的报文段（如果当发送端接收到三个重复的确认ACK时，则断定分组丢失，立即重传丢失的报文段，而不必等待重传计时器超时）。慢开始算法只是在TCP建立时才使用。
快重传算法并非取消了重传机制，只是在某些情况下更早的重传丢失的报文段（如果当发送端接收到三个重复的确认ACK时，则断定分组丢失，立即重传丢失的报文段，而不必等待重传计时器超时）。慢开始算法只是在TCP建立时才使用。
TCP的确认机制
发送方发送segment序号为1，接收方收到之后需要ACK确认，这里需要敲黑板提醒还在睡觉同学的注意，ACK确认号是多少？
ACK = 2 ，什么意思呢？ 意思是说，segment 1已经成功接收，寡人等待segment 2的到来
ACK = 2 ，什么意思呢？ 意思是说，segment 1已经成功接收，寡人等待segment 2的到来
快恢复算法
1）当发送方连续收到三个重复确认时，就执行“乘法减小”算法，把慢开始门限减半，这是为了预防网络发生拥塞。
2）由于发送方现在认为网络很可能没有发生拥塞，因此现在不执行慢开始算法，而是把cwnd值设置为慢开始门限减半后的值，然后开始执行拥塞避免算法，使拥塞窗口的线性增大。
2）由于发送方现在认为网络很可能没有发生拥塞，因此现在不执行慢开始算法，而是把cwnd值设置为慢开始门限减半后的值，然后开始执行拥塞避免算法，使拥塞窗口的线性增大。
总结
没有发生拥塞之前使用前两种算法，发生拥塞之后(即三次重复确认)使用后两种算法。
区别
拥塞控制就是防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不会过载
流量控制往往是点对点通信量的控制，是一个端到端的问题，流量控制要做的是抑制发送端发送数据的速率，以便接收端来得及接收。
流量控制往往是点对点通信量的控制，是一个端到端的问题，流量控制要做的是抑制发送端发送数据的速率，以便接收端来得及接收。
TCP怎么保证可靠性？
应用数据被分割成TCP认为最适合发送的数据块
超时重传：当TCP发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段
TCP给发送的每一个包进行编号，接收方对数据包进行排序，把有序数据传送给应用层
校验和：TCP将保持它首部和数据的检验和。这是一个端到端的检验和，目的是检测数据在传输过程中的任何变化。如果收到段的检验和有差错，TCP将丢弃这个报文段和不确认收到此报文段
TCP的接收端会丢弃重复的数据
流量控制：让发送方的发送速率不要太快，要让接收方来得及接收
拥塞控制：当网络拥塞时，减少数据的发送
超时重传：当TCP发出一个段后，它启动一个定时器，等待目的端确认收到这个报文段。如果不能及时收到一个确认，将重发这个报文段
TCP给发送的每一个包进行编号，接收方对数据包进行排序，把有序数据传送给应用层
校验和：TCP将保持它首部和数据的检验和。这是一个端到端的检验和，目的是检测数据在传输过程中的任何变化。如果收到段的检验和有差错，TCP将丢弃这个报文段和不确认收到此报文段
TCP的接收端会丢弃重复的数据
流量控制：让发送方的发送速率不要太快，要让接收方来得及接收
拥塞控制：当网络拥塞时，减少数据的发送
https
http协议与TCP协议的联系
TCP协议是传输层协议，主要解决数据如何在网络中传输，而HTTP是应用层协议，主要解决如何包装数据。
Http协议是建立在TCP协议基础之上的，当浏览器需要从服务器获取网页数据的时候，会发出一次Http请求。Http会通过TCP建立起一个到服务器的连接通道，当本次请求需要的数据完毕后，Http会立即将TCP连接断开，这个过程是很短的。所以Http连接是一种短连接，是一种无状态的连接。
Http协议是建立在TCP协议基础之上的，当浏览器需要从服务器获取网页数据的时候，会发出一次Http请求。Http会通过TCP建立起一个到服务器的连接通道，当本次请求需要的数据完毕后，Http会立即将TCP连接断开，这个过程是很短的。所以Http连接是一种短连接，是一种无状态的连接。
http/1.0和http/1.1的区别？
http1.1提供永久性连接，即1.0使用非持久连接
http1.1增加host头
http1.1还提供了身份认证，状态管理和cache缓存机制等相关的请求头和响应头。
http1.1增加host头
http1.1还提供了身份认证，状态管理和cache缓存机制等相关的请求头和响应头。
http四个会话过程？
建立tcp连接
发出请求文档
发出响应文档
释放tcp连接
网页解析的过程
发出请求文档
发出响应文档
释放tcp连接
网页解析的过程
SSL/TLS
SSL(Secure Socket Layer 安全套接层)是基于HTTPS下的一个协议加密层，TLS（传输层安全）是更为安全的升级版 SSL。由于 SSL 这一术语更为常用，因此我们仍然将我们的安全证书称作 SSL
它利用对称加密、公私钥不对称加密及其密钥交换算法，CA系统进行加密且可信任的信息传输
SSL协议
SSL协议可分为两层
SSL记录协议（SSL Record Protocol）：它建立在可靠的传输协议（如TCP）之上，为高层协议提供数据封装、压缩、加密等基本功能的支持
SSL握手协议（SSL Handshake Protocol）：它建立在SSL记录协议之上，用于在实际的数据传输开始前，通讯双方进行身份认证、协商加密算法、交换加密密钥等。
作用
裸http协议明文传输的三大风险
（1） 窃听风险（eavesdropping）：第三方可以获知通信内容。
（2） 篡改风险（tampering）：第三方可以修改通信内容。
（3） 冒充风险（pretending）：第三方可以冒充他人身份参与通信。
（2） 篡改风险（tampering）：第三方可以修改通信内容。
（3） 冒充风险（pretending）：第三方可以冒充他人身份参与通信。
SSL/TLS协议的作用
（1） 所有信息都是加密传播，第三方无法窃听。
（2） 具有校验机制，一旦被篡改，通信双方会立刻发现。
（3） 配备身份证书，防止身份被冒充。
（2） 具有校验机制，一旦被篡改，通信双方会立刻发现。
（3） 配备身份证书，防止身份被冒充。
http加密握手过程
CA认证过程
基本的运行过程
（1） 客户端向服务器端索要并验证公钥(非对称加密)。
（2） 双方协商生成"对话密钥"。（对称加密）
（3） 双方采用"对话密钥"进行加密通信。
（2） 双方协商生成"对话密钥"。（对称加密）
（3） 双方采用"对话密钥"进行加密通信。
使用openssl生成https证书
rpc接口和http接口的区别和联系
http接口
http接口是基于http协议的post和get接口。
rpc接口
rpc接口就相当于调用本地接口一样调用远程服务的接口。
常用的rpc框架
目前流行的开源RPC框架还是比较多的。下面重点介绍三种：
- gRPC是Google最近公布的开源软件，基于最新的HTTP2.0协议，并支持常见的众多编程语言。 我们知道HTTP2.0是基于二进制的HTTP协议升级版本，目前各大浏览器都在快马加鞭的加以支持。 这个RPC框架是基于HTTP协议实现的，底层使用到了Netty框架的支持。
- Thrift是Facebook的一个开源项目，主要是一个跨语言的服务开发框架。它有一个代码生成器来对它所定义的IDL定义文件自动生成服务代码框架。用户只要在其之前进行二次开发就行，对于底层的RPC通讯等都是透明的。不过这个对于用户来说的话需要学习特定领域语言这个特性，还是有一定成本的。
- Dubbo是阿里集团开源的一个极为出名的RPC框架，在很多互联网公司和企业应用中广泛使用。协议和序列化框架都可以插拔是及其鲜明的特色。同样 的远程接口是基于Java Interface，并且依托于spring框架方便开发。可以方便的打包成单一文件，独立进程运行，和现在的微服务概念一致。
socket
select、poll、epoll
select，poll，epoll都是IO多路复用的机制。I/O多路复用就通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间
select缺点
（1）每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大
（2）同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大
（3）select支持的文件描述符数量太小了，默认是1024
（2）同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大
（3）select支持的文件描述符数量太小了，默认是1024
poll
poll的机制与select类似，与select在本质上没有多大差别，管理多个描述符也是进行轮询，根据描述符的状态进行处理，但是poll没有最大文件描述符数量的限制。poll和select同样存在一个缺点就是，包含大量文件描述符的数组被整体复制于用户态和内核的地址空间之间，而不论这些文件描述符是否就绪，它的开销随着文件描述符数量的增加而线性增大。
epoll
两种工作模式
水平触发模式
这种模式和select的触发方式是一样的，即只要文件描述符的缓冲区中有数据，就永远通知用户这个描述符是可读的，这种模式对block和noblock的描述符都支持，编程的难度也比较小
边缘触发模式
更高效且只有epoll提供的模式
只支持nonblock的文件描述符，他只有在文件描述符有新的监听事件发生的时候（例如有新的数据包到达）才会通知应用程序，在没有新的监听时间发生时，即使缓冲区有数据（即上一次没有读完，或者甚至没有读），epoll也不会继续通知应用程序，使用这种模式一般要求应用程序收到文件描述符读就绪通知时，要一直读数据直到收到EWOULDBLOCK/EAGAIN错误，使用边缘触发就必须即将缓冲区中的内容读完，否则有可能引起死等.
这种模式虽然容易出错，但是性能要比前面的模式更高效，因为只需要监听是否有事件发生，发生了就直接将描述符加入就绪队列即可。
这种模式虽然容易出错，但是性能要比前面的模式更高效，因为只需要监听是否有事件发生，发生了就直接将描述符加入就绪队列即可。
优化特点
对于第一个缺点，epoll的解决方案在epoll_ctl函数中。每次注册新的事件到epoll句柄中时（在epoll_ctl中指定EPOLL_CTL_ADD），会把所有的fd拷贝进内核，而不是在epoll_wait的时候重复拷贝。epoll保证了每个fd在整个过程中只会拷贝一次。
对于第二个缺点，epoll的解决方案不像select或poll一样每次都把current轮流加入fd对应的设备等待队列中，而只在epoll_ctl时把current挂一遍（这一遍必不可少）并为每个fd指定一个回调函数，当设备就绪，唤醒等待队列上的等待者时，就会调用这个回调函数，而这个回调函数会把就绪的fd加入一个就绪链表）。epoll_wait的工作实际上就是在这个就绪链表中查看有没有就绪的fd（利用schedule_timeout()实现睡一会，判断一会的效果，和select实现中的第7步是类似的）
对于第三个缺点，epoll没有这个限制，它所支持的FD上限是最大可以打开文件的数目，这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左右，具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。
核心数据结构
epoll的核心是3个API，核心数据结构是：1个红黑树和1个链表
API
int epoll_create(int size)
功能：内核会产生一个epoll 实例数据结构并返回一个文件描述符，这个特殊的描述符就是epoll实例的句柄，后面的两个接口都以它为中心（即epfd形参）。
功能：内核会产生一个epoll 实例数据结构并返回一个文件描述符，这个特殊的描述符就是epoll实例的句柄，后面的两个接口都以它为中心（即epfd形参）。
int epoll_ctl(int epfd， int op， int fd， struct epoll_event *event)
功能：
将被监听的描述符添加到红黑树或从红黑树中删除或者对监听事件进行修改
功能：
将被监听的描述符添加到红黑树或从红黑树中删除或者对监听事件进行修改
int epoll_wait(int epfd， struct epoll_event *events， int maxevents， int timeout);
功能：
阻塞等待注册的事件发生，返回事件的数目，并将触发的事件写入events数组中。
功能：
阻塞等待注册的事件发生，返回事件的数目，并将触发的事件写入events数组中。
总结
（1）select，poll实现需要自己不断轮询所有fd集合，直到设备就绪，期间可能要睡眠和唤醒多次交替。而epoll其实也需要调用epoll_wait不断轮询就绪链表，期间也可能多次睡眠和唤醒交替，但是它是设备就绪时，调用回调函数，把就绪fd放入就绪链表中，并唤醒在epoll_wait中进入睡眠的进程。虽然都要睡眠和交替，但是select和poll在“醒着”的时候要遍历整个fd集合，而epoll在“醒着”的时候只要判断一下就绪链表是否为空就行了，这节省了大量的CPU时间。这就是回调机制带来的性能提升。
（2）select，poll每次调用都要把fd集合从用户态往内核态拷贝一次，并且要把current往设备等待队列中挂一次，而epoll只要一次拷贝，而且把current往等待队列上挂也只挂一次（在epoll_wait的开始，注意这里的等待队列并不是设备等待队列，只是一个epoll内部定义的等待队列）。这也能节省不少的开销。
（2）select，poll每次调用都要把fd集合从用户态往内核态拷贝一次，并且要把current往设备等待队列中挂一次，而epoll只要一次拷贝，而且把current往等待队列上挂也只挂一次（在epoll_wait的开始，注意这里的等待队列并不是设备等待队列，只是一个epoll内部定义的等待队列）。这也能节省不少的开销。
常问问题
select用法
int select(int nfds, fd_set *readfds, fd_set *writefds,
fd_set *exceptfds, struct timeval *timeout);
nfds是监听文件描述符的总数。它通常被设置为select监听的所有文件描述符的最大值加1.
readfds, writefds, exceptfds指向可读、可写、异常等事件对应的文件描述符集合。应用程序调用select时，通过这3个参数，传入自己感兴趣的文件描述符。select返回时，内核通过修改它们来通知应用程序哪些文件描述符已经就绪。我们看到，应用程序和内核都修改了这些参数。
fd_set *exceptfds, struct timeval *timeout);
nfds是监听文件描述符的总数。它通常被设置为select监听的所有文件描述符的最大值加1.
readfds, writefds, exceptfds指向可读、可写、异常等事件对应的文件描述符集合。应用程序调用select时，通过这3个参数，传入自己感兴趣的文件描述符。select返回时，内核通过修改它们来通知应用程序哪些文件描述符已经就绪。我们看到，应用程序和内核都修改了这些参数。
非阻塞 connect 函数的写法
阻塞socket与非阻塞socket的区别
send/recv函数的返回值情形
epoll 的水平和边缘模式
三年以上号称设计过服务器
nagle算法
算法规则
Nagle算法的规则（可参考tcp_output.c文件里tcp_nagle_check函数注释）：
（1）如果包长度达到MSS，则允许发送；
（2）如果该包含有FIN，则允许发送；
（3）设置了TCP_NODELAY选项，则允许发送；
（4）未设置TCP_CORK选项时，若所有发出去的小数据包（包长度小于MSS）均被确认，则允许发送；
（5）上述条件都未满足，但发生了超时（一般为200ms），则立即发送。
（1）如果包长度达到MSS，则允许发送；
（2）如果该包含有FIN，则允许发送；
（3）设置了TCP_NODELAY选项，则允许发送；
（4）未设置TCP_CORK选项时，若所有发出去的小数据包（包长度小于MSS）均被确认，则允许发送；
（5）上述条件都未满足，但发生了超时（一般为200ms），则立即发送。
关闭参数
默认情况下，发送数据采用Negle 算法。这样虽然提高了网络吞吐量，但是实时性却降低了，在一些交互性很强的应用程序来说是不允许的，
使用TCP_NODELAY选项可以禁止Negale 算法。
使用TCP_NODELAY选项可以禁止Negale 算法。
延迟确认机制
与Nagle算法一样，延迟ACK的目的也是为了减少网络中传输大量的小报文数，但该报文数是针对ACK报文的。
一个来自发送端的报文到达接收端，TCP会延迟ACK的发送，希望应用程序会对刚刚收到的数据进行应答，这样就可以用新数据将ACK捎带过去。
一个来自发送端的报文到达接收端，TCP会延迟ACK的发送，希望应用程序会对刚刚收到的数据进行应答，这样就可以用新数据将ACK捎带过去。
关闭延迟确认Delayed Ack， 每次都得设置 TCP_QUICKACK
linux下socket有一个pingpong属性来表明当前链接是否为交互数据流，如其值为1，则表明为交互数据流，会使用延迟确认机制。但是pingpong这个值是会动态变化的。所以要每次都设置
keepalive选项
Linger选项
有下列三种情况：
1、设置 l_onoff为0，则该选项关闭，l_linger的值被忽略，等于内核缺省情况，close调用会立即返回给调用者，如果可能将会传输任何未发送的数据；
2、设置 l_onoff为非0，l_linger为0，则套接口关闭时TCP夭折连接，TCP将丢弃保留在套接口发送缓冲区中的任何数据并发送一个RST给对方，而不是通常的四分组终止序列，这避免了TIME_WAIT状态；
3、设置 l_onoff 为非0，l_linger为非0，当套接口关闭时内核将拖延一段时间（由l_linger决定）。如果套接口缓冲区中仍残留数据，进程将处于睡眠状态，直 到（a）所有数据发送完且被对方确认，之后进行正常的终止序列（描述字访问计数为0）或（b）延迟时间到。此种情况下，应用程序检查close的返回值是非常重要的，如果在数据发送完并被确认前时间到，close将返回EWOULDBLOCK错误且套接口发送缓冲区中的任何数据都丢失。close的成功返回仅告诉我们发送的数据（和FIN）已由对方TCP确认，它并不能告诉我们对方应用进程是否已读了数据。如果套接口设为非阻塞的，它将不等待close完成。
原文链接：https://blog.csdn.net/factor2000/article/details/3929816
1、设置 l_onoff为0，则该选项关闭，l_linger的值被忽略，等于内核缺省情况，close调用会立即返回给调用者，如果可能将会传输任何未发送的数据；
2、设置 l_onoff为非0，l_linger为0，则套接口关闭时TCP夭折连接，TCP将丢弃保留在套接口发送缓冲区中的任何数据并发送一个RST给对方，而不是通常的四分组终止序列，这避免了TIME_WAIT状态；
3、设置 l_onoff 为非0，l_linger为非0，当套接口关闭时内核将拖延一段时间（由l_linger决定）。如果套接口缓冲区中仍残留数据，进程将处于睡眠状态，直 到（a）所有数据发送完且被对方确认，之后进行正常的终止序列（描述字访问计数为0）或（b）延迟时间到。此种情况下，应用程序检查close的返回值是非常重要的，如果在数据发送完并被确认前时间到，close将返回EWOULDBLOCK错误且套接口发送缓冲区中的任何数据都丢失。close的成功返回仅告诉我们发送的数据（和FIN）已由对方TCP确认，它并不能告诉我们对方应用进程是否已读了数据。如果套接口设为非阻塞的，它将不等待close完成。
原文链接：https://blog.csdn.net/factor2000/article/details/3929816
对于某一端出现大量CLOSE_WAIT 或者 TIME_WAIT如何解决
服务器保持了大量TIME_WAIT状态
TIME_WAIT状态可以通过优化服务器参数得到解决，因为发生TIME_WAIT的情况是服务器自己可控的，要么就是对方连接的异常，要么就是自己没有迅速回收资源，总之不是由于自己程序错误导致的。
下面来看一下我们网管对/etc/sysctl.conf文件的修改：
#对于一个新建连接，内核要发送多少个 SYN 连接请求才决定放弃,不应该大于255，默认值是5，对应于180秒左右时间
net.ipv4.tcp_syn_retries=2
#net.ipv4.tcp_synack_retries=2
#表示当keepalive起用的时候，TCP发送keepalive消息的频度。缺省是2小时，改为300秒
net.ipv4.tcp_keepalive_time=1200
net.ipv4.tcp_orphan_retries=3
#表示如果套接字由本端要求关闭，这个参数决定了它保持在FIN-WAIT-2状态的时间
net.ipv4.tcp_fin_timeout=30
#表示SYN队列的长度，默认为1024，加大队列长度为8192，可以容纳更多等待连接的网络连接数。
net.ipv4.tcp_max_syn_backlog = 4096
#表示开启SYN Cookies。当出现SYN等待队列溢出时，启用cookies来处理，可防范少量SYN攻击，默认为0，表示关闭
net.ipv4.tcp_syncookies = 1
#表示开启重用。允许将TIME-WAIT sockets重新用于新的TCP连接，默认为0，表示关闭
net.ipv4.tcp_tw_reuse = 1
#表示开启TCP连接中TIME-WAIT sockets的快速回收，默认为0，表示关闭
net.ipv4.tcp_tw_recycle = 1
##减少超时前的探测次数
net.ipv4.tcp_keepalive_probes=5
##优化网络设备接收队列
net.core.netdev_max_backlog=3000
修改完之后执行/sbin/sysctl -p让参数生效。
这里头主要注意到的是net.ipv4.tcp_tw_reuse
net.ipv4.tcp_tw_recycle
net.ipv4.tcp_fin_timeout
net.ipv4.tcp_keepalive_*
这几个参数。
net.ipv4.tcp_tw_reuse和net.ipv4.tcp_tw_recycle的开启都是为了回收处于TIME_WAIT状态的资源。
net.ipv4.tcp_fin_timeout这个时间可以减少在异常情况下服务器从FIN-WAIT-2转到TIME_WAIT的时间。
net.ipv4.tcp_keepalive_*一系列参数，是用来设置服务器检测连接存活的相关配置。
#对于一个新建连接，内核要发送多少个 SYN 连接请求才决定放弃,不应该大于255，默认值是5，对应于180秒左右时间
net.ipv4.tcp_syn_retries=2
#net.ipv4.tcp_synack_retries=2
#表示当keepalive起用的时候，TCP发送keepalive消息的频度。缺省是2小时，改为300秒
net.ipv4.tcp_keepalive_time=1200
net.ipv4.tcp_orphan_retries=3
#表示如果套接字由本端要求关闭，这个参数决定了它保持在FIN-WAIT-2状态的时间
net.ipv4.tcp_fin_timeout=30
#表示SYN队列的长度，默认为1024，加大队列长度为8192，可以容纳更多等待连接的网络连接数。
net.ipv4.tcp_max_syn_backlog = 4096
#表示开启SYN Cookies。当出现SYN等待队列溢出时，启用cookies来处理，可防范少量SYN攻击，默认为0，表示关闭
net.ipv4.tcp_syncookies = 1
#表示开启重用。允许将TIME-WAIT sockets重新用于新的TCP连接，默认为0，表示关闭
net.ipv4.tcp_tw_reuse = 1
#表示开启TCP连接中TIME-WAIT sockets的快速回收，默认为0，表示关闭
net.ipv4.tcp_tw_recycle = 1
##减少超时前的探测次数
net.ipv4.tcp_keepalive_probes=5
##优化网络设备接收队列
net.core.netdev_max_backlog=3000
修改完之后执行/sbin/sysctl -p让参数生效。
这里头主要注意到的是net.ipv4.tcp_tw_reuse
net.ipv4.tcp_tw_recycle
net.ipv4.tcp_fin_timeout
net.ipv4.tcp_keepalive_*
这几个参数。
net.ipv4.tcp_tw_reuse和net.ipv4.tcp_tw_recycle的开启都是为了回收处于TIME_WAIT状态的资源。
net.ipv4.tcp_fin_timeout这个时间可以减少在异常情况下服务器从FIN-WAIT-2转到TIME_WAIT的时间。
net.ipv4.tcp_keepalive_*一系列参数，是用来设置服务器检测连接存活的相关配置。
对于TIME_WAIT，它只会出现在主动断开方，也就是上图中的客户端。之所以有TIME_WAIT这个状态而不是直接编程CLOSED状态主要有以下两个原因：
（1）、保证服务端能够正常收到最后一个ACK包，确保是正常断开，可靠释放；
（2）、防止数据错乱。假如没有这个TIME_WAIT状态，假设当前有一条连接，因某些原因先关闭，紧接着又以相同的四元组建立一条新的连接，由于TCP无法区分这两条连接有什么不同，就可能会发生这样的情况：发送数据可能会发送到上一条连接中，这就会出现一些数据混乱的问题。
TIME_WAIT状态有一个默认过期时间，默认是2MSL（最大生存时间），不同的操作系统默认的MSL是不一样的。如果有大量的TIME_WAIT，就会造成本地端口不释放，无法通过这个端口建立新的连接，如果本地端口都用完了，就会出现无法建立TCP连接来访问服务端了。
解决方法一般有两种（具体需要根据自身情况来定）:
1、调节内核参数，以CentOS为例，主要的参数有tcp_max_tw_buckets、tcp_tw_recycle、tcp_tw_reuse这三个配置项。
（1）、tcp_max_tw_buckets：该配置项用来防范简单的DoS攻击 ，在某些情况下，可以适当调大，但绝对不应调小。作用：在 TIME_WAIT 数量等于 tcp_max_tw_buckets 时，不会有新的 TIME_WAIT 产生。
（2）、tcp_tw_recycle：该配置项可用于快速回收处于TIME_WAIT状态的socket以便重新分配。默认是关闭的，必要时可以开启该配置。
（3）、tcp_tw_reuse：开启该选项后，kernel会复用处于TIME_WAIT状态的socket，当然复用的前提是“从协议角度来看，复用是安全的”。
2、修改应用程序。
（1）、将TCP短连接改造为长连接。通常情况下，如果发起连接的目标也是自己可控制的服务器时，它们自己的TCP通信最好采用长连接，避免大量TCP短连接每次建立/释放产生的各种开销；如果建立连接的目标是不受自己控制的机器时，能否使用长连接就需要考虑对方机器是否支持长连接方式了。
（2）、通过getsockopt/setsockoptapi设置socket的SO_LINGER选项。
（1）、保证服务端能够正常收到最后一个ACK包，确保是正常断开，可靠释放；
（2）、防止数据错乱。假如没有这个TIME_WAIT状态，假设当前有一条连接，因某些原因先关闭，紧接着又以相同的四元组建立一条新的连接，由于TCP无法区分这两条连接有什么不同，就可能会发生这样的情况：发送数据可能会发送到上一条连接中，这就会出现一些数据混乱的问题。
TIME_WAIT状态有一个默认过期时间，默认是2MSL（最大生存时间），不同的操作系统默认的MSL是不一样的。如果有大量的TIME_WAIT，就会造成本地端口不释放，无法通过这个端口建立新的连接，如果本地端口都用完了，就会出现无法建立TCP连接来访问服务端了。
解决方法一般有两种（具体需要根据自身情况来定）:
1、调节内核参数，以CentOS为例，主要的参数有tcp_max_tw_buckets、tcp_tw_recycle、tcp_tw_reuse这三个配置项。
（1）、tcp_max_tw_buckets：该配置项用来防范简单的DoS攻击 ，在某些情况下，可以适当调大，但绝对不应调小。作用：在 TIME_WAIT 数量等于 tcp_max_tw_buckets 时，不会有新的 TIME_WAIT 产生。
（2）、tcp_tw_recycle：该配置项可用于快速回收处于TIME_WAIT状态的socket以便重新分配。默认是关闭的，必要时可以开启该配置。
（3）、tcp_tw_reuse：开启该选项后，kernel会复用处于TIME_WAIT状态的socket，当然复用的前提是“从协议角度来看，复用是安全的”。
2、修改应用程序。
（1）、将TCP短连接改造为长连接。通常情况下，如果发起连接的目标也是自己可控制的服务器时，它们自己的TCP通信最好采用长连接，避免大量TCP短连接每次建立/释放产生的各种开销；如果建立连接的目标是不受自己控制的机器时，能否使用长连接就需要考虑对方机器是否支持长连接方式了。
（2）、通过getsockopt/setsockoptapi设置socket的SO_LINGER选项。
服务器保持了大量CLOSE_WAIT状态
如果一直保持在CLOSE_WAIT状态，那么只有一种情况，就是在对方关闭连接之后服务器程序自己没有进一步发出FIN信号，一般原因都是TCP连接没有调用关闭方法。换句话说，就是在对方连接关闭之后，程序里没有检测到，或者程序压根就忘记了这个时候需要关闭连接，于是这个资源就一直被程序占着。这种情况，通过服务器内核参数也没办法解决，服务器对于程序抢占的资源没有主动回收的权利，除非终止程序运行，一定程度上，可以使用TCP的KeepAlive功能，让操作系统替我们自动清理掉CLOSE_WAIT连接。
但是实际上，还是主要是因为我们的程序代码有问题，通常是如下问题：
当对方调用closesocket的时候，你的程序正在
C代码
int nRet = recv(s,….);
if (nRet == SOCKET_ERROR)
{
// closesocket(s);
return FALSE;
} 很多人就是忘记了那句closesocket
当主动关闭的一方发送FIN到被动关闭这边后，被动关闭这边的 TCP马上回应一个ACK过去，同时向上面应用程序提交一个ERROR，
导致上面的SOCKET的send或者recv返回SOCKET_ERROR，正常情况下，如果上面在返回SOCKET_ERROR后调用了 closesocket,那么被动关闭的者一方的TCP就会发送一个FIN过去，自己的状态就变迁到LAST_ACK。
但是实际上，还是主要是因为我们的程序代码有问题，通常是如下问题：
当对方调用closesocket的时候，你的程序正在
C代码
int nRet = recv(s,….);
if (nRet == SOCKET_ERROR)
{
// closesocket(s);
return FALSE;
} 很多人就是忘记了那句closesocket
当主动关闭的一方发送FIN到被动关闭这边后，被动关闭这边的 TCP马上回应一个ACK过去，同时向上面应用程序提交一个ERROR，
导致上面的SOCKET的send或者recv返回SOCKET_ERROR，正常情况下，如果上面在返回SOCKET_ERROR后调用了 closesocket,那么被动关闭的者一方的TCP就会发送一个FIN过去，自己的状态就变迁到LAST_ACK。
通讯协议如何设计或如何解决数据包的粘包与分片问题
在大多数场景下，是不存在丢包和包乱序问题的，TCP 通信是可靠通信方式，TCP 协议栈通过序列号和包重传确认机制保证数据包的有序和一定被正确发到目的地；
固定包长的数据包
以指定字符（串）为包的结束标志
包头 + 包体格式
心跳机制如何设计；（可能不会直接问问题本身，如问如何检查死链）
方法1：应用层自己实现的心跳包
由应用程序自己发送心跳包来检测连接是否正常，大致的方法是：服务器在一个 Timer事件中定时 向客户端发送一个短小精悍的数据包，然后启动一个低级别的线程，在该线程中不断检测客户端的回应， 如果在一定时间内没有收到客户端的回应，即认为客户端已经掉线；同样，如果客户端在一定时间内没 有收到服务器的心跳包，则认为连接不可用。
方法2：TCP的KeepAlive保活机制
因为要考虑到一个服务器通常会连接多个客户端，因此由用户在应用层自己实现心跳包，代码较多 且稍显复杂，而利用TCP／IP协议层为内置的KeepAlive功能来实现心跳功能则简单得多。 不论是服务端还是客户端，一方开启KeepAlive功能后，就会自动在规定时间内向对方发送心跳包， 而另一方在收到心跳包后就会自动回复，以告诉对方我仍然在线。 因为开启KeepAlive功能需要消耗额外的宽带和流量，所以TCP协议层默认并不开启KeepAlive功 能，尽管这微不足道，但在按流量计费的环境下增加了费用，另一方面，KeepAlive设置不合理时可能会 因为短暂的网络波动而断开健康的TCP连接。并且，默认的KeepAlive超时需要7,200，000 MilliSeconds， 即2小时，探测次数为5次。对于很多服务端应用程序来说，2小时的空闲时间太长。因此，我们需要手工开启KeepAlive功能并设置合理的KeepAlive参数。
由应用程序自己发送心跳包来检测连接是否正常，大致的方法是：服务器在一个 Timer事件中定时 向客户端发送一个短小精悍的数据包，然后启动一个低级别的线程，在该线程中不断检测客户端的回应， 如果在一定时间内没有收到客户端的回应，即认为客户端已经掉线；同样，如果客户端在一定时间内没 有收到服务器的心跳包，则认为连接不可用。
方法2：TCP的KeepAlive保活机制
因为要考虑到一个服务器通常会连接多个客户端，因此由用户在应用层自己实现心跳包，代码较多 且稍显复杂，而利用TCP／IP协议层为内置的KeepAlive功能来实现心跳功能则简单得多。 不论是服务端还是客户端，一方开启KeepAlive功能后，就会自动在规定时间内向对方发送心跳包， 而另一方在收到心跳包后就会自动回复，以告诉对方我仍然在线。 因为开启KeepAlive功能需要消耗额外的宽带和流量，所以TCP协议层默认并不开启KeepAlive功 能，尽管这微不足道，但在按流量计费的环境下增加了费用，另一方面，KeepAlive设置不合理时可能会 因为短暂的网络波动而断开健康的TCP连接。并且，默认的KeepAlive超时需要7,200，000 MilliSeconds， 即2小时，探测次数为5次。对于很多服务端应用程序来说，2小时的空闲时间太长。因此，我们需要手工开启KeepAlive功能并设置合理的KeepAlive参数。
断线重连机制如何设计
对 IO Multiplexing 技术的理解；
收发数据包正确的方式，收发缓冲区如何设计
proc文件系统下的值和sysctl中的值都是全局值，应用程序可根据需要在程序中使用setsockopt（）对某个socket的发送缓冲区尺寸进行单独修改。
解决思路：通过合理的设置“TCP.SO_RCVBUF & TCP.SO_SNDBUF”来提高系统的吞吐量以及快速检测tcp链路的连通性； 这两个选项就是来设置TCP连接的两个buffer尺寸的。
解决思路：通过合理的设置“TCP.SO_RCVBUF & TCP.SO_SNDBUF”来提高系统的吞吐量以及快速检测tcp链路的连通性； 这两个选项就是来设置TCP连接的两个buffer尺寸的。
UDP：当套接口接收缓冲区满时，新来的数据报无法进入接收缓冲区，此数据报就被丢弃。UDP是没有流量控制的；快的发送者可以很容易地就淹没慢的接收者，导致接收方的UDP丢弃数据报。
优雅关闭；
TCP连接的关闭过程有两种，一种是优雅关闭（graceful close），一种是强制关闭（hard close或abortive close）。所谓优雅关闭是指，如果发送缓存中还有数据未发出则其发出去，并且收到所有数据的ACK之后，发送FIN包，开始关闭过程。而强制关闭是指如果缓存中还有数据，则这些数据都将被丢弃，然后发送RST包，直接重置TCP连接。
定时器如何设计；
epoll 的实现原理。
去BiliBili被问过这样一个问题：如果A机器与B机器网络 connect 成功后从未互发过数据，此时其中一机器突然断电，则另外一台机器与断电的机器之间的网络连接处于哪种状态？
什么是半开连接？
当客户端与服务器建立起正常的TCP连接后，如果客户主机掉线（网线断开）、电源掉电、或系统崩溃，服务器进程将永远不会知道（通过我们常用的select，epoll监测不到断开或错误事件），如果不主动处理或重启系统的话对于服务端来说会一直维持着这个连接，任凭服务端进程如何望穿秋水，也永远再等不到客户端的任何回应。这种情况就是半开连接，浪费了服务器端可用的文件描述符。
如何处理？
熟悉套接字通用选项的朋友一定已经有了想法。TCP套接字不是有个保持存活选项SO_KEEPALIVE嘛，如果在两个小时之内在该套接字的任何一个方向上都没数据交换，TCP就自动给对端发送一个保持存活探测分节，如果此TCP探测分节的响应为RST，说明对端已经崩溃且已经重新启动，该套接字的待处理错误被置为ECONNRESET，套接字本身则被关闭。如果没有对此TCP探测分节的任何响应，该套接字的处理错误就被置为ETIMEOUT，套接字本身则被关闭。
确实，这个选项确实可以处理我们前面遇到的TCP半开连接的问题，但是默认两小时间隔探测的实时性是不是差了些呢？当然，我们可以通过修改内核参数改小时间间隔，完美了吧？但是必须注意的是大多数内核是基于整个内核维护这些时间参数的，而不是基于每个套接字维护的，因此如果把无活动周期从两小时改为（比如）2分钟，那将影响到该主机上所有开启了此选项的套接字。我想大家都不会愿意承担服务器端的这种不确定性吧。另外，心跳除了说明应用程序还活着（进程存在，网络畅通），更重要的是表明应用程序能正常工作。而SO_KEEPALIVE由操作系统负责探查，即便是进程死锁或有其他异常，操作系统也会正常收发TCP keepalive消息，而对方无法得知这一异常。
没关系，其实我们可以在应用层模拟SO_KEEPALIVE的方式，用心跳包来模拟保活探测分节。由于服务器通常要承担成千上万的并发连接，所以肯定是由客户端在应用层进行心跳来模拟保活探测分节，客户端多次收不到服务器的响应时可终止此TCP连接，而服务端可监测客户端的心跳包，若在一定时间间隔内未收到任何来自客户端的心跳包则可以终止此TCP连接，这样就有效避免了TCP半开连接的情况。
当客户端与服务器建立起正常的TCP连接后，如果客户主机掉线（网线断开）、电源掉电、或系统崩溃，服务器进程将永远不会知道（通过我们常用的select，epoll监测不到断开或错误事件），如果不主动处理或重启系统的话对于服务端来说会一直维持着这个连接，任凭服务端进程如何望穿秋水，也永远再等不到客户端的任何回应。这种情况就是半开连接，浪费了服务器端可用的文件描述符。
如何处理？
熟悉套接字通用选项的朋友一定已经有了想法。TCP套接字不是有个保持存活选项SO_KEEPALIVE嘛，如果在两个小时之内在该套接字的任何一个方向上都没数据交换，TCP就自动给对端发送一个保持存活探测分节，如果此TCP探测分节的响应为RST，说明对端已经崩溃且已经重新启动，该套接字的待处理错误被置为ECONNRESET，套接字本身则被关闭。如果没有对此TCP探测分节的任何响应，该套接字的处理错误就被置为ETIMEOUT，套接字本身则被关闭。
确实，这个选项确实可以处理我们前面遇到的TCP半开连接的问题，但是默认两小时间隔探测的实时性是不是差了些呢？当然，我们可以通过修改内核参数改小时间间隔，完美了吧？但是必须注意的是大多数内核是基于整个内核维护这些时间参数的，而不是基于每个套接字维护的，因此如果把无活动周期从两小时改为（比如）2分钟，那将影响到该主机上所有开启了此选项的套接字。我想大家都不会愿意承担服务器端的这种不确定性吧。另外，心跳除了说明应用程序还活着（进程存在，网络畅通），更重要的是表明应用程序能正常工作。而SO_KEEPALIVE由操作系统负责探查，即便是进程死锁或有其他异常，操作系统也会正常收发TCP keepalive消息，而对方无法得知这一异常。
没关系，其实我们可以在应用层模拟SO_KEEPALIVE的方式，用心跳包来模拟保活探测分节。由于服务器通常要承担成千上万的并发连接，所以肯定是由客户端在应用层进行心跳来模拟保活探测分节，客户端多次收不到服务器的响应时可终止此TCP连接，而服务端可监测客户端的心跳包，若在一定时间间隔内未收到任何来自客户端的心跳包则可以终止此TCP连接，这样就有效避免了TCP半开连接的情况。
所遇问题
Socket hang up
什么是 Socket hang up
hang up 翻译为英文有挂断的意思, socket hang up 也可以理解为 socket（链接）被挂断
无论使用哪种语言，也许多多少少应该都会遇见过，只是不知道你有没有去思考这是为什么？例如在 Node.js 中系统提供的 http server 默认超时为 2 分钟（server.timeout 可以查看），如果一个请求超出这个时间，http server 会关闭这个请求链接，当客户端想要返回一个请求的时候发现这个 socket 已经被 “挂断”，就会报 socket hang up 错误。
网络IO模型
阻塞
从系统调用直到数据到达并复制到应用进程缓冲区或发生错误才返回，整段时间都是被阻塞的
非阻塞
如果系统调用缓冲区没有数据的话，立即返回一个EWOULDBLOCK错误，然后轮询检查这个状态，检查内核是不是有数据到达
I/O复用模型
进程通过将一个或多个fd传给select或者poll系统调用，阻塞在select操作上，这样select/poll会帮我们检测多个fd是否处于就绪状态，select/poll是顺序扫描fd，且支持的数量有限，因此使用收到了一些限制。Linux还支持一种epoll系统调用，epoll使用了基于事件驱动代替顺序扫描，因此性能更高，当fd就绪时，立即回调函数rollback。(进程将用户socket对应的fd注册进epoll，然后epoll帮你监听哪些socket上有消息到达，这样就避免了大量的无用操作。此时的socket应该采用非阻塞模式。这样，整个过程只在调用select、poll、epoll这些调用的时候才会阻塞，收发客户消息是不会阻塞的，整个进程或者线程就被充分利用起来，这就是事件驱动)
信号驱动I/O模型
首先开启套接口信号驱动IO功能，并通过系统调用sigaction执行一个信号处理函数（此调用立即返回，进程继续工作，是非阻塞的）。当数据准备就绪时，为该进程生成一个sigio信号,通过信号回调通知进程调用recvfrom来读取数据。
异步I/O模型
告知内核启动某个操作，并让内核在整个操作（包括将数据从内核拷贝到用户自己的缓冲区）完成后通知我们。与信号驱动IO模型的区别：信号驱动IO由内核通知我们核实开始一个IO操作，.异步IO由内核通知我们IO操作已经完成。
tcp优化
TFO（TCP Fast Open）
server和client都支持tfo,client 发一个SYN包，server根据对端IP等参数计算出一个cookie
，跟syn+ACK一起发送给客户端。当下一次client在次进行连接的时候，就可以把这个cookie同
SYN包+DATA一起发送过来，server先解cookie，如果跟之前的cookie一致，且没有过期，就可以直接建立连接，把SYN和ACK发过去，且同时把请求的数据回过去。
，跟syn+ACK一起发送给客户端。当下一次client在次进行连接的时候，就可以把这个cookie同
SYN包+DATA一起发送过来，server先解cookie，如果跟之前的cookie一致，且没有过期，就可以直接建立连接，把SYN和ACK发过去，且同时把请求的数据回过去。
•net.ipv4.tcp_fastopen系统开启TFO功能
0 :关闭
• 1 ：作为客户端时可以使用TFO
, 2：作为服务器时可以使用TFO
, 3 :无论作为客户端还是服务器，都可以使用TFO
• 1 ：作为客户端时可以使用TFO
, 2：作为服务器时可以使用TFO
, 3 :无论作为客户端还是服务器，都可以使用TFO
Nginx配置：listen address[:port] [fastopen=number];
fastopen=number
,为防止带数据的SYN攻击，限制最大长度，指定TFO连接队列的最大长度
,为防止带数据的SYN攻击，限制最大长度，指定TFO连接队列的最大长度
背景
RTT
RTT(Round-Trip Time): 往返时延。在计算机网络中它是一个重要的性能指标，表示从发送端发送数据开始，到发送端收到来自接收端的确认（接收端收到数据后便立即发送确认），总共经历的时延。
RTT=传播时延（往返哒）+排队时延（路由器和交换机的）+数据处理时延（应用程序的）
据google的统计(chrome浏览器),尽管chrome开启了http的 keepalive(chrome是4分钟)，可是依然有35%的请求是重新发起一条连接。而三次握手会造成一个RTT的延迟，因此TFO的目标就是去除 这个延迟，在三次握手期间也能交换数据
工作原理
> 客户端发送SYN包，包尾加一个FOC请求，只有4个字节。
> 服务端受到FOC请求，验证后根据来源ip地址声称cookie(8个字节)，将这个COOKIE加载SYN+ACK包的末尾发送回去。
> 客户端缓存住获取到的Cookie 可以给下一次使用。
> 下一次请求开始，客户端发送SYN包，这时候后面带上缓存的COOKIE，然后就是正式发送的数据。
> 服务器端验证COOKIE正确，将数据交给上层应用处理得到相应结果，然后在发送SYN+ACK时，不再等待客户端的ACK确认，即开始发送相应数据。
> 服务端受到FOC请求，验证后根据来源ip地址声称cookie(8个字节)，将这个COOKIE加载SYN+ACK包的末尾发送回去。
> 客户端缓存住获取到的Cookie 可以给下一次使用。
> 下一次请求开始，客户端发送SYN包，这时候后面带上缓存的COOKIE，然后就是正式发送的数据。
> 服务器端验证COOKIE正确，将数据交给上层应用处理得到相应结果，然后在发送SYN+ACK时，不再等待客户端的ACK确认，即开始发送相应数据。
性能优化率
局域网
普通模式下1024次请求耗时:272微秒
TFO模式下1024次请求耗时:198微秒
1024次请求性能: (272/198-1)*100 ~=37%
TFO模式下1024次请求耗时:198微秒
1024次请求性能: (272/198-1)*100 ~=37%
广域网
北美与大陆之间测试：
普通模式下1024次请求耗时：588584微秒
TFO模式下1024次请求耗时：288504微秒
1024次请求性能：（588584/288504-1）*100~=104%
普通模式下1024次请求耗时：588584微秒
TFO模式下1024次请求耗时：288504微秒
1024次请求性能：（588584/288504-1）*100~=104%
丢包重传
限制重传次数
•net.ipv4.tcp_retries1 = 3
-达到上限后，更新路由缓存
•net.ipv4.tcp_retries2 = 15
•达到上限后，关闭TCP连接
•仅作近似理解，实际以超时时间为准，可能少于retries次数就认定达到上限
-达到上限后，更新路由缓存
•net.ipv4.tcp_retries2 = 15
•达到上限后，关闭TCP连接
•仅作近似理解，实际以超时时间为准，可能少于retries次数就认定达到上限
TCP缓冲区
net.ipv4.tcp_rmem = 4096 87380 6291456
读缓存最小值、默认值、最大值，单位为字节 ，覆盖net.core.rmem_max
读缓存最小值、默认值、最大值，单位为字节 ，覆盖net.core.rmem_max
net.ipv4.tcp_wmem = 4096 16384 4194304
写缓存最小值、默认值、最大值，单位字节，覆盖net.core.wmem_max
写缓存最小值、默认值、最大值，单位字节，覆盖net.core.wmem_max
net.ipv4.tcp_mem = 1541646 2055528 3083292
只有开启自动调整缓存模式才有效。系统无内存压力、启动压力模式阈值、最大值，单位为页的数量
只有开启自动调整缓存模式才有效。系统无内存压力、启动压力模式阈值、最大值，单位为页的数量
net.ipv4.tcp_moderate_rcvbuf = 1
开启自动调整缓存模式
开启自动调整缓存模式
BDP=带宽*时延。 吞吐量= 最大接收窗口/时延
最大接收窗口应该为处在网络中的传输的字节量。BDP带宽*时延
每个客户端的时延不一致，但内网是一致的。
Nagle（內狗）算法
小报文合成大报文一起发送，不然小报文，可能tcp包头IP包头，远远超过内容的长度。发送大量小报文严重影响带宽
优点
-避免一个连接上同时存在大量小报文
,最多只存在一个小报文
,合并多个小报文一起发送
-提高带宽利用率
,最多只存在一个小报文
,合并多个小报文一起发送
-提高带宽利用率
Nginx配置：
,吞吐量优先：启用Nagle算法，tcp_nodelay off
,低时延优先：禁用Nagle算法，tcp_nodelay on
,低时延优先：禁用Nagle算法，tcp_nodelay on
CORK算法
仅针对sendfile on开启时有效，完全禁止小报文的发送，提升网络效率
keepalive功能
发送心跳周期单位秒 定时器如果两个小时没有请求响应报文，tcp开始启动检测功能，先发一个探测包，
如果网络可直达，对方如果已经关掉了连接，操作系统会给我们发送一个RST报文。但如果网络不可达，
就会重试。9*75秒都没有收到回复，就会把连接关掉
• net.ipv4.tcp_keepalive_time = 7200
探测包发送间隔
• net.ipv4.tcp_keepalive_intvl = 75
探测包重试次数
• net.ipv4.tcp_keepalive_probes = 9
使用 sysctl -A 命令查看所有有效的内核变量，使用 grep net.ipv4 过滤。
$ sysctl -A | grep net.ipv4
应当有下列变量
- net.ipv4.tcp_keepalive_time - 在第一次keep alive请求发送后，不活动连接的时间
- net.ipv4.tcp_keepalive_probes - 在这个连接被认为是断开之前，keep alive请求被重发的次数
- net.ipv4.tcp_keepalive_intvl - keep alive探测的时间间隔
可以使用下面的命令操作这些变量:
$ sysctl -w net.ipv4.tcp_keepalive_time=60 net.ipv4.tcp_keepalive_probes=3 net.ipv4.tcp_keepalive_intvl=10
这个命令将TCP keepalive的超时设为60秒，并有三次重发，每次间隔10秒。
因此，你的应用程序90秒(60 + 10 + 10 + 10)后检测到TCP断开
如果网络可直达，对方如果已经关掉了连接，操作系统会给我们发送一个RST报文。但如果网络不可达，
就会重试。9*75秒都没有收到回复，就会把连接关掉
• net.ipv4.tcp_keepalive_time = 7200
探测包发送间隔
• net.ipv4.tcp_keepalive_intvl = 75
探测包重试次数
• net.ipv4.tcp_keepalive_probes = 9
使用 sysctl -A 命令查看所有有效的内核变量，使用 grep net.ipv4 过滤。
$ sysctl -A | grep net.ipv4
应当有下列变量
- net.ipv4.tcp_keepalive_time - 在第一次keep alive请求发送后，不活动连接的时间
- net.ipv4.tcp_keepalive_probes - 在这个连接被认为是断开之前，keep alive请求被重发的次数
- net.ipv4.tcp_keepalive_intvl - keep alive探测的时间间隔
可以使用下面的命令操作这些变量:
$ sysctl -w net.ipv4.tcp_keepalive_time=60 net.ipv4.tcp_keepalive_probes=3 net.ipv4.tcp_keepalive_intvl=10
这个命令将TCP keepalive的超时设为60秒，并有三次重发，每次间隔10秒。
因此，你的应用程序90秒(60 + 10 + 10 + 10)后检测到TCP断开
NginxTcp keepalive
• so_keepalive=30m::10
• keepidle, keepintvl, keepcnt
• so_keepalive=30m::10
• keepidle, keepintvl, keepcnt
三次握手四次挥手
主动关闭连接端的状态
•fin_wait 1 状态
•net.ipv4.tcp_orphan_retries = 0
•发送FIN报文的重试次数，0相当于8
•fin_wait 2 状态
•net.ipv4.tcp_fin_timeout = 60
•保持在FIN_WAIT_2状态的时间
•net.ipv4.tcp_orphan_retries = 0
•发送FIN报文的重试次数，0相当于8
•fin_wait 2 状态
•net.ipv4.tcp_fin_timeout = 60
•保持在FIN_WAIT_2状态的时间
•time_wait状态有什么作用？
如何解决time_wait
net.ipv4.tcp_tw_reuse = 1
开启后，作为客户端时新连接可 以使用仍然处于TIME-WAIT状态 的端口
•由于timestamp的存在，操作系统 可以拒绝迟到的报文
• net.ipv4.tcp timestamps = 1
•由于timestamp的存在，操作系统 可以拒绝迟到的报文
• net.ipv4.tcp timestamps = 1
•net.ipv4.tcp_tw_recycle = 0
-开启后，同时作为客户端和服务器都可以使用TIME-WAIT状态的端口
•不安全，无法避免报文延迟、重复等给新连接造成混乱
-开启后，同时作为客户端和服务器都可以使用TIME-WAIT状态的端口
•不安全，无法避免报文延迟、重复等给新连接造成混乱
•net.ipv4.tcp_max_tw_buckets = 262144
• time_wait状态连接的最大数量
•超出后直接关闭连接
• time_wait状态连接的最大数量
•超出后直接关闭连接
三次握手时的优化
三次握手建立连接的首要目的是同步序列号。只有同步了序列号才有可靠的传输，TCP 协议的许多特性都是依赖序列号实现的，比如流量控制、消息丢失后的重发等等，这也是三次握手中的报文被称为 SYN 的原因，因为 SYN 的全称就叫做 Synchronize Sequence Numbers。
客户端的 优化
客户端会重发 SYN，重试的次数由 tcp_syn_retries 参数控制
net.ipv4.tcp_syn_retries = 6 默认6次
服务端的优化
SYN 半连接队列满了，接收到的SYN消息会被丢弃
调大队列大小的方法，是设置 Linux 的 tcp_max_syn_backlog 参数：
net.ipv4.tcp_max_syn_backlog = 1024
开启 syncookies 功能就可以在不使用 SYN 队列的情况下成功建立连接
syncookies 是这么做的：服务器根据当前状态计算出一个值，放在己方发出的 SYN+ACK 报文中发出，当客户端返回 ACK 报文时，取出该值验证，如果合法，就认为连接建立成功。这样可以不用进过SYN半连接队列了
Linux 下怎样开启 syncookies 功能呢？修改 tcp_syncookies 参数即可，其中值为 0 时表示关闭该功能，2 表示无条件开启功能，而 1 则表示仅当 SYN 半连接队列放不下时，再启用它。由于 syncookie 仅用于应对 SYN 泛洪攻击（攻击者恶意构造大量的 SYN 报文发送给服务器，造成 SYN 半连接队列溢出，导致正常客户端的连接无法建立），这种方式建立的连接，许多 TCP 特性都无法使用。所以，应当把 tcp_syncookies 设置为 1，仅在队列满时再启用。
如果服务器没有收到 ACK，就会一直重发 SYN+ACK 报文。当网络繁忙、不稳定时，报文丢失就会变严重，此时应该调大重发次数
修改重发次数的方法是，调整 tcp_synack_retries 参数：net.ipv4.tcp_synack_retries = 5
修改重发次数的方法是，调整 tcp_synack_retries 参数：net.ipv4.tcp_synack_retries = 5
服务器收到 ACK 后连接建立成功，此时，内核会把连接从 SYN 半连接队列中移出，再移入 accept 队列，等待进程调用 accept 函数时把连接取出来。如果进程不能及时地调用 accept 函数，就会造成 accept 队列溢出，最终导致建立好的 TCP 连接被丢弃。
可以选择向客户端发送 RST 复位报文，告诉客户端连接已经建立失败。打开这一功能需要将 tcp_abort_on_overflow 参数设置为 1。
怎样调整 accept 队列的长度呢？listen 函数的 backlog 参数就可以设置 accept 队列的大小。事实上，backlog 参数还受限于 Linux 系统级的队列长度上限，当然这个上限阈值也可以通过 somaxconn 参数修改。
net.core.somaxconn = 128
TFO 技术如何绕过三次握手？
TFO
整体步骤
子主题
四次挥手时的优化
互联网中往往服务器才是主动关闭连接的一方
主动方的优化
关闭连接有多种方式，比如进程异常退出时，针对它打开的连接，内核就会发送 RST 报文来关闭。RST 的全称是 Reset 复位的意思，它可以不走四次挥手强制关闭连接
安全关闭连接的方式必须通过四次挥手，它由进程调用 close 或者 shutdown 函数发起，这二者都会向对方发送 FIN 报文（shutdown 参数须传入 SHUT_WR 或者 SHUT_RDWR 才会发送 FIN），区别在于 close 调用后，哪怕对方在半关闭状态下发送的数据到达主动方，进程也无法接收。
此时，这个连接叫做孤儿连接，如果你用 netstat -p 命令，会发现连接对应的进程名为空。而 shutdown 函数调用后，即使连接进入了 FIN_WAIT1 或者 FIN_WAIT2 状态，它也不是孤儿连接，进程仍然可以继续接收数据
此时，这个连接叫做孤儿连接，如果你用 netstat -p 命令，会发现连接对应的进程名为空。而 shutdown 函数调用后，即使连接进入了 FIN_WAIT1 或者 FIN_WAIT2 状态，它也不是孤儿连接，进程仍然可以继续接收数据
内核会定时重发 FIN 报文，其中重发次数由 tcp_orphan_retries 参数控制
net.ipv4.tcp_orphan_retries = 0 默认值是 0，特指 8 次
当重试次数达到 tcp_orphan_retries 时，连接就会直接关闭掉
当重试次数达到 tcp_orphan_retries 时，连接就会直接关闭掉
tcp_max_orphans 定义了孤儿连接的最大数量
如果连接是用 shutdown 函数关闭的，连接可以一直处于 FIN_WAIT2 状态。但对于 close 函数关闭的孤儿连接，这个状态不可以持续太久，而 tcp_fin_timeout 控制了这个状态下连接的持续时长。
net.ipv4.tcp_fin_timeout = 60
它的默认值是 60 秒。这意味着对于孤儿连接，如果 60 秒后还没有收到 FIN 报文，连接就会直接关闭
它的默认值是 60 秒。这意味着对于孤儿连接，如果 60 秒后还没有收到 FIN 报文，连接就会直接关闭
优化TIME_WAIT
Linux 提供了 tcp_max_tw_buckets 参数，当 TIME_WAIT 的连接数量超过该参数时，新关闭的连接就不再经历 TIME_WAIT 而直接关闭。
net.ipv4.tcp_max_tw_buckets = 5000
如果服务器会主动向上游服务器发起连接的话，就可以把 tcp_tw_reuse 参数设置为 1，它允许作为客户端的新连接，在安全条件下使用 TIME_WAIT 状态下的端口
net.ipv4.tcp_tw_reuse = 1
net.ipv4.tcp_timestamps = 1
当然，要想使 tcp_tw_reuse 生效，还得把 timestamps 参数设置为 1，它满足安全复用的先决条件（对方也要打开 tcp_timestamps ）
当然，要想使 tcp_tw_reuse 生效，还得把 timestamps 参数设置为 1，它满足安全复用的先决条件（对方也要打开 tcp_timestamps ）
老版本的 Linux 还提供了 tcp_tw_recycle 参数，它并不要求 TIME_WAIT 状态存在 60 秒，很容易导致数据错乱，不建议设置为 1
net.ipv4.tcp_tw_recycle = 0
所以在 Linux 4.12 版本后，直接取消了这一参数。
所以在 Linux 4.12 版本后，直接取消了这一参数。
被动方的优化
当被动方收到 FIN 报文时，就开启了被动方的四次挥手流程。内核自动回复 ACK 报文后，连接就进入 CLOSE_WAIT 状态，顾名思义，它表示等待进程调用 close 函数关闭连接。内核没有权力替代进程去关闭连接，因为若主动方是通过 shutdown 关闭连接，那么它就是想在半关闭连接上接收数据。因此，Linux 并没有限制 CLOSE_WAIT 状态的持续时间。当然，大多数应用程序并不使用 shutdown 函数关闭连接，所以，当你用 netstat 命令发现大量 CLOSE_WAIT 状态时，要么是程序出现了 Bug，read 函数返回 0 时忘记调用 close 函数关闭连接，要么就是程序负载太高，close 函数所在的回调函数被延迟执行了。此时，我们应当在应用代码层面解决问题。
总结
TFO,nagle算法，keeplive,短连接改成长连接
udp
udp缓冲区溢出怎么办
数据包在应用程序阶段丢包主要取决于以下因素
应用程序缓冲区大小
应用程序处理数据包的能力，即如何尽可能快的从缓冲区取走数据包
应用程序处理数据包的能力，即如何尽可能快的从缓冲区取走数据包
丢包诊断
网卡缓冲区溢出丢包诊断
在Linux操作系统中，可以通过netstat -i –udp <NIC> 命令来诊断网卡缓冲区是否溢出，RX-DRP列显示网卡丢失的数据包个数。
For example: netstat -i –udp eth1
For example: netstat -i –udp eth1
解决方案
可以通过增大网卡缓冲区来有效减少网卡缓冲区溢出。
操作系统内核网络缓冲区溢出诊断
在Linux操作系统中可以通过cat /proc/net/snmp | grep -w Udp命令来查看，InErrors 列显示当操作系统UDP队列溢出时丢失的UDP数据包总个数。
如下几种方法可以有效减缓操作系统缓冲区溢出
1) 增大操作系统内核网络缓冲区的大小
2) 在数据包路径图中直接绕过操作系统内核缓冲区，通过使用用户空间栈或一些可以 绕过内核缓冲区的中间件 (e.g. Solarflare's OpenOnload).
3) 关闭未使用的网络相关的应用和服务使操作系统的负载降到最低
4) 系统中仅保留适当数量的工作的网卡，最大效率的合理化利用网卡和系统资源
2) 在数据包路径图中直接绕过操作系统内核缓冲区，通过使用用户空间栈或一些可以 绕过内核缓冲区的中间件 (e.g. Solarflare's OpenOnload).
3) 关闭未使用的网络相关的应用和服务使操作系统的负载降到最低
4) 系统中仅保留适当数量的工作的网卡，最大效率的合理化利用网卡和系统资源
应用程序socket缓冲区溢出诊断
在Linux操作系统中可以通过cat /proc/net/snmp | grep -w Udp命令来查看，RcvbufErrors 列显示当应用程序socket缓冲区溢出时丢失的UDP数据包总个数。
如下几种方法可以有效减缓应用程序socket缓冲区溢出
1) 接受缓冲区尽可能快地处理接受到的数据包（e.g.通过使用NIO的方式来异步非阻塞接受UDP数据包或者提高接受UDP数据包线程的优先级）
2) 增大应用程序接受socket缓冲区大小，注意这个受限于全局socket缓冲区大小，如果应用程序的socket缓冲区大于全局socket缓冲区将没有效果。
3) 把应用程序或接受线程指定到CPU专用的核上
4) 提高应用程序的io优先级(e.g.使用nice或ionice命令来调节)
5) 关闭所有未使用的网络相关的应用和服务使操作系统的负载降到最低
2) 增大应用程序接受socket缓冲区大小，注意这个受限于全局socket缓冲区大小，如果应用程序的socket缓冲区大于全局socket缓冲区将没有效果。
3) 把应用程序或接受线程指定到CPU专用的核上
4) 提高应用程序的io优先级(e.g.使用nice或ionice命令来调节)
5) 关闭所有未使用的网络相关的应用和服务使操作系统的负载降到最低
调优
网卡缓冲区调优
通过命令ethtool -G d<NIC> rx NEW-BUFFER-SIZE可以设置RX ring的缓冲区大小，改变会立即生效不需要重启操作系统或刷新网络栈，这种变化直接作用于网卡本身而不影响操作系统，不影响操作系统内核网络栈但是会影响网卡固件参数。更大的ring size能承受较大的数据流量而不会丢包，但是因为工作集的增加可能会降低网卡效率，影响性能，所以建议谨慎设置网卡固件参数。
操作系统内核缓冲区调优
运行命令sysctl -A | grep net | grep 'mem\|backlog' | grep 'udp_mem\|rmem_max\|max_backlog'查看当前操作系统缓冲区的设置。如下：
[root@TENCENT64 /usr/local/games]# sysctl -A | grep net | grep 'mem\|backlog' | grep 'udp_mem\|rmem_max\|max_backlog'net.core.netdev_max_backlog = 1000net.core.rmem_max = 212992net.ipv4.udp_mem = 188169 250892 376338
增加最大socket接收缓冲区大小为32MB：
sysctl -w net.core.rmem_max=33554432
增加最大可分配的缓冲区空间总量,数值以页面为单位，每个页面单位等于4096 bytes：
sysctl -w net.ipv4.udp_mem="262144 327680 393216"
增加接收数据包队列大小：
sysctl -w net.core.netdev_max_backlog=2000
修改完成后，需要运行命令 sysctl –p 使之生效
[root@TENCENT64 /usr/local/games]# sysctl -A | grep net | grep 'mem\|backlog' | grep 'udp_mem\|rmem_max\|max_backlog'net.core.netdev_max_backlog = 1000net.core.rmem_max = 212992net.ipv4.udp_mem = 188169 250892 376338
增加最大socket接收缓冲区大小为32MB：
sysctl -w net.core.rmem_max=33554432
增加最大可分配的缓冲区空间总量,数值以页面为单位，每个页面单位等于4096 bytes：
sysctl -w net.ipv4.udp_mem="262144 327680 393216"
增加接收数据包队列大小：
sysctl -w net.core.netdev_max_backlog=2000
修改完成后，需要运行命令 sysctl –p 使之生效
应用程序调优
其他减少丢包策略
UDP发送端增加流量控制，控制每秒发送的数据包，尽量避免由于发送端发包速率过快，导致UDP接收端缓冲区很快被填满从而出现溢出丢包。测试采用google提供的工具包guava。RateLimiter类来做流控，采用了一种令牌桶的流控算法，RateLimiter会按照一定的频率往桶里扔令牌，线程拿到令牌才能执行，比如你希望自己的应用程序QPS不要超过1000，那么RateLimiter设置1000的速率后，就会每秒往桶里扔1000个令牌。
采用流控后每秒发指定数量的数据包，而且每秒都会出现波谷波峰，如果不做流控，UDP发送端会全力发包一直在波峰附近抖动，大流量会一直持续，随着时间的增加，UDP发送端生产的速率肯定会超过UDP接收端消费的速率，丢包是迟早的。
采用流控后每秒发指定数量的数据包，而且每秒都会出现波谷波峰，如果不做流控，UDP发送端会全力发包一直在波峰附近抖动，大流量会一直持续，随着时间的增加，UDP发送端生产的速率肯定会超过UDP接收端消费的速率，丢包是迟早的。
udp如何实现可靠传输
kcp
概述
KCP是一个快速可靠协议，基于UDP，能以比 TCP浪费10%-20%的带宽的代价，换取平均延迟降低 30%-40%，且最大延迟降低三倍的传输效果
整个协议只有 ikcp.h, ikcp.c两个源文件，可以方便的集成到用户自己的协议栈中
整个协议只有 ikcp.h, ikcp.c两个源文件，可以方便的集成到用户自己的协议栈中
KCP有正常模式和快速模式两种，通过以下策略达到提高流速的结果
特性
RTO翻倍vs不翻倍
TCP超时计算是RTOx2，这样连续丢三次包就变成RTOx8了，十分恐怖，而KCP启动快速模式后不x2，只是x1.5（实验证明1.5这个值相对比较好），提高了传输速度
RTT: 发送一个数据包到收到对应的ACK，所花费的时间
RTO: 发送数据包，启动重传定时器，重传定时器到期所花费的时间，称为RTO
RTO: 发送数据包，启动重传定时器，重传定时器到期所花费的时间，称为RTO
选择性重传 vs 全部重传
TCP丢包时会全部重传从丢的那个包开始以后的数据，KCP是选择性重传，只重传真正丢失的数据包
快速重传
发送端发送了1,2,3,4,5几个包，然后收到远端的ACK: 1, 3, 4, 5，当收到ACK3时，KCP知道2被跳过1次，收到ACK4时，知道2被跳过了2次，此时可以认为2号丢失，不用等超时，直接重传2号包，大大改善了丢包时的传输速度。
延迟ACK vs 非延迟ACK
TCP为了充分利用带宽，延迟发送ACK（NODELAY都没用），这样超时计算会算出较大 RTT时间，延长了丢包时的判断过程。KCP的ACK是否延迟发送可以调节。
UNA vs ACK+UNA
ARQ模型响应有两种，UNA（此编号前所有包已收到，如TCP）和ACK（该编号包已收到），光用UNA将导致全部重传，光用ACK则丢失成本太高，以往协议都是二选其一，而 KCP协议中，除去单独的 ACK包外，所有包都有UNA信息。
quic
QUIC协议的主要目的
为了整合TCP协议的可靠性和UDP协议的速度和效率。
QUIC的特性
低延迟连接的建立 (Connection Establishment Latency)
前向纠错 (Forward Error Correction)
QUIC使用了FEC（前向纠错码）来恢复数据，FEC采用简单异或的方式，每发送一组数据，包括若干个数据包后，并对这些数据包依次做异或运算，最后的结果作为一个FEC包再发送出去。接收方收到一组数据后，根据数据包和FEC包即可以进行校验和纠错。比如：10个包，编码后会增加2个包，接收端丢失第2和第3个包，仅靠剩下的10个包就可以解出丢失的包，不必重新发送，但这样也是有代价的，每个UDP数据包会包含比实际需要更多的有效载荷，增加了冗余和CPU编解码的消耗。
连接迁移 (Connection Migration)
QUIC协议使用流ID取代IP和端口，这样就能实现连接迁移。例如说从4G信号切换到wifi，下层的IP和端口变了，但是由于QUIC的流ID没有变，这个连接不会变，可以继续使用这个连接
无队头阻塞的多路复用 (Multiplexing without head-of-line blocking)
HTTP2的最大特性就是多路复用，而HTTP2最大的问题就是队头阻塞。
首先了解下为什么会出现队头阻塞。比如HTTP2在一个TCP连接上同时发送3个stream，其中第2个stream丢了一个Packet，TCP为了保证数据可靠性，需要发送端重传丢失的数据包，虽然这时候第3个数据包已经到达接收端，但被阻塞了。这就是所谓的队头阻塞。
而QUIC多路复用可以避免这个问题，因为QUIC的丢包、流控都是基于stream的，所有stream是相互独立的，一条stream上的丢包，不会影响其他stream的数据传输。
首先了解下为什么会出现队头阻塞。比如HTTP2在一个TCP连接上同时发送3个stream，其中第2个stream丢了一个Packet，TCP为了保证数据可靠性，需要发送端重传丢失的数据包，虽然这时候第3个数据包已经到达接收端，但被阻塞了。这就是所谓的队头阻塞。
而QUIC多路复用可以避免这个问题，因为QUIC的丢包、流控都是基于stream的，所有stream是相互独立的，一条stream上的丢包，不会影响其他stream的数据传输。
TCP与UDP的概念，相互的区别及优劣。
TCP（Transmission Control Protocol）的概念
TCP是一种面向连接的，提供可靠交付服务和全双工通信的，基于字节流的端到端的传输层通信协议。
TCP在传输数据之前必须先建立连接，数据传输结束后要释放连接。
每一条TCP连接只能有2个端点，故TCP不提供广播或多播服务。
TCP提供可靠交付，通过TCP连接传输的数据，无差错、不丢失、不重复、并且按序到达。
TCP是面向字节流的。虽然应用进程和TCP的交互是一次一个数据块(大小不等），但TCP把应用程序交下来的数据看成仅仅是一连串的无结构的字节流。TCP并不知道所传输的字节流的含义。
UDP（UserDatagram Protocol）的概念
UDP是一种无连接的，尽最大努力交付的，基于报文的端到端的传输层通信协议。
UDP，在发送数据之前不需要建立连接
UDP不保证可靠交付，主机不需要位置复杂的连接状态
UDP是面向报文的。UDP对应用层交下来的报文，既不合并，也不拆分，而是保留这些报文的的边界，即应用层交给UDP多长的报文，UDP就照样发送，即一次发送一个报文。在接收端，UDP一次交付一个完整的报文。
UDP没有拥塞控制，网络出现的拥塞不会使源主机的发送速率降低。
UDP支持一对一、一对多、多对一和多对多的交互通信。
UDP的首部开销小，只有8个字节，比TCP的20个字节的首部要短。
区别
TCP协议面向连接，UDP协议面向非连接
TCP协议传输速度慢，UDP协议传输速度快
TCP协议保证数据顺序，UDP协议不保证
TCP协议保证数据正确性，UDP协议可能丢包
TCP协议对系统资源要求多，UDP协议要求少
使用情况
TCP协议适用于对效率要求相对低，但对准确性要求相对高的场景下，或者是有一种连接概念的场景下；而UDP协议适用于对效率要求相对高，对准确性要求相对低的场景。
TCP是一种面向连接的，提供可靠交付服务和全双工通信的，基于字节流的端到端的传输层通信协议。
TCP在传输数据之前必须先建立连接，数据传输结束后要释放连接。
每一条TCP连接只能有2个端点，故TCP不提供广播或多播服务。
TCP提供可靠交付，通过TCP连接传输的数据，无差错、不丢失、不重复、并且按序到达。
TCP是面向字节流的。虽然应用进程和TCP的交互是一次一个数据块(大小不等），但TCP把应用程序交下来的数据看成仅仅是一连串的无结构的字节流。TCP并不知道所传输的字节流的含义。
UDP（UserDatagram Protocol）的概念
UDP是一种无连接的，尽最大努力交付的，基于报文的端到端的传输层通信协议。
UDP，在发送数据之前不需要建立连接
UDP不保证可靠交付，主机不需要位置复杂的连接状态
UDP是面向报文的。UDP对应用层交下来的报文，既不合并，也不拆分，而是保留这些报文的的边界，即应用层交给UDP多长的报文，UDP就照样发送，即一次发送一个报文。在接收端，UDP一次交付一个完整的报文。
UDP没有拥塞控制，网络出现的拥塞不会使源主机的发送速率降低。
UDP支持一对一、一对多、多对一和多对多的交互通信。
UDP的首部开销小，只有8个字节，比TCP的20个字节的首部要短。
区别
TCP协议面向连接，UDP协议面向非连接
TCP协议传输速度慢，UDP协议传输速度快
TCP协议保证数据顺序，UDP协议不保证
TCP协议保证数据正确性，UDP协议可能丢包
TCP协议对系统资源要求多，UDP协议要求少
使用情况
TCP协议适用于对效率要求相对低，但对准确性要求相对高的场景下，或者是有一种连接概念的场景下；而UDP协议适用于对效率要求相对高，对准确性要求相对低的场景。
ping 的工作过程
假定主机A的IP地址是192.168.1.1，主机B的IP地址是192.168.1.2，都在同一子网内，则当你在主机A上运行“Ping192.168.1.2”后，都发生了些什么呢?
首先，Ping命令会构建一个固定格式的ICMP请求数据包，然后由ICMP协议将这个数据包连同地址“192.168.1.2”一起交给IP层协议（和ICMP一样，实际上是一组后台运行的进程），IP层协议将以地址“192.168.1.2”作为目的地址，本机IP地址作为源地址，加上一些其他的控制信息，构建一个IP数据包，并在一个映射表中查找出IP地址192.168.1.2所对应的物理地址（也叫MAC地址，熟悉网卡配置的朋友不会陌生，这是数据链路层协议构建数据链路层的传输单元——帧所必需的），一并交给数据链路层。后者构建一个数据帧，目的地址是IP层传过来的物理地址，源地址则是本机的物理地址，还要附加上一些控制信息，依据以太网的介质访问规则，将它们传送出去。
其中映射表由ARP实现。ARP(Address Resolution Protocol)是地址解析协议,是一种将IP地址转化成物理地址的协议。ARP具体说来就是将网络层（IP层，也就是相当于OSI的第三层）地址解析为数据连接层（MAC层，也就是相当于OSI的第二层）的MAC地址。
主机B收到这个数据帧后，先检查它的目的地址，并和本机的物理地址对比，如符合，则接收；否则丢弃。接收后检查该数据帧，将IP数据包从帧中提取出来，交给本机的IP层协议。同样，IP层检查后，将有用的信息提取后交给ICMP协议，后者处理后，马上构建一个ICMP应答包，发送给主机A，其过程和主机A发送ICMP请求包到主机B一模一样。
即先由IP地址，在网络层传输，然后再根据mac地址由数据链路层传送到目的主机
作者：杰伦哎呦哎呦
链接：https://www.jianshu.com/p/972a10dd2e53
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
首先，Ping命令会构建一个固定格式的ICMP请求数据包，然后由ICMP协议将这个数据包连同地址“192.168.1.2”一起交给IP层协议（和ICMP一样，实际上是一组后台运行的进程），IP层协议将以地址“192.168.1.2”作为目的地址，本机IP地址作为源地址，加上一些其他的控制信息，构建一个IP数据包，并在一个映射表中查找出IP地址192.168.1.2所对应的物理地址（也叫MAC地址，熟悉网卡配置的朋友不会陌生，这是数据链路层协议构建数据链路层的传输单元——帧所必需的），一并交给数据链路层。后者构建一个数据帧，目的地址是IP层传过来的物理地址，源地址则是本机的物理地址，还要附加上一些控制信息，依据以太网的介质访问规则，将它们传送出去。
其中映射表由ARP实现。ARP(Address Resolution Protocol)是地址解析协议,是一种将IP地址转化成物理地址的协议。ARP具体说来就是将网络层（IP层，也就是相当于OSI的第三层）地址解析为数据连接层（MAC层，也就是相当于OSI的第二层）的MAC地址。
主机B收到这个数据帧后，先检查它的目的地址，并和本机的物理地址对比，如符合，则接收；否则丢弃。接收后检查该数据帧，将IP数据包从帧中提取出来，交给本机的IP层协议。同样，IP层检查后，将有用的信息提取后交给ICMP协议，后者处理后，马上构建一个ICMP应答包，发送给主机A，其过程和主机A发送ICMP请求包到主机B一模一样。
即先由IP地址，在网络层传输，然后再根据mac地址由数据链路层传送到目的主机
作者：杰伦哎呦哎呦
链接：https://www.jianshu.com/p/972a10dd2e53
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
由于UDP不建立会话，因此一旦数据和端口号准备就绪，UDP就可以生成数据报并递交给网络层，并在网络上寻址和发送。
ARP（Address Resolution Protocol）是地址解析协议，简单语言解释一下工作原理。
(1)首先，每个主机都会在自己的ARP缓冲区中建立一个ARP列表，以表示IP地址和MAC地址之间的对应关系。
（2）当源主机要发送数据时，首先检查ARP列表中是否有对应IP地址的目的主机的MAC地址，如果有，则直接发送数据，如果没有，就向本网段的所有主机发送ARP数据包，该数据包包括的内容有：源主机IP地址，源主机MAC地址，目的主机的IP地址。
（3）当本网络的所有主机收到该ARP数据包时，首先检查数据包中的IP地址是否是自己的IP地址，如果不是，则忽略该数据包，如果是，则首先从数据包中取出源主机的IP和MAC地址写入到ARP列表中，如果已经存在，则覆盖，然后将自己的MAC地址写入ARP响应包中，告诉源主机自己是它想要找的MAC地址。
（4）源主机收到ARP响应包后。将目的主机的IP和MAC地址写入ARP列表，并利用此信息发送数据。如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。
广播发送ARP请求，单播发送ARP响应。
作者：杰伦哎呦哎呦
链接：https://www.jianshu.com/p/972a10dd2e53
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
（2）当源主机要发送数据时，首先检查ARP列表中是否有对应IP地址的目的主机的MAC地址，如果有，则直接发送数据，如果没有，就向本网段的所有主机发送ARP数据包，该数据包包括的内容有：源主机IP地址，源主机MAC地址，目的主机的IP地址。
（3）当本网络的所有主机收到该ARP数据包时，首先检查数据包中的IP地址是否是自己的IP地址，如果不是，则忽略该数据包，如果是，则首先从数据包中取出源主机的IP和MAC地址写入到ARP列表中，如果已经存在，则覆盖，然后将自己的MAC地址写入ARP响应包中，告诉源主机自己是它想要找的MAC地址。
（4）源主机收到ARP响应包后。将目的主机的IP和MAC地址写入ARP列表，并利用此信息发送数据。如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。
广播发送ARP请求，单播发送ARP响应。
作者：杰伦哎呦哎呦
链接：https://www.jianshu.com/p/972a10dd2e53
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
CDN(内容分发网络)
概念
CDN的全称是Content Delivery Network,即内容分发网络。使用户可就近取得所需内容，解决Internet网络拥挤的状况，提高用户访问网站的响应速度。
CDN的分类
静态网页加速
流媒体加速
大文件加速
应用协议加速
优点
负载均衡
当用户访问http://www.test.com/1.html这个域名时
会首先发送请求到本地DNS服务器,对http://www.test.com/1.html这个域名进行解析
然后本地DNS向只能DNS发送请求,进行递归查询
智能DNS会返回一个最佳接入节点
用户就会访问这个最佳接入节点
会首先发送请求到本地DNS服务器,对http://www.test.com/1.html这个域名进行解析
然后本地DNS向只能DNS发送请求,进行递归查询
智能DNS会返回一个最佳接入节点
用户就会访问这个最佳接入节点
概念
通俗的说就是把原来的单台服务器完成的工作交给多台服务器完成,以此来减轻单个服务器的压力,提高服务器数据处理能力的效果
特点
本地负载均衡
全局负载均衡
方式二:CDN主动探测目标最近距离
方式一:根据IP地址库投票匹配
内容分发技术
当源站需要分发内容的时候,可以将分发内容分发到CDN中间源
再由CDN中间源转发内容到各个CDN节点
如果CDN节点需要请求某个URL内容请求时,会将请求先发送到CDN中间源
再由CDN中间源主动向源站发送请求内容,最后将获取到的数据存储到中间源和内容节点上,从而达到节点加速的效果
再由CDN中间源转发内容到各个CDN节点
如果CDN节点需要请求某个URL内容请求时,会将请求先发送到CDN中间源
再由CDN中间源主动向源站发送请求内容,最后将获取到的数据存储到中间源和内容节点上,从而达到节点加速的效果
CDN对跨域的处理?
子主题
httpDNS
什么是HTTPDNS
HTTPDNS使用HTTP与DNS服务器交互，代替传统的基于UDP的DNS协议，域名解析请求直接发送到HTTPDNS服务端，从而绕过运营商的Local DNS
HTTPDNS的特性
防止域名劫持
精准调度
用户连接失败率下降
0 条评论
下一页
