0、数据结构 & C++ & Go & Java
2021-03-12 16:26:26 0 举报AI智能生成
计算机基础知识
作者其他创作
大纲/内容
数据结构
动态数组
扩容缩容：2倍扩容
均摊复杂度
复杂度震荡：缩容时
链表
使用虚拟头结点统一代码逻辑
双向链表
循环链表
栈 & 队列 & 循环队列
循环队列（head、tail 两个指针，扩容时从 head 到 tail 进行拷贝）
树
二叉树
二分搜索树
删除结点
只有左/右孩子：把左孩子的左孩子接到当前结点
左右孩子都有：选右孩子的最小值进行替换待删除结点
AVL 树（平衡的二叉树）
适合查找多于插入删除的操作
LL：右旋（LL意思是不平衡发生在当前结点的左侧的左侧）
RR：左旋
LR：左旋（对当前结点的左孩子进行左旋转） + 右旋（对当前结点进行右旋转）
RL：右旋 + 左旋
红黑树（黑平衡、左倾）
适合插入、删除多于查找的操作（因为旋转次数少，但是树的高度较高）
原理：与 2-3 树是等价的（2-3树是直接插入到叶子结点，如果变成4结点则拆分并将拆分完后的父亲结点向上合并）
因为2-3树是绝对平衡的，所以可以将3结点的左侧结点当成红的，右结点当成黑的，从而形成左倾的红黑树
因为2-3树是绝对平衡的，所以可以将3结点的左侧结点当成红的，右结点当成黑的，从而形成左倾的红黑树
左旋、右旋、颜色翻转
添加新元素
B 系列树
参考链接
关于MySQL索引背后的数据结构及算法原理，这里还有一篇很好的文章
关于B 树、B+ 树、B* 树及R 树，本blog内有篇绝佳文章
B 树
B 树是泛化版本的 2-3 树，可以支持 [L, R] 树，最少 L 结点最大 R 结点，插入时同样有分裂、合并、转移操作
1）利用磁盘预读的局部性原理：一般索引比较大，需要放在硬盘上，所以性能指标主要是磁盘 IO 次数，
所以一般数据库索引中，每创建一个结点申请一页大小的空间即 4K，计算机存储是按页对齐的，这样一个结点一次 IO
故B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)
上面出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3），B+Tree更适合外存索引，原因就和内节点出度d有关。
从上面分析可以看到，d越大索引的性能越好，而出度d的上限取决于节点内key和data的大小：
所以一般数据库索引中，每创建一个结点申请一页大小的空间即 4K，计算机存储是按页对齐的，这样一个结点一次 IO
故B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)
上面出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3），B+Tree更适合外存索引，原因就和内节点出度d有关。
从上面分析可以看到，d越大索引的性能越好，而出度d的上限取决于节点内key和data的大小：
2）插入(2-3-4树)
插入到一个 4 结点
先插入成 5 结点，然后将中间结点合并到父结点上，左右两边分裂成两个；
如果父结点也满了，则将父结点再次分裂
如果父结点也满了，则将父结点再次分裂
3）删除(2-3-4树)
从 2 结点删除一个
从孩子中找到最 "丰满" 的孩子，找到最接近父结点的一个结点（比如该孩子位于最右侧，则将孩子中最小的结点上移）
如果父亲结点不能分裂，但相邻结点有比较 "丰满" 的：则先从父结点借一个，父结点此时不够了则从那么丰满孩子中借一个
如果父结点和相邻结点都不能分裂：则先删除结点后从父结点借一个，然后和相邻孩子进行合并，合并完之后比较 "丰满"，
父结点不够了，则父结点和他的相邻结点进行合并
父结点不够了，则父结点和他的相邻结点进行合并
B+ 树
vs B 树
内结点不存储数据信息，只存索引，所以一个内结点可以存储更多关键字信息，树的高度也更低
叶子结点有指向相邻叶子结点的指针（顺序访问指针），这样进行区间遍历效率更高
实现上
B树：有序数组+平衡多叉树
B+树：有序数组链表+平衡多叉树
MySQL 索引
MyISAM
非聚集索引：叶子结点 data 域存储的是指向数据的指针
InnoDB
聚集索引：叶子结点 data 域存储的就是真正的数据（数据文件本身就是索引文件）
主键选择：用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，
非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，
故如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。
非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，
故如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。
优先队列
(最大堆)
(最大堆)
构建堆：层层 sift up（heapify）
取出最大元素：新的堆顶元素 sift down 直到合适位置
线段树
经典问题：墙壁区间染色、基于区间的统计查询（今年消费 top10 的用户等）
实现：所有非叶子节点保存的是区间信息（区间为该结点所涵盖的所有孩子结点）
优化：懒惰更新（先不更新叶子结点，只是在父亲、祖父结点进行标记）
字典树
Trie
Trie
优势：空间换时间，查找一个字符串的时间复杂度只是这个被查找字符串的长度
空间优化：路径压缩（将叶子结点和父亲、祖父结点合并成一个字符串结点，前提是在这段被压缩的路径中应不包含其他单词）
并查集
特点：由孩子指向父亲（主要用于处理连接问题，查看两个节点是否连接）
实现：可用数组实现，也可用树实现
优化
基于 size 优化：让结点树少的指向多的
基于 rank 优化：让树低的指向高的（降低树的高度）
路径压缩：在 find 时：parent[p] = parent[parent[p]]，使得结点指向最顶上祖先结点而非父亲结点，从而降低树的高度
集合 (Set)
映射 (Map)
映射 (Map)
有序：红黑树
无序：哈希表
哈希函数的设计
大整数：对一个素数取模
字符串：code = (c * 26^3 + o * 26^2 + d * 26^1 + e) % 素数
复合类型：对每一个字段值进行上述方法取模，然后再对最终结果进行素数取模
哈希碰撞的解决
开放地址法：往后找空位插进去
链地址法：Java 中是相同的哈希值用链表进行串联，链表长度较大时转换为红黑树
再次哈希法
海量数据处理
参考链接：教你如何迅速秒杀掉：99%的海量数据处理面试题
1. 分治/Hash映射 + Hashmap统计
+ 堆排序 + 归并排序
+ 堆排序 + 归并排序
思想
1）分治：将很大原文件中每个元素按照 % 1000 分成 1000 个小文件
2）使用 hashmap 对每个小文件中进行统计（频率统计等）
3）对每个小文件的统计结果进行堆排序（选出题目要求的结果数量）
4）对每个小文件中堆排序结果进行归并排序（得出最终的结果数量）
题目
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
2、寻找热门查询，300万个查询字符串中统计最热门的10个查询
3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
4、海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10
5、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
6、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
7、怎么在海量数据中找出重复次数最多的一个？
8、上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。
9、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
11. 一个文本文件，找出前10个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解。
12. 100w个数中找出最大的100个数。
2. Bitmap / Bloom filter
Bitmap
代码示例
初始化
int num[] = {3,5,2,10,6,12,8,14,9};
char *p = new char[2]; // 待排序中的最大值是14，因此只需要2个Bytes(16个Bit)就可以了。
memset(pBuffer, 0, 2); // 要将所有的Bit位置为0，否则结果不可预知
将值为 i 对应的 bit 位置 1 => *p = *p | (0x01 << (i % BYTESIZE));
#define BYTESIZE 8（一个字节有 8 个 bit 位）
输出排序结果
for(int i=0; i＜2; i++) // 每次处理一个字节(Byte)
for(int j=0; j＜8; j++) { // 处理该字节中的每个Bit位
// 判断该位上是否是1，进行输出，这里的判断比较笨。
// 首先得到该第j位的掩码（0x01<＜j），将内存区中的位和此掩码作与操作。
// 最后判断掩码是否和处理后的结果相同
if((*pBuffer&(0x01<<j)) == (0x01<<j))
printf("%d ", i*BYTESIZE + j);
pBuffer++;
}
for(int j=0; j＜8; j++) { // 处理该字节中的每个Bit位
// 判断该位上是否是1，进行输出，这里的判断比较笨。
// 首先得到该第j位的掩码（0x01<＜j），将内存区中的位和此掩码作与操作。
// 最后判断掩码是否和处理后的结果相同
if((*pBuffer&(0x01<<j)) == (0x01<<j))
printf("%d ", i*BYTESIZE + j);
pBuffer++;
}
例题
1) 已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
答：8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。(可以理解为从0-99 999 999的数字，
每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）
答：8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。(可以理解为从0-99 999 999的数字，
每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）
2) 2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
答：将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，
如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，
我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。
答：将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上，在遍历这些数的时候，
如果对应位置的值是0，则将其置为1；如果是1，将其置为2；如果是2，则保持不变。或者我们不用2bit来进行表示，
我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。
3) 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
方案1：用Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，
读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
方案1：用Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，
读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
Bloom filter
原理
长度为m的bit数组 + k个独立hash函数。将hash函数对应的值的bit数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。
优化：上述不支持删除 (因为该关键字对应的位会牵动到其他的关键字) => counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了
例题
1）给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？
答：4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些；
可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。
答：4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些；
可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。
2）判断一个元素在亿级数据中是否重复
3. 多层划分
因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。
例题：5亿个int找它们的中位数
思路一：这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。
实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。
思路二：同样需要做两遍统计，如果数据存在硬盘上，就需要读取2次。
方法同基数排序有些像，开一个大小为65536的Int数组，第一遍读取，统计Int32的高16位的情况，也就是0-65535，都算作0,65536 - 131071都算作1。就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况，因此开一个长度为65536的数组计数就可以。每读取一个数，数组中对应的计数+1，考虑有负数的情况，需要将结果加32768后，记录在相应的数组内。
第一遍统计之后，遍历数组，逐个累加统计，看中位数处于哪个区间，比如处于区间k，那么0- k-1的区间里数字的数量sum应该<n/2（2.5亿）。而k+1 - 65535的计数和也<n/2，第二遍统计同上面的方法类似，但这次只统计处于区间k的情况，也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。并且利用刚才统计的sum，比如sum = 2.49亿，那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果了。
方法同基数排序有些像，开一个大小为65536的Int数组，第一遍读取，统计Int32的高16位的情况，也就是0-65535，都算作0,65536 - 131071都算作1。就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况，因此开一个长度为65536的数组计数就可以。每读取一个数，数组中对应的计数+1，考虑有负数的情况，需要将结果加32768后，记录在相应的数组内。
第一遍统计之后，遍历数组，逐个累加统计，看中位数处于哪个区间，比如处于区间k，那么0- k-1的区间里数字的数量sum应该<n/2（2.5亿）。而k+1 - 65535的计数和也<n/2，第二遍统计同上面的方法类似，但这次只统计处于区间k的情况，也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。并且利用刚才统计的sum，比如sum = 2.49亿，那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果了。
4. Trie树/数据库索引/倒排索引
Trie树
适用范围：数据量大，重复多，但是数据种类小可以放入内存
数据库索引
适用范围：大数据量的增删改查；基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。
关于MySQL索引背后的数据结构及算法原理，这里还有一篇很好的文章
关于B 树、B+ 树、B* 树及R 树，本blog内有篇绝佳文章
5. 外排序
外排序的归并方法，置换选择败者树原理，最优归并树
6. 分布式处理之Mapreduce
简单的说就是将大批量的工作（数据）分解（map）执行，然后再将结果合并成最终结果（reduce）。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序。
C++
关键字
static
全局静态变量
内存中的位置：静态存储区，在整个程序运行期间一直存在。
全局静态变量在声明他的文件之外是不可见的，准确地说是从定义之处开始，到文件结尾。
局部静态变量
内存中的位置：静态存储区。
作用域仍为局部作用域，当定义它的函数或者语句块结束的时候，作用域结束。
但是当局部静态变量离开作用域后，并没有销毁，而是仍然驻留在内存当中，只不过我们不能再对它进行访问，直到该函数再次被调用，并且值不变；
static定义的静态局部变量分配在数据段上，普通的局部变量分配在栈上，会因为函数栈帧的释放而被释放掉。
但是当局部静态变量离开作用域后，并没有销毁，而是仍然驻留在内存当中，只不过我们不能再对它进行访问，直到该函数再次被调用，并且值不变；
static定义的静态局部变量分配在数据段上，普通的局部变量分配在栈上，会因为函数栈帧的释放而被释放掉。
静态函数
函数的实现使用 static 修饰，那么这个函数只可在本 cpp 内使用（不能在其他源文件中被引用），不会同其他 cpp 中的同名函数引起冲突；
类的静态成员变量/成员函数
静态成员是类的所有对象中共享的成员，而不是某个对象的成员。对多个对象来说，静态数据成员只存储一处，供所有对象共用。
cast 转换
const_cast
用于将 const 变量转为非 const
static_cast
用于各种隐式转换，比如非 const 转 const，void* 转指针等,
static_cast 能用于多态向上转化，如果向下转能成功但是不安全，结果未知；
static_cast 能用于多态向上转化，如果向下转能成功但是不安全，结果未知；
dynamic_cast
用于动态类型转换。只能用于含有虚函数的类，用于类层次间的向上和向下转化。只能转指针或引用。
向下转化时，如果是非法的对于指针返回NULL，对于引用抛异常。
向下转化时，如果是非法的对于指针返回NULL，对于引用抛异常。
reinterpret_cast
几乎什么都可以转，比如将int转指针，可能会出问题，尽量少用
智能指针
auto_ptr
C++ 98中的，C++11 已废弃
采用所有权模式
auto_ptr< string> p1 (new string ("I reigned lonely as a cloud.”));
auto_ptr p2;
p2 = p1; //auto_ptr不会报错.
此时不会报错，p2剥夺了p1的所有权，但是当程序运行时访问p1将会报错。
所以 auto_ptr 的缺点是：存在潜在的内存崩溃问题！
auto_ptr
p2 = p1; //auto_ptr不会报错.
此时不会报错，p2剥夺了p1的所有权，但是当程序运行时访问p1将会报错。
所以 auto_ptr 的缺点是：存在潜在的内存崩溃问题！
unique_ptr
C++ 11 中使用这个替换了 auto_ptr
还是采用所有权模式，unique_ptr实现独占式拥有或严格拥有概念，保证同一时间内只有一个智能指针可以指向该对象。
还是上面的例子，p1 赋值给 p2 时会报错，编译器认为这种行为非法，这样就避免了 p1 不再指向有效数据的问题。
还是上面的例子，p1 赋值给 p2 时会报错，编译器认为这种行为非法，这样就避免了 p1 不再指向有效数据的问题。
当程序试图将一个 unique_ptr 赋值给另一个时，如果源 unique_ptr 是个临时右值，编译器允许这么做；
如果源 unique_ptr 将存在一段时间，编译器将禁止这么做
如果源 unique_ptr 将存在一段时间，编译器将禁止这么做
优点：它对于避免资源泄露 (例如：以 new 创建对象后因为发生异常而忘记调用 delete) 特别有用。
实现原理：在类中把拷贝构造函数和拷贝赋值声明为 private，这样就不可以对指针指向进行拷贝了，也就不能产生指向同一个对象的指针。
shared_ptr
增加引用计数
weak_ptr
如果两个智能指针相互引用，会造成内存泄露，两个都释放不掉，weak_ptr 可以解决该问题，因为 weak_ptr 不增加引用计数
指针 vs 引用
1. 指针有自己的一块空间，而引用只是一个别名；
2. 使用 sizeof 看一个指针的大小是 4，而引用则是被引用对象的大小；
3. 指针可以被初始化为NULL，而引用必须被初始化且必须是一个已有对象 的引用；
4. 作为参数传递时，指针需要被解引用才可以对对象进行操作，而直接对引 用的修改都会改变引用所指向的对象；
5. 可以有 const 指针，但是没有 const 引用（即：你既然引用了就是要修改的）；
6. 指针在使用中可以指向其它对象，但是引用只能是一个对象的引用，不能 被改变；
7. 指针可以有多级指针（**p），而引用只有一级；
8. 指针和引用使用 ++ 运算符的意义不一样（指针使用 ++ 是地址向后移动一个内存单位，引用调用 ++ 则是将被引用对象的值加一）；
9. 如果返回动态内存分配的对象或者内存，必须使用指针，引用可能引起内存泄露。
2. 使用 sizeof 看一个指针的大小是 4，而引用则是被引用对象的大小；
3. 指针可以被初始化为NULL，而引用必须被初始化且必须是一个已有对象 的引用；
4. 作为参数传递时，指针需要被解引用才可以对对象进行操作，而直接对引 用的修改都会改变引用所指向的对象；
5. 可以有 const 指针，但是没有 const 引用（即：你既然引用了就是要修改的）；
6. 指针在使用中可以指向其它对象，但是引用只能是一个对象的引用，不能 被改变；
7. 指针可以有多级指针（**p），而引用只有一级；
8. 指针和引用使用 ++ 运算符的意义不一样（指针使用 ++ 是地址向后移动一个内存单位，引用调用 ++ 则是将被引用对象的值加一）；
9. 如果返回动态内存分配的对象或者内存，必须使用指针，引用可能引起内存泄露。
多态
静态多态
函数重载，这是编译期间就确定的
动态多态
虚函数
一个父类类型的指针指向一个子类对象时，使用父类的指针去调用子类中重写了的父类中的虚函数的时候，会调用子类重写过后的函数；
在父类中声明为加了 virtual 关键字的函数，在子类中重写时不需要加 virtual 也是虚函数。
在父类中声明为加了 virtual 关键字的函数，在子类中重写时不需要加 virtual 也是虚函数。
虚函数实现：在有虚函数的类中，类的最开始部分是一个虚函数表的指针，这个指针指向一个虚函数表，表中放了虚函数的地址，实际的虚函数在 .text 段中
注意：虚函数表是属于类的，而不是某个对象的
注意：虚函数表是属于类的，而不是某个对象的
当子类继承了父类的时候也会继承其虚函数表，当子类重写父类中虚函数时候，会将其继承到的虚函数表中的地址替换为重新写的函数地址。
为什么析构函数必须是虚函数
将可能会被继承的父类的析构函数设置为虚函数，可以保证当我们 new 一个子类，然后使用基类指针指向该子类对象，
释放基类指针时可以释放掉子类的空间，防止内存泄漏。
释放基类指针时可以释放掉子类的空间，防止内存泄漏。
此时析构顺序：1）派生类本身的析构函数；2）对象成员析构函数；3）基类析构函数。
为什么默认析构函数不是虚函数
因为虚函数需要额外的虚函数表和虚表指针，占用额外的内存。而对于不会被继承的类来说，其析构函数如果是虚函数，就会浪费内存。
因此 C++ 默认的析构函数不是虚函数，而是只有当需要当作父类时，设置为虚函数。
因此 C++ 默认的析构函数不是虚函数，而是只有当需要当作父类时，设置为虚函数。
malloc vs new
malloc/free是标准库函数，new/delete是C++运算符
分配内存的位置
new 是在自由存储区（自由存储区不仅可以为堆，还可以是静态存储区），malloc 是在堆上
分配内存的大小
new 由编译器根据类型计算得出，malloc 必须显式指定字节数
返回类型安全性
new 返回完整类型指针，malloc 返回 void* 需进行强制转换 reinterpret_cast
分配失败返回值
new 默认抛出异常，malloc 返回 NULL
处理数组
new 有处理数组的 new[]，malloc 需要用户计算数组的大小后进行内存分配
内存扩充
new 无法直观地处理，malloc 可使用 realloc 简单完成
构造&析构
new 会调用，malloc 不调用
是否可以重载
new 是一个操作符可以重载，malloc 是一个库函数
C 语言函数调用
1. 分配函数栈帧；
2. 压栈：函数返回地址 -> 参数从右到左入栈 -> 函数内局部变量 -> 返回值
拷贝构造函数能否参数值传递
不能。调用拷贝构造函数的时候，首先要将实参传递给形参，这个传递的时候又要调用拷贝构造函数。。如此循环，无法完成拷贝，栈也会溢出。
所以拷贝改造函数的参数必须为引用。
所以拷贝改造函数的参数必须为引用。
malloc 原理
1. malloc 其采用内存池的方式，先申请大块内存作为堆区，然后将堆区分为多个内存块，以块作为内存管理的基本单位。
2. 当用户申请内存时，直接从堆区分配一块合适的空闲块。malloc 采用隐式链表结构将堆区分成连续的、大小不一的块，包含已分配块和未分配块；
同时 malloc 使用一个双向链表将空闲块连接起来，每一个空闲块记录了一个连续的、未分配的地址。
同时 malloc 使用一个双向链表将空闲块连接起来，每一个空闲块记录了一个连续的、未分配的地址。
3. 当申请内存 < 128K 时，调用 brk() 在堆区分配；当大于 128K 时，调用 mmap() 在映射区分配
STL 内存优化
大于 128 字节
一级配置器：以 malloc()、free()、realloc() 等 C 函数执行实际的内存配置、释放、重新配置
小于 128 字节
二级配置器（内存池）
16 个空闲链表，分别管理大小为 8、16、24......120、128 的数据块
1. 将字节数扩展到 8 的倍数，然后在自由链表中查找对应大小的子链表；如果找到直接返回；
如果在自由链表查找不到或者块数不够，则向内存池进行申请，一般一次申请 20 块
如果在自由链表查找不到或者块数不够，则向内存池进行申请，一般一次申请 20 块
2. 如果内存池空间足够，则取出内存；如果不够分配 20 块，则分配最多的块数给自由链表，并且更新每次申请的块数；
如果一块都无法提供，则把剩余的内存挂到自由链表，然后向系统 heap 申请空间，如果申请失败，则看看自由链表还有没有可用的块,
如果也没有，则最后调用一级空间配置器。
如果一块都无法提供，则把剩余的内存挂到自由链表，然后向系统 heap 申请空间，如果申请失败，则看看自由链表还有没有可用的块,
如果也没有，则最后调用一级空间配置器。
内存布局
静态区域
代码段（text）：包括只读存储区和文本区，其中只读存储区存储字符串常量，文本区存储程序的机器代码
数据段（data）：已初始化的全局变量和静态变量
bss 段：存储未初始化的全局变量和静态变量（局部+全局），以及所有被初始化为 0 的全局变量和静态变量
动态区域
堆区：调用 new/malloc 函数时在堆区动态分配内存，同时需要调用 delete/free 来手动释放申请的内存（小于 128K）
映射区：动态链接库 + 调用 mmap() 进行的文件映射（申请大内存）
栈区：每个函数一个栈帧，存放函数返回地址、参数、局部变量、返回值
内存泄漏
1. 堆内存泄漏：忘记 free/delete
2. 系统资源泄漏：文件句柄没关
3. 没有将析构函数定义为虚函数
发生段错误
1. 使用野指针
未初始化的指针
指针指向的对象释放后没有置空又重新解引用
指向非法内存区域：指向栈内的局部变量
2. 试图修改常量字符串内容
C++ 11
关键字与新语法
auto
auto 并没有让 C++ 成为弱类型语言，只是使用 auto 的时候，编译器根据上下文情况，确定 auto 变量的真正类型。
auto 不能做什么：auto作为函数返回值时，只能用于定义函数，不能用于声明函数。
nullptr
NULL 的毛病：NULL在c++里表示空指针，我们调用 test.TestWork(NULL)，其实期望是调用的是 void TestWork(int * index)，
但结果调用了 void TestWork (int index)。但使用 nullptr 的时候，我们能调用到正确的函数。
但结果调用了 void TestWork (int index)。但使用 nullptr 的时候，我们能调用到正确的函数。
for 循环
类似 Java 中的 foreach，即：可以支持 for(auto str : strs) { ... }
STL 容器
std::array
std::array 相对于数组，增加了迭代器等函数
std::forward_list
std::forward_list 为新增的线性表，与 list 区别在于它是单向链表。
std::unordered_map
std::unordered_set
多线程
std::atomic
原子数据类型不会发生数据竞争，能直接用在多线程中而不必用户对其进行添加互斥资源锁的类型。
std::thread
std::condition_variable
智能指针
auto_ptr（C++98 的方案，已弃用）
unique_ptr
shared_ptr
weak_ptr
右值引用
目的
消除两个对象交互时不必要的对象拷贝，节省运算存储资源，提高效率；
能够更简洁明确地定义泛型函数。
概念
1. 左值：能对表达式取地址、或具名对象/变量。一般指表达式结束后依然存在的持久对象。
2. 右值：不能对表达式取地址，或匿名对象。一般指表达式结束就不再存在的临时对象。
区别
1. 左值可以寻址，而右值不可以；
2. 左值可以被赋值，右值不可以被赋值，可以用来给左值赋值；
3. 左值可变，右值不可变（仅对基础类型适用，用户自定义类型右值引用可以通过成员函数改变）。
其他
std::function & std::bind
lamda 表达式
[]：中括号用于控制 main 函数与 lamda 表达式之前的变量在 lamda 表达式中的访问形式；（闭包）
(int a,int b)：为函数的形参
->int：lamda 表达式函数的返回值定义
{}：大括号内为lamda表达式的函数体。
其他面试题
C++ 是不是类型安全的？
不是。两个不同类型的指针之间可以强制转换（用 reinterpret cast )。C# 是类型安全的。
main 函数之前执行的代码
全局对象的构造函数会在 main 函数之前执行
一个 class 的 sizeof
sizeof(object) = 对象成员的 size + 虚函数表个数 * 4
虚函数表的个数
该类是父类，则虚函数表个数为 1
该类继承于一个父类，则虚函数表个数为 1
该类继承于两个父类，则虚函数表个数为 2
C
链接
C语言深度总结与拓展 —— 关键词篇
参考的是 《C 语言深度解剖》
C 语言再学习系列
C 语言 32 个关键字总结
volatile 关键字
变量如果加了 volatile 修饰，则会从内存重新装载内容，而不是直接从寄存器拷贝内容
（因为 GCC 编译器会做优化，将内存变量缓存到寄存器；调整指令顺序充分利用CPU指令流水线，常见的是重新排序读写指令）。
（因为 GCC 编译器会做优化，将内存变量缓存到寄存器；调整指令顺序充分利用CPU指令流水线，常见的是重新排序读写指令）。
作用：volatile 的作用是作为指令关键字，确保本条指令不会因编译器的优化而省略，且要求每次直接读值。volatile 可以保证对特殊地址的稳定访问。
面试题
1. 一个参数既可以是 const 还可以是 volatile 吗？
可以，例如只读的状态寄存器。它是 volatile 因为它可能被意想不到地改变。它是 const 因为程序不应该试图去修改它。
可以，例如只读的状态寄存器。它是 volatile 因为它可能被意想不到地改变。它是 const 因为程序不应该试图去修改它。
2. 一个指针可以是 volatile 吗？
可以，当一个中服务子程序修改一个指向一个 buffer 的指针时。
可以，当一个中服务子程序修改一个指向一个 buffer 的指针时。
register 关键字
与 volatile 关键字相对，register 关键字暗示编译程序相应的变量将被频繁地使用，如果可能的话，应将其保存在 CPU 的寄存器中，以加快其存储速度。
限制
1. register变量必须是能被CPU所接受的类型。这通常意味着register变量必须是一个单个的值，并且长度应该小于或者等于整型的长度
2. 因为register变量可能不存放在内存中，所以不能用“&”来获取register变量的地址。
3. 只有局部自动变量和形式参数可以作为寄存器变量，其它（如全局变量）不行。
在调用一个函数时占用一些寄存器以存放寄存器变量的值，函数调用结束后释放寄存器。
此后，在调用另外一个函数时又可以利用这些寄存器来存放该函数的寄存器变量。
在调用一个函数时占用一些寄存器以存放寄存器变量的值，函数调用结束后释放寄存器。
此后，在调用另外一个函数时又可以利用这些寄存器来存放该函数的寄存器变量。
4. 局部静态变量不能定义为寄存器变量。不能写成：register static int a, b, c;
GCC 扩展关键字
__builtin_expect
流水线优化：将流水线引入cpu，让cpu可以预先取出下一条指令，提高cpu的效率。但是如果遇到跳转语句，提前取出的指令就没用了。
__thread
释义
__thread 是 GCC 内置的线程局部存储设施，存取效率可以和全局变量相比。__thread 变量每一个线程有一份独立实体，各个线程的值互不干扰。
可以用来修饰那些带有全局性且值可能变，但是又不值得用全局变量保护的变量。
可以用来修饰那些带有全局性且值可能变，但是又不值得用全局变量保护的变量。
使用规则
只能修饰 POD 类型 (类似整型指针的标量，不带自定义的构造、拷贝、赋值、析构的类型，二进制内容可以任意复制memset, memcpy, 且内容可以复原)，不能修饰 class 类型，因为无法自动调用构造函数和析构函数
可以用于修饰全局变量，函数内的静态变量，不能修饰函数的局部变量或者class的普通成员变量，且__thread变量值只能初始化为编译器常量
Go
new 和 make 的区别
new 的主要作用是为类型申请一片内存空间，并返回指向这片内存的指针
make 主要用于内建类型 slice、map、channel
map
深度解密Go语言之map
源码数据结构
key 定位
用最后的 5 个 bit 位，也就是 01010，值为 10，也就是 10 号桶
再用哈希值的高 8 位（bmap 中的 tophash），找到此 key 在 bucket 中的位置，这是在寻找已有的 key
哈希碰撞
链表法（在 bmap 结构体中的 *overflow 指针指向下一个 bucket）
协程
线程实现模型：用户级线程模型，内核级线程模型和两级线程模型
协程的目的就是避免过多的内核切换时产生的内核态与用户态之间切换的开销
goroutine 调度机制（协程和调度机制，总结的比较简练）
1）M 必须和 P 绑定，每个 P 有一个 G 任务队列
2）M 查找 G 并执行（查找过程：本地任务队列 -> 全局任务队列 -> 从其他 P 中借一半来干活）
3）sysmon 线程监控协程
记录所有P的G任务计数schedtick，（schedtick会在每执行一个G任务后递增）
如果检查到 schedtick一直没有递增，说明这个P一直在执行同一个G任务，如果超过一定的时间（10ms），就在这个G任务的栈信息里面加一个标记
然后这个G任务在执行的时候，如果遇到非内联函数调用，就会检查一次这个标记，然后中断自己，把自己加到队列末尾，执行下一个G；
如果没有遇到非内联函数（有时候正常的小函数会被优化成内联函数）调用的话，那就惨了，会一直执行这个G任务，直到它自己结束；
如果是个死循环，并且 GOMAXPROCS=1 的话，恭喜你，夯住了！
如果没有遇到非内联函数（有时候正常的小函数会被优化成内联函数）调用的话，那就惨了，会一直执行这个G任务，直到它自己结束；
如果是个死循环，并且 GOMAXPROCS=1 的话，恭喜你，夯住了！
内存分配
Go内存分配那些事，就这么简单！
思想
使用缓存提高效率。在存储的整个体系中到处可见缓存的思想，Go内存分配和管理也使用了缓存，
利用缓存一是减少了系统调用的次数，二是降低了锁的粒度 减少加锁的次数，从这2点提高了内存管理效率。
利用缓存一是减少了系统调用的次数，二是降低了锁的粒度 减少加锁的次数，从这2点提高了内存管理效率。
以空间换时间，提高内存管理效率。
TCMalloc
概念
Page：操作系统对内存管理以页为单位，TCMalloc也是这样，只不过TCMalloc里的Page大小与操作系统里的大小并不一定相等，
而是倍数关系。《TCMalloc解密》里称x64下Page大小是8KB。
而是倍数关系。《TCMalloc解密》里称x64下Page大小是8KB。
Span：一组连续的Page被称为Span，比如可以有2个页大小的Span，也可以有16页大小的Span，
Span比Page高一个层级，是为了方便管理一定大小的内存区域，Span是TCMalloc中内存管理的基本单位。
Span比Page高一个层级，是为了方便管理一定大小的内存区域，Span是TCMalloc中内存管理的基本单位。
ThreadCache：每个线程各自的Cache，一个Cache包含多个空闲内存块链表，每个链表连接的都是内存块，
同一个链表上内存块的大小是相同的，也可以说按内存块大小，给内存块分了个类，这样可以根据申请的内存大小，
快速从合适的链表选择空闲内存块。由于每个线程有自己的ThreadCache，所以ThreadCache访问是无锁无系统调用的。
但mcache与ThreadCache也有不同点，TCMalloc中是每个线程1个ThreadCache，Go中是每个P拥有1个mcache，因为在Go程序中，当前最多有GOMAXPROCS个线程在运行，所以最多需要GOMAXPROCS个mcache就可以保证各线程对mcache的无锁访问，线程的运行又是与P绑定的，把mcache交给P刚好
同一个链表上内存块的大小是相同的，也可以说按内存块大小，给内存块分了个类，这样可以根据申请的内存大小，
快速从合适的链表选择空闲内存块。由于每个线程有自己的ThreadCache，所以ThreadCache访问是无锁无系统调用的。
但mcache与ThreadCache也有不同点，TCMalloc中是每个线程1个ThreadCache，Go中是每个P拥有1个mcache，因为在Go程序中，当前最多有GOMAXPROCS个线程在运行，所以最多需要GOMAXPROCS个mcache就可以保证各线程对mcache的无锁访问，线程的运行又是与P绑定的，把mcache交给P刚好
CentralCache：是所有线程共享的缓存，也是保存的空闲内存块链表，链表的数量与ThreadCache中链表数量相同，当ThreadCache内存块不足时，
可以从CentralCache取，当ThreadCache内存块多时，可以放回CentralCache。由于CentralCache是共享的，所以它的访问是要加锁的。
mcentral与CentralCache也有不同点，CentralCache是每个级别的Span有1个链表，mcache是每个级别的Span有2个链表
可以从CentralCache取，当ThreadCache内存块多时，可以放回CentralCache。由于CentralCache是共享的，所以它的访问是要加锁的。
mcentral与CentralCache也有不同点，CentralCache是每个级别的Span有1个链表，mcache是每个级别的Span有2个链表
PageHeap：PageHeap是堆内存的抽象，PageHeap存的也是若干链表，链表保存的是Span，当CentralCache没有内存的时，会从PageHeap取，
当CentralCache内存多的时候，会放回PageHeap。mheap的Span不够用时会向OS申请，向OS的内存申请是按页来的。
mheap与PageHeap也有不同点：mheap把Span组织成了树结构，而不是链表，这样做是为了更高效的利用内存：分配、回收和再利用
当CentralCache内存多的时候，会放回PageHeap。mheap的Span不够用时会向OS申请，向OS的内存申请是按页来的。
mheap与PageHeap也有不同点：mheap把Span组织成了树结构，而不是链表，这样做是为了更高效的利用内存：分配、回收和再利用
Go 内存分配
分配策略
小对象大小：0~256KB => ThreadCache -> CentralCache -> HeapPage，大部分时候，ThreadCache缓存都是足够的，
不需要去访问CentralCache和HeapPage，无锁分配加无系统调用，分配效率是非常高的。
中对象大小：257~1MB => 直接在PageHeap中选择适当的大小即可，128 Page的Span所保存的最大内存就是1MB。
大对象大小：>1MB => 从large span set选择合适数量的页面组成span，用来存储数据。
不需要去访问CentralCache和HeapPage，无锁分配加无系统调用，分配效率是非常高的。
中对象大小：257~1MB => 直接在PageHeap中选择适当的大小即可，128 Page的Span所保存的最大内存就是1MB。
大对象大小：>1MB => 从large span set选择合适数量的页面组成span，用来存储数据。
Go中的内存分类并不像TCMalloc那样分成小、中、大对象，但是它的小对象里又细分了一个Tiny对象，Tiny对象指大小在1Byte到16Byte之间并且不包含指针的对象。小对象和大对象只用大小划定，无其他区分。
逃逸分析
垃圾回收
高并发
百万 TCP 连接问题
来一个请求建立一个 goroutine
缺陷：耗费内存太多，Go调度器不停调度
单 goroutine (epoller)
一个 goroutine 接收请求，添加到 epoll 队列；另一个 goroutine 进行 epoll_wait
缺陷：单个 goroutine 处理速度慢，没有利用多核优势）
多 epoller (prefork)
多epoller， 每个epoller处理一批连接，每个epoller独自占用一个goroutine
Reactor 方式
将I/O goroutine和业务goroutine分离， I/O goroutine采用单goroutine的方式，监听的消息交给一个goroutine池 (workerpool)去处理
这样可以并行的处理业务消息，而不会阻塞I/O goroutine
这样可以并行的处理业务消息，而不会阻塞I/O goroutine
1. Go的好处
接口相当灵活
既有静态语言的类型检查，又有动态语言的 duck typing（只需要实现接口定义的方法，非常灵活）
面向过程 → 面向对象 (继承) → 面向接口 (接口定义了一种规范，描述了类的行为和功能，而不做具体实现)
C++ vs Go 的接口
C++ 和 Go 在定义接口方式上的不同，也导致了底层实现上的不同。
C++ 通过虚函数表来实现基类调用派生类的函数；而 Go 通过 itab 中的 fun 字段来实现接口变量调用实体类型的函数。
C++ 中的虚函数表是在编译期生成的；而 Go 的 itab 中的 fun 字段是在运行期间动态生成的。
原因在于，Go 中实体类型可能会无意中实现 N 多接口，很多接口并不是本来需要的，
所以不能为类型实现的所有接口都生成一个 itab， 这也是“非侵入式”带来的影响；
这在 C++ 中是不存在的，因为派生需要显示声明它继承自哪个基类。
C++ 通过虚函数表来实现基类调用派生类的函数；而 Go 通过 itab 中的 fun 字段来实现接口变量调用实体类型的函数。
C++ 中的虚函数表是在编译期生成的；而 Go 的 itab 中的 fun 字段是在运行期间动态生成的。
原因在于，Go 中实体类型可能会无意中实现 N 多接口，很多接口并不是本来需要的，
所以不能为类型实现的所有接口都生成一个 itab， 这也是“非侵入式”带来的影响；
这在 C++ 中是不存在的，因为派生需要显示声明它继承自哪个基类。
支持函数式编程
函数是一等公民、闭包
defer 很好用
不用担心中间代码崩溃导致资源（文件描述符等）内存泄露
面向对象
继承 -> 匿名字段组合
封装 -> 结构体方法
多态 -> 接口(duck typing)
高并发支持好
两级线程模型，协程
协程和线程的区别是：协程避免了无意义的调度，由此可以提高性能，但也因此，程序员必须自己承担调度的责任。
执行协程只需要极少的栈内存（大概是4～5KB），默认情况下，线程栈的大小为1MB。
执行协程只需要极少的栈内存（大概是4～5KB），默认情况下，线程栈的大小为1MB。
编译速度快
性能好
是 GC 语言中最快的了
标准库很好
http 包等，开发网络程序相当方便，所以非常适合工程化
容易阅读，规范
看别人的代码很容易读懂
测试支持的很好
写个单元测试很方便，还有表格驱动：测试逻辑和数据分离
2. Go不好的地方
不支持泛型
所以对通用编程支持的很差，不过在 2.0 版本要增加泛型支持
不支持默认参数
不方便，没有C++函数重载那么灵活
3. 语言特性
支持类型继承吗？
不支持，使用匿名字段进行组合的方式代替继承
for 循环
支持continue和break来控制循环，但是它提供了一个更高级的break，可以选择中断哪一个循环
不支持以逗号为间隔的多个赋值语句，必须使用平行赋值的方式来初始化多个变量
switch 语句
在case中明确添加fallthrough关键字，可以继续执行紧跟的下一个case
支持方法重载吗？
不支持，这也是不支持默认参数的，不太方便的地方
支持指针运算吗？
不支持
区分大小写吗？
区分，通过变量首字母的大小写来判断是否包外可以访问，相当于面向对象的 public、private 标识，一目了然
静态类型和动态类型
1）静态类型是变量声明时的声明类型，在变量声明、new方法创建对象时或者结构体元素的类型定义，参数类型等。
2）接口(interface)类型的变量还有一个动态类型，它是运行时赋值给这个变量的具体的值的类型(当然值为nil的时候没有动态类型)。
一个变量的动态类型在运行时可能改变，这主要依赖它的赋值。
2）接口(interface)类型的变量还有一个动态类型，它是运行时赋值给这个变量的具体的值的类型(当然值为nil的时候没有动态类型)。
一个变量的动态类型在运行时可能改变，这主要依赖它的赋值。
如何在Go中打印变量的类型
利用反射 reflect.TypeOf
Go 语言中 this 指针
Go 语言的方法有接收者，方法接收者显式传递，没有被隐藏起来，在方法内可以直接使用
Go 语言中 select 机制
select 机制用来处理 channel 异步 IO 问题
select 机制最大的一条限制就是每个 case 语句里必须是一个 IO 操作
select 会随机选择一个可用 case 执行
Go 语言触发异常的场景
空指针解析
下标越界
除数为 0
调用 panic 函数
将参数传递给方法的方式有多少
通过方法的接收者（哪个结构体的方法，将要传的参数放入结构体内部）
通过方法的形参
通过包内的全局变量
通过闭包引用方法作用域外的变量
通过 channel
如果获取 goroutine id
这是Golang的开发者故意为之，避免开发者滥用Goroutine Id实现Goroutine Local Storage(类似java的Thread Local Storage)，
因为Goroutine Local Storage很难进行垃圾回收。因此尽管Go1.4之前暴露出了相应的方法，现在已经把它隐藏了
因为Goroutine Local Storage很难进行垃圾回收。因此尽管Go1.4之前暴露出了相应的方法，现在已经把它隐藏了
获取方法：在go源码runtime包中增加函数Goid，直接调用runtime的getg函数获取
Go 可能的内存泄露
1. goroutine 本身的栈所占用的空间造成内存泄露。
2. goroutine 中的变量所占用的堆内存导致堆内存泄露，这一部分是能通过 heap profile 体现出来的。
3. context 没有 cancel 的时候（主要就是这一点）
子 goroutine 与主线程的同步
channel 机制
每个 goroutine 传一个 channel 进去然后往里写数据，再在主线程中读取这些 channel，
直到全部读到数据了子 goroutine 也就全部运行完了，那么主 goroutine 也就可以结束了。
这种模式是子线程去通知主线程结束。
直到全部读到数据了子 goroutine 也就全部运行完了，那么主 goroutine 也就可以结束了。
这种模式是子线程去通知主线程结束。
context cancel 机制
这种模式是主线程去通知子线程结束
sync.WaitGroup 模式
Add 方法设置等待子 goroutine 的数量，使用 Done 方法设置等待子 goroutine 的数量减 1，
当等待的数量等于 0 时，Wait() 返回
当等待的数量等于 0 时，Wait() 返回
0 条评论
下一页
