百度（内部技术架构部）-c++（提前批）-一面

2021-07-20：
1、自我介绍
2、设计一个缓存，替换k的策略有哪些？
参考：
数据缓存的过程：设置缓存容量（通常为15%-30%）->缓存淘汰机制->处理被淘汰的数据（脏数据重新存入数据库，干净数据直接删除）

• RANDOM:随机替换算法
• FIFO：先进先出算法，高速缓存看成是一个队列优先替换最先进入队列的字块
• LRU：最不经常使用算法，替换掉最近被请求最少的对象
• LFU：最近最少使用算法，替换掉访问次数最少的缓存

3、代码开发，c++语言方面熟吗？
4、const关键字作用是什么？
参考：const代表常量，用const修饰的量都具有不可修改

5、数据结构问题：hashmap怎么实现，用到什么数据结构、注意什么样的问题？
参考：

• HashMap基于哈希表的Map接口实现。是以key-value存储形式存在。线程不安全,也就是说多个线程同时对HashMap进行增删改操作时，不能保证数据时一致的。key和value都可以为null，无序存放。
• 实现：通过计算key的hashCode值，再将值进行高位右移16位后异或刚刚得到的hashCode值，即hash值。底层采用key的hashCode()的值结合数组长度进行无符号右移（>>>）,按位异或（^）计算hash值，按位与（&）计算索引。
• Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
• 数据结构：在JDK1.8之前HashMap是数组+链表的形式，在JDK1.8包括之后是数组+链表+红黑树，当链表超过8且数组总量超过64才会转红黑树。
• HashMap是如何解决hash碰撞的：HashMap采用采用 “拉链法” ，将hash值相同的元素放到同一个链表下面，还可以采用的方法：平方取中法，伪随机数法，取余法
• HashMap的resize()扩容机制：当put进去元素后，table中的元素个数> table*loadFactor(默认加载因子0.75) ，那么数组就开始扩容，例如：table数组的默认大小是16，当put后的数组长度超过12 * 0.75 = 12时，数组开始扩容，扩容大小 = 原来的一倍，然后重新计算每个元素在数组中的位置。

6、hashmap的接口元素：放入元素、查找元素
HashMap最为核心的put方法：
方法执行流程：
（1）put方法传入键值
（2）Node<K,V>[] table 是否为空 (JDK1.8),如果为空，则进行resize()扩容
（3）table 不为空，根据hash值+高位右移+异或+取模计算索引值。确定存放的位置。
（4）如果存放的位置为空，则直接插入，++size
（5）如果存放的位置不为空，通过重写Object的equals的方法进行遍历链表中是否存在相等的key
（6）若存在相等的，则直接覆盖value值
（7）否则判断链表的阈值是否>8 ,数组长度是否>64(满不满足生成红黑二叉树)，若满足，则将键值对插入红黑二叉树中
（8）如果不满足，则开始遍历链表插入，如果插入后链表长度 > 8且table长度 > 64,则转换称红黑树后插入
（9）倘若仍不满足红黑树，则遍历链表插入，遇到相同的key,覆盖value插入
HashMap核心get方法：
（1）先从数组下标，找到对应的Node2.　　
（2） 如果Node里的第一个节点命中，直接返回　　
（3）如果有冲突，则通过key.equals(k)去查找对应的entry　　
（4）若为树，则在树中通过key.equals(k)查找，O(logn)；　　
（5）若为链表，则在链表中通过key.equals(k)查找，O(n)。
7、一致性hash介绍
8、mysql使用过吧
9、算法写代码：二叉树判断是否是另一个二叉树的一部分
我当时写的（还有些小问题）

10、虚函数使用场景
参考：父类决定调用时机，子类决定具体实现
被virtual关键字修饰的成员函数，就是虚函数。虚函数的作用：实现多态性，多态性是将接口与实现进行分离；用形象的语言来解释就是实现以共同的方法，但因个体差异而采用不同的策略。
多态还有个关键之处就是一切用指向基类的指针或引用来操作对象
虚函数底层机制：虚函数是使用虚函数表和虚函数表指针实现的。虚函数表是一个类虚函数的地址，用于索引类本身和类虚函数，若子类重写父类函数，则会在相应的虚函数表处替换成子类虚函数的地址。虚函数表指针存在于每一个对象中，它指向对象所对应类的虚函数地址。
这些函数不能声明为虚函数：普通函数（非成员函数）、构造函数、友元函数、静态成员函数、内联成员函数
11、指针和引用的区别

• 定义一个指针变量编译器会为它分配内存，而引用不占用任何内存；
• 引用必须在定义时被初始化，指针不必；
• 不存在指向空值的引用，但存在指向空值的指针。

12、如何防止一个类被拷贝
参考：实现对类实例化对象的拷贝：通过该类中的拷贝构造函数和赋值运算符的重载（operator=）来实现的，防止该类被拷贝：将拷贝构造函数和赋值运算符的重载，声明为private(私有，类外无权访问），可以不给出实现。
13、智能指针及其使用场景
参考：
智能指针能够避免内存泄漏问题，在指针过期的时候会自动调用析构函数。

• unique_ptr：由 unique_ptr 管理的内存，只能被一个对象持有；unique_ptr 不支持复制和赋值，只支持移动，使用 std::move 转移当前对象的所有权；内存上没有任何的额外消耗，性能是最优的。
• shared_ptr：多个 shared_ptr 可以共享同一块内存；shared_ptr 是支持复制的，利用引用计数来实现内存的自动管理，每当复制一个 shared_ptr，引用计数会 + 1。当一个 shared_ptr 离开作用域时，引用计数会 - 1。当引用计数为 0 的时候，则 delete 内存；shared_ptr 也支持移动；内存占用高，原子操作性能低，使用移动优化性能
• weak_ptr ：为了解决 shared_ptr 双向引用的问题；weak_ptr 不会增加引用计数，因此可以打破 shared_ptr 的循环引用；通常做法是 parent 类持有 child 的 shared_ptr, child 持有指向 parent 的 weak_ptr。

14、unique_ptr是怎么实现的

15、多线程了解吗，多线程的同步机制

16、一般有哪几种锁

17、前面答得不好，强行转到答epoll
18、进程之间的通信方式有哪些？
参考：进程之间的通信方式主要有六种，包括管道，信号量，消息队列，信号，共享内存，套接字。
19、tcp建立连接的过程，怎么建立连接，发什么包
20、智力题：有一个抽奖项目，每个人报一个1-100的数，只要你报的数越接近所有人的平均数的二分之一，中奖概率越大，你会报多少。
21、内存分配的几种方式？

• 从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量。
• 在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
• 从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。

22、new和malloc的区别
22、拷贝构造函数
拷贝构造函数是用该类型的另外一个实例化的对象来初始化一个新建的对象

• 用类的一个对象去初始化另一个对象时
• 当函数的形参是类的对象时（也就是值传递时），如果是引用传递则不会调用
• 当函数的返回值是类的对象或引用时