承接上次更新的文章，本节继续给大家推送几道C++基础面试题目。

1、C++的内存管理方式，STL的allocator，最新版本默认使用的分配器。

C++的内存管理方式：

在c++中内存主要分为5个存储区：

栈（Stack）：局部变量，函数参数等存储在该区，由编译器自动分配和释放.栈属于计算机系统的数据结构，进栈出栈有相应的计算机指令支持，而且分配专门的寄存器存储栈的地址，效率分高，内存空间是连续的，但栈的内存空间有限。

堆（Heap）：需要程序员手动分配和释放（new,delete），属于动态分配方式。内存空间几乎没有限制，内存空间不连续，因此会产生内存碎片。操作系统有一个记录空间内存的链表，当收到内存申请时遍历链表，找到第一个空间大于申请空间的堆节点，将该节点分配给程序，并将该节点从链表中删除。一般，系统会在该内存空间的首地址处记录本次分配的内存大小，用于delete释放该内存空间。

全局/静态存储区:全局变量，静态变量分配到该区，到程序结束时自动释放，包括DATA段（全局初始化区）与BSS段（全局未初始化段）。其中，初始化的全局变量和静态变量存放在DATA段，未初始化的全局变量和静态变量存放在BSS段。BSS段特点：在程序执行前BSS段自动清零，所以未初始化的全局变量和静态变量在程序执行前已经成为0。

文字常量区：存放常量，而且不允许修改。程序结束后由系统释放。

程序代码区：存放程序的二进制代码

SGI 版本STL的默认配置器std::alloc

参见：《STL源码剖析》

1）考虑到小型区块所可能造成的内存碎片问题，SGI设计了双层配置器。第一级配置器直接使用malloc（）和free（）；第二级则视情况采取不同的策略：当配置区块超过128bytes时，视为“足够大”，便调用第一级配置器；当配置区块小于128bytes时，视之为“过小”，为了降低额外负担，便采用memory pool（内存池）整理方式，而不在求助于第一级配置器。

2）内存池的核心：内存池和16个自由链表（各自管理8,16，...，128bytes的小额区块）。在分配一个小区块时，首先在所属自由链表中寻找，如果找到，直接抽出分配；若所属自由链表为空，则请求内存池为所属自由链表分配空间；默认情况下，为该自由链表分配20个区块，若内存池剩余容量不足，则分配可分配的最大容量；若内存池连一个区块都无法分配，则调用chunk_alloc为内存池分配一大块区块；若内存不足，则尝试调用malloc分配，否则返回bad_alloc异常。

2、hash表的实现，包括STL中的哈希桶长度常数。

hash表的实现主要涉及两个问题：散列函数和碰撞处理。

1）hash function （散列函数）。最常见的散列函数：f（x） = x % TableSize .

2）碰撞问题（不同元素的散列值相同）。解决碰撞问题的方法有许多种，包括线性探测、二次探测、开链等做法。SGL版本使用开链法，使用一个链表保持相同散列值的元素。

虽然开链法并不要求表格大小必须为质数，但SGI STL仍然以质数来设计表格大小，并且将28个质数（逐渐呈现大约两倍的关系）计算好，以备随时访问，同时提供一个函数，用来查询在这28个质数之中，“最接近某数并大于某数”的质数。

3、hash表如何rehash，怎么处理其中保存的资源

先想想为什么需要rehash:

因为，当loadFactor（负载因子）<；=1时，hash表查找的期望复杂度为O（1）. 因此，每次往hash表中添加元素时，我们必须保证是在loadFactor <；1的情况下，才能够添加。

模仿C++的vector扩容方式，Hash表中每次发现loadFactor==1时，就开辟一个原来桶数组的两倍空间（称为新桶数组），然后把原来的桶数组中元素全部转移过来到新的桶数组中。注意这里转移是需要元素一个个重新哈希到新桶中的。

4、Redis的rehash怎么做的，为什么要渐进rehash，渐进rehash怎么实现的。

为了避免rehash对服务器造成影响，服务器不是一次将ht[0]里面的所有键值对全部rehash到ht[1]，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1].

以下是哈希表渐进式 rehash 的详细步骤：

为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。

在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。

在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。

随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。

5、Redis的定时机制怎么实现的，有哪些弊端，你将如何改进这个弊端？

Redis服务器是一个事件驱动程序，服务器需要处理以下两类事件：文件事件（服务器对套接字操作的抽象）和时间事件（服务器对定时操作的抽象）。Redis的定时机制就是借助时间事件实现的。

一个时间事件主要由以下三个属性组成：id：时间事件标识号；when：记录时间事件的到达时间；timeProc：时间事件处理器，当时间事件到达时，服务器就会调用相应的处理器来处理时间。一个时间事件根据时间事件处理器的返回值来判断是定时事件还是周期性事件。

弊端：Redis对时间事件的实际处理时间并不准时，通常会比时间事件设定的到达事件稍晚一些。

改进：多线程？一个处理文件事件，一个处理时间事件？（不确定）。

免责声明：内容和图片源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。