17 QA

17 QA

1.平衡树（红黑树）/B树、B+树、B*树、DOM树的实现模拟

红黑树：(1) 每个节点或者是黑色，或者是红色。
    　　    (2) 根节点是黑色。
    　　    (3) 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
    　　    (4) 如果一个节点是红色的，则它的子节点必须是黑色的。
    　　    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点（确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树）。
    B树：(1)根节点至少有两个子节点
          (2)每个节点有M-1个key，并且以升序排列
          (3)位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
          (4)其它节点至少有M/2个子节点
    B+树： (1)B+树是应文件系统所需而产生的一种B-tree的变形树，有n棵子树的结点中含有n-1 个关键字
              (2)所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
              (3)所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)
    B*树：是B+树的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，B*树中非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。
    DOM树：文档对象模型”(Document Object Model)

2.索引index、联合索引

聚合索引：主键索引
非聚合索引：普通索引、唯一索引、组合索引、全文索引

3.贪心算法与其弊端

贪心算法是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。
　　贪心算法每一步必须满足一下条件：
　　    (1)、可行的：即它必须满足问题的约束。
　　    (2)、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
　　    (3)、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。
缺点：有时无法得到全局上的最优解的数据。

4.进程间通信方式、TCP/UDP建立连接的步骤、三次握手四次挥手、TCP的超时等待

TCP
        TCP编程的服务器端一般步骤是：
            1、创建一个socket，用函数socket()；
            2、设置socket属性，用函数setsockopt(); * 可选
            3、绑定IP地址、端口等信息到socket上，用函数bind();
            4、开启监听，用函数listen()；
            5、接收客户端上来的连接，用函数accept()；
            6、收发数据，用函数send()和recv()，或者read()和write();
            7、关闭网络连接；
            8、关闭监听；
        TCP编程的客户端一般步骤是：
            1、创建一个socket，用函数socket()；
            2、设置socket属性，用函数setsockopt();* 可选
            3、绑定IP地址、端口等信息到socket上，用函数bind();* 可选
            4、设置要连接的对方的IP地址和端口等属性；
            5、连接服务器，用函数connect()；
            6、收发数据，用函数send()和recv()，或者read()和write();
            7、关闭网络连接；
UDP
        UDP编程的服务器端一般步骤是：
            1、创建一个socket，用函数socket()；
            2、设置socket属性，用函数setsockopt();* 可选
            3、绑定IP地址、端口等信息到socket上，用函数bind();
            4、循环接收数据，用函数recvfrom();
            5、关闭网络连接；
        UDP编程的客户端一般步骤是：
            1、创建一个socket，用函数socket()；
            2、设置socket属性，用函数setsockopt();* 可选
            3、绑定IP地址、端口等信息到socket上，用函数bind();* 可选
            4、设置对方的IP地址和端口等属性;
            5、发送数据，用函数sendto();
            6、关闭网络连接；
三次握手：
    第一次握手：客户端想与服务器进行连接了，所以状态变为主动打开，同时发送一个连接请求报文给服务器段SYN=1，并且会携带x个字节过去。发送完请求连接报文后，客户端的状态就变为了SYN_SENT，可以说这个状态是等待发送确认(为了发送第三次握手时的确认包)
    第二次握手：服务端接收到连接请求报文后，从LSTTEN状态变为被动打开状态，然后给客户端返回一个报文。这个报文有两层意思，一是确认报文，而可以达到告诉客户端，我也打开连接了。发完后，变为SYN_RCVD状态(也可以说是等待接受确认状态，接受客户端发过来的确认包)
    第三次握手：客户端得到服务器端的确认和知道服务器端也已经准备好了连接后，还会发一个确认报文到服务器端，告诉服务器端，我接到了你发送的报文，接下来就让我们两个进行连接了。客户端发送完确认报文后，进入ESTABLISHED，而服务器接到了，也变为ESTABLISHED
四次挥手：
    第一次挥手：从ESTABLISHED变为主动关闭状态，客户端主动发送释放连接请求给服务器端，FIN=1。发送完之后就变为FIN_WAIT_1状态，这个状态可以说是等待确认状态。
    第二次挥手：服务器接收到客户端发来的释放连接请求后，状态变为CLOSE_WAIT，然后发送确认报文给客户端，告诉他我接收到了你的请求。为什么变为CLOSE_WAIT，原因是是客户端发送的释放连接请求，可能自己这端还有数据没有发送完呢，所以这个时候整个TCP连接的状态就变为了半关闭状态。服务器端还能发送数据，并且客户端也能接收数据，但是客户端不能在发送数据了，只能够发送确认报文。客户端接到服务器的确认报文后，就进入了FIN_WAIT_2
状态。也可以说这是等待服务器释放连接状态。
    第三次挥手：服务器端所有的数据度发送完了，认为可以关闭连接了，状态变为被动关闭，所以向客户端发送释放连接报文，发完之后自己变为LAST_WAIT状态，也就是等待客户端确认状态
    第四次挥手：客户端接到释放连接报文后，发送一个确认报文，然后自己变为TIME_WAIT,而不是立马关闭，因为客户端发送的确认报文可能会丢失，丢失的话服务器就会重传一个FIN，也就是释放连接报文，这个时候客户端必须还没关闭。 当服务器接受到确认报文后，服务器就进入CLOSE状态，也就是关闭了。但是由于上面说的这个原因，客户端必须等待一定的时间才能够进入CLOSE状态。
TCP的超时等待：在发送一个数据之后，就开启一个定时器，若是在这个时间内没有收到发送数据的ACK确认报文，则对该报文进行重传，在达到一定次数还没有成功时放弃并发送一个复位信号。

5.Mysql数据库中join的类型与区别、含义

INNER JOIN（内连接,或等值连接）：取得两个表中存在连接匹配关系的记录。
LEFT JOIN（左连接）：取得左表（table1）完全记录，即是右表（table2）并无对应匹配记录。
RIGHT JOIN（右连接）：与 LEFT JOIN 相反，取得右表（table2）完全记录，即是左表（table1）并无匹配对应记录。
注意：mysql不支持Full join,不过可以通过UNION 关键字来合并 LEFT JOIN 与 RIGHT JOIN来模拟FULL join.

6.线程池的了解、线程池对线程的管理方式（初始化线程的方法、线程创建后的管理、指派任务的方式）、优点、调度处理方式和保护任务队列的方式

线程池：线程池就是首先创建一些线程，它们的集合称为线程池。使用线程池可以很好地提高性能，线程池在系统启动时即创建大量空闲的线程，程序将一个任务传给线程池，线程池就会启动一条线程来执行这个任务，执行结束以后，该线程并不会死亡，而是再次返回线程池中成为空闲状态，等待执行下一个任务。
线程池的工作机制：在线程池的编程模式下，任务是提交给整个线程池，而不是直接提交给某个线程，线程池在拿到任务后，就在内部寻找是否有空闲的线程，如果有，则将任务交给某个空闲的线程。一个线程同时只能执行一个任务，但可以同时向一个线程池提交多个任务。
使用线程池的原因：多线程运行时间，系统不断的启动和关闭新线程，成本非常高，会过渡消耗系统资源，以及过渡切换线程的危险，从而可能导致系统资源的崩溃。这时，线程池就是最好的选择了。

7.对象复用的了解

继承复用：继承复用通过扩展一个已有对象的实现来得到新的功能，基类明显地捕获共同的属性和方法，而子类通过增加新的属性和方法来扩展超类的实现。继承是类型的复用。
继承复用的优点：
    新的实现较为容易，因为超类的大部分功能可通过继承关系自动进入子类；新的实现较为容易，因为超类的大部分功能可通过继承关系自动进入子类；
    修改或扩展继承而来的实现较为容易。
继承复用的缺点：
    继承复用破坏封装，因为继承将超类的实现细节暴露给子类。“白箱”复用；
    如果超类的实现发生改变，那么子类的实现也不得不发生改变。
    从超类继承而来的实现是静态的，不可能再运行时间内发生改变，因此没有足够的灵活性。
合成/聚合复用：由于合成/聚合可以将已有的对象纳入到新对象中，使之成为新对象的一部分，因此新的对象可以调用已有对象的功能，
合成/聚合优点：
    新对象存取成分对象的唯一方法是通过成分对象的接口；
    成分对象的内部细节对新对象不可见。 “黑箱”复用；
    该复用支持封装。
    该复用所需的依赖较少。
    每一个新的类可将焦点集中在一个任务上。
    该复用可在运行时间内动态进行，新对象可动态引用于成分对象类型相同的对象。
合成/聚合缺点：
    通过这种复用建造的系统会有较多的对象需要管理。
    为了能将多个不同的对象作为组合块（composition block）来使用，必须仔细地对接口进行定义。 
    要正确的选择合成/复用和继承，必须透彻地理解里氏替换原则和Coad法则。

8.零拷贝的了解

零拷贝：零拷贝就是一种避免 CPU 将数据从一块存储拷贝到另外一块存储的技术。
零拷贝技术的目标：
    避免数据拷贝
        避免操作系统内核缓冲区之间进行数据拷贝操作。
        避免操作系统内核和用户应用程序地址空间这两者之间进行数据拷贝操作。
        用户应用程序可以避开操作系统直接访问硬件存储。
        数据传输尽量让 DMA 来做。
    将多种操作结合在一起
        避免不必要的系统调用和上下文切换。
        需要拷贝的数据可以先被缓存起来。
        对数据进行处理尽量让硬件来做。

9.Linux的I/O模型

阻塞式I/O模型： 读写操作和阻塞阶段
非阻塞式I/O模型：应用阻塞于读写函数
I/O复用式模型：应用阻塞于I/O复用系统调用，但可同时监听多个I/O事件。对I/O本身的读写操作是非阻塞的
信号驱动动式I/O模型：信号触发读写就绪事件，用户程序执行读写操作。应用没有阻塞阶段
异步I/O模型：内核执行读写操作并触发读写完成事件。应用没有阻塞阶段

10.异步I/O的详细解释（同步I/O与异步I/O的区别，包括定义异步I/O、I/O实质上的交谁完成、如何实现异步）、I/O的复用技术，epoll优于select的原因、处理多个套接字的I/O复用介绍

异步非阻塞 I/O
     异步非阻塞 I/O 模型是一种处理与 I/O 重叠进行的模型。读请求会立即返回，说明 read 请求已经成功发起了。在后台完成读操作时，应用程序然后会执行其他处理操作。当 read 的响应到达时，就会产生一个信号或执行一个基于线程的回调函数来完成这次 I/O 处理过程。

11.文件读写使用的系统调用以及涉及的磁盘缓冲区与其手动flush问题

C标准库的I/O缓冲区有三种类型:
    全缓冲：如果缓冲区写满了就写回内核。对于驻留在磁盘上的文件通常是由标准I/O库实施全缓冲的。在一个流上执行第一次I/O操作时，相关标准I/O函数通常调用malloc获得需使用的缓冲区。
    行缓冲：如果用户程序写的数据中有换行符就把这一行写回内核,或者如果缓冲区写满了就写回内核。标准输入和标准输出对应终端设备时通常是行缓冲的。 
    无缓冲：用户程序每次调库函数做写操作都要通过系统调用写回内核。标准错误输出通常是无缓冲的,这样用户程序产生的错误信息可以尽快输出到设备。
除了写缓冲区满、写入换行符之外,行缓冲还有两种情况会自动做Flush操作：
    用户程序调用库函数从无缓冲的文件中读取 
    或者从行缓冲的文件中读取,并且这次读操作会引发系统调用从内核读取数据
如果用户程序不想完全依赖于自动的Flush操作,可以调fflush函数手动做Flush操作。

12.struct与class的区别

1、class是引用类型，struct是值类型；
2、class可以继承类、接口和被继承，struct只能继承接口，不能被继承；
3、class有默认的无参构造函数，有析构函数，struct没有默认的无参构造函数，且只能声明有参的构造函数，没有析构函数；
4、class可以使用abstract和sealed，有protected修饰符，struct不可以用abstract和sealed，没有protected修饰符；
5、class必须使用new初始化，结构可以不用new初始化；
6、class实例由垃圾回收机制来保证内存的回收处理，而struct变量使用完后立即自动解除内存分配；
7、从职能观点来看，class表现为行为，而struct常用于存储数据；
8、作为参数传递时，class变量以按址方式传递，而struct变量是以按值方式传递的。

13.STL库的介绍、STL底层介绍

C++ STL 的实现：
1.vector  底层数据结构为数组 ，支持快速随机访问
2.list    底层数据结构为双向链表，支持快速增删
3.deque   底层数据结构为一个中央控制器和多个缓冲区，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问
4.stack   底层一般用list、deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
5.queue   底层一般用list、deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
注意:stack和queue是适配器,而不叫容器，因为是对容器的再封装
6.priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现（优先队列）
7.set       底层数据结构为红黑树，有序，不重复
8.multiset  底层数据结构为红黑树，有序，可重复 
9.map      底层数据结构为红黑树，有序，不重复
10.multimap 底层数据结构为红黑树，有序，可重复
11.hash_set 底层数据结构为hash表，无序，不重复
12.hash_multiset 底层数据结构为hash表，无序，可重复 
13.hash_map      底层数据结构为hash表，无序，不重复
14.hash_multimap 底层数据结构为hash表，无序，可重复

14.vector的使用注意点及原因，频繁对vector调用push_back()对性能的影响和原因、vector重新分配内存的大小与方式

vector实现的关键点:
    （1）元素存储空间的增长方式，建议使用参考书籍的增长方式，每次增长的空间至少是原来空间的一半，即N=(N+N/2)，注意存储空间利用率和当元素增长时程序的运行性能之间的平衡。
    （2）实现时vector内的成员对象只有一个内存分配器对象和三个指向元素储存空间的指针（First、Last和End）。
    （3）vector的特例化模板vector<bool>的存在主要是对于bool类型的元素存储和操作时在空间和时间上的优化。
    （4）vector一般保留一个大小大于实际所需大小的数组空间，多余的存储空间在成为有效数组的一部分前保持为未构造状态。
    （5）插入insert元素时需要移动元素的位置，移动时需要注意内存重叠，使元素的拷贝移动方向与元素的增长方向相反可解决内存重叠问题。
vector使用注意事项：
    （1）max_size函数返回的是vector中的内存分配器allocator能够分配的最大内存空间，即vector所能管控的最大序列长度，注意和capacity的区别。
    （2）resize重新调整大小，既可以减小也可以增加size（数组的有效长度），但是内存并不一定减小。
    （3）insert是在所指的元素之前进行插入，erase返回的迭代器指向被最后删除的元素的下一个元素。
    （4）注意插入和删除元素后迭代器失效的问题。
    （5）当预先知道所需的存储空间时，可以使用reserve预先分配内存。
    （6）vector对象作为一个高效的栈使用时，应该让容器保持一定的预留存储空间，频繁的重新分配内存会影响栈的性能，可以使用reserve预分配内存，使用push_back、pop_back和back插入、删除和读取最后一个元素。
    （7）clear只是保证了析构所有的元素，即size()=0，但并不保证释放所有的存储空间，即capacity不一定等于0，可以使用如下方式释放所有内存：vec.swap(vector<T>());

15.Hash/hashmap（实现方式）/hashtable（hash函数如何保证冲突最小）底层实现

hashmap：HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
hashtable：
    映射方法：直接寻址、数字分析法、平方取中、折叠法、随机数法、除留余数法
    解决冲突：开放寻址法、再散列法、链地址法（拉链法）、建立一个公共溢出区

16.C++虚函数的具体实现原理（虚函数表）

请参考：2.5 虚函数的实现及基本原理

17.析构函数一般写成虚函数的原因

原因：在实现多态时，当用基类操作派生类，在析构时防止只析构基类而不析构派生类的状况发生。
当基类的析构函数不是虚函数时：
    1、派生类的指针操作派生类，当析构这个派生类的指针的时候，先释放派生类资源，在释放基类资源。
    2、基类指针操作派生类，当析构这个基类指针的时候，只是放了基类的资源，而没有释放派生类的资源，造成了内存泄漏。
当基类的析构函数是虚函数是：
    基类指针操作派生类，当析构这个基类指针的时候，先释放派生类的资源，在调用基类的析构函数释放基类的资源。
如果不要基类对派生类及其对象操作，则不应写成虚函数，因为一旦写成虚函数，编辑器就会自动给类分配一个虚函数表，并且给类一个指向这个虚函数表的指针，增加了额外的内存开销。

18.手写实现智能指针类

/*
智能指针类设计实现：当用同一块内存去建立own对象时，不会新建smartpointer类
*/
#include<iostream>  
#include<vector>  
#include<map>  
#include<fstream>
#include<sstream>  
#include<algorithm>
#include<list>
#include<cstring>
using namespace std;
class smartpointer{//定义一个智能指针类
private:
    friend class own;
    int *p;//被管理内存的类型
    size_t use;//对象使用计数器
    smartpointer(int *pt) :use(1), p(pt){}
    ~smartpointer(){ delete p; }
};
typedef struct t{
    smartpointer *spt;
    struct t *next;
}node;
class own{
public:
    //复制控制部分
    own(int *p,int val){
        int flag = true;
        if (link == NULL){//如果是空的话
            node *temp = new node;
            temp->spt = new smartpointer(p);
            temp->next = NULL;
            link= temp;
        }
        else{
            node *head = link;
            while (head != NULL){
                if (p ==head->spt->p){
                    ptr = head->spt;
                    ptr->use++;
                    value = val;
                    flag = false;
                    break;
                }
                head=head->next;
            }
        }
        if (true){
            node *temp=new node;
            ptr = new smartpointer(p);
            temp->spt = ptr;
            temp->next = link;
            link = temp;
            value = val;
        }
    }
    own & operator=(const own &obj){
        ++obj.ptr->use;
        if (--ptr->use == 0)delete ptr;
        value = obj.value;
        ptr = obj.ptr;
        return *this;
    }
    own(const own&obj){
        value = obj.value;
        ptr = obj.ptr;
        ptr->use++;//两者指向同一个智能指针对象
    }
    ~own(){
        if (ptr->use == 0)delete ptr;
    }
    //获取类的值
    int *get_ptr(){
        return ptr->p;
    }
    int get_value(){
        return value;
    }
    void set_ptr(int *new_ptr){//将其设置为指向一个新值的
        ptr->use--;
        if (ptr->use == 0)delete ptr;
        ptr = new smartpointer(new_ptr);
    }
    void set_val(int val){
        value = val;
    }
private:
    int value;
    smartpointer *ptr;
    static node *link ;//用来保存已经存在的smartpoint类对象
};
node *own::link = NULL;//刚开始设为空值
int main(){
    int *p = new int[50];
    own b1(p, 1);
    own b2(p, 2);
    cout << b1.get_ptr() << endl;
    cout << b2.get_ptr() << endl;
    delete []p;
    return 0;
}

19.常见Linux命令

whoami命令可以知道当前使用的帐号
文件系统中可以使用路径描述某个文件或者文件夹的位置。
绝对路径从文件系统的开始文件夹描述路径，例如
/home/tarena
所有绝对路径都是以/做开头的
相对路径是从某一个文件夹开始描述另外一个文件夹的位置。
.        代表当前文件夹
..       代表当前目录的父目录
tarena   代表的是当前目录中叫tarena的子目录
pwd命令可以返回当前目录的绝对路径
clear命令可以把屏幕上的所有内容清除掉
ls命令可以察看指定目录里的内容，使用方法如下
ls <目录路径>
如果要察看当前目录的内容可以省略路径
ls命令支持-a和-l选项，-a选项可以把所有内容都显示在屏幕上，-l选项可以显示每个文件或目录的详细信息。-a选项和-l选项可以合并成-al。
cd命令可以把任何一个目录调整成当前目录，使用方法如下
cd <目录路径>
mkdir命令可以创建新目录，使用方法如下
mkdir 目录路径1 目录路径2
mkdir命令还可以同时创建多个具有父子关系的目录，需要使用-p选项，例如
mkdir -p 目录路径
rmdir命令可以删除一个空目录，使用方法如下
rmdir 目录路径
rm命令可以删除一个非空的目录，需要使用-rf选项，使用方法如下
rm -rf 目录路径
touch命令可以创建一个新文件，使用方法如下
touch 文件路径
如果文件已经存在则会修改文件的时间
rm命令可以删除一个文件，使用方法如下
rm 文件路径
cp命令可以把一个文件复制一份，使用方法如下
cp 文件路径1 文件路径2
命令执行完成后路径1对应的文件会被复制一份以路径2的方式保存
mv命令可以实现对文件的剪切复制效果，使用方法如下
mv 文件路径1 文件路径2
tar命令可以用来实现打包压缩处理，使用方法如下
tar zcvf day03.tar.gz day03
这个命令可以把day03目录制作成day03.tar.gz文件
tar命令还可以对压缩文件进行解压缩处理，使用方法如下
tar zxvf day03.tar.gz
脚本文件可以包含多条操作命令，执行脚本文件就相当于按顺序执行内部的所有操作命令。
脚本文件制作完成后需要添加执行属性，使用chmod命令，方法如下
chmod <属性值>  文件路径
ln命令可以制作链接文件，使用方法如下
ln 文件路径1 文件路径2
文件路径1代表一个已经存在的文件，文件路径2代表一个还不存在的文件。
使用这种命令创建的链接文件叫做硬链接。
cd $OLDWPD 切换两个目录
ln命令也可以用来制作软链接文件，使用方法如下
ln -s 文件路径1 文件路径2
软链接文件依赖于原有文件
ps命令可以察看当前终端窗口中运行的所有程序，每个程序都有一个进程ID。
kill命令可以强制终止一个程序的运行，需要使用那个程序的进程ID。可以使用-9选项强制终止。
sudo命令可以使用最高权限执行某些命令
查看环境变量echo $CPATH查看，环境变量配置 vi .bashrc（永久设置）
export PATH=.:%PATH
用source .bashrc永久生效
临时设置 vi ~/.bash_profile 打开脚本写入，用source保存，清除 unset CPATH 设置

20.Linux内核的了解

系统调用接口（SCI）：open、read、write等系统调用
进程管理（PM）：创建进程、删除进程、调度进程等
内存管理（MM）：内存分配、管理等
虚拟文件系统（VFS）：为多种文件系统提供统一的操作接口
网络协议栈：提供各种网络协议
CPU架构相关代码（Arch）：为的是提高至移植性
设备驱动程序（DD）：各种设备驱动，占到内核的70%左右代码

21.C++11的新特性

1. Auto
2. 智能指针，no delete
3. Nullptr
4. Range for
5. 非成员begin和end
6. Lambda函数和算法
7. Move/&&
8. 统一的初始化和初始化列表

22.对文件系统的了解

由上而下主要分为用户层、VFS层、文件系统层、缓存层、块设备层、磁盘驱动层、磁盘物理层
    用户层：最上面用户层就是我们日常使用的各种程序，需要的接口主要是文件的创建、删除、打开、关闭、写、读等。 
    VFS层：我们知道Linux分为用户态和内核态，用户态请求硬件资源需要调用System Call通过内核态去实现。用户的这些文件相关操作都有对应的System Call函数接口，接口调用 VFS对应的函数。 
    文件系统层：不同的文件系统实现了VFS的这些函数，通过指针注册到VFS里面。所以，用户的操作通过VFS转到各种文件系统。文件系统把文件读写命令转化为对磁盘LBA的操作，起了一个翻译和磁盘管理的作用。 
    缓存层：文件系统底下有缓存，Page Cache，加速性能。对磁盘LBA的读写数据缓存到这里。
    块设备层：块设备接口Block Device是用来访问磁盘LBA的层级，读写命令组合之后插入到命令队列，磁盘的驱动从队列读命令执行。Linux设计了电梯算法等对很多LBA的读写进行优化排序，尽量把连续地址放在一起。
    磁盘驱动层：磁盘的驱动程序把对LBA的读写命令转化为各自的协议，比如变成ATA命令，SCSI命令，或者是自己硬件可以识别的自定义命令，发送给磁盘控制器。Host Based SSD甚至在块设备层和磁盘驱动层实现了FTL，变成对Flash芯片的操作。 
    磁盘物理层：读写物理数据到磁盘介质。

23.介绍C++内存管理（内存模型）

进程映像：程序在内存空间中的分布
---- 命令行参数与环境变量 ----
         环境变量：0xbfb1aebc
       命令行参数：0xbfb1aeb4
-------------- 桟  -----------
       常局部变量：0xbfb1adf8
       前局部变量：0xbfb1adfc
       后局部变量：0xbfb1ae00
-------------- 堆 ------------
         后堆变量：0x97d2018
         前堆变量：0x97d2008
------------- BSS ------------
 未初始化全局变量：0x804a03c
 未初始化静态变量：0x804a038
------------ 数据 ------------
   初始化静态变量：0x804a028
   初始化全局变量：0x804a024
------------ 代码 ------------
       常静态变量：0x8048a50
       字面值常量：0x80487b4
       常全局变量：0x80487b0
             函数：0x80484f4

34.C++内存泄漏及检测

在Linux平台上有valgrind可以非常方便的帮助我们定位内存泄漏，因为Linux在开发领域的使用场景大多是跑服务器，再加上它的开源属性，相对而言，处理问题容易形成“统一”的标准。而在Windows平台，服务器和客户端开发人员惯用的调试方法有很大不同。下面结合我的实际经验，整理下常见定位内存泄漏的方法。
注意：我们的分析前提是Release版本，因为在Debug环境下，通过VLD这个库或者CRT库本身的内存泄漏检测函数能够分析出内存泄漏，相对而言比较简单。而服务器有很多问题需要在线上并发压力情况下才出现，因此讨论Debug版调试方法意义不大。
一、对象计数
方法：在对象构造时计数++，析构时–，每隔一段时间打印对象的数量
优点：没有性能开销，几乎不占用额外内存。定位结果精确。
缺点：侵入式方法，需修改现有代码，而且对于第三方库、STL容器、脚本泄漏等因无法修改代码而无法定位。
二、重载new和delete
方法：重载new/delete，记录分配点（甚至是调用堆栈），定期打印。
优点：没有看出
缺点：侵入式方法，需将头文件加入到大量源文件的头部，以确保重载的宏能够覆盖所有的new/delete。记录分配点需要加锁（如果你的程序是多线程），而且记录分配要占用大量内存（也是占用的程序内存）。
三、Hook Windows系统API
方法：使用微软的detours库，hook分配内存的系统Api：HeapAlloc/HeapRealloc/HeapFree（new/malloc的底层调用）,记录分配点，定期打印。
优点：非侵入式方法，无需修改现有文件（hook api后，分配和释放走到自己的钩子函数中），检查全面，对第三方库、脚本库等等都能统计到。
缺点：记录内存需要占用大量内存，而且多线程环境需要加锁。
四、使用LeakDiag检测
微软出品的内存泄漏分析工具，原理同hookapi方式。配合LDGraph可视化展示内存分配数据，更方便查找泄漏。
1.在IDE工程选项里面配置Release版本也生成调试信息，发布时，将pdb文件和exe文件一起发布。
2.程序运行后，打开LeakDiag，设置Symbol path
3.定期Log下目标进程的内存分配情况，通过LDGraph打印分配增长情况，来发现内存泄漏。
优点：同hookapi方法，非侵入式修改，无需做任何代码改动。跟踪全面。可视化分析堆栈一览无余！
缺点：对性能有影响，hook分配加锁，遍历堆栈。但是不会占用目标进程的自身内存。

25.进程与线程的区别

根本区别：进程是操作系统资源分配的基本单位，而线程是任务调度和执行的基本单位
在开销方面：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。
所处环境：在操作系统中能同时运行多个进程（程序）；而在同一个进程（程序）中有多个线程同时执行（通过CPU调度，在每个时间片中只有一个线程执行）
内存分配方面：系统在运行的时候会为每个进程分配不同的内存空间；而对线程而言，除了CPU外，系统不会为线程分配内存（线程所使用的资源来自其所属进程的资源），线程组之间只能共享资源。
包含关系：没有线程的进程可以看做是单线程的，如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的；线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程。

26.C与C++的特点与区别

C语言特点：
1.作为一种面向过程的结构化语言，易于调试和维护；
2.表现能力和处理能力极强，可以直接访问内存的物理地址；
3.C语言实现了对硬件的编程操作，也适合于应用软件的开发；
4.C语言还具有效率高，可移植性强等特点。
C++语言特点：
1.在C语言的基础上进行扩充和完善，使C++兼容了C语言的面向过程特点，又成为了一种面向对象的程序设计语言；
2.可以使用抽象数据类型进行基于对象的编程；
3.可以使用多继承、多态进行面向对象的编程；
4.可以担负起以模版为特征的泛型化编程。
C++与C语言的本质差别：在于C++是面向对象的，而C语言是面向过程的。或者说C++是在C语言的基础上增加了面向对象程序设计的新内容，是对C语言的一次更重要的改革，使得C++成为软件开发的重要工具。

27.单链表的倒置

 1 // 实现一个单向线性链表类
 2 // 1.建立(追加)、测长、正反向打印
 3 // 2.逆转
 4 // 3.获取中间节点值，单次遍历
 5 // 4.有序链表的插入和删除
 6 #include <iostream>
 7 #include <stdexcept>
 8 using namespace std;
 9 class List {
 10 public:
 11         List (void) : m_head (NULL), m_tail (NULL) {}
 12         ~List (void) { //释放剩余节点
 13                 for (Node* next; m_head; m_head = next) {
 14                         next = m_head->m_next;
 15                         delete m_head;
 16                 }
 17         }
 18         void append (int data) {  //追加
 19                 Node* node = new Node (data);
 20                 if (m_tail)
 21                         m_tail->m_next = node;
 22                 else
 23                         m_head = node;
 24                 m_tail = node;//必须
 25         }
 26         size_t size (void) const { //测长
 27                 size_t cn = 0;
 28                 for (Node* node = m_head; node;node = node->m_next)
 29                         ++cn;
 30                 return cn;
 31         }
 32         void print (void) const { //正向打印
 33                 for (Node* node = m_head; node;node = node->m_next)
 34                         cout << node->m_data << ' ';
 35                 cout << endl;
 36         }
 37         void rprint (void) const {  //反向打印
 38                 rprint (m_head);
 39                 cout << endl;
 40         }
 41         /************************************
 42          * void reverse (void) {   //实现逆转
 43          *      reverse (m_head);
 44          *      swap (m_head, m_tail);  //调换
 45          * }
 46          ************************************/
 47         void reverse (void) {  //不用递归逆转
 48                 if (m_head != m_tail) {
 49                         Node* p1 = m_tail = m_head; //
 50                         Node* p2 = p1->m_next;
 51                         Node* p3 = p2->m_next;
 52                         for (p1->m_next=NULL;p3;p3=p3->m_next) {
 53                                 p2->m_next = p1;
 54                                 p1 = p2;
 55                                 p2 = p3;
 56                         }
 57                         (m_head = p2)->m_next = p1; //调整最后两个
 58                 }
 59         }
 60         int middle (void) const { // 获取中间节点值
 61                 if (! m_head || ! m_tail)
 62                         throw underflow_error ("链表下溢！");
 63                 if (m_head == m_tail)//只有一个
 64                         return m_head->m_data;
 65                 Node* mid = m_head;//慢指针
 66                 for (Node* node = m_head;//快指针
 67                         node->m_next && node->m_next->m_next;
 68                         node = node->m_next->m_next) //一次跳两个
 69                         mid = mid->m_next;
 70                 return mid->m_data;
 71         }
 72         // 插入data，仍然保持有序
 73         void insert (int data) {
 74         }
 75         // 删除所有的data，保持有序
 76         void remove (int data) {
 77         }
 78 private: //节点
 79         class Node {
 80         public:
 81                Node (int data = 0, Node* next = NULL) :m_data (data), m_next (next) {}
 82                 int m_data;
 83                 Node* m_next;
 84         };
 85         void rprint (Node* head) const {    //逆向打印
 86                 if (head) {
 87                         rprint (head->m_next); //逆向节点打印，利用函数递归
 88                         cout << head->m_data << ' ';//利用了函数堆栈
 89                 }
 90         }
 91         void reverse (Node* head) {   //逆转 
 92                 if (head && head->m_next) {
 93                         reverse (head->m_next);//
 94                         head->m_next->m_next = head;
 95                         head->m_next = NULL;
 96                 }
 97         }
 98         Node* m_head;
 99         Node* m_tail;
100 };
101 int main (void) {
102         List list;
103         for (int i = 0; i < 11; ++i)
104                 list.append (i);
105         cout << list.size () << endl;
106         list.print ();
107         list.rprint ();
108         list.reverse ();
109         list.print ();
110         cout << list.middle () << endl;
111         return 0;
112 }

28.快速排序的优化、字符串匹配算法

请参考：7.4 快速排序

29.http和https的区别

HTTPS和HTTP的区别：
https协议需要到ca申请证书，一般免费证书很少，需要交费。
http是超文本传输协议，信息是明文传输，https 则是具有安全性的ssl加密传输协议。
http和https使用的是完全不同的连接方式用的端口也不一样，前者是80，后者是443。
http的连接很简单，是无状态的。
HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，要比http协议安全。

30.设计模式（手写单例模式）

  1 // 单例模式（懒汉方式）
  2 #include <iostream>
  3 using namespace std;
  4 class Singleton {
  5 public:
  6         static Singleton& getInst (void) {
  7                 if (! m_inst)
  8                         m_inst = new Singleton;
  9                 ++m_cn;
 10                 return *m_inst;
 11         }
 12         void releaseInst (void) {    //释放实例
 13                 if (m_cn && --m_cn == 0)
 14                         delete this;
 15         }
 16 private:
 17         Singleton (void) {
 18                 cout << "构造：" << this << endl;
 19         }
 20         Singleton (const Singleton&);
 21         ~Singleton (void) {
 22                 cout << "析构：" << this << endl;
 23                 m_inst = NULL;
 24         }
 25         static Singleton* m_inst;
 26         static unsigned int m_cn;
 27 };
 28 Singleton* Singleton::m_inst = NULL;
 29 unsigned int Singleton::m_cn = 0;
 30 int main (void) {
 31         Singleton& s1 = Singleton::getInst ();
 32         Singleton& s2 = Singleton::getInst ();
 33         Singleton& s3 = Singleton::getInst ();
 34         cout << &s1 << ' ' << &s2 << ' ' << &s3 << endl;
 35         s3.releaseInst ();
 36         s2.releaseInst ();
 37         s1.releaseInst ();
 38         return 0;
 39 }

31.手写翻转二叉树

1 //有序二叉树(二叉搜索树)
  2 #include <iostream>
  3 using namespace std;
  4 // 有序二叉树(二叉搜索树)
  5 class Tree {
  6 public:
  7         // 构造过程中初始化为空树
  8         Tree (void) : m_root (NULL), m_size (0) {}
  9         // 析构过程中销毁剩余节点
 10         ~Tree (void) {
 11                 clear (); //函数
 12         }
 13         // 插入数据
 14         void insert (int data) {
 15                 insert (new Node (data), m_root); //插入子树
 16                 ++m_size; //计数
 17         }
 18         // 删除第一个匹配数据，不存在返回false
 19         bool erase  (int data) {  //删除一个
 20                 Node*& node = find (data, m_root);//找
 21                 if (node) {//不空
 22                         // 左插右
 23                 insert (node->m_left, node->m_right); //匹配节点的左子树插到右子树
 24                         Node* temp = node;//备份后一会在去删除
 25                         // 右提升
 26                         node = node->m_right;
 27                         delete temp;//删除匹配节点
 28                         --m_size;//计数
 29                         return true;
 30                 }
 31                 return false;
 32         }
 33         // 删除所有匹配数据
 34         void remove (int data) {
 35                 while (erase (data));//循环删除
 36         }
 37         // 清空树
 38         void clear (void) {
 39                 clear (m_root); //删根
 40                 m_size = 0;
 41         }
 42         // 将所有的_old替换为_new //   替换
 43         void update (int _old, int _new) {
 44                 while (erase (_old)) //删一个_old;这样不会破坏规则
 45                         insert (_new); //插一个_new
 46         }
 47         // 判断data是否存在（查找）
 48         bool find (int data) {
 49                 return find (data, m_root) != NULL;
 50         }
 51         // 中序遍历
 52         void travel (void) { //判断正确与否
 53                 travel (m_root);
 54                 cout << endl;
 55         }
 56         // 获取大小
 57         size_t size (void) {
 58                 return m_size;
 59         }
 60         // 获取树高
 61         size_t height (void) {
 62                 return height (m_root);
 63         }
 64 private:
 65         // 节点
 66         class Node {
 67         public:
 68                 Node (int data) : m_data (data),m_left (NULL), m_right (NULL) {}
 69                 int m_data; // 数据
 70                 Node* m_left; // 左树指针
 71                 Node* m_right; // 右树指针
 72         };
 73     //插入函数
 74         void insert (Node* node, Node*& tree) {//节点，引用为了向成员变量赋值；子树
 75                 if (! tree)//别名//空
 76                         tree = node; //父节点的下边；空//也是递归终止条件
 77                 else if (node) {//节点
 78                         if (node->m_data < tree->m_data) //插左边
 79                                 insert (node, tree->m_left); //递归，插左边
 80                         else
 81                                 insert (node, tree->m_right);//递归，插右边
 82                 }
 83         }
 84         // 返回子树tree中值与data相匹配的节点的父节点中指向该节点的成员变量                      的别名（返回的是指向该节点的别名（引用；笔记中的/\））
 85         Node*& find (int data, Node*& tree) { //子树；返回引用
 86                 if (! tree) //空
 87                         return tree;//找不到//返回指针（既是别名）
 88                 else
 89                 if (data == tree->m_data)//匹配的情况
 90                         return tree;//已经匹配
 91                 else
 92                 if (data < tree->m_data)//不匹配
 93                         return find (data, tree->m_left); //递归，在左子树里面找
 94                 else
 95                         return find (data, tree->m_right); //否则在右子树里找
 96         }
 97     //删除子树
 98         void clear (Node*& tree) {
 99                 if (tree) { //递归
100                         clear (tree->m_left);//终止条件，自动删到叶节点
101                         clear (tree->m_right);
102                         delete tree;
103                         tree = NULL;
104                 }
105         }
106     //中序遍历
107         void travel (Node* tree) {
108                 if (tree) { //此一下顺序决定遍历方式 // 非空为终止条件
109                         travel (tree->m_left);//递归
110                         cout << tree->m_data << ' ';
111                         travel (tree->m_right); //递归
112                 }
113         }
114     //获取树高
115         size_t height (Node* tree) {
116                 if (tree) {
117                         size_t lh = height (tree->m_left);//求左子树树高
118                         size_t rh = height (tree->m_right);//求右子树树高
119                         return (lh > rh ? lh : rh)+ 1;//取大加一
120                 }
121                 return 0;//空的时候
122         }
123     //成员变量
124         Node* m_root; // 树根
125         size_t m_size; // 大小
126  };
127  int main (void) {
128         Tree tree;
129         tree.insert (50);
130         tree.insert (70);
131         tree.insert (20);
132         tree.insert (60);
133         tree.insert (40);
134         tree.insert (30);
135         tree.insert (10);
136         tree.insert (90);
137         tree.insert (80);
138         tree.travel ();//中序遍历
139         cout << tree.size () << ' ' << tree.height ()<< endl;
140         tree.erase (70);
141         tree.travel ();
142         tree.insert (70);
143         tree.insert (70);
144         tree.insert (70);
145         tree.travel ();
146         tree.remove (70);
147         tree.travel ();
148         tree.insert (40);
149         tree.insert (40);
150         tree.travel ();
151         tree.update (40, 69);
152         tree.travel ();
153         cout << boolalpha << tree.find (50) << endl;//boolalpha输出判断真假
154         cout << tree.find (55) << endl;
155         tree.clear ();
156         tree.travel ();
157         return 0;
158 }

32.手写strcpy的实现

char *strcpy(char *strDes, const char *string)
{
    if (string == NULL&&strDes == NULL)
        return NULL;
    char* address = strDes;
    while (*string != '\0')
        *(strDes++) = *(string++);
    *strDes = '\0';//一定注意最后结束时一定要加一个\0结尾；
    return address;//返回保存的strDes首地址;
}

33.Mysql数据库引擎的介绍

1.ISAM
    在设计ISAM之前就考虑到查询的次数要大于数据更新的次数，因此ISAM引擎的读取的效率是非常的快的，不占用大量的内存和存储空间，但是不支持事物的处理，下面分析ISAM引擎的优缺点。
    ISAM的优点：
        读取数据速度快、不占用大量的内存和存储资源
    ISAM的缺点：
        不支持事物
        不容错
    使用ISAM引擎的注意点：
        由于他不支持事物的处理，并且不容错，所以必要备份数据。
2.MyISAM
    MyISAM是MySQL对于ISAM的扩展引擎，在MySQL5.6以后的版本出现，简单来说ISAM引擎有的东西，它都有，MyISAM提供了索引和字段管理的大量功能，MyISAM还提供了表格锁定的机制用来优化多个并发的读写操作、但是有代价的，要经常运行 OPTIMIZE TABLE 命令来恢复优化过机制所浪费的空间、MyISAM知道自己的缺点所以提供了优化工具、比如MyISAMCHK工具用来恢复浪费的空间。
    MyISAM的优点：
        增强了ISAM引擎的功能，增加了索引、表格锁的机制优化并发读写
    MyISAM的缺点：
        因为有了表格锁的机制、最大的缺陷就是不能在表损坏后恢复数据，和ISAM一样不支持事物，数据量越大、写入效率越低。
    使用MyISAM引擎的注意点：
        数据要备份、虽然有索引提升效率，但是要正确的使用索引，如果索引的字段越多维护索引的信息就会越多，随着数据量的增加，相对的效率也会降低。
        使用MyISAM引擎生成的文件
        如果使用MyISAM数据库引擎，会生成三个文件：
        .frm:表结构信息
        .MYD:数据文件
        .MYI:表的索引信息
3.InnoDB引擎
    InnoDB数据库引擎是直接造就MySQL辉煌的引擎，他能弥补ISAM、MyISAM的不足之处，他能支持事物的处理、也能支持外键、尽管比ISAM、MyISAM的查询速度慢一点，但是自身‘全能’的优点完全可以胜出，现在MySQL5.6以上的版本默认的数据库引擎是InnoDB引擎MySQL，官方对InnoDB是这样解释的：InnoDB给MySQL提供了具有提交、回滚和崩溃恢复能力的事务安全（ACID兼容）存储引擎。InnoDB锁定在行级并且也在SELECT语句提供一个Oracle风格一致的非锁定读，这些特色增加了多用户部署的性能。没有在InnoDB中扩大锁定的需要，因为在InnoDB中行级锁定适合非常小的空间。InnoDB也支持FOREIGN KEY强制。在SQL查询中，你可以自由地将InnoDB类型的表与其它MySQL的表的类型混合起来，甚至在同一个查询中也可以混合。
    InnoDB的优点：
        遵循ACID模式设计，具有事务，回滚和保护用户数据的崩溃恢复能力，InnoDB为大数据量发挥最大性能而设计的，针对提升CPU的效率而生，其它任何基于磁盘的关系数据库引擎都不能和它做比较。
InnoDB的缺点：
    没有MyISAM、ISAM查询速度来的快。
InnoDB引擎的特点:
    支持事务
    数据多版本读取（InnoDB+MyISAM+ISAM）
    锁定机制的改进
    实现外键
innodb与myisam区别：
    InnoDB支持事务，MyISAM不支持，对于InnoDB每一条SQL语言都默认封装成事务，自动提交，这样会影响速度，所以最好把多条SQL语言放在begin transaction和commit之间，组成一个事务；
    InnoDB支持外键，而MyISAM不支持。对一个包含外键的InnoDB表转为MYISAM会失败；
    InnoDB是聚集索引，数据文件是和索引绑在一起的，必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。而MyISAM是非聚集索引，数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。
    InnoDB不保存表的具体行数，执行select count(*) from table时需要全表扫描。而MyISAM用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快；
    InnoDB从1.2.x开始支持全文索引技术（FULLTEXT），myisam也支持全文索引，查询效率上myisam要高；

34.一个只含有虚函数类的size大小、含有虚函数的虚函数表存放位置

4个字节/对象的前四位

35.手画字典树

特点：
根节点不包含字符，除根节点外每一个节点都只包含一个字符； 
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 
每个节点的所有子节点包含的字符都不相同。

36.快速排序（代码）

 45 void quickSort (int data[], size_t left,size_t right) {  //左右边界
 46         size_t p = (left + right) / 2;//取中间
 47         int pivot = data[p]; //中间数
 48         for (size_t i = left, j = right; i < j;) {
 49                 while (! (i>= p || pivot < data[i])) // 不能碰上、比他大
 50                         ++i;
 51                 if (i < p) {
 52                         data[p] = data[i];
 53                         p = i; //p放到i上
 54                 }
 55                 while (! (j <= p || data[j] < pivot))
 56                         --j;
 57                 if (j > p) {
 58                         data[p] = data[j];
 59                         p = j;
 60                 }
 61         }
 62         data[p] = pivot;//三点一线时
 63         if (p - left > 1)//左侧分组；也是终止条件
 64                 quickSort (data, left, p - 1);
 65         if (right - p > 1)//右侧分组
 66                 quickSort (data, p + 1, right);
 67 }

37.游标种类

游标分为动态游标(强类型和弱类型)和静态游标(显性和隐性)

5.7 游标

42.进程间通讯的方式及优缺点

1)管道
管道分为有名管道和无名管道
无名管道是一种半双工的通信方式,数据只能单向流动,而且只能在具有亲缘关系的进程间使用.进程的亲缘关系一般指的是父子关系。无明管道一般用于两个不同进程之间的通信。当一个进程创建了一个管道,并调用fork创建自己的一个子进程后,父进程关闭读管道端,子进程关闭写管道端,这样提供了两个进程之间数据流动的一种方式。
有名管道也是一种半双工的通信方式,但是它允许无亲缘关系进程间的通信。
无名管道：优点：简单方便；缺点：1）局限于单向通信2）只能创建在它的进程以及其有亲缘关系的进程之间;3）缓冲区有限；
有名管道：优点：可以实现任意关系的进程间的通信；缺点：1）长期存于系统中，使用不当容易出错；2）缓冲区有限
2)信号量
信号量是一个计数器,可以用来控制多个线程对共享资源的访问.,它不是用于交换大批数据,而用于多线程之间的同步.它常作为一种锁机制,防止某进程在访问资源时其它进程也访问该资源.因此,主要作为进程间以及同一个进程内不同线程之间的同步手段.
优点：可以同步进程；缺点：信号量有限
3)信号
信号是一种比较复杂的通信方式,用于通知接收进程某个事件已经发生.
4)消息队列
消息队列是消息的链表,存放在内核中并由消息队列标识符标识.消息队列克服了信号传递信息少,管道只能承载无格式字节流以及缓冲区大小受限等特点.消息队列是UNIX下不同进程之间可实现共享资源的一种机制,UNIX允许不同进程将格式化的数据流以消息队列形式发送给任意进程.对消息队列具有操作权限的进程都可以使用msget完成对消息队列的操作控制.通过使用消息类型,进程可以按任何顺序读信息,或为消息安排优先级顺序.
优点：可以实现任意进程间的通信，并通过系统调用函数来实现消息发送和接收之间的同步，无需考虑同步问题，方便；缺点：信息的复制需要额外消耗CPU的时间，不适宜于信息量大或操作频繁的场合
5)共享内存
共享内存就是映射一段能被其他进程所访问的内存,这段共享内存由一个进程创建,但多个进程都可以访问.共享内存是最快的IPC(进程间通信)方式,它是针对其它进程间通信方式运行效率低而专门设计的.它往往与其他通信机制,如信号量,配合使用,来实现进程间的同步与通信.
优点：无须复制，快捷，信息量大；缺点：1）通信是通过将共无法实现享空间缓冲区直接附加到进程的虚拟地址空间中来实现的，因此进程间的读写操作的同步问题；2)利用内存缓冲区直接交换信息，内存的实体存在于计算机中，只能同一个计算机系统中的诸多进程共享，不方便网络通信
6)套接字：可用于不同及其间的进程通信
优点：1）传输数据为字节级，传输数据可自定义，数据量小效率高；2）传输数据时间短，性能高；3) 适合于客户端和服务器端之间信息实时交互；4) 可以加密,数据安全性强
缺点：1) 需对传输的数据进行解析，转化成应用级的数据

43.GDB常用命令

编译程序时需要加上-g，之后才能用gdb进行调试：gcc -g main.c -o main
gdb中命令：
回车键：重复上一命令
（gdb）help：查看命令帮助，具体命令查询在gdb中输入help + 命令,简写h
（gdb）run：重新开始运行文件（run-text：加载文本文件，run-bin：加载二进制文件）,简写r
（gdb）start：单步执行，运行程序，停在第一执行语句
（gdb）list：查看原代码（list-n,从第n行开始查看代码。list+ 函数名：查看具体函数）,简写l
（gdb）set：设置变量的值
（gdb）next：单步调试（逐过程，函数直接执行）,简写n
（gdb）step：单步调试（逐语句：跳入自定义函数内部执行）,简写s
（gdb）backtrace：查看函数的调用的栈帧和层级关系,简写bt
（gdb）frame：切换函数的栈帧,简写f
（gdb）info：查看函数内部局部变量的数值,简写i
（gdb）finish：结束当前函数，返回到函数调用点
（gdb）continue：继续运行,简写c
（gdb）print：打印值及地址,简写p
（gdb）quit：退出gdb,简写q
（gdb）break+num：在第num行设置断点,简写b
（gdb）info breakpoints：查看当前设置的所有断点
（gdb）delete breakpoints num：删除第num个断点,简写d
（gdb）display：追踪查看具体变量值
（gdb）undisplay：取消追踪观察变量
（gdb）watch：被设置观察点的变量发生修改时，打印显示
（gdb）i watch：显示观察点
（gdb）enable breakpoints：启用断点
（gdb）disable breakpoints：禁用断点
（gdb）x：查看内存x/20xw 显示20个单元，16进制，4字节每单元
（gdb）run argv[1] argv[2]：调试时命令行传参
（gdb）set follow-fork-mode child#Makefile项目管理：选择跟踪父子进程（fork()）
   core文件：先用$ ulimit -c 1024 开启core，当程序出错会自动生成core文件。调试时 gdb a.out core
ctrl+c：退出输入

44.hash类型及实现方式

6.5 HashMap

45.常用的设计模式

13.1 设计模式

46.MySQL数据库查询结果过大解决内存溢出的解决方案

正常来说，一般是不会出现这种情况的，但也不能保证，偶尔有这种情况发生，解决方案如下：

1.使用分页查询语句

因为分页查询每次只会查询少量数据，所以不会占用太多内存，而且数据量很大的时候，分页查询会节约一些时间的。

    String sql = " SELECT uid，uname  FROM t_user LIMIT ?,? " ;
    PreparedStatement  ps = con.prepareStatement(sql) ;
    int pageSize = 10000; 
    int pageId = 0; 
    do { 
        pst.setInt(1, pageId * pageSize); 
        pst.setInt(2, pageSize); 
        ResultSet rs = pst.executeQuery();
        boolean isEmpty = true; 
        while (rs.next()) { 
             isEmpty = false; 
             id = rs.getInt(1); 
             name = rs.getString(2); 
        } 
        if (isEmpty) { 
            break; 
        } 
        pageId++; 
    } while (true); 
    con.close(); 
} catch (SQLException e) { 
    e.printStackTrace(); 
}

2.添加url参数配置

在jdbc的URL上加两个参数就OK，成功解决内存溢出的问题。 “jdbc:mysql://localhost:3306/db3?useCursorFetch=true&defaultFetchSize=100”;

( 解释一下Fetch，当我们执行一个SQL查询语句的时候，需要在客户端和服务器端都打开一个游标，并且分别申请一块内存空间，作为存放查询的数据的一个缓冲区。这块内存区，存放多少条数据就由fetchsize来决定，同时每次网络包会传送fetchsize条记录到客户端 )

47.线程安全

在多线程程序开发当中,可以使用一些编程技巧规避线程安全问题或减少使用锁导致的额外开销.

1.线程封闭

当多个线程访问修改同一对象时需要使用同步机制,其中一种规避方法是不共享任何数据.参数传入线程时传入变量的复制.或所有变量/对象都从线程当中创建.这种方法将所有线程所能触及的变量都封闭在线程内部本身,即使被封闭的对象不是线程安全,也可以达到线程安全的效果.

2.实例封闭

当一个对象被封闭在另一个新创建的对象当中时,能访问该对象的所有代码路径都是已知的.例如struct2中的Action就是使用实例封闭的方式实现线程安全.框架保证每一个请求都创建一个全新的Action对象,从而将线程安全委托给实例封闭

3.栈封闭

栈封闭的使用方式在三层架构当中非常常用.通常使用在封闭的方法当中,方法只操作传入参数进行业务处理.例如service只操作通过上层传入的参数调用DAO层,SpringMVC由于Controller是单例对象,所有的操作都在方法级别进行栈封闭从而实现线程安全.

4.ThreadLocal

ThreadLocal在多线程的Web系统中应用非常广泛,如Struct2的ActionContext.JSF的FacesContext.Spring的Transactional都是通过ThreadLocal实现.ThreadLocal允许被置入的对象访问域提升到线程的级别.但使用ThreadLocal时需要注意,这是一种变量侵入式的设计.ThreadLocal的设置位置可能和读取位置相隔甚远,甚至无法从代码调用的上下文中寻找到设置该变量的位置.这导致业务逻辑依赖ThreadLocal.

5.不变对象

不变对象天生对多线程环境友好.当一个对象创建后就没有任何代码路径会修改对象中的属性.由于没有提供任何方法对其属性修改,因此可以自由地在多线程中共享访问.但需要注意并非不提供setter方法就视为不变对象,而是所有暴露出去的方法中没有任何一个会对属性进行修改.对象的所有属性在创建对象时已经确定.并且不会有改变

6.委托并发容器发布对象

Java当中提供了很多线程安全的容器.当一个对象通过线程安全容器进行发布时,我们可以认为这个对象已被安全的发布出去并处于线程安全状态.

总结:

以上实现线程安全的方式都不曾提及公有的静态变量.而公有的静态变量往往是容易被忽略导致线程安全问题发生的原因.包括一些全局的作用域例如HttpServletRequest操作Application作用域时,由于Application是全局共享的,所以当操作Application时仍然需要同步操作.

48.判断线程安全

Java对线程的支持有如一把双刃剑,线程安全性可能是非常复杂的.在没有足够的同步情况下,多个线程中得操作执行顺序是不可预测的,甚至会发生奇怪的结果.而分辨所编写的代码/程序/类是否线程安全或代码运行结果是否一直正确,是每个多线程开发人员必须具备的能力.

对于判断所编写的类是否线程安全,可以参考以下几个方面

1.该对象是否会被多个线程访问修改

假如对象会被多个线程访问,例如各种的Context或Factory,如Hibernate中的SessionFactory.SessionFactory是Session的生产工厂,一般对单库应用全局只需要保持一个SessionFactory,但对其属性的修改则是可以多个线程进行修改,因此若然没有足够的加锁机制,SessionFactory是一个线程不安全的对象.

2.注意静态变量

请注意变量一词,由于静态变量是属于该类和该类下所有对象共享,可直接通过类名访问/修改,因此在多线程的环境下.可以断言所有对静态变量的修改都会发生线程安全问题.除非静态变量为并发容器,通过委托线程安全容器发布对象.

3.改变对象内部状态的方法调用

请回看第一点,当一个对象的属性会被多个线程修改时,需要进行同步操作.但并不代表不提供某属性的setter方法就可以万事安心.而真正需要关注的是,哪些内部方法的调用或对外公开的方法调用会导致对象内部属性(状态)的改变.

4.单例

相信大家在学习编程的时候都知道懒加载单例存在线程安全问题.先检查后操作是多线程开发中一个经常大意忽略的问题.因为并行程序共享的变量无时无刻都有可能发生变化,这涉及到数据失效性的问题.而单例由于是全局唯一,所以单例对象会被所有线程所访问,而单例中的属性若然允许进行修改,则会引发线程安全问题.当对象在Spring管理下默认是Singleton,当我们在三层架构开发下.在DAO(Repository)或Service中声明全局变量并对其进行操作,同样会引发线程安全问题.

总结:

不必要的同步会带来性能损耗,判断失误缺少同步系统将失去正确性.判断自己开发的类是否线程安全是每一个多线程开发人员的必修课.

49.翻转字符串里的单词

题目描述：

给定一个字符串，逐个翻转字符串中的每个单词。

示例:

输入: "the sky is blue",
输出: "blue is sky the".

说明:

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。

解题思路：

1、先反转整个字符串，变成(两个空格)eulb(一个空格)si(两个空格)yks(三个空格)eht(两个空格)。

2、把后面的字符往前挪，去掉多余的空格，变成eulb(一个空格)si(一个空格)yks(一个空格)eht

3、在单词内部进行反转，变成blue(一个空格)is(一个空格)sky(一个空格)the。

所以具体代码如下：（附详解）

#include<iostream>
using namespace std;
void reverseWords(string& sStr){
    int iLen = sStr.size(),iIndex=0;
    reverse(sStr.begin(),sStr.end());//整体翻转
    for (int i=0;i<iLen;++i)
    {
        if (' '!=sStr[i])
        {
            if(0!=iIndex)
                sStr[iIndex++]=' ';//单词结束补空格
            int j = i;
            while (j<iLen && ' '!=sStr[j])
                sStr[iIndex++]=sStr[j++];//找到整个单词
            reverse(sStr.begin()+iIndex-(j-i),sStr.begin()+iIndex);//对单词翻转
            i = j;
        }
    }
    sStr.resize(iIndex);//调整string大小
}
int main(){    
    char acStr[100]="";
    gets(acStr);
    //字符串倒置
    //strrev(acStr);
    string sStr = acStr;
    reverseWords(sStr);
    cout<<sStr.c_str()<<endl;
    system("pause");
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int main(){
    string s;
    vector<string> vs;
    while(cin >> s)
        vs.push_back(s);
    for(int i = vs.size()-1; i > 0; --i)
        cout << vs[i] << " ";
    cout << vs[0] << endl;
    return 0;
}

50.TCP协议-如何保证传输可靠性

TCP协议传输的特点主要就是面向字节流、传输可靠、面向连接。

TCP协议保证数据传输可靠性的方式主要有：

校验和
确认应答与序列号
超时重传
连接管理
流量控制
拥塞控制

1、校验和

计算方式：在数据传输的过程中，将发送的数据段都当做一个16位的整数。将这些整数加起来。并且前面的进位不能丢弃，补在后面，最后取反，得到校验和。

发送方：在发送数据之前计算检验和，并进行校验和的填充。

接收方：收到数据后，对数据以同样的方式进行计算，求出校验和，与发送方的进行比对。

注意：如果接收方比对校验和与发送方不一致，那么数据一定传输有误。但是如果接收方比对校验和与发送方一致，数据不一定传输成功。

2、确认应答与序列号

序列号：TCP传输时将每个字节的数据都进行了编号，这就是序列号。

确认应答：TCP传输的过程中，每次接收方收到数据后，都会对传输方进行确认应答。也就是发送ACK报文。这个ACK报文当中带有对应的确认序列号，告诉发送方，接收到了哪些数据，下一次的数据从哪里发。

序列号的作用不仅仅是应答的作用，有了序列号能够将接收到的数据根据序列号排序，并且去掉重复序列号的数据。这也是TCP传输可靠性的保证之一。

3、超时重传

在进行TCP传输时，由于确认应答与序列号机制，也就是说发送方发送一部分数据后，都会等待接收方发送的ACK报文，并解析ACK报文，判断数据是否传输成功。如果发送方发送完数据后，迟迟没有等到接收方的ACK报文，这该怎么办呢？而没有收到ACK报文的原因可能是什么呢？

首先，发送方没有介绍到响应的ACK报文原因可能有两点：

数据在传输过程中由于网络原因等直接全体丢包，接收方根本没有接收到。

接收方接收到了响应的数据，但是发送的ACK报文响应却由于网络原因丢包了。

TCP在解决这个问题的时候引入了一个新的机制，叫做超时重传机制。简单理解就是发送方在发送完数据后等待一个时间，时间到达没有接收到ACK报文，那么对刚才发送的数据进行重新发送。如果是刚才第一个原因，接收方收到二次重发的数据后，便进行ACK应答。如果是第二个原因，接收方发现接收的数据已存在（判断存在的根据就是序列号，所以上面说序列号还有去除重复数据的作用），那么直接丢弃，仍旧发送ACK应答。

那么发送方发送完毕后等待的时间是多少呢？如果这个等待的时间过长，那么会影响TCP传输的整体效率，如果等待时间过短，又会导致频繁的发送重复的包。如何权衡？

由于TCP传输时保证能够在任何环境下都有一个高性能的通信，因此这个最大超时时间（也就是等待的时间）是动态计算的。

在Linux中（BSD Unix和Windows下也是这样）超时以500ms为一个单位进行控制，每次判定超时重发的超时时间都是500ms的整数倍。重发一次后，仍未响应，那么等待2500ms的时间后，再次重传。等待4500ms的时间继续重传。以一个指数的形式增长。累计到一定的重传次数，TCP就认为网络或者对端出现异常，强制关闭连接。

4、连接管理

连接管理就是三次握手与四次挥手的过程，在前面详细讲过这个过程，这里不再赘述。保证可靠的连接，是保证可靠性的前提。

5、流量控制

接收端在接收到数据后，对其进行处理。如果发送端的发送速度太快，导致接收端的结束缓冲区很快的填充满了。此时如果发送端仍旧发送数据，那么接下来发送的数据都会丢包，继而导致丢包的一系列连锁反应，超时重传呀什么的。而TCP根据接收端对数据的处理能力，决定发送端的发送速度，这个机制就是流量控制。

在TCP协议的报头信息当中，有一个16位字段的窗口大小。在介绍这个窗口大小时我们知道，窗口大小的内容实际上是接收端接收数据缓冲区的剩余大小。这个数字越大，证明接收端接收缓冲区的剩余空间越大，网络的吞吐量越大。接收端会在确认应答发送ACK报文时，将自己的即时窗口大小填入，并跟随ACK报文一起发送过去。而发送方根据ACK报文里的窗口大小的值的改变进而改变自己的发送速度。如果接收到窗口大小的值为0，那么发送方将停止发送数据。并定期的向接收端发送窗口探测数据段，让接收端把窗口大小告诉发送端。

注：16位的窗口大小最大能表示65535个字节（64K），但是TCP的窗口大小最大并不是64K。在TCP首部中40个字节的选项中还包含了一个窗口扩大因子M，实际的窗口大小就是16为窗口字段的值左移M位。每移一位，扩大两倍。

6、拥塞控制

TCP传输的过程中，发送端开始发送数据的时候，如果刚开始就发送大量的数据，那么就可能造成一些问题。网络可能在开始的时候就很拥堵，如果给网络中在扔出大量数据，那么这个拥堵就会加剧。拥堵的加剧就会产生大量的丢包，就对大量的超时重传，严重影响传输。

所以TCP引入了慢启动的机制，在开始发送数据时，先发送少量的数据探路。探清当前的网络状态如何，再决定多大的速度进行传输。这时候就引入一个叫做拥塞窗口的概念。发送刚开始定义拥塞窗口为 1，每次收到ACK应答，拥塞窗口加 1。在发送数据之前，首先将拥塞窗口与接收端反馈的窗口大小比对，取较小的值作为实际发送的窗口。

拥塞窗口的增长是指数级别的。慢启动的机制只是说明在开始的时候发送的少，发送的慢，但是增长的速度是非常快的。为了控制拥塞窗口的增长，不能使拥塞窗口单纯的加倍，设置一个拥塞窗口的阈值，当拥塞窗口大小超过阈值时，不能再按照指数来增长，而是线性的增长。在慢启动开始的时候，慢启动的阈值等于窗口的最大值，一旦造成网络拥塞，发生超时重传时，慢启动的阈值会为原来的一半（这里的原来指的是发生网络拥塞时拥塞窗口的大小），同时拥塞窗口重置为 1。

拥塞控制是TCP在传输时尽可能快的将数据传输，并且避免拥塞造成的一系列问题。是可靠性的保证，同时也是维护了传输的高效性。

参考链接

51.C++中重载、重写（覆盖）和隐藏的区别

一、基本概念：

1、重载：是指同一可访问区内被声明的几个具有不同参数列（参数的类型，个数，顺序不同）的同名函数，根据参数列表确定调用哪个函数，重载不关心函数返回类型。

1 class A{
2 public:
3   void test(int i);
4   void test(double i);//overload
5   void test(int i, double j);//overload
6   void test(double i, int j);//overload
7   int test(int i);         //错误，非重载。注意重载不关心函数返回类型。
8 };

2、隐藏：是指派生类的函数屏蔽了与其同名的基类函数，注意只要同名函数，不管参数列表是否相同，基类函数都会被隐藏。

 1 #include "stdafx.h"
 2 #include "iostream"
 3 
 4 using namespace std;
 5 
 6 class Base
 7 {
 8 public:
 9     void fun(double ,int ){ cout << "Base::fun(double ,int )" << endl; }
10 };
11 
12 class Derive : public Base
13 {
14 public:
15     void fun(int ){ cout << "Derive::fun(int )" << endl; }
16 };
17 
18 int main()
19 {
20     Derive pd;
21     pd.fun(1);//Derive::fun(int )
22     pb.fun(0.01, 1);//error C2660: “Derive::fun”: 函数不接受 2 个参数
23 
24     Base *fd = &pd;
25     fd->fun(1.0,1);//Base::fun(double ,int);
26     fd->fun(1);//error 
27     system("pause");
28     return 0;
29 }

3、重写(覆盖)：是指派生类中存在重新定义的函数。其函数名，参数列表，返回值类型，所有都必须同基类中被重写的函数一致。只有函数体不同（花括号内），派生类调用时会调用派生类的重写函数，不会调用被重写函数。重写的基类中被重写的函数必须有virtual修饰。

注：fd为基类的指针，这是调用fun是基类的函数

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class Base
 6 {
 7 public:
 8     virtual void fun(int i){ cout << "Base::fun(int) : " << i << endl;}
 9 };
10 
11 class Derived : public Base
12 {
13 public:
14     virtual void fun(int i){ cout << "Derived::fun(int) : " << i << endl;}
15 };
16 int main()
17 {
18     Base b;
19     Base * pb = new Derived();
20     pb->fun(3);//Derived::fun(int)
21 
22     system("pause");
23     return 0;
24 }

二、区别

1、重载和重写的区别：

（1）范围区别：重写和被重写的函数在不同的类中，重载和被重载的函数在同一类中。

（2）参数区别：重写与被重写的函数参数列表一定相同，重载和被重载的函数参数列表一定不同。

（3）virtual的区别：重写的基类必须要有virtual修饰，重载函数和被重载函数可以被virtual修饰，也可以没有。

2、隐藏和重写，重载的区别：

（1）与重载范围不同：隐藏函数和被隐藏函数在不同类中。

（2）参数的区别：隐藏函数和被隐藏函数参数列表可以相同，也可以不同，但函数名一定同；当参数不同时，无论基类中的函数是否被virtual修饰，基类函数都是被隐藏，而不是被重写。

 1 #include "stdafx.h"
 2 #include <iostream>
 3 
 4 using namespace std;
 5 
 6 class Base
 7 {
 8 public:
 9     virtual void f(float x){ cout << "Base::f(float) " << x << endl; }
10     void g(float x){ cout << "Base::g(float) " << x << endl; }
11     void h(float x){ cout << "Base::h(float) " << x << endl; }
12 };
13 
14 class Derived : public Base
15 {
16 public:
17     virtual void f(float x){ cout << "Derived::f(float) " << x << endl; }
18     void g(int x){ cout << "Derived::g(int) " << x << endl; }
19     void h(float x){ cout << "Derived::h(float) " << x << endl; }
20 };
21 
22 int main(void)
23 {
24     Derived d;
25     Base *pb = &d;
26     Derived *fd = &d;
27     // Good : behavior depends solely on type of the object
28     pb->f(3.14f); //Derived::f(float) 3.14
29     fd->f(3.14f); //Derived::f(float) 3.14
30 
31     // Bad : behavior depends on type of the pointer
32     pb->g(3.14f); //Base::g(float) 3.14
33     fd->g(3.14f); //Derived::g(int) 3
34 
35     // Bad : behavior depends on type of the pointer
36     pb->h(3.14f); //Base::h(float) 3.14
37     fd->h(3.14f); //Derived::h(float) 3.14
38 
39     system("pause");
40     return 0;
41 }

（1）函数Derived::f(float)覆盖了Base::f(float)。

（2）函数Derived::g(int)隐藏了Base::g(float)，而不是重载。

（3）函数Derived::h(float)隐藏了Base::h(float)，而不是覆盖。

52.什么是 RPC 框架

1、本地过程调用

RPC就是要像调用本地的函数一样去调远程函数。在研究RPC前，我们先看看本地调用是怎么调的。假设我们要调用函数Multiply来计算lvalue * rvalue的结果:

1 int Multiply(int l, int r) {
2    int y = l * r;
3    return y;
4 }
5 
6 int lvalue = 10;
7 int rvalue = 20;
8 int l_times_r = Multiply(lvalue, rvalue);

那么在第8行时，我们实际上执行了以下操作：

将 lvalue 和 rvalue 的值压栈
进入Multiply函数，取出栈中的值10 和 20，将其赋予 l 和 r
执行第2行代码，计算 l * r ，并将结果存在 y
将 y 的值压栈，然后从Multiply返回
第8行，从栈中取出返回值 200 ，并赋值给 l_times_r

以上5步就是执行本地调用的过程。（20190116注：以上步骤只是为了说明原理。事实上编译器经常会做优化，对于参数和返回值少的情况会直接将其存放在寄存器，而不需要压栈弹栈的过程，甚至都不需要调用call，而直接做inline操作。仅就原理来说，这5步是没有问题的。）

2、远程过程调用带来的新问题

在远程调用时，我们需要执行的函数体是在远程的机器上的，也就是说，Multiply是在另一个进程中执行的。这就带来了几个新问题：

Call ID映射。我们怎么告诉远程机器我们要调用Multiply，而不是Add或者FooBar呢？在本地调用中，函数体是直接通过函数指针来指定的，我们调用Multiply，编译器就自动帮我们调用它相应的函数指针。但是在远程调用中，函数指针是不行的，因为两个进程的地址空间是完全不一样的。所以，在RPC中，所有的函数都必须有自己的一个ID。这个ID在所有进程中都是唯一确定的。客户端在做远程过程调用时，必须附上这个ID。然后我们还需要在客户端和服务端分别维护一个 {函数 <—> Call ID} 的对应表。两者的表不一定需要完全相同，但相同的函数对应的Call ID必须相同。当客户端需要进行远程调用时，它就查一下这个表，找出相应的Call ID，然后把它传给服务端，服务端也通过查表，来确定客户端需要调用的函数，然后执行相应函数的代码。
序列化和反序列化。客户端怎么把参数值传给远程的函数呢？在本地调用中，我们只需要把参数压到栈里，然后让函数自己去栈里读就行。但是在远程过程调用时，客户端跟服务端是不同的进程，不能通过内存来传递参数。甚至有时候客户端和服务端使用的都不是同一种语言（比如服务端用C++，客户端用Java或者Python）。这时候就需要客户端把参数先转成一个字节流，传给服务端后，再把字节流转成自己能读取的格式。这个过程叫序列化和反序列化。同理，从服务端返回的值也需要序列化反序列化的过程。
网络传输。远程调用往往用在网络上，客户端和服务端是通过网络连接的。所有的数据都需要通过网络传输，因此就需要有一个网络传输层。网络传输层需要把Call ID和序列化后的参数字节流传给服务端，然后再把序列化后的调用结果传回客户端。只要能完成这两者的，都可以作为传输层使用。因此，它所使用的协议其实是不限的，能完成传输就行。尽管大部分RPC框架都使用TCP协议，但其实UDP也可以，而gRPC干脆就用了HTTP2。Java的Netty也属于这层的东西。

有了这三个机制，就能实现RPC了，具体过程如下：

// Client端 
//    int l_times_r = Call(ServerAddr, Multiply, lvalue, rvalue)
1. 将这个调用映射为Call ID。这里假设用最简单的字符串当Call ID的方法
2. 将Call ID，lvalue和rvalue序列化。可以直接将它们的值以二进制形式打包
3. 把2中得到的数据包发送给ServerAddr，这需要使用网络传输层
4. 等待服务器返回结果
5. 如果服务器调用成功，那么就将结果反序列化，并赋给l_times_r
// Server端
1. 在本地维护一个Call ID到函数指针的映射call_id_map，可以用std::map<std::string, std::function<>>
2. 等待请求
3. 得到一个请求后，将其数据包反序列化，得到Call ID
4. 通过在call_id_map中查找，得到相应的函数指针
5. 将lvalue和rvalue反序列化后，在本地调用Multiply函数，得到结果
6. 将结果序列化后通过网络返回给Client

所以要实现一个RPC框架，其实只需要按以上流程实现就基本完成了。

其中：

Call ID映射可以直接使用函数字符串，也可以使用整数ID。映射表一般就是一个哈希表。
序列化反序列化可以自己写，也可以使用Protobuf或者FlatBuffers之类的。
网络传输库可以自己写socket，或者用asio，ZeroMQ，Netty之类。

参考链接

打赏

License

本作品由Simon（http://www.uusystem.com）创作，采用知识共享署名-非商业性使用-禁止演绎 2.5 中国大陆许可协议进行许可。欢迎转载，但任何转载必须保留完整文章，在显要地方显示此声明以及原文链接。如您有任何疑问或者授权方面的协商，请邮件：postmaster@uusystem.com。

17 QA

17 QA

1.平衡树（红黑树）/B树、B+树、B*树、DOM树的实现模拟

2.索引index、联合索引

3.贪心算法与其弊端

4.进程间通信方式、TCP/UDP建立连接的步骤、三次握手四次挥手、TCP的超时等待

5.Mysql数据库中join的类型与区别、含义

6.线程池的了解、线程池对线程的管理方式（初始化线程的方法、线程创建后的管理、指派任务的方式）、优点、调度处理方式和保护任务队列的方式

7.对象复用的了解

8.零拷贝的了解

9.Linux的I/O模型

10.异步I/O的详细解释（同步I/O与异步I/O的区别，包括定义异步I/O、I/O实质上的交谁完成、如何实现异步）、I/O的复用技术，epoll优于select的原因、处理多个套接字的I/O复用介绍

11.文件读写使用的系统调用以及涉及的磁盘缓冲区与其手动flush问题

12.struct与class的区别

13.STL库的介绍、STL底层介绍

14.vector的使用注意点及原因，频繁对vector调用push_back()对性能的影响和原因、vector重新分配内存的大小与方式

15.Hash/hashmap（实现方式）/hashtable（hash函数如何保证冲突最小）底层实现

16.C++虚函数的具体实现原理（虚函数表）

17.析构函数一般写成虚函数的原因

18.手写实现智能指针类

19.常见Linux命令

20.Linux内核的了解

21.C++11的新特性

22.对文件系统的了解

23.介绍C++内存管理（内存模型）

34.C++内存泄漏及检测

25.进程与线程的区别

26.C与C++的特点与区别

27.单链表的倒置

28.快速排序的优化、字符串匹配算法

29.http和https的区别

30.设计模式（手写单例模式）

31.手写翻转二叉树

32.手写strcpy的实现

33.Mysql数据库引擎的介绍

35.手画字典树

36.快速排序（代码）

37.游标种类

38.广度优先算法、深度优先算法、堆排序

39.智能指针使用注意的地方

40.函数调用和压栈的工作原理

41.二叉树遍历方式

42.进程间通讯的方式及优缺点

43.GDB常用命令

44.hash类型及实现方式

45.常用的设计模式

46.MySQL数据库查询结果过大解决内存溢出的解决方案

47.线程安全

48.判断线程安全

49.翻转字符串里的单词

50.TCP协议-如何保证传输可靠性

51.C++中重载、重写（覆盖）和隐藏的区别

52.什么是 RPC 框架