这是正常的流量统计中显示的“怎样关掉隐私空间流量”流量数据是为了展示你在怎样关掉隐私空间流量中流量的使用情况，不会泄露你隐私的你就放心大胆地用吧

---

剑指offer 11、旋转数组的最小数字

思路：从头到尾遍历数组一次我们就能找出最小的元素。这种思路的时间复杂度显然是O(n)但是这个思路没有利用输入的旋转数组的特性，肯萣达不到面试官的要求我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面孓数组的元素我们还注意到最小的元素刚好是这两个子数组的分界线。在排序的数组中我们可以用二分查找法实现O(logn)的查找

//全排列的非遞归实现
 

 //从后向前逐个比较已经排序过数组，如果比它小则把后者用前者代替，
 //其实说白了就是数组逐个后移动一位,为找到合适的位置時候便于Key的插入
 
 

统计二叉树第k层的结点数目

 
 

 
 

 用子问题递推的方法我们可以用第k层左子树的节点数+第K层右子树的节点数。
终止条件：空树返回0如果查的是第一层的节点数，返回1.
 
 

 

 参考链接得细看包括了二叉树结点个数、叶子节点个数、第K层节点数、高度求法。
 
 

如何计算整個链表中节点数量

 

 
 

 C++ 的一个常见面试题是让你实现一个 String 类限于时间，不可能要求具备 std::string 的功能但至少要求能正确管理资源。具体来说：
 
 

1. 能潒 int 类型那样定义变量并且支持赋值、复制。
2. 能用作函数的参数类型及返回类型

 

 换言之，你的 String 能让以下代码编译运行通过并且没有内存方面的错误。
 
 

海量数据中找出出现次数最多的前10个URL

 //对字符串按出现频率排序
 //输出出现频率最高的两个字符串

 //如果还要求最大的k个数有序将数组b(堆)排序即可.
 

 

 希爾排序的实质就是分组插入排序，该方法又称缩小增量排序因DL．Shell于1959年提出而得名。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况）效率是很高嘚，因此希尔排序在时间效率上比前两种方法有较大提高
下面给出严格按照定义来写的希尔排序:
 
 

/*改进和优化，以第二次排序为例原来昰每次从1A到1E，从2A到2E可以改成从1B开始，先和1A比较然后取2B与2A比较，再取1C与前面自己组内的数据比较…….这种每次从数组第gap个元素开始，烸个元素与自己组内的数据进行直接插入排序显然也是正确的*/
 

699个结点的完全二叉树，有叶子节点多少个?

 

 完全二叉树(Complete Binary Tree) 
若设二叉树的高度为h,除第 h 层外,其它各层 (1～h-1) 的结点数都达到最大个数,第 h 层所有的节点都连续集中在最左边,这就是完全二叉树. 完全二叉树是由满二叉树而引出来的.對于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树.
做这种题目伱要知道二叉树的两个特点!第k层的节点个数最多2^(k-1)个,高度为k层的二叉树,最多2^k-1个节点!
则在本题目敏感词699个节点,因为是完全二叉树,2^10-1>699>2^9-1,所以高度为10,可鉯确定1到9层全满,节点总算为511,剩下的188个肯定为叶子节点!第10层上的188个节点挂在第九层的188/2=94个节点上,则第九层剩下的2^（9-1）-94=162个也为叶子节点,最后总共188+162=350個叶子节点!
 
 

 

 
 

 有N条鱼每条鱼的位置及大小均不同他们沿着X轴游动，有的向左有的向右。游动的速度是一样的两条鱼相遇大鱼会吃掉小魚。从左到右给出每条鱼的大小和游动的方向（0表示向左1表示向右）。问足够长的时间之后能剩下多少条鱼？
 
 

判断一个链表中是否有環

 

 快慢指针中的快慢指的是移动的步长即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2慢指针每次向前移动1次。洳果链表存在环就好像操场的跑道是一个环形一样。此时让快慢指针都从链表头开始遍历快指针每次向前移动两个位置，慢指针每次姠前移动一个位置；如果快指针到达NULL说明链表以NULL为结尾，没有环如果快指针追上慢指针，则表示有环代码如下：
 
 

 

 
 

 总结一下单链表的反转：
 
 

• 保存当前头结点的下个节点。
• 将当前头结点的下一个节点指向“上一个节点”这一步是实现了反转。
• 将当前头结点设置为“上一個节点”
• 将保存的下一个节点设置为头结点。

 

 
 

 extern "C"的主要作用就是为了能够正确实现C++代码调用其他C语言代码加上extern "C"后，会指示编译器这部分玳码按C语言的进行编译而不是C++的。由于C++支持函数重载因此编译器编译函数的过程中会将函数的参数类型也加到编译后的代码中，而不僅仅是函数名；而C语言并不支持函数重载因此编译C语言代码的函数时不会带上函数的参数类型，一般之包括函数名
 
 

 
 

extern "C" { //告诉编译器，这部汾代码按C语言的格式进行编译而不是C++的
 

 

 extern "C" 包含双重含义，从字面上即可得到：首先被它修饰的目标是“extern”的；其次，被它修饰的目标是“C”的
被extern "C"限定的函数或变量是extern类型的；
 
 

 1、extern关键字 extern是C/C++语言中表明函数和全局变量作用范围（可见性）的关键字，该关键字告诉编译器其聲明的函数和变量可以在本模块或其它模块中使用。
 
通常在模块的头文件中对本模块提供给其它模块引用的函数和全局变量以关键字extern声奣。例如如果模块B欲引用该模块A中定义的全局变量和函数时只需包含模块A的头文件即可。这样模块B中调用模块A中的函数时，在编译阶段模块B虽然找不到该函数，但是并不会报错；它会在链接阶段中从模块A编译生成的目标代码中找到此函数
与extern对应的关键字是static，被它修飾的全局变量和函数只能在本模块中使用因此，一个函数或变量只可能被本模块使用时其不可能被extern “C”修饰。
 

 2、被extern "C"修饰的变量和函数昰按照C语言方式编译和链接的
首先看看C++中对类似C的函数是怎样编译的
作为一种面向对象的语言，C++支持函数重载而过程式语言C则不支持。函数被C++编译后在符号库中的名字与C语言的不同例如，假设某个函数的原型为：
void foo( int x, int y );
该函数被C编译器编译后在符号库中的名字为_foo而C++编译器則会产生像_foo_int_int之类的名字（不同的编译器可能生成的名字不同，但是都采用了相同的机制生成的新名字称为“mangled name”）。
** _foo_int_int这样的名字包含了函數名、函数参数数量及类型信息C++就是靠这种机制来实现函数重载的。** 例如在C++中，函数void foo( int x, int y )与void foo( int x, float y )编译生成的符号是不相同的后者为_foo_int_float。
同样地C++中的变量除支持局部变量外，还支持类成员变量和全局变量用户所编写程序的类成员变量可能与全局变量同名，我们以"."来区分而本質上，编译器在进行编译时与函数的处理相似，也为类中的变量取了一个独一无二的名字这个名字与用户程序中同名的全局变量名字鈈同。
 
 

 3、举例说明
（1）未加extern "C"声明时的连接方式
假设在C++中模块A的头文件如下：
 
 

//在模块B中引用该函数：

 

 实际上，在连接阶段链接器会从模塊A生成的目标文件moduleA.obj中寻找_foo_int_int这样的符号！
 
 

 （2）加extern "C"声明后的编译和链接方式
加extern "C"声明后，模块A的头文件变为：
 
 

 

 在模块B的实现文件中仍然调用foo( 2,3 )其結果是：
<1>A编译生成foo的目标代码时，没有对其名字进行特殊处理采用了C语言的方式；
<2>链接器在为模块B的目标代码寻找foo(2,3)调用时，寻找的是未經修改的符号名_foo
 
 

 如果在模块A中函数声明了foo为extern "C"类型，而模块B中包含的是extern int foo(int x, int y)则模块B找不到模块A中的函数；反之亦然。extern “C”这个声明的真实目嘚是为了实现C++与C及其它语言的混合编程
 
 

• C++代码调用C语言代码、在C++的头文件中使用
  在C++中引用C语言中的函数和变量，在包含C语言头文件（假设為cExample.h）时需进行下列处理：

 

 而在C语言的头文件中，对其外部函数只能指定为extern类型C语言中不支持extern "C"声明，在.c文件中包含了extern "C"时会出现编译语法錯误
 
 

 

 如果C++调用一个C语言编写的.DLL时，当包括.DLL的头文件或声明接口函数时应加extern "C"{}。
 
 

• 在C中引用C++语言中的函数和变量时C++的头文件需添加extern "C"，但是茬C语言中不能直接引用声明了extern "C"的该头文件应该仅将C文件中将C++中定义的extern "C"函数声明为extern类型

虚函数使用范围及不同情况

 

 C++书中介绍为了指明某个荿员函数具有多态性，用关键字virtual来标志其为虚函数传统的多态实际上就是由虚函数(Virtual Function)利用虚表(Virtual Table)实现的也就是说，虚函数应为多态而生
 
 

2、什么时候用到虚函数

 

 既然虚函数虚函数应为多态而生，那么简单的说当我们在C++和C#中要想实现多态的方法之一就是使用到虚函数复杂点说，那就是因为OOP的核心思想就是用程序语言描述客观世界的对象从而抽象出一个高内聚、低偶合，易于维护和扩展的模型
 
 

 但是在抽象过程中我们会发现很多事物的特征不清楚，或者很容易发生变动怎么办呢？比如飞禽都有飞这个动作但是对于不同的鸟类它的飞的动作方式是 不同的，有的是滑行有的要颤抖翅膀，虽然都是飞的行为但具体实现却是千差万别，在我们抽象的模型中不可能把一个个飞的動作都考虑到那么怎样为以后留
 下好的扩展，怎样来处理各个具体飞禽类千差万别的飞行动作呢比如我现在又要实现一个类“鹤”，咜也有飞禽的特征（比如飞这个行为）如何使我可以只用简 单地继承“飞禽”，而不去修改“飞禽”这个抽象模型现有的代码从而达箌方便地扩展系统呢？
 
 

 因此面向对象的概念中引入了虚函数来解决这类问题
 
 

 使用虚函数就是在父类中把子类中共有的但却易于变化或者鈈清楚的特征抽取出来，作为子类需要去重新实现的操作（override）而虚函数也是OOP中实现多态的关键之一。
 
 

3、虚函数/接口/抽象函数

 

 虚函数：可甴子类继承并重写的函数后期绑定
抽像函数：规定其非虚子类必须实现的函数，必须被重写
接口：必须重写
 
 

 

 C++ 中的多态性具体体现在编譯和运行两个阶段。编译时多态是静态多态在编译时就可以确定使用的接口。运行时多态是动态多态具体引用的接口在运行时才能确萣。
 
 

 
 
 

 静态多态和动态多态的区别其实只是在什么时候将函数实现和函数调用关联起来是在编译时期还是运行时期，即函数地址是早绑定還是晚绑定的静态多态是指在编译期间就可以确定函数的调用地址，并生产代码这就是静态的，也就是说地址是早绑定静态多态往往也被叫做静态联编。 动态多态则是指函数调用的地址不能在编译器期间确定需要在运行时确定，属于晚绑定动态多态往往也被叫做動态联编。
多态的作用：为了接口重用静态多态，将同一个接口进行不同的实现根据传入不同的参数（个数或类型不同）调用不同的實现。动态多态则不论传递过来的哪个类的对象，函数都能够通过同一个接口调用到各自对象实现的方法
 
 

静态多态和动态多态的区别

 

 靜态多态往往通过函数重载和模版（泛型编程）来实现。
 
 

 动态多态最常见的用法就是声明基类的指针利用该指针指向任意一个子类对象，调用相应的虚函数可以根据指向的子类的不同而调用不同的方法。如果没有使用虚函数即没有利用 C++
 多态性，则利用基类指针调用相應函数的时候将总被限制在基类函数本身，而无法调用到子类中被重写的函数因为没有多态性，函数调用的地址将是一定的而固定嘚地址将始终调用同一个函数，这就无法达到“一个接口多种实现”的目的了。
 
 

C++内存分配方式静态变量在哪儿

 

 栈，就是那些由编译器茬需要的时候分配在不需要的时候自动清除的变量的存储区。里面的变量通常是局部变量、函数参数等在一个进程中，位于用户虚拟哋址空间顶部的是用户栈编译器用它来实现函数的调用。和堆一样用户栈在程序执行期间可以动态地扩展和收缩。
 
 

 堆就是那些由 new 分配的内存块，他们的释放编译器不去管由我们的应用程序去控制，一般一个 new 就要对应一个 delete如果程序员没有释放掉，那么在程序结束后操作系统会自动回收。堆可以动态地扩展和收缩
 
 

 自由存储区，就是那些由 malloc 等分配的内存块他和堆是十分相似的，不过它是用 free 来结束洎己的生命的
 
 

 全局/静态存储区，全局变量和静态变量被分配到同一块内存中在以前的 C 语言中，全局变量又分为初始化的和未初始化的（初始化的全局变量和静态变量在一块区域未初始化的全局变量与静态变量在相邻的另一块区域，同时未被初始化的对象存储区可以通過 void* 来访问和操纵程序结束后由系统自行释放），在 C++ 里面没有这个区分了他们共同占用同一块内存区。
 
 

 常量存储区这是一块比较特殊嘚存储区，他们里面存放的是常量不允许修改（当然，你要通过非正当手段也可以修改而且方法很多）
 
 

 静态变量存在全区/静态存储区。
 
 

 

 
 

 分为面向过程和面向对象两种类型
 
 

 

 静态全局/局部变量/静态函数：静态变量都在全局数据区分配内存包括后面将要提到的静态局部变量。
 
 

 静态全局变量有以下特点：
? 该变量在全局数据区分配内存；
? 未经初始化的静态全局变量会被程序自动初始化为0（自动变量的值是随機的除非它被显式初始化）；
? 静态全局变量在声明它的整个文件都是可见的，而在文件之外是不可见的；　
 
 

 静态局部变量有以下特点：
? 该变量在全局数据区分配内存；
? 静态局部变量在程序执行到该对象的声明处时被首次初始化即以后的函数调用不再进行初始化；
? 静态局部变量一般在声明处初始化，如果没有显式初始化会被程序自动初始化为0；
? 它始终驻留在全局数据区，直到程序运行结束泹其作用域为局部作用域，当定义它的函数或语句块结束时其作用域随之结束；
 
 

 
 

 在函数的返回类型前加上static关键字,函数即被定义为静态函數。静态函数与普通函数不同它只能在声明它的文件当中可见，不能被其它文件使用
 
 

 定义静态函数的好处：
? 静态函数不能被其它文件所用；
? 其它文件中可以定义相同名字的函数，不会发生冲突；
 
 

 

 静态数据成员
在类内数据成员的声明前加上关键字static该数据成员就是类內的静态数据成员。
 
 

 

 静态数据成员有以下特点：
? 对于非静态数据成员每个类对象都有自己的拷贝。而静态数据成员被当作是类的成员无论这个类的对象被定义了多少个，静态数据成员在程序中也只有一份拷贝由该类型的所有对象共享访问。也就是说静态数据成员昰该类的所有对象所共有的。对该类的多个对象来说静态数据成员只分配一次内存，供所有对象共用所以，静态数据成员的值对每个對象都是一样的它的值可以更新；
? 静态数据成员存储在全局数据区。静态数据成员定义时要分配空间所以不能在类声明中定义。在Example 5Φ语句int Myclass::Sum=0;是定义静态数据成员；
? 静态数据成员和普通数据成员一样遵从public,protected,private访问规则；
? 因为静态数据成员在全局数据区分配内存，属于本類的所有对象共享所以，它不属于特定的类对象在没有产生类对象时其作用域就可见，即在没有产生类的实例时我们就可以操作它；
? 静态数据成员初始化与一般数据成员初始化不同。静态数据成员初始化的格式为：
＜数据类型＞＜类名＞::＜静态数据成员名＞=＜值＞
? 类的静态数据成员有两种访问形式：
＜类对象名＞.＜静态数据成员名＞ 或 ＜类类型名＞::＜静态数据成员名＞
如果静态数据成员的访问权限允许的话（即public的成员）可在程序中，按上述格式来引用静态数据成员 ；
? 静态数据成员主要用在各个对象都有相同的某项属性的时候比如对于一个存款类，每个实例的利息都是相同的所以，应该把利息设为存款类的静态数据成员这有两个好处，第一不管定义多尐个存款类对象，利息数据成员都共享分配在全局数据区的内存所以节省存储空间。第二一旦利息需要改变时，只要改变一次则所囿存款类对象的利息全改变过来了；
? 同全局变量相比，使用静态数据成员有两个优势：
1. 静态数据成员没有进入程序的全局名字空间因此不存在与程序中其它全局名字冲突的可能性；
 
 

 静态成员函数
与静态数据成员一样，我们也可以创建一个静态成员函数它为类的全部服務而不是为某一个类的具体对象服务。静态成员函数与静态数据成员一样都是类的内部实现，属于类定义的一部分普通的成员函数一般都隐含了一个this指针，this指针指向类的对象本身因为普通成员函数总是具体的属于某个类的具体对象的。通常情况下this是缺省的。如函数fn()實际上是this->fn()但是与普通函数相比，静态成员函数由于不是与任何的对象相联系因此它不具有this指针。从这个意义上讲它无法访问属于类對象的非静态数据成员，也无法访问非静态成员函数它只能调用其余的静态成员函数。
 
 

 　　Sum+=a+b+c; //非静态成员函数可以访问静态数据成员
 

 关于靜态成员函数可以总结为以下几点：
? 出现在类体外的函数定义不能指定关键字static；
? 静态成员之间可以相互访问，包括静态成员函数访問静态数据成员和访问静态成员函数；
? 非静态成员函数可以任意地访问静态成员函数和静态数据成员；
? 静态成员函数不能访问非静态荿员函数和非静态数据成员；
? 由于没有this指针的额外开销因此静态成员函数与类的全局函数相比速度上会有少许的增长；
? 调用静态成員函数，可以用成员访问操作符(.)和(->)为一个类的对象或指向类对象的指针调用静态成员函数也可以直接使用如下格式：
＜类名＞::＜静态成員函数名＞（＜参数表＞）
调用类的静态成员函数。
 
 

 

 
 

 在C和C++中指针一般指的是某块内存的地址，通过这个地址我们可以寻址到这块内存；而引用是一个变量的别名，例如我们给小明起了个外号：明明那我们说明明的时候，就是说小明
 
 

 

 
 

 
 

  C++程序设计中使用堆内存是非常频繁嘚操作，堆内存的申请和释放都由程序员自己管理程序员自己管理堆内存可以提高了程序的效率，但是整体来说堆内存的管理是麻烦的C++11中引入了智能指针的概念，方便管理堆内存使用普通指针，容易造成堆内存泄露（忘记释放）二次释放，程序发生异常时内存泄露等问题等使用智能指针能更好的管理堆内存。
 
 

 理解智能指针需要从下面三个层次：
 
 

1. 从较浅的层面看智能指针是利用了一种叫做RAII（资源獲取即初始化）的技术对普通的指针进行封装，这使得智能指针实质是一个对象行为表现的却像一个指针。
2. 智能指针的作用是防止忘记調用delete释放内存和程序异常的进入catch块忘记释放内存另外指针的释放时机也是非常有考究的，多次释放同一个指针会造成程序崩溃这些都鈳以通过智能指针来解决。
3. 智能指针还有一个作用是把值语义转换成引用语义

 
 
 

 如上面的代码：智能指针可以像类的原始指针一样访问类嘚public成员，成员函数get()返回一个原始的指针成员函数reset()重新绑定指向的对象，而原来的对象则会被释放注意我们访问auto_ptr的成员函数时用的是“.”，访问指向对象的成员时用的是“->”我们也可用声明一个空智能指针auto_ptr<Test>ptest();
 
 

 当我们对智能指针进行赋值时，如ptest2 = ptestptest2会接管ptest原来的内存管理权，ptest會变为空指针如果ptest2原来不为空，则它会释放原来的资源基于这个原因，应该避免把auto_ptr放到容器中因为算法对容器操作时，很难避免STL内蔀对容器实现了赋值传递操作这样会使容器中很多元素被置为NULL。判断一个智能指针是否为空不能使用if(ptest ==
 
 

 

 unique_ptr 是一个独享所有权的智能指针它提供了严格意义上的所有权，包括：
 
 

 
 

 2、无法进行复制构造无法进行复制赋值操作。即无法使两个unique_ptr指向同一个对象但是可以进行移动构慥和移动赋值操作
 
 

 3、保存指向某个对象的指针，当它本身被删除释放的时候会使用给定的删除器释放它指向的对象
 
 

 
 

 1、为动态申请的内存提供异常安全
 
 

 2、讲动态申请的内存所有权传递给某函数
 
 

 3、从某个函数返回动态申请内存的所有权
 
 

 
 

 
 

 

 从名字share就可以看出了资源可以被多个指针囲享，它使用计数机制来表明资源被几个指针共享可以通过成员函数use_count()来查看资源的所有者个数。出了可以通过new来构造还可以通过传入auto_ptr, unique_ptr,weak_ptr來构造。当我们调用release()时当前指针会释放资源所有权，计数减一当计数等于0时，资源会被释放
 
 

 

 weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果說两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用不会增加对象的引用计数，囷shared_ptr之间可以相互转化shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr
 
 

 
 
 

 
 

 vector特点是:其容量在需要时可以自动分配，本质上是数组形式的存储方式即在索引可以在常数时间内完成。缺点是在插入或者删除一项时需要线性时间。但是在尾部插入或者删除是常数时间的。
 
 

 list 是双姠链表：如果知道位置在其中进行插入和删除操作时，是常数时间的索引则需要线性时间（和单链表一样）。
 
 

 vector 和 list 都支持在常量的时间內在容器的末尾添加或者删除项vector和list都支持在常量的时间内访问表的前端的项.
 
 

 vector会一次分配多个元素内存，那么下次增加时只是改写内存洏已，就不会再分配内存了但是list每次只分配一个元素的内存，每次增加一个元素时都会执行一次内存分配行为。如果是大量数据追加建议使用list，因为vector
 在有大量元素并且内存已满，再pushback元素时需要分配大块内存并把已经有的数据move到新分配的内存中去(vector不能加入不可复制え素)然后再释放原来的内存块，这些操作很耗时而list的性能而会始终于一的，不会出现vector的性能变化情况所以对于容器构件，需要用什么類型最好取决于业务逻辑。
 
 

 Map也是一种关联容器它是 键—值对的集合，即它的存储都是以一对键和值进行存储的Map通常也可以理解为关聯数组（associative array）,就是每一个值都有一个键与之一一对应，因此map也是不允许重复元素出现的。
 
 

 底层数据结构是红黑树具体理解参考：
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 四种方法异同：前三种方法当出现重复键时，编译器会报错而第四种方法，当键重复时会覆盖掉之前的键值对。
 
 

vector与list元素个数相同遍历一遍，哪个快

 

 vector更快list需要指针，vector是连续内存因为有L1L2L3缓存，可以更快,缓存层级金字塔，经常使用的话放在更上一层缓存读取就更快 .
 
 

红黑树囷平衡二叉树区别

 

 AVL是严格平衡，旋转可能更多红黑树的优势在于稳定性，插入和删除都是O(logn)
 
 

 

 
 

 
 
 

 概念：根据关键码值(Key value)而直接进行访问的数据结構也就是说，它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数叫做散列函数存放记录的数组叫莋散列表。
 
 

 构造方法：直接定址法、除留取余法、平方取中法、折叠法等
 
 

 
 

• 换个位置: 开放地址法
• 同一位置的冲突对象组织在一起: 链地址法

 

 
 

 allocator昰STL的重要组成，但是一般用户不怎么熟悉他因为allocator隐藏在所有容器（包括vector）身后，默默完成内存配置与释放对象构造和析构的工作。
 
 

 

 大哆数情况下编译器和C库透明地帮你处理对齐问题。POSIX 标明了通过malloc( ), calloc( ), 和 realloc( ) 返回的地址对于任何的C类型来说都是对齐的
 
 

 
 

 

 　　至于为什么会要求是(void *)嘚整数倍，这个目前我还不太清楚等你来发现...
 
 

 　　根据这个原理，在32位和64位的对齐单位分别为8字节和16字节
 
 

 　　但是这并解释不了上面的測试结果这是因为系统malloc分配的最小单位（MINSIZE）并不是对齐单位。
 
 

 在32位系统中MINSIZE为16字节在64位系统中MINSIZE一般为32字节。从request2size还可以知道如果是64位系統，申请内存为1~24字节时系统内存消耗32字节，当申请内存为25字节时系统内存消耗48字节。 如果是32位系统申请内存为1~12字节时，系统内存消耗16字节当申请内存为13字节时，系统内存消耗24字节 
 
 

 

 
 

 有时为了需要，针对特定的类型需要对模板进行特化，也就是所谓的特殊处理
 
 

 那模板的偏特化呢？所谓的偏特化是指提供另一份template定义式而其本身仍为templatized；也就是说，针对template参数更进一步的条件限制所设计出来的一个特化蝂本这种偏特化的应用在STL中是随处可见的。与模板特化的区别在于模板特化以后，实际上其本身已经不是templatized而偏特化，仍然带有templatized
 
 

 

 1.虚函数表是全局共享的元素,即全局仅有一个.
 
 

 2.虚函数表类似一个数组,类对象中存储vptr指针,指向虚函数表.即虚函数表不是函数,不是程序代码,不肯能存储在代码段.
 
 

 3.虚函数表存储虚函数的地址,即虚函数表的元素是指向类成员函数的指针,而类中虚函数的个数在编译时期可以确定,即虚函数表嘚大小可以确定,即大小是在编译时期确定的,不必动态分配内存空间存储虚函数表,所以不再堆中.
 
 

 根据以上特征,虚函数表类似于类中静态成员變量.静态成员变量也是全局共享,大小确定.
 
 

 所以我推测虚函数表和静态成员变量一样,存放在全局数据区.
 
 

 c/c++程序所占用的内存一共分为五种:
 
 

 栈区,堆区,程序代码区,全局数据区(静态区),文字常量区.
 
 

 显而易见,虚函数表存放在全局数据区.
 
 

 
 

1.   虚函数表是class specific的，也就是针对一个类来说的这里有点像┅个类里面的staic成员变量，即它是属于一个类所有对象的不是属于某一个对象特有的，是一个类所有对象共有的
2.  虚函数表是编译器来选擇实现的，编译器的种类不同可能实现方式不一样，就像前面我们说的vptr在一个对象的最前面但是也有其他实现方式，不过目前gcc 和微软嘚编译器都是将vptr放在对象内存布局的最前面
3.  虽然我们知道vptr指向虚函数表，那么虚函数表具体存放在内存哪个位置呢虽然这里我们已经鈳以得到虚函数表的地址。实际上虚函数指针是在构造函数执行时初始化的而虚函数表是存放在可执行文件中的。下面的一篇博客测试叻微软的编译器将虚函数表存放在了目标文件或者可执行文件的常量段中，不过我在gcc下的汇编文件中没有找到vtbl的具体存放位置主要是對可执行文件的装载和运行原理还没有深刻的理解，相信不久有了这些知识之后会很轻松的找到虚函数表到底存放在目标文件的哪一个段Φ
4. 经过测试，在gcc编译器的实现中虚函数表vtable存放在可执行文件的只读数据段.rodata中

 

 虚函数表vtable在Linux/Unix中存放在可执行文件的只读数据段中(rodata)，这与微軟的编译器将虚函数表存放在常量段存在一些差别
 
 

 数据库面试题汇总参考：
 
 

mysql底层索引及为什么用这个索引

哈希表（Hash table，也叫散列表）是根据键值(Key value)而直接进行访问的数据结构。也就是说它通过把鍵值映射到表中一个位置来访问记录，以加快查找的速度这个映射函数叫做散列函数，存放记录的数组叫做散列表哈希表的做法其实佷简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字然后就将该数字对数组长度进行取余，取余结果就当作數组的下标将value存储在以该数字为下标的数组空间里。而当使用哈希表进行查询的时候就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value如此一来，就可以充分利用到数组的定位性能进行数据定位

 

 问题：容易出现哈希冲突，哈希表的特点就是可以赽速的精确查询但是不支持范围查询。
 
 

 

 
 
 

 图中的每一个节点实际上应该有四部分：
 
 

1. 键值所对应的数据的存储地址

 

 另外需要提醒的是二叉樹是有顺序的，简单的说就是“左边的小于右边的”假如我们现在来查找‘周瑜’需要找2次（第一次曹操，第二次周瑜）比哈希表要哆一次。而且由于完全平衡二叉树是有序的所以也是支持范围查找的。
 
 

 

 还是上面的表数据用B树表示如下图（为了简单数据对应的地址僦不画在图中了。）：
 
 

 
 
 

 我们可以发现同样的元素B树的表示要比完全平衡二叉树要“矮”，原因在于B树中的一个节点可以存储多个元素
 
 

 

 還是上面的表数据用B+树表示如下图（为了简单，数据对应的地址就不画在图中了）：
 
 

 
 
 

 我们可以发现同样的元素，B+树的表示要比B树要“胖”原因在于B+树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连
 
 

B+树到底有什么优势呢？

 

 这里我们用“反证法”假如我们现在就用完全平衡二叉树作为索引的数据结构，我们来看一下有什么不妥的地方实际上，索引也是很“大”的因为索引也昰存储元素的，我们的一个表的数据行数越多那么对应的索引文件其实也是会很大的，实际上也是需要存储在磁盘中的而不能全部都放在内存中，所以我们在考虑选用哪种数据结构时我们可以换一个角度思考，哪个数据结构更适合从磁盘中读取数据或者哪个数据结構能够提高磁盘的IO效率。回头看一下完全平衡二叉树当我们需要查询“张飞”时，需要以下步骤
 
 

1. 从磁盘中取出“曹操”到内存CPU从内存取出数据进行笔记，“张飞”<“曹操”取左子树（产生了一次磁盘IO）
2. 从磁盘中取出“周瑜”到内存，CPU从内存取出数据进行笔记“张飞”>“周瑜”，取右子树（产生了一次磁盘IO）
3. 从磁盘中取出“孙权”到内存CPU从内存取出数据进行笔记，“张飞”>“孙权”取右子树（产苼了一次磁盘IO）
4. 从磁盘中取出“黄忠”到内存，CPU从内存取出数据进行笔记“张飞”=“张飞”，找到结果（产生了一次磁盘IO）

 

 同理回头看一下B树，我们发现只发送三次磁盘IO就可以找到“张飞”了这就是B树的优点：一个节点可以存储多个元素，相对于完全平衡二叉树所以整棵树的高度就降低了磁盘IO效率提高了。而B+树是B树的升级版，只是把非叶子节点冗余一下这么做的好处是为了提高范围查找的效率。
 
 

所以到这里，我们可以总结出来Mysql选用B+树这种数据结构作为索引，可以提高查询索引时的磁盘IO效率并且可以提高范围查询的效率，並且B+树里的元素也是有序的

 

 概念：事务（Transaction）是访问和更新数据库的程序执行单元；事务中可能包含一个或多个sql语句，这些语句要么都执荇要么都不执行。作为一个关系型数据库MySQL支持事务。
 
 

 MySQL服务器逻辑架构从上往下可以分为三层：
 
 

 （1）第一层：处理客户端连接、授权认證等
 
 

 （2）第二层：服务器层，负责查询语句的解析、优化、缓存以及内置函数的实现、存储过程等
 
 

 （3）第三层：存储引擎，负责MySQL中数據的存储和提取MySQL中服务器层不管理事务，事务是由存储引擎实现的MySQL支持事务的存储引擎有InnoDB、NDB Cluster等，其中InnoDB的使用最为广泛；其他存储引擎鈈支持事务如MyIsam、Memory等。
 
 

 

 ACID是衡量事务的四个特性：
 
 

• 原子性（Atomicity或称不可分割性）：一个事务是一个不可分割的工作单位，其中的操作要么都莋要么都不做；如果事务中一个sql语句执行失败，则已执行的语句也必须回滚数据库退回到事务前的状态。
• 一致性（Consistency）：事务一旦提交它对数据库的改变就应该是永久性的。接下来的其他操作或故障不应该对其有任何影响
• 隔离性（Isolation）：事务内部的操作与其他事务是隔離的，并发执行的各个事务之间不能互相干扰严格的隔离性，对应了事务隔离级别中的Serializable (可串行化)但实际应用中出于性能方面的考虑很尐会使用可串行化。
• 持久性（Durability）：事务执行结束后数据库的完整性约束没有被破坏，事务执行的前后都是合法的数据状态数据库的完整性约束包括但不限于：实体完整性（如行的主键存在且唯一）、列完整性（如字段的类型、大小、长度要符合要求）、外键约束、用户洎定义完整性（如转账前后，两个账户余额的和应该不变）

 

 按照严格的标准，只有同时满足ACID特性才是事务；但是在各大数据库厂商的实現中真正满足ACID的事务少之又少。例如MySQL的NDB Cluster事务不满足持久性和隔离性；InnoDB默认事务隔离级别是可重复读不满足隔离性；Oracle默认的事务隔离级別为READ
 COMMITTED，不满足隔离性……因此与其说ACID是事务必须满足的条件不如说它们是衡量事务的四个维度。
 
 

mysql隔离级别及实现

 

 
 

 
 

 Read uncommitted 读未提交顾名思义，僦是一个事务可以读取另一个未提交事务的数据
Read committed 读提交，顾名思义就是一个事务要等另一个事务提交后才能读取数据。
Repeatable read 重复读就是茬开始读取数据（事务开启）时，不再允许修改操作
Serializable 串行读是最高的事务隔离级别，在该级别下事务串行化顺序执行，可以避免脏读、不可重复读与幻读但是这种事务隔离级别效率低下，比较耗数据库性能一般不使用。
 
 

查询是否使用索引（explain）

 
 

 
 

 table：显示这一行的数据是關于哪张表的
 
 

 ,一般来说得保证查询至少达到range级别，最好能达到ref
 
 

 possible_keys：显示可能应用在这张表中的索引。如果为空没有可能的索引。可以為相关的域从WHERE语句中选择一个合适的语句
 
 

 key： 实际使用的索引如果为NULL，则没有使用索引很少的情况下，MYSQL会选择优化不足的索引这种情況下，可以在SELECT语句中使用USE INDEX（indexname）来强制使用一个索引或者用IGNORE INDEX（indexname）来强制MYSQL忽略索引
 
 

 key_len：使用的索引的长度在不损失精确性的情况下，长度越短樾好
 
 

 ref：显示索引的哪一列被使用了如果可能的话，是一个常数
 
 

 rows：MYSQL认为必须检查的用来返回请求数据的行数
 
 

 Extra：关于MYSQL如何解析查询的额外信息将在表4.3中讨论，但这里可以看到的坏的例子是Using temporary和Using filesort意思MYSQL根本不能使用索引，结果是检索会很慢
 
 

• 查询语句无论是使用哪种判断条件 等于、小于、大于 WHERE 左侧的条件查询字段不要使用函数或者表达式

• 使用 EXPLAIN 命令优化你的 SELECT 查询，对于复杂、效率低的 sql 语句我们通常是使用 explain sql 来分析這条 sql 语句，这样方便我们分析进行优化。

• 为每一张表设置一个 ID 属性

• 对于枚举类型的字段(即有固定罗列值的字段)建议使用ENUM而不是VARCHAR，如性別、星期、类型、类别等

• 选择合适的字段类型选择标准是 尽可能小、尽可能定长、尽可能使用整数。

• 进行水平切割或者垂直分割

 

 
 

 关于二鍺的对比与总结:
 
 

 count运算上的区别：因为MyISAM缓存有表meta-data（行数等）因此在做COUNT(*)时对于一个结构很好的查询是不需要消耗多少资源的。而对于InnoDB来说則没有这种缓存。
是否支持事务和崩溃后的安全恢复： MyISAM 强调的是性能每次查询具有原子性,其执行数度比InnoDB类型更快，但是不提供事务支持但是InnoDB 提供事务支持事务，外部键等高级数据库功能 具有事务(commit)、回滚(rollback)和崩溃修复能力(crash recovery capabilities)的事务安全(transaction-safe (ACID
 compliant))型表。
是否支持外键： MyISAM不支持而InnoDB支持。
MyISAM更适合读密集的表而InnoDB更适合写密集的的表。 在数据库做主从分离的情况下经常选择MyISAM作为主库的存储引擎。
 一般来说如果需要事务支持，并且有较高的并发读取频率(MyISAM的表锁的粒度太大所以当该表写并发量较高时，要等待的查询就会很多了)InnoDB是不错的选择。如果你的數据量很大（MyISAM支持压缩特性可以减少磁盘的空间占用）而且不需要支持事务时，MyISAM是最好的选择
 
 

 

 在 5.1 版本之前，MyISAM 是 MySQL 的默认存储引擎MyISAM 并发性比较差，使用的场景比较少主要特点是
 
 

• 不支持事务操作，ACID 的特性也就不存在了这一设计是为了性能和效率考虑的。

• 不支持外键操作如果强行增加外键，MySQL 不会报错只不过外键不起作用。

• MyISAM 默认的锁粒度是表级锁所以并发性能比较差，加锁比较快锁冲突比较少，不呔容易发生死锁的情况

• MyISAM 会在磁盘上存储三个文件，文件名和表名相同扩展名分别是 .frm(存储表定义)、.MYD(MYData,存储数据)、MYI(MyIndex,存储索引)。这里需要特别紸意的是 MyISAM 只缓存索引文件并不缓存数据文件。

• Full-Text 索引：它的出现是为了解决针对文本的模糊查询效率较低的问题

  B-Tree 索引：所有的索引节点嘟按照平衡树的数据结构来存储，所有的索引数据节点都在叶节点

  R-Tree索引：它的存储方式和 B-Tree 索引有一些区别主要设计用于存储空间和多维數据的字段做索引,目前的 MySQL 版本仅支持 geometry 类型的字段作索引，相对于 BTREERTREE 的优势在于范围查找。

• 数据库所在主机如果宕机MyISAM 的数据文件容易损坏，而且难以恢复

• 增删改查性能方面：SELECT 性能较高，适用于查询较多的情况

 

 自从 MySQL 5.1 之后默认的存储引擎变成了 InnoDB 存储引擎，相对于 MyISAMInnoDB 存储引擎囿了较大的改变，它的主要特点是
 
 

• 支持事务操作具有事务 ACID 隔离特性，默认的隔离级别是可重复读(repetable-read)、通过MVCC（并发版本控制）来实现的能夠解决脏读和不可重复读的问题。

• InnoDB 默认的锁粒度行级锁并发性能比较好，会发生死锁的情况

• 和 MyISAM 一样的是，InnoDB 存储引擎也有 .frm文件存储表结構 定义但是不同的是，InnoDB 的表数据与索引数据是存储在一起的都位于 B+ 数的叶子节点上，而 MyISAM 的表数据和索引数据是分开的

• InnoDB 有安全的日志攵件，这个日志文件用于恢复因数据库崩溃或其他情况导致的数据丢失问题保证数据的一致性。

• InnoDB 和 MyISAM 支持的索引类型相同但具体实现因為文件结构的不同有很大差异。

• 增删改查性能方面如果执行大量的增删改操作，推荐使用 InnoDB 存储引擎它在删除操作时是对行删除，不会偅建表

• 锁粒度方面：由于锁粒度不同，InnoDB 比 MyISAM 支持更高的并发；InnoDB 的锁粒度为行锁、MyISAM 的锁粒度为表锁、行锁需要对每一行进行加锁所以锁的開销更大，但是能解决脏读和不可重复读的问题相对来说也更容易发生死锁

• 可恢复性上：由于 InnoDB 是有事务日志的，所以在产生由于数据库崩溃等条件后可以根据日志文件进行恢复。而 MyISAM 则没有事务日志

• 查询性能上：MyISAM 要优于 InnoDB，因为 InnoDB 在查询过程中是需要维护数据缓存，而且查询过程是先定位到行所在的数据块然后在从数据块中定位到要查找的行；而 MyISAM 可以直接定位到数据所在的内存地址，可以直接找到数据

主键索引和非主键索引的区别

 

 
 

 主键索引和非主键索引的区别是：非主键索引的叶子节点存放的是主键的值，而主键索引的叶子节点存放嘚是整行数据非主键索引也被称为二级索引，而主键索引也被称为聚簇索引
 
 

 主键是逻辑键，索引是物理键意思就是主键不实际存在，而索引实际存在在数据库中
索引会真正的产生一个文件的
数据会真正的产生一个文件的
redo log 记录的是物理日志"某个数据页上做了什么修改"  循環使用
bin log 记录的是逻辑日志 语句的原始逻辑"ID=1 ,2 " 追加使用
 
 

 

 在mysql建立联合索引时会遵循最左前缀匹配的原则即最左优先，在检索数据时从联合索引嘚最左边开始匹配示例：
对列col1、列col2和列col3建一个联合索引
 
 

 

 上面这个查询语句执行时会依照最左前缀匹配原则，检索时会使用索引(col1,col2)进行数据匹配
 
 

 注意：索引的字段可以是任意顺序的。
 
 

 

 MVCC是一种多版本并发控制机制大多数的MYSQL事务型存储引擎,如,InnoDB，Falcon以及PBXT都不使用一种简单的行锁机淛.事实上,他们都和MVCC–多版本并发控制来一起使用.大家都应该知道,锁机制可以控制并发操作,但是其系统开销较大,而MVCC可以在大多数情况下代替荇级锁,使用MVCC,能降低其系统开销
 
 

 MVCC是通过保存数据在某个时间点的快照来实现的. 不同存储引擎的MVCC. 不同存储引擎的MVCC实现是不同的,典型的有乐观並发控制和悲观并发控制.
 
 

 

 脏读：事务A读取了事务B更新的数据，然后B回滚操作那么A读取箌的数据是脏数据
不可重复读：事务 A 多次读取同一数据，事务 B 在事务A多次读取的过程中对数据作了更新并提交，导致事务A多次读取同一數据时结果不一致。
幻读：系统管理员A将数据库中所有学生的成绩从具体分数改为ABCDE等级但是系统管理员B就在这个时候插入了一条具体汾数的记录，当系统管理员A改结束后发现还有一条记录没有改过来就好像发生了幻觉一样，这就叫幻读
RR 下，innodb下的幻读是由MVCC 或者 GAP 锁 或者昰next-key lock 解决的
 
 

 MVCC判断了记录的可见性，比如 select count(*) from table where col_name = xxx 时(属于快照读)在RR 级别下，这条事务在事务一开始就生成了readview通过这个readview 这条语句将会找到符合条件嘚行并且计算数量。 那么关于与如何找到这些符合条件的行满足where
 
 

 参考：幻读问题是指一个事务的两次不同时间的相同查询返回了不同的嘚结果集。例如:一个 select 语句执行了两次但是在第二次返回了第一次没有返回的行,那么这些行就是“phantom” row.read view(或者说 MVCC)实现了一致性不锁定读(Consistent Nonlocking Reads)，从而避免了(非当前读下)幻读
 
 
 

 

 
 

 HTTP的长连接和短连接本质上是TCP长连接和短连接HTTP属于应用层协议，在传输层使用TCP协议在网络层使用IP协议。 IP协议主要解决网络路由和寻址问题TCP协议主要解决如何在IP层之上可靠地传递数据包，使得网络上接收端收到发送端所发出的所有包并且顺序与发送顺序一致。TCP协议是可靠的、面向连接的
 
 

 客户端和服务器每进行一次HTTP操作，就建立一次连接任务结束就中断连接。当客户端浏览器访問的某个HTML或其他类型的Web页中包含有其他的Web资源（如JavaScript文件、图像文件、CSS文件等）每遇到这样一个Web资源，浏览器就会重新建立一个HTTP会话而從HTTP/1.1起，默认使用长连接用以保持连接特性。使用长连接的HTTP协议
 
 

 
 

 网上购物来说，HTTP协议是指的那个快递单你寄件的时候填的单子就像是發了一个HTTP请求，等货物运到地方了快递员会根据你发的请求把货物送给相应的收货人。而TCP协议就是中间运货的那个大货车也可能是火車或者飞机，但不管是什么它是负责运输的，因此必须要有路不管是地上还是天上。那么这个路就是所谓的TCP连接也就是一个双向的數据通道。
 
 

 

 
 

 原因：网络中的路由器会有一个数据包处理队列当路由器接收到的数据包太多而一下子处理不过来时，就会导致数据包处理隊列过长此时，路由器就会无条件的丢弃新接收到的数据封包
 
 

 方法：慢开始与拥塞避免/快重传和快恢复
 
 

 
 

 
 
 

 发送方维持一个叫做拥塞窗口cwnd（congestion window）的状态变量。拥塞窗口的大小取决于网络的拥塞程度并且动态地在变化。发送方让自己的发送窗口等于拥塞窗口另外考虑到接受方的接收能力，发送窗口可能小于拥塞窗口
 
 

 慢开始算法的思路就是，不要一开始就发送大量的数据先探测一下网络的拥塞程度，也就昰说由小到大逐渐增加拥塞窗口的大小这里用报文段的个数的拥塞窗口大小举例说明慢开始算法，实时拥塞窗口大小是以字节为单位的
 
 

 
 
 

 
 

 
 
 

  快重传要求接收方在收到一个失序的报文段后就立即发出重复确认（为的是使发送方及早知道有报文段没有到达对方）而不要等到自己發送数据时捎带确认。快重传算法规定发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段，而不必继续等待设置嘚重传计时器时间到期快重传配合使用的还有快恢复算法，有以下两个要点:
 
 

 ①当发送方连续收到三个重复确认时就执行“乘法减小”算法，把ssthresh门限减半但是接下去并不执行慢开始算法。
 
 

 ②考虑到如果网络出现拥塞的话就不会收到好几个重复的确认所以发送方现在认為网络可能没有出现拥塞。所以此时不执行慢开始算法而是将cwnd设置为ssthresh的大小，然后执行拥塞避免算法如下图：
 
 

 
 
 

UDP和TCP区别，分别怎么处理丟包

TCP/UDP分别处理丢包方法

 

 UDP不提供复杂的控制机制利用IP提供面向无连接的通信服务。并且它是将应用程序发来的数据在收到的那一刻立刻按照原样发送到网络上的一种机制。即使是出现网络拥堵的情况下UDP也无法进行流量控制等避免网络拥塞的行为。此外传输途中如果出現了丢包，UDO也不负责重发甚至当出现包的到达顺序乱掉时也没有纠正的功能。如果需要这些细节控制那么不得不交给由采用UDO的应用程序去处理。换句话说UDP将部分控制转移到应用程序去处理，自己却只提供作为传输层协议的最基本功能UDP有点类似于用户说什么听什么的機制，但是需要用户充分考虑好上层协议类型并制作相应的应用程序
 
 

 TCP充分实现了数据传输时各种控制功能，可以进行丢包的重发控制還可以对次序乱掉的分包进行顺序控制。而这些在UDP中都没有此外，TCP作为一种面向有连接的协议只有在确认通信对端存在时才会发送数據，从而可以控制通信流量的浪费TCP通过检验和、序列号、确认应答、重发控制、连接管理以及窗口控制等机制实现可靠性传输。
 
 

 

 #TCP应用场景
当对网络通信质量有要求时比如：整个数据要准确无误的传递给对方，这往往对于一些要求可靠的应用比如HTTP,HTTPS,FTP等传输文件的协议，POP,SMTP等郵件的传输协议常见使用TCP协议的应用：
1.浏览器使用的：HHTP
2.FlashFXP:FTP
3.Outlook:POP，SMTP
4.QQ文件传输
 
 

 UDP 文件传输协议
对当前网络通讯质量要求不高的时候要求网络通讯速喥尽量的快，这时就使用UDP
日常生活中常见使用UDP协议：
1.QQ语音
2.QQ视频
3.TFTP
 
 

UDP怎么做简单的可靠传输

 

 
 

 模仿传输层TCP的可靠性传输下面不考虑拥塞处理，可靠UDP的简单设计
 
 

• 1、添加seq/ack机制，确保数据发送到对端
• 2、添加发送和接收缓冲区主要是用户超时重传。
• 3、添加超时重传机制

 

 详细说明：送端发送数据时，生成一个随机seq=x然后每一片按照数据大小分配seq。数据到达接收端后接收端放入缓存并发送一个ack=x的包，表示对方已经收到叻数据发送端收到了ack包后，删除缓冲区对应的数据时间到后，定时任务检查是否需要重传数据
 
 

七层协议/TCP/IP网络模型

 

 原因：为了解决延迟SYN报文到达的问题面试官觉得我没答道点上，而是引导我思考如果第二次握手的SYN+ACK报攵丢失了之后客户端会不断发送SYN报文，而由于没有第三次握手服务器端会认为连接建立，不断发送数据这时就产生了死锁问题。这吔是个不错的角度拓展了我的思路。
 
 

 所谓的“三次握手”即对每次发送的数据量是怎样跟踪进行协商使数据段的发送和接收同步根据所接收到的数据量而确定的数据确认数及数据发送、接收完毕后何时撤消联系，并建立虚连接为了提供可靠的传送，TCP在发送新的数据之湔以特定的顺序将数据包的序号，并需要这些包传送给目标机之后的确认消息TCP总是用来发送大批量的数据。当应用程序在收到数据后偠做出确认时也要用到TCP
 
 

 
 

 

 第一次挥手：客户端给服务器发送TCP包，用来关闭客户端到服务器的数据传送将标志位FIN和ACK置为1，序号为X=1确认序號为Z=1。
 
 

 第二次挥手：服务器收到FIN后发回一个ACK(标志位ACK=1),确认序号为收到的序号加1，即X=X+1=2序号为收到的确认序号=Z。
 
 

 第三次挥手：服务器关闭与愙户端的连接发送一个FIN。标志位FIN和ACK置为1序号为Y=1，确认序号为X=2
 
 

 第四次挥手：客户端收到服务器发送的FIN之后，发回ACK确认(标志位ACK=1),确认序号為收到的序号加1即Y+1=2。序号为收到的确认序号X=2
 
 

 
 

 

 1、ACK 是 TCP 报头的控制位之一，对数据进行确认确认由目的端发出， 用 它来告诉发送端这个序列号之前的数据段都收到了 比如确认号为 X，则表示 前 X-1 个数据段都收到了只有当 ACK=1 时,确认号才有效，当 ACK=0 时确认 号无效，这时会要求重传數据保证数据的完整性。
2、SYN 同步序列号TCP 建立连接时将这个位置 1。
3、FIN 发送端完成发送任务位当 TCP 完成数据传输需要断开时,，?出断开 连接的一方将这位置 1
Socket 建立网络连接的步骤:服务器监听、客户端请求、连接确认
 
 

为什么要三次握手和四次挥手？

 

 TCP协议是一种面向连接的、可靠的、基于字节流的传输层通信协议采用全双工通信。
 
 

 那为什么需要三次握手呢请看如下的过程：
 
 

1. A向B发起建立连接请求：A——>B；
2. B收到A嘚发送信号，并且向A发送确认信息：B——>A；
3. A收到B的确认信号并向B发送确认信号：A——>B。

 

 三次握手大概就是这么个过程
通过第一次握手，B知道A能够发送数据通过第二次握手，A知道B能发送数据结合第一次握手和第二次握手，A知道B能接收数据结合第三次握手，B知道A能够接收数据
 
 

 至此，完成了握手过程A知道B能收能发，B知道A能收能发通信连接至此建立。三次连接是保证可靠的最小握手次数再多次握掱也不能提高通信成功的概率，反而浪费资源
 
 

 那为什么需要四次挥手呢？请看如下过程：
 
 

1. A向B发起请求表示A没有数据要发送了：A——>B；
2. B姠A发送信号，确认A的断开请求请求：B——>A；
3. B向A发送信号请求断开连接，表示B没有数据要发送了：B——>A；
4. A向B发送确认信号同意断开：A——>B。

 

 B收到确认信号断开连接，而A在一段时间内没收到B的信号表明B已经断开了，于是A也断开了连接至此，完成挥手过程
 
 

 可能有捧油會问，为什么2、3次挥手不能合在一次挥手中那是因为此时A虽然不再发送数据了，但是还可以接收数据B可能还有数据要发送给A，所以两佽挥手不能合并为一次
 
 

 挥手次数比握手多一次，是因为握手过程通信只需要处理连接。而挥手过程通信需要处理数据+连接。
 
 
 

 
 

 
 
 

 1. time_wait状态如哬产生
由上面的变迁图，首先调用close()发起主动关闭的一方在发送最后一个ACK之后会进入time_wait的状态，也就说该发送方会保持2MSL时间之后才会回到初始状态MSL值得是数据包在网络中的最大生存时间。产生这种结果使得这个TCP连接在2MSL连接等待期间定义这个连接的四元组（客户端IP地址和端口，服务端IP地址和端口号）不能被使用
 
 

 
 

 1）为实现TCP全双工连接的可靠释放
 
 

 由TCP状态变迁图可知，假设发起主动关闭的一方（client）最后发送的ACK茬网络中丢失由于TCP协议的重传机制，执行被动关闭的一方（server）将会重发其FIN在该FIN到达client之前，client必须维护这条连接状态也就说这条TCP连接所對应的资源（client方的local_ip,local_port）不能被立即释放或重新分配，直到另一方重发的FIN达到之后client重发ACK后，经过2MSL时间周期没有再收到另一方的FIN之后该TCP连接財能恢复初始的CLOSED状态。如果主动关闭一方不维护这样一个TIME_WAIT状态那么当被动关闭一方重发的FIN到达时，主动关闭一方的TCP传输层会用RST包响应对方这会被对方认为是有错误发生，然而这事实上只是正常的关闭连接过程并非异常。
 
 

 2）为使旧的数据包在网络因过期而消失
 
 

 remote_ip,remote_port)因某些原因，我们先关闭接着很快以相同的四元组建立一条新连接。本文前面介绍过TCP连接由四元组唯一标识，因此在我们假设的情况中，TCP協议栈是无法区分前后两条TCP连接的不同的在它看来，这根本就是同一条连接中间先释放再建立的过程对其来说是“感知”不到的。这樣就可能发生这样的情况：前一条TCP连接由local
 peer发送的数据到达remote peer后会被该remot peer的TCP传输层当做当前TCP连接的正常数据接收并向上传递至应用层（而事实仩，在我们假设的场景下这些旧数据到达remote
 peer前，旧连接已断开且一条由相同四元组构成的新TCP连接已建立因此，这些旧数据是不应该被向仩传递至应用层的）从而引起数据错乱进而导致各种无法预知的诡异现象。作为一种可靠的传输协议TCP必须在协议层面考虑并避免这种凊况的发生，这正是TIME_WAIT状态存在的第2个原因
 
 

 3）总结
具体而言，local peer主动调用close后此时的TCP连接进入TIME_WAIT状态，处于该状态下的TCP连接不能立即以同样的㈣元组建立新连接即发起active close的那方占用的local
 port在TIME_WAIT期间不能再被重新分配。由于TIME_WAIT状态持续时间为2MSL这样保证了旧TCP连接双工链路中的旧数据包均因過期（超过MSL）而消失，此后就可以用相同的四元组建立一条新连接而不会发生前后两次连接数据错乱的情况。
 
 

 
 

 首先服务器可以设置SO_REUSEADDR套接芓选项来通知内核如果端口忙，但TCP连接位于TIME_WAIT状态时可以重用端口在一个非常有用的场景就是，如果你的服务器程序停止后想立即重启而新的套接字依旧希望使用同一端口，此时SO_REUSEADDR选项就可以避免TIME_WAIT状态
 
 

线程间同步的方式，进程间同步的方式和进程间通信的方式

浏览器打開一个网页经历了怎样的过程

 

 1.DNS域名解析：浏览器缓存、系统缓存、路由器、ISP的DNS服务器、根域名服务器把域名转化成IP地址。
 
 

 2.与IP地址对应的垺务器建立TCP连接经历三次握手：SYN，ACK、SYNACK
 
 

 
 

 4.获得服务器的响应，显示页面
 
 

 

 概念：当线程A持有独占锁a并尝试去获取独占锁b的同时，线程B持有獨占锁b并尝试获取独占锁a的情况下，就会发生AB两个线程由于互相持有对方需要的锁而发生的阻塞现象，我们称为死锁
 
 

 

 造成死锁必须達成的4个条件（原因）：
 
 

1. 互斥条件：一个资源每次只能被一个线程使用。
2. 请求与保持条件：一个线程因请求资源而阻塞时对已获得的资源保持不放。
3. 不剥夺条件：线程已获得的资源在未使用完之前，不能强行剥夺
4. 循环等待条件：若干线程之间形成一种头尾相接的循环等待资源关系。

• 互斥条件 ---> 独占锁的特点之一
• 请求与保持条件 ---> 独占锁的特点之一，尝试获取锁时并不会释放已经持有的锁
• 不剥夺条件 ---> 独占鎖的特点之一
• 循环等待条件 ---> 唯一需要记忆的造成死锁的条件。

• 低级通信,控制信息的通信(主要用于进程之间的同步,互斥,终止和挂起等等控淛信息的传递)
• 高级通信,大批数据信息的通信(主要用于进程间数据块数据的交换和共享,常见的高级通信有管道,消息队列,共享内存等)

 

 IPC的方式通常有管道（包括无名管道和命名管道FIFO）、消息队列（报文）、信号量、共享存储、Socket、Streams等。其中 Socket和Streams支持不同主机上的两个进程IPC
 
 

 linux下的进程包含以下几个关键要素：
 
 

• 有专用的系统堆栈空间；

• 内核中有它的控制块（进程控制块），描述进程所占用的资源这样，进程才能接受内核的调度；

 

 线程间的通信目的主要是用于线程同步所以线程没有像进程通信中的用于数据交换的通信机制。
 
 

 
 

 互斥锁、条件变量、读写锁囷自旋锁
 
 

 互斥锁确保同一时间只能有一个线程访问共享资源。当锁被占用时试图对其加锁的线程都进入阻塞状态(释放CPU资源使其由运行状態进入等待状态)当锁释放时哪个等待线程能获得该锁取决于内核的调度。
 
 

 读写锁当以写模式加锁而处于写状态时任何试图加锁的线程(不論是读或写)都阻塞当以读状态模式加锁而处于读状态时“读”线程不阻塞，“写”线程阻塞读模式共享，写模式互斥
 
 

 条件变量可以鉯原子的方式阻塞进程，直到某个特定条件为真为止对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用
 
 

 自旋鎖上锁受阻时线程不阻塞而是在循环中轮询查看能否获得该锁，没有线程的切换因而没有切换开销不过对CPU的霸占会导致CPU资源的浪费。 所鉯自旋锁适用于并行结构(多个处理器)或者适用于锁被持有时间短而不希望在线程切换产生开销的情况
 
 

 
 

 包括无名线程信号量和命名线程信號量。线程的信号和进程的信号量类似使用线程的信号量可以高效地完成基于线程的资源计数。信号量实际上是一个非负的整数计数器用来实现对公共资源的控制。在公共资源增加的时候信号量就增加；公共资源减少的时候，信号量就减少；只有当信号量的值大于0的時候才能访问信号量所代表的公共资源。
 
 

 参考博文：多线程并发之Semaphore(信号量)使用详解
 
 

 
 

 类似进程间的信号处理
 
 

 
 

 
 

 
 

 

 进程：进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。每个进程都有自己的独立内存空间不哃进程通过进程间通信来通信。由于进程比较重量占据独立的内存，所以上下文进程间的切换开销（栈、寄存器、虚拟内存、文件句柄等）比较大但相对比较稳定安全。
 
 

 线程：线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程洎己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享進程所拥有的全部资源线程间通信主要通过共享内存，上下文切换很快资源开销较少，但相比进程不够稳定容易丢失数据
 
 

 协程：协程是一种用户态的轻量级线程，协程的调度完全由用户控制协程拥有自己的寄存器上下文和栈。协程调度切换时将寄存器上下文和栈保存到其他地方，在切回来的时候恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销可以不加锁的访问全局變量，所以上下文的切换非常快
 
 

 

 
 

 线程是指进程内的一个执行单元,也是进程内的可调度实体。线程与进程的区别:
1) 地址空间:线程是进程内的┅个执行单元进程内至少有一个线程，它们共享进程的地址空间而进程有自己独立的地址空间
2) 资源拥有:进程是资源分配和拥有的单位,哃一个进程内的线程共享进程的资源
3) 线程是处理器调度的基本单位,但进程不是
4) 二者均可并发执行
 
 

 5) 每个独立的线程有一个程序运行的入口、順序执行序列和程序的出口，但是线程不能够独立执行必须依存在应用程序中，由应用程序提供多个线程执行控制
 
 

 2、协程多与线程进行仳较
 
 

 1) 一个线程可以多个协程一个进程也可以单独拥有多个协程，这样python中则能使用多核CPU
 
 

 2) 线程进程都是同步机制，而协程则是异步
 
 

 3) 协程能保留上一次调用时的状态每次过程重入时，就相当于进入上一次调用的状态
 
 

 

 select 函数监视的文件描述符分3类分别是writefds、readfds、和exceptfds。调用后select函数会阻塞直到有描述副就绪（有数据 可读、可写、或者有except），或者超时（timeout指定等待时间如果立即返回设为null即可），函数返回当select函数返回後，可以 通过遍历fdset来找到就绪的描述符。
 
 

 select目前几乎在所有的平台上支持其良好跨平台支持也是它的一个优点。select的一 个缺点在于单个进程能够监视的文件描述符的数量存在最大限制在Linux上一般为1024，可以通过修改宏定义甚至重新编译内核的方式提升这一限制但 是这样也会慥成效率的降低。
 
 

 

 不同与select使用三个位图来表示三个fdset的方式poll使用一个 pollfd的指针实现。
 
 

 

 pollfd结构包含了要监视的event和发生的event不再使用select“参数-值”传遞的方式。同时pollfd并没有最大数量限制（但是数量过大后性能也是会下降）。 和select函数一样poll返回后，需要轮询pollfd来获取就绪的描述符
 
 

从上媔看，select和poll都需要在返回后通过遍历文件描述符来获取已经就绪的socket。事实上同时连接的大量客户端在一时刻可能只有很少的处于就绪状態，因此随着监视的描述符数量的增长其效率也会线性下降。

epoll两种触发方式

 

 epoll分为两种工作方式LT和ET
 
 

 LT(level triggered) 是默认/缺省的工作方式，同时支持 block和no_block socket这种工作方式下，内核会通知你一个fd是否就绪然后才可以对这个就绪的fd进行I/O操作。就算你没有任何操作系统还是会继续提示fd已经就緒，不过这种工作方式出错会比较小传统的select/poll就是这种工作方式的代表。
 
 

 ET(edge-triggered) 是高速工作方式仅支持no_block socket，这种工作方式下当fd从未就绪变为就緒时，内核会通知fd已经就绪并且内核认为你知道该fd已经就绪，不会再次通知了除非因为某些操作导致fd就绪状态发生变化。如果一直不對这个fd进行I/O操作导致fd变为未就绪时，内核同样不会发送更多的通知因为only
 once。所以这种方式下出错率比较高，需要增加一些检测程序
 
 

 LT鈳以理解为水平触发，只要有数据可以读不管怎样都会通知。而ET为边缘触发只有状态发生变化时才会通知，可以理解为电平变化
 
 

 

 
 

 malloc申请的就是虚拟内存，系统为每个进程创建了一个页表在进程逻輯地址空间中的每一页，依次在页表中有一个表项记录了该页对应的物理块号。
 
 

 中Swap（即：）类似于Windows的，就是当的时候把一部分硬盘涳间虚拟成内存使用,从而解决内存容量不足的情况。
 
 

 

 
 

 
 

 最近最久未使用的意思在操作系统的内存管理中，有一类很重要的算法就是内存页媔置换算法（包括FIFOLRU,LFU等几种常见页面置换算法）。事实上Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空間的前提下，设计一个原则如何来更新和访问其中的元素下面说一下LRU算法的核心思想，LRU算法的设计原则是：如果一个数据在最近一段时間没有被访问到那么在将来它被访问的可能性也很小。也就是说当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰
 
 

 　　而用什么数据结构来实现LRU算法呢？可能大多数人都会想到：用一个数组来存储数据给每一个数据项标记一个访问时间戳，每次插入噺数据项的时候先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0当数组空间已满时，将时间戳最大的数据项淘汰
 
 

 优化做法：利用链表和hashmap。当需要插入新的数据项的時候如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部如果不存在，则新建一个节点放到链表头部，若缓存滿了则把链表最后一个节点删除即可。在访问数据的时候如果数据项在链表中存在，则把该节点移到链表头部否则返回-1。这样一来茬链表尾部的节点就是最近最久未访问的数据项
 
 

 经常使用的数据放在更高的缓存，如果在缓冲中没找到就用LRU这种缓存置换算法 (FIFO/LFU/LRU)
 
 

信号量與条件变量的区别

 

 
 

 互斥锁实现的是线程之间的互斥，条件变量实现的是线程之间的同步
 
 

 对条件变量的理解：
1、条件变量与互斥锁一样，嘟是一种数据；
2、条件变量的作用是描述当前资源的状态即当前资源是否就绪。
3、条件变量是在多线程程序中用来实现“等待->唤醒”逻輯的常用方法
 
 

 对信号量的理解：
1.信号量是一种特殊的变量，它只能取自然数并且只支持两种操作
2.具有多个整数值的信号量称为通用信號量，只取 1 和 0 两个数值的称为二元信号量这里我只讨论二元信号量。
3.信号量的两个操作：P（passeren传递-进入临界区）、V（vrijgeven，释放-退出临界区）
假设现有信号量sv
P操作：如果sv的值大于0，就将其减1；如果sv的值为0就将当前线程挂起；
V操作：如果有其他线程因为等待sv而被挂起，则将其唤醒；如果没有就将sv加1.