1.C++语言的特点？（面向对象：封装、继承、多态）

2.虚函数表里存放的内容是什么时候写进去的？
在编译期写入
虚表指针->虚函数表(虚函数表里存放的是函数指针)

3.单例模式的构造函数？单例模式的创建过程？如何保证线程安全？
1）.使用静态成员变量，构造函数和普通构造函数一样
2）.构造函数私有，只有类内代码可以调用

4.C++中的智能指针？三种指针解决的问题以及区别？
share_ptr智能指针，利用引用计数和栈区对象释放调用析构函数的特性，创建的智能指针。为了解决内存泄漏问题。但是share_ptr不能很好的解决智能指针循环引用的问题，weak_ptr是为了解决这个问题而设计的。weak_ptr只能从share_ptr和weak_ptr中构造，引用时不增加引用计数，但是不能单独使用，需要调用lock，将weak_ptr转成share_ptr才能用。使用前需要判断对象是不是已经被释放了。
unique_ptr，不能共享指针，某个时刻只能有一个unique_ptr指向一个对象，当unique_ptr被销毁时，它指向的对象也将被释放。可以使用拷贝和赋值一个即将被销毁的unique_ptr，如函数返回一个unique_ptr
unique_ptr get_result()
{
unique_ptr up(new int(100));
return up;
}

5.new和malloc之间有什么区别？new申请内存空间的时候为什么不需要类型转化，底层做了些什么事情呢？
（new的作用:实例化一个对象。申请内存空间，然后调用相关的构造函数）
malloc只是申请内存空间，需要指定申请空间的大小，malloc是一个函数调用，内存申请失败会返回NULL
new是C++的关键字。new首先也要先申请内存空间，在申请内存空间后，后调用对象的构造函数，去初始化成员变量。内存申请识别会抛出异常。new 操作从自由存储区上分配内存（自由存储区不等于堆，布局new就可以不在堆中）。malloc从堆上分配内存。

6.C++内存分为哪几块？有什么作用？
栈区：由编译器自动分配释放，存放局部变量。操作和栈类似
堆区：由程序员分配释放
静态存储区：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域。未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束之后由系统释放。
文字常量区：常量字符串放在这,程序结束之后由系统释放。
程序代码区：存放函数体的二进制代码。
全局变量初始化在main函数之前，静态变量初始化在第一次函数调用这个静态局部变量之前。

7.C++中函数指针和指针函数的区别？
指针函数是返回指针的函数，函数指针是指向函数的指针。

8.C++编译的过程
先结果预编译，将include的头文件和宏的动展开；然后是编译，将预处理过的代码转成汇编代码；然后是汇编，将汇编代码转成二进制格式目标文件；最后是链接，将编译的二进制目标文件和动态库进行链接得到最终的可执行程序。

操作系统：
9.进程、线程、协程是什么？区别是什么？
进程是操作系统分配资源的最小单位，线程是操作系统调度的最小单位。
进程独享一块虚拟内存，访问更加安全，一个进程完全不会影响另外一个进程，但是进程间通信比线程间通信性能差很多。
线程共享进程中的大部分资源，线程切换开销更低。
协程相比于线程，更加轻量，线程间切换需要从用户态切换到内核态，进行系统调度，协程间是用户级的。

10.协程是轻量级的线程，轻量级表现在哪里？
协程是程序员自己控制的，进程线程有上下文切换，协程没有内核态的概念，是用户态的

17.从实用的角度来讲，三次握手的真实目的？（从硬件的角度来看，每一次握手的意义？）
客户端A给服务端B发送了一个请求，此时A并不知道自己的发送设备是好的还是坏的。如果B收到了，说明客户端A的发送端硬件设备是没有问题的，B接收端的硬件设备也是好的，于是进行第二次握手。A收到后知道B的发送端设备是好的，A的接收设备是没有问题的

18.网络的七层模型？每一层的协议？
1）OSI七层协议模型主要是：应用层（Application）、表示层（Presentation）、会话层（Session）、传输层（Transport）、网络层（Network）、数据链路层（Data Link）、物理层（Physical）。
2）五层体系结构包括：应用层、运输层、网络层、数据链路层和物理层。


四、各层的作用
1、物理层：比特
主要定义物理设备标准，如网线的接口类型、光纤的接口类型、各种传输介质的传输速率等。它的主要作用是传输比特流（就是由1、0转化为电流强弱来进行传输,到达目的地后在转化为1、0，也就是我们常说的数模转换与模数转换）。这一层的数据叫做比特。

2、数据链路层：帧
定义了如何让格式化数据以进行传输，以及如何让控制对物理介质的访问。这一层通常还提供错误检测和纠正，以确保数据的可靠传输。

3、网络层：数据报
在位于不同地理位置的网络中的两个主机系统之间提供连接和路径选择。Internet的发展使得从世界各站点访问信息的用户数大大增加，而网络层正是管理这种连接的层。

4、运输层：报文段/用户数据报
定义了一些传输数据的协议和端口号（WWW端口80等），如：
TCP（transmission control protocol –传输控制协议，传输效率低，可靠性强，用于传输可靠性要求高，数据量大的数据）
UDP（user datagram protocol–用户数据报协议，与TCP特性恰恰相反，用于传输可靠性要求不高，数据量小的数据，如QQ聊天数据就是通过这种方式传输的）。 主要是将从下层接收的数据进行分段和传输，到达目的地址后再进行重组。常常把这一层数据叫做段。

5、会话层：
通过运输层（端口号：传输端口与接收端口）建立数据传输的通路。主要在你的系统之间发起会话或者接受会话请求（设备之间需要互相认识可以是IP也可以是MAC或者是主机名）

6、表示层：
可确保一个系统的应用层所发送的信息可以被另一个系统的应用层读取。例如，PC程序与另一台计算机进行通信，其中一台计算机使用扩展二一十进制交换码（EBCDIC），而另一台则使用美国信息交换标准码（ASCII）来表示相同的字符。如有必要，表示层会通过使用一种通格式来实现多种数据格式之间的转换。

7.应用层：报文
1 第五层——应用层(application layer)
应用层(application layer)：是体系结构中的最高。直接为用户的应用进程（例如电子邮件、文件传输和终端仿真）提供服务。
在因特网中的应用层协议很多，如支持万维网应用的HTTP协议，支持电子邮件的SMTP协议，支持文件传送的FTP协议，DNS，POP3，SNMP，Telnet等等。
2. 第四层——运输层(transport layer)
运输层(transport layer)：负责向两个主机中进程之间的通信提供服务。由于一个主机可同时运行多个进程，因此运输层有复用和分用的功能
复用，就是多个应用层进程可同时使用下面运输层的服务。
分用，就是把收到的信息分别交付给上面应用层中相应的进程。
运输层主要使用以下两种协议：
(1) 传输控制协议TCP(Transmission Control Protocol)：面向连接的，数据传输的单位是报文段，能够提供可靠的交付。
(2) 用户数据包协议UDP(User Datagram Protocol)：无连接的，数据传输的单位是用户数据报，不保证提供可靠的交付，只能提供“尽最大努力交付”。
3. 第三层——网络层(network layer)
网络层(network layer)主要包括以下两个任务：
(1) 负责为分组交换网上的不同主机提供通信服务。在发送数据时，网络层把运输层产生的报文段或用户数据报封装成分组或包进行传送。在TCP/IP体系中，由于网络层使用IP协议，因此分组也叫做IP数据报，或简称为数据报。
(2) 选中合适的路由，使源主机运输层所传下来的分组，能够通过网络中的路由器找到目的主机。
协议：IP,ICMP,IGMP,ARP,RARP
4. 第二层——数据链路层(data link layer)
数据链路层(data link layer)：常简称为链路层，我们知道，两个主机之间的数据传输，总是在一段一段的链路上传送的，也就是说，在两个相邻结点之间传送数据是直接传送的(点对点)，这时就需要使用专门的链路层的协议。
在两个相邻结点之间传送数据时，数据链路层将网络层交下来的IP数据报组装成帧(framing)，在两个相邻结点之间的链路上“透明”地传送帧中的数据。
每一帧包括数据和必要的控制信息(如同步信息、地址信息、差错控制等)。典型的帧长是几百字节到一千多字节。
注：”透明”是一个很重要的术语。它表示，某一个实际存在的事物看起来却好像不存在一样。”在数据链路层透明传送数据”表示无力什么样的比特组合的数据都能够通过这个数据链路层。因此，对所传送的数据来说，这些数据就“看不见”数据链路层。或者说，数据链路层对这些数据来说是透明的。
(1)在接收数据时，控制信息使接收端能知道一个帧从哪个比特开始和到哪个比特结束。这样，数据链路层在收到一个帧后，就可从中提取出数据部分，上交给网络层。
(2)控制信息还使接收端能检测到所收到的帧中有无差错。如发现有差错，数据链路层就简单地丢弃这个出了差错的帧，以免继续传送下去白白浪费网络资源。如需改正错误，就由运输层的TCP协议来完成。
5. 第一层——物理层(physical layer)
物理层(physical layer)：在物理层上所传数据的单位是比特。物理层的任务就是透明地传送比特流。
6. 数据在各层之间的传递过程

19.http和https的区别？
1）HTTP和HTTPS的基本概念
HTTP：是互联网上应用最为广泛的一种网络协议，是一个客户端和服务器端请求和应答的标准（TCP），用于从WWW服务器传输超文本到本地浏览器的传输协议，它可以使浏览器更加高效，使网络传输减少。
　　HTTPS：是以安全为目标的HTTP通道，简单讲是HTTP的安全版，即HTTP下加入SSL层，HTTPS的安全基础是SSL，因此加密的详细内容就需要SSL。
　　HTTPS协议的主要作用可以分为两种：一种是建立一个信息安全通道，来保证数据传输的安全；另一种就是确认网站的真实性。
2）HTTP与HTTPS有什么区别？
　　HTTP协议传输的数据都是未加密的，也就是明文的，因此使用HTTP协议传输隐私信息非常不安全，为了保证这些隐私数据能加密传输，于是网景公司设计了SSL（Secure Sockets Layer）协议用于对HTTP协议传输的数据进行加密，从而就诞生了HTTPS。简单来说，HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，要比http协议安全。
　　HTTPS和HTTP的区别主要如下：
　　1、https协议需要到ca申请证书，一般免费证书较少，因而需要一定费用。
　　2、http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl加密传输协议。
　　3、http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。
　　4、http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。
3）HTTPS的工作原理
　　我们都知道HTTPS能够加密信息，以免敏感信息被第三方获取，所以很多银行网站或电子邮箱等等安全级别较高的服务都会采用HTTPS协议。
HTTP与HTTPS的区别
　客户端在使用HTTPS方式与Web服务器通信时有以下几个步骤，如图所示。
　　（1）客户使用https的URL访问Web服务器，要求与Web服务器建立SSL连接。
　　（2）Web服务器收到客户端请求后，会将网站的证书信息（证书中包含公钥）传送一份给客户端。
　　（3）客户端的浏览器与Web服务器开始协商SSL连接的安全等级，也就是信息加密的等级。
　　（4）客户端的浏览器根据双方同意的安全等级，建立会话密钥，然后利用网站的公钥将会话密钥加密，并传送给网站。
　　（5）Web服务器利用自己的私钥解密出会话密钥。
　　（6）Web服务器利用会话密钥加密与客户端之间的通信。

20.tcp是面向字节流的，出数据可靠的，也有时序性的问题；UDP是面向高通量，不一定要求对方收到信息是准确的这样一个场景。电话沟通是用什么协议？（TCP）什么情况下用TCP协议呢？（邮件的发送协议）

算法：
21.如何判断一个链表有没有环？

22.B树和B+树的特点以及应用场景？
B 树：
B 树就是常说的“B 减树（B- 树）”，又名平衡多路（即不止两个子树）查找树，它和平衡二叉树的不同有这么几点：
1）平衡二叉树节点最多有两个子树，而 B 树每个节点可以有多个子树，M 阶 B 树表示该树每个节点最多有 M 个子树
2）平衡二叉树每个节点只有一个数据和两个指向孩子的指针，而 B 树每个中间节点有 k-1 个关键字（可以理解为数据）和 k 个子树（ **k 介于阶数 M 和 M/2 之间，M/2 向上取整）
3）B 树的所有叶子节点都在同一层，并且叶子节点只有关键字，指向孩子的指针为 null
和平衡二叉树相同的点在于：B 树的节点数据大小也是按照左小右大，子树与节点的大小比较决定了子树指针所处位置。
对比平衡二叉树和 B 树

B 树中的每个节点由两部分组成：
1）关键字（可以理解为数据）
2）指向孩子节点的指针
一棵 B 树必须满足以下条件：
1）若根结点不是终端结点，则至少有2棵子树
2）除根节点以外的所有非叶结点至少有 M/2 棵子树，至多有 M 个子树（关键字数为子树减一）
所有的叶子结点都位于同一层

可以看到，B 树的每个节点可以表示的信息更多，因此整个树更加“矮胖”，这在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘 IO 的次数，从而提升查找速度。

B 树中如何查找数据
因为 B 树的子树大小排序规则，因此在 B 树中查找数据时，一般需要这样：
1）从根节点开始，如果查找的数据比根节点小，就去左子树找，否则去右子树
2）和子树的多个关键字进行比较，找到它所处的范围，然后去范围对应的子树中继续查找
3）以此循环，直到找到或者到叶子节点还没找到为止

B 树如何保证平衡
我们知道，平衡的树之所以能够加快查找速度，是因为在添加、删除的时候做了某些操作以保证平衡。
平衡二叉树的平衡条件是：左右子树的高度差不大于 1；而 B 树的平衡条件则有三点：
1）叶子节点都在同一层
2）每个节点的关键字数为子树个数减一（子树个数 k 介于树的阶 M 和它的二分之一
3）子树的关键字保证左小右大的顺序
也就是说，一棵 3 阶的 B 树（即节点最多有三个子树），每个节点的关键字数最少为 1，最多为 2，如果要添加数据的子树的关键字数已经是最多，就需要拆分节点，调整树的结构。

B树使用场景：
Windows：HPFS 文件系统
Mac：HFS，HFS+ 文件系统
Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统
数据库：ORACLE，MYSQL，SQLSERVER 等中
数据库：ORACLE，MYSQL，SQLSERVER 等中

B+ 树
B+ 树，它比 B 树的查询性能更高。
一棵 B+ 树需要满足以下条件：

1）节点的子树数和关键字数相同（B 树是关键字数比子树数少一）
2）节点的关键字表示的是子树中的最大数，在子树中同样含有这个数据
3）叶子节点包含了全部数据，同时符合左小右大的顺序

简单概括下 B+ 树的三个特点：
1）关键字数和子树相同
2）非叶子节点仅用作索引，它的关键字和子节点有重复元素
3）叶子节点用指针连在一起

第一：
在 B 树中，节点的关键字用于在查询时确定查询区间，因此关键字数比子树数少一；
而在 B+ 树中，节点的关键字代表子树的最大值，因此关键字数等于子树数。
第二：
除叶子节点外的所有节点的关键字，都在它的下一级子树中同样存在，最后所有数据都存储在叶子节点中。
根节点的最大关键字其实就表示整个 B+ 树的最大元素。
第三：
叶子节点包含了全部的数据，并且按顺序排列，B+ 树使用一个链表将它们排列起来，这样在查询时效率更快。

B+ 树的三个优点：
1）层级更低，IO 次数更少
2）每次都需要查询到叶子节点，查询性能稳定
3）叶子节点形成有序链表，范围查询方便

23.希尔排序算法思想？
希尔排序原理：
希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
**增量d 的范围： **1<= d < 待排序数组的长度 （d 需为 int 值）
**增量的取值： **一般的初次取序列（数组）的一半为增量，以后每次减半，直到增量为1。
第一个增量=数组的长度/2,
第二个增量= 第一个增量/2,
第三个增量=第二个增量/2,
以此类推，最后一个增量=1。

时间复杂度：（n指待排序序列长度）

1. 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
2. 最坏情况：O(nlog2n)。
3. 渐进时间复杂度（平均时间复杂度）：O(nlog2n)

24.hashmap实现的思路和方法(类似于STL中的unordered_map)
哈希及unordered_map与unordered_set的底层实现
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或称散列表)
常见哈希函数
1） 直接定址法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先 知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
面试题：1. 字符串中第一个只出现一次字符；2. 公司员工年龄排序
2）除留余数法–(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函 数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3） 平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。
使用场景：不知道关键字的分布，而位数又不是很大的情况
4）折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加 求和，并按散列表表长，取后几位作为散列地址。
使用场景：适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
5） 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为 随机数函数。
使用场景：通常应用于关键字长度不等时采用此法
6）数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
使用场景：数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

25.哈希冲突如何解决？
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是哈希冲突无法避免
解决哈希冲突两种常见的方法是：闭散列和开散列
1）闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去。
线性探测：
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入:
1.1） 通过哈希函数获取待插入元素在哈希表中的位置
1.2） 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
线性探测优点
实现简单，易于理解
线性探测缺点
一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

2）二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i^2) % m,或者Hi = (H0-i ^ 2)%m.其中：i = 1,2,3…，是通过散列函数Hash(x)对元素的关键码key进行计算得到的位置，m是表的大小。 对于2.1中如果要插入44，产生冲突，使用解决后的情况为：

因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

3）开散列
开散列法又叫链地址法(拉链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

4）开散列增容
桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容。开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

场景：
26.硬盘上有10G的数据，可能会有重复，如何找出有多少个数据是重复的？
用bitmap(用于对大量整型数据去重和查询操作)，一个位代表一个数据，一个一个的读数据，如果该位已经有数据了，说明当前是重复的数据，count+1就可以