面试八股文对校招的用处有多大？网络编程篇
前言
1.本系列面试八股文的题目及答案均来自于网络平台的内容整理，对其进行了归类整理，在格式和内容上或许会存在一定错误，大家自行理解。内容涵盖部分若有侵权部分，请后台联系，及时删除。
2.本系列发布内容分为12篇 分别是：
网络编程
mysql
redis
服务器
RPG
本文为第八篇，后续会陆续更新。 共计200+道八股文。
3.本系列的200+道为整理的八股文系列的一小部分。完整整理完的八股文面试题共计1000+道，100W字左右，体量太大，故此处放至百度云盘链接： https://pan.baidu.com/s/1IOxQs0ifbSPGgxK7Yz7BtQ?pwd=zl1i
提取码：zl1i 需要的同学自取即可。
4.八股文对于面试的同学来说仅作为参考使用，不能作为面试上岸的唯一准备，还是要结合自身的技术能力和项目，同步发育。
八、网络编程
01.为什么要用epoll
select不足 1.select需要从用户态将监听的集合拷贝给内核， 2.内核通过轮询的方式查找有事件的文件描述符并返回 3.且文件描述符有上限 4.没有直接告诉我们具体哪个fd有数据，导致需要遍历 Epoll函数就是解决select的不足的 从第一个函数看起int epoll_create(int size); 创建epoll函数 返回一个epoll对象 这个epoll对象其实也是个文件描述符，但是这个文件描述符的本质其实是一个二叉树，平衡二叉树，也就是红黑树左子树和右子树高度差小于1.这个函数调用成功将在内核中发生。
第二个函数int epoll_ctl(int epfd, int op, int fd, struct epoll_event event); 第一个参数epfd是那个红黑树文件描述符不必说了 第二个参数Int op代表的是对这个对象的各种操作增删改查 第三个参数指的是需要监听的套接字。 第四个参数则是结构体的指针 struct epoll_event { uint32_t events; / Epoll 事件 / 就是监听套接字的各种事件 读写连接等等 epoll_data_t data; / 用户数据 */ IP端口等等 };
等待返回函数int epoll_wait(int epid, struct epoll_event *events, int maxevents, int timeout); 这个就是epoll最大的优势，当wait接收到响应的时候将把端口的信息放在event里面，int返回有几个信号，只要for循环一下int的次数，就可以将客户端的消息一次接收然后做出相应的应答，好用！。
02.epoll实现原理，epoll使用的哪种模式， 除了epoll，了解select/poll吗
select和poll的缺点：
（1）、每轮循环都要从用户空间往内核空间拷贝数据；
（2）、内核轮询，检测每个描述符有没有就绪事件，O(n);
（3）、I/O函数返回后，遍历每个描述符找到有事件就绪的描述符，O(n);
（select、poll）和（epoll）的区别：
（1）、select、poll每次循环都需要从用户空间向内核空间传递数据；
epoll直接在内核空间创建事件表，每个描述符只需要传递一次；
（2）、select、poll在内核中以轮询的方式检测就绪事件描述符；
epoll在每个描述符上注册回调函数，事件就绪后执行回调函数将描述符添加到就绪队列；
（3）、select、epoll返回后，需要遍历所有文件描述符，才能找到就绪的文件描述符；
epoll返回后，直接得到就绪描述符不需要遍历所有描述符；
epoll的两种模式：
（1）、LT模式（电平触发）：描述符事件就绪后，如果用户没有处理完数据，epoll会一直提醒，直到处理完成；代码实现（epoll-LT.c）
（2）、ET模式（边沿触发）：高效模式。描述符事件就绪后，无论用户有没有处理完数据，epoll都只会提醒一次，所以在处理时要获取完整数据，需要循环获取所有数据；代码实现（epoll-ET.c）
//epoll-LT.c
//I/O复用：epoll() LT模式
//LT模式：描述符时间就绪后，如果用户没有处理完数据，epoll会反复提醒，直到处理完成
#define _GNU_SOURCE
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <pthread.h>
#include <sys/epoll.h>
#define MAXFD 10
int create_socket();
void epoll_add(int epfd,int fd)
{
struct epoll_event ev;
ev.events = EPOLLIN; //LT模式
ev.data.fd = fd;
if( epoll_ctl(epfd,EPOLL_CTL_ADD,fd,&ev) == -1 )
{
perror("epoll_ctl error");
}
}
void epoll_del(int epfd,int fd)
{
if( epoll_ctl(epfd,EPOLL_CTL_DEL,fd,NULL) == -1 )
{
perror("epoll del erreo");
}
}
int main()
{
int sockfd = create_socket();
assert(sockfd != -1);
int epfd = epoll_create(MAXFD);
assert(epfd != -1);
epoll_add(epfd,sockfd);
struct epoll_event events[MAXFD];
while (1)
{
int n = epoll_wait(epfd,events,MAXFD,5000);
if( n == -1 )
{
perror("epoll error");
}
else if(n == 0)
{
printf("time out\n");
}
else
{
int i = 0;
for(;i<n;i++)
{
if(events[i].events & EPOLLIN)
{
if( events[i].data.fd == sockfd )
{
struct sockaddr_in caddr;
int len = sizeof(caddr);
int c = accept(sockfd,(struct sockaddr*)&caddr,&len);
if ( c < 0 )
{
continue;
}
epoll_add(epfd,c);
printf("accept = %d\n",c);
}
else
{
char buff[128] = {0};
int num = recv(events[i].data.fd,buff,1,0);
if( num <= 0)
{
epoll_del(epfd,events[i].data.fd);
close(events[i].data.fd);
printf("one client over\n");
}
else
{
printf("recv(%d):%s\n",events[i].data.fd,buff);
send(events[i].data.fd,"ok",2,0);
}
}
}
}
}
}
}
int create_socket()
{
int sockfd = socket(AF_INET,SOCK_STREAM,0);
if(sockfd == -1)
{
return -1;
}
struct sockaddr_in saddr;
memset(&saddr,0,sizeof(saddr));
saddr.sin_family = AF_INET;
saddr.sin_port = htons(6000);
saddr.sin_addr.s_addr = inet_addr("127.0.0.1");
int res = bind(sockfd,(struct sockaddr*)&saddr,sizeof(saddr));
assert(res != -1);
listen(sockfd,5);
return sockfd;
}
//epoll-ET.c
//I/O复用：epoll() ET模式
//ET模式必须使用非阻塞模式
#define _GNU_SOURCE
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <pthread.h>
#include <sys/epoll.h>
#include <fcntl.h>
#define MAXFD 10
int create_socket();
void setnonblock(int fd)
{
int oldflg = fcntl(fd,F_GETFL); //fcntl()可以设置非阻塞
int newflg = oldflg | O_NONBLOCK;
if(fcntl(fd,F_SETFL,newflg) == -1)
{
perror("fcntl error\n");
}
}
void epoll_add(int epfd,int fd)
{
struct epoll_event ev;
ev.events = EPOLLIN | EPOLLET; //ET模式
ev.data.fd = fd;
setnonblock(fd);
if( epoll_ctl(epfd,EPOLL_CTL_ADD,fd,&ev) == -1 )
{
perror("epoll_ctl error");
}
}
void epoll_del(int epfd,int fd)
{
if( epoll_ctl(epfd,EPOLL_CTL_DEL,fd,NULL) == -1 )
{
perror("epoll del erreo");
}
}
int main()
{
int sockfd = create_socket();
assert(sockfd != -1);
int epfd = epoll_create(MAXFD);
assert(epfd != -1);
epoll_add(epfd,sockfd);
struct epoll_event events[MAXFD];
while (1)
{
int n = epoll_wait(epfd,events,MAXFD,5000);
if( n == -1 )
{
perror("epoll error");
}
else if(n == 0)
{
printf("time out\n");
}
else
{
int i = 0;
for(;i<n;i++)
{
int fd = events[i].data.fd;
if(events[i].events & EPOLLIN)
{
if( fd == sockfd )
{
struct sockaddr_in caddr;
int len = sizeof(caddr);
int c = accept(sockfd,(struct sockaddr*)&caddr,&len);
if ( c < 0 )
{
continue;
}
epoll_add(epfd,c);
printf("accept = %d\n",c);
}
else
{
while(1)
{
char buff[128] = {0};
int num = recv(fd,buff,1,0);
if( num == -1 )
{
send(fd,"ok",2,0);
break;
}
else if( num == 0 )
{
epoll_del(epfd,fd);
close(fd);
printf("one client over\n");
break;
}
else
{
printf("buff(%d) = %s\n",fd,buff);
}
}
}
}
}
}
}
}
int create_socket()
{
int sockfd = socket(AF_INET,SOCK_STREAM,0);
if(sockfd == -1)
{
return -1;
}
struct sockaddr_in saddr;
memset(&saddr,0,sizeof(saddr));
saddr.sin_family = AF_INET;
saddr.sin_port = htons(6000);
saddr.sin_addr.s_addr = inet_addr("127.0.0.1");
int res = bind(sockfd,(struct sockaddr*)&saddr,sizeof(saddr));
assert(res != -1);
listen(sockfd,5);
return sockfd;
}
03.怎么理解多路复用机制的
准备：文件描述符，水平触发，边缘触发
在Linux世界使用文件，我们也需要借助一个号码，这个号码就被称为了文件描述符。因此，文件描述仅仅就是一个数字而已，但是通过这个数字我们可以操作一个打开的文件
文件描述符在形式上是一个非负整数。
实际上，它是一个索引值，指向内核为每一个进程所维护的该进程打开文件的记录表。
当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。
内核通过文件描述符来访问文件。文件描述符指向一个文件。
水平触发：只要一个文件描述符就绪，就会触发通知，如果用户程序没有一次性把数据读写完，下次还会通知；
边缘触发：当描述符从未就绪变为就绪时通知一次，之后不会再通知，直到再次从未就绪变为就绪（缓冲区从不可读/写变为可读/写）。
区别：边缘触发效率更高，减少了被重复触发的次数，函数不会返回大量用户程序可能不需要的文件描述符。
边缘触发一定要用非阻塞IO：避免由于一个描述符的阻塞读/阻塞写操作让处理其它描述符的任务出现饥饿状态。
1，什么是I/O多路复用
IO多路复用（IO Multiplexing）是指单个进程/线程就可以同时处理多个IO请求。
2，多路复用实现原理
实现原理：用户将想要监视的文件描述符（File Descriptor）添加到select/poll/epoll函数中，由内核监视，函数阻塞。一旦有文件描述符就绪（读就绪或写就绪），或者超时（设置timeout），函数就会返回，然后该进程可以进行相应的读/写操作。
3，在Linux世界中的三种机制实现I/O多路复用
select：需要把想监控的文件描述集合通过函数参数的形式告诉select，然后select会将这些文件描述符集合拷贝到内核中，
为了减少数据拷贝带来的性能损耗，Linux内核对集合的大小做了限制，规定用户监控的文件描述集合不能超过1024个，
同时当select返回后我们仅仅能知道有些文件描述符可以读写了，但是我们不知道是哪一个，
因此程序员必须再遍历一边找到具体是哪个文件描述符可以读写了。
特点：
1：数据拷贝。每次都要复制，开销大
2：集合大小有限制，32位机默认是1024（64位：2048）；
3：水平触发机制。select函数返回后，需遍历集合，找到就绪的文件描述符（缺点3：轮询的方式效率较低）
poll：和select类似，select和poll都会随着监控的文件描述增加而出现性能下降，因此不适合高并发场景。基于轮询
特点：
1，采用链表的方式存储，没有最大存储数量的限制；
epoll：基于事件驱动
1，通过内核和用户空间共享内存，避免了不断复制的问题；
2，支持的同时连接数上限很高（1G左右的内存支持10W左右的连接数）；
3，文件描述符就绪时，采用回调机制，避免了轮询（回调函数将就绪的描述符添加到一个链表中，执行epoll_wait时，返回这个链表）；
4，支持水平触发和边缘触发，采用边缘触发机制时，只有活跃的描述符才会触发回调函数。
三种方式区别主要在于：
一个线程/进程所能打开的最大连接数
文件描述符传递方式（是否复制）
水平触发 or 边缘触发
查询就绪的描述符时的效率（是否轮询）
4，select/poll/epoll的应用场景
当连接数较多并且有很多的不活跃连接时，epoll的效率比其它两者高很多；但是当连接数较少并且都十分活跃的情况下，由于epoll需要很多回调，因此性能可能低于其它两者。
5，多路复用的应用场景
1，redis通过I/O多路复用处理客户端的连接请求与相应，6.0以后采用多个IO线程来处理网络请求，提高网络请求处理的并行度，数据读写依然保持单线程
6，总结
单个线程监听多个连接，某个连接就绪而触发读写事件时，就会通知对应的应用程序主动获取这个就绪连接进行读写操作，
即在应用程序里使用单个线程处理多个客户端连接，减少系统资源的消耗，也提升服务端的连接处理数量。
实现原理大体就是客户端传输数据过程中。为避免服务端read数据时阻塞，服务端会先把请求注册到selector 复路器，服务端不需等待，
只需启动个线程通过selector.select()方法去阻塞轮询复路器上就绪的channel，
客户端数据传输完成后，select()方法就会返回这个就绪的channel，然后执行相关处理逻辑即可。
04.reactor和proactor的好处和坏处。为什么要用reactor而不用proactor
Reactor和Proactor都是常见的I/O多路复用模型，其主要区别在于事件驱动模式和数据驱动模式。下面是它们的优缺点以及为什么要使用Reactor而不是Proactor的原因：
Reactor的优点：
- 应用程序通过回调函数处理I/O事件，避免了线程创建、同步、销毁等开销。
- Reactor采用同步I/O，可以直接操作文件描述符，避免了额外的内存拷贝开销。
- Reactor对于大量短连接场景效果更好，因为没有额外的数据传输和处理阻塞等待。
Reactor的缺点：
- 需要手动控制缓冲区大小和拆包粘包问题。
- 对于大量长连接场景效果较差，需要占用大量线程资源导致系统崩溃。
Proactor的优点：
- 应用程序通过异步回调函数处理I/O事件，避免了线程创建、同步、销毁等开销。
- Proactor采用异步I/O，在完成后自动触发回调函数，避免了阻塞等待问题。
- Proactor适合长连接场景，并且可以利用操作系统提供的零拷贝技术减少数据传输开销。
Proactor的缺点：
- 由于应用程序无法直接操作文件描述符，需要进行数据拷贝和缓冲区管理等额外开销。
- Proactor对于大量短连接场景效果较差，因为异步I/O需要占用大量内存资源导致系统崩溃。
综上所述，Reactor适合处理大量短连接的请求，而Proactor适合处理大量长连接的请求。由于在实际应用中大多数场景是短连接，在性能、可靠性和易用性方面Reactors更优秀一些。
05.select怎么用。底层原理
select是一种I/O多路复用的机制，可以同时监视多个文件描述符的状态，当某个文件描述符就绪时，select会返回该文件描述符。其使用方法如下：
- 创建一个fd_set类型的集合对象，并将要监听的所有文件描述符添加到集合中。
- 调用select函数，等待其中任何一个文件描述符变为可读/可写/异常。
- select函数返回后，遍历集合中所有文件描述符，判断哪些文件描述符发生了事件。
- 处理发生事件的文件描述符。
底层原理：
在Linux系统中，select基于内核提供的轮询机制实现。当应用程序调用select函数时，它会将需要监听的所有文件描述符添加到内核维护的数据结构中（通常是一个位图或数组），然后进入阻塞状态等待。当有一个或多个文件描述符准备好时（即满足了指定条件：可读、可写或异常），内核会将这些已经就绪的事件返回给应用程序，并且清空之前存储在数据结构中对应位置上的位标记。此时应用程序可以通过遍历数据结构来确定哪些文件描述符处于就绪状态，并进行相应处理。
select存在以下缺点：
- 监听数量受限：由于数据结构本身大小限制和系统资源限制等原因，在某些情况下select只能监听1024个文件描述符。
- 每次调用都需要将所有待检查的fd集合从用户态拷贝到内核态，存在额外的系统调用和内存开销。
- 无法高效地处理大量连接：当需要同时处理大量连接时，采用轮询机制会导致系统开销过大。
因此，在高性能、高并发的应用场景中，通常采用更为高效的I/O多路复用机制（如epoll）代替select。
06.select为什么只能支持1024个。poll和epoll是怎么解决这个问题的。
各自支持的最大fd数上限以及原因
select支持的fd数是固定的，默认一般为1024，用一个常数FD_SETSIZE定义，如果要monitor更多的fd，需要修改这个常数，并且重新编译(?),一般如果要monitor超过1024的fd，推荐使用poll/epoll
poll和epoll，因为他们monitor的fd list是通过数组或者说链表来保存，所以没有数量限制
区别
select
select是三者中最早被使用的多路复用机制，因此可移植性最好
通过给定三个fd set（bit mask），分别对应关注的是否可读，可写，是否出现异常三种类别，在调用select的时候，这三个集合被传给内核，内核逐一检测这些fd是否ready，然后把三个集合中ready的fd对应的bit置为1，返回
然后用户再逐一检测set中的fd是否处于ready，如果是，就对对应的fd执行相应的操作
注意到，在上面的描述中，用户始终需要扫描整个集合，也就是说扫描的个数和io事件的个数无关，而是始终是FD_SETSIZE,为了提高效率，我们可以使用一个maxfd,这样可以只检测maxfd以下的，从而扫描的个数正比于监听的fd个数，而不是始终是固定的FD_SETSIZE
缺点：
1.每次调用select都需要把三个集合传给内核，然后内核又把修改过的三个集合传回来，耗费时间
2.扫描时耗时与monitor的fd个数成正比，所以如果监听的个数很多，就会很慢
3.监听个数有上限
poll
基本和select相同，优点是监听的fd没有数量限制(因为poll不是用bit mask保存关注的fd，而是用pollfd 结构体数组
epoll
首先他和poll一样，监听的fd数没有限制（或者说只受硬件配置限制
为什么epoll的性能更好：
1.每次有io event让fd编程ready，内核都把该ready fd加入到epoll ready list，执行wait的时候直接从ready list里取而select每次调用都要扫描所有的fd
2.每次调用select/poll,都把三个set传给内核，然后内核把ready的用三个set传回来而epoll，使用epoll_ctl在内核里创建一个数据结构，之后epoll_wait时不需要传什么数据
返回的时候，也只返回ready的（事实上因为返回时我们也必须检查所有的位，判断是否ready，而epoll只返回ready的，所以还是有区别的
3.每次调用select之前，都必须初始化三个集合，还有返回之后必须检查所有的位（不过貌似这些是小头
我们可以说select/poll的耗时和N（fd数）呈线性关系，epoll的耗时和发生的io事件呈线性关系
所以epoll十分实用下面这种情况：monitor大量的fd，但是其中大部分是空闲的（因此io事件相对较少
此外epoll还提供edge trigger和level trigger两种形式的通知，而select/poll 都只支持level trigger
这两种的区别在于：
level trigger：只要fd处于ready（可读可写），就会报告给用户
edge trigger：仅当上一次调用epoll_wait之后有新的io事件，才报告给用户（如果是之前没有使用epoll_wait,那么就看创建fd之后有没有新的io事件）
举例说明edge trigger和level trigger的区别
假设现在一个fd处于ready，可读，我们执行一次epoll wait，此时一定是ready，不管采用level trigger还是edge trigger
再执行一次，如果是level trigger，那么仍然报告ready
但如果是edge trigger，那么就不会报告ready，因为从上次调用epoll wait以来，没有发生io事件
07.epoll 底层为什么用红黑树不用hash
一、epoll使用红黑树来管理文件描述符，而不是哈希表的原因
1、红黑树容易缩容
红黑树容易缩容，在处理完大规模数据后能够很好的缩容。哈希表是不容易缩容的，如果某个时刻，有大量的网络请求通过哈希来记录，触发哈希表扩容，之后这个哈希表很难缩容回去，这也是为什么一些go程序oom的问题，都是go map太大了无法gc。
2、红黑树处理大规模数据效率高
红黑树是一种自平衡二叉查找树，它的查询、插入和删除操作的平均复杂度都是O(log n)。而哈希表的查询、插入和删除操作的平均复杂度是O(1)，在处理一些小规模的数据时，哈希表可能表现得更出色，但在处理大规模的数据时，红黑树更加高效稳定。
3、红黑树能同时支持文件描述符和事件的管理
在epoll中，红黑树能够同时支持文件描述符和事件的管理，可以快速地定位某个事件对应的文件描述符。而哈希表只能支持根据文件描述符快速查找对应的事件，而对于事件对应的文件描述符则无法快速定位，因此不符合epoll的需求。
二、红黑树简介
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。
红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
- 结点是红色或黑色。
- 根结点是黑色。
- 所有叶子都是黑色。（叶子是NIL结点）
- 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。因为红黑树是一种特化的二叉查找树，所以红黑树上的只读操作与普通二叉查找树相同。
在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也是二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量（O(log n)）的颜色变更（这在实践中是非常快速的）并且不超过三次树旋转（对于插入是两次）。这允许插入和删除保持为 O(log n)次，但是它导致了非常复杂的操作。
三、哈希表简介
散列表（Hash table，也叫哈希表），是根据关键码值（Key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希（Hash）函数。若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数**f(k)**和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
常用方法：
- 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key)中已经有值了，就往下一个找，直到H(key)中没有值了，就放进去。
- 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
- 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。
- 随机数法：选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。
- 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p，p≤m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
08.ET和LT的区别、IO多路复用
LT模式和ET模式 1、LT模式:内核如果检测就绪事件并将其通知给应用程序后,应用程序可以不立即处理该事件，因为下次调用epoll _wait时，还会将此事件通知给应用程序。 2、ET模式:内核如果检测就绪事件并将其通知给应用程序后,应用程序必须立即处理该事件，否则下次调用epoll wait时，不会将此事件再通知给应用程序。 3、select和poll只能工作在LT模式下，epoll支持高效的ET模式
实例说明 1、epoll在默认情况下是LT模式，如果想要让他支持ET模式，可以在获取新连接的代码下在事件类型中加上EPOLLET。
2、LT模式下 在每次处理客户端发过来的数据时，将每次读取数据的长度设置为5，运行结果为：
原因是：同一个事件，虽然只发了一次数据，但是这个事件将epoll_wait触发了三次。 3、ET模式下（加上EPOLLET后） 文件描述符是以ET模式来处理的。
4、ET模式下如何处理就绪的事件？ 因为要求应用程序必须立即处理并且处理完该事件，所以必须要用while（1）去处理。 存在问题： （1）如何判断已经将本次的事件处理完成。 解决方法：recv返回值如果是-1，并且判断全局的errno。
用返回值来判断文件读取是否完成。但是用recv处理时，如果用它来操作具体的客户端链接文件描述符，它本身是会阻塞的，如果阻塞了，是无法判断的。 （2）为了解决recv阻塞问题，可以使得recv操作accept返回的文件描述符时以非阻塞方式处理。用fcntl()方法。
epoll的EPOLLONESHOT事件 前言 一个线程在读取完某个socket上的数据后开始处理这些数据，而在数据的处理过程中该socket上又有新数据可读(EPOLLIN再次被触发)，此时另外一个线程被唤醒来读取这些新的数据。于是就出现了两个线程同时操作一个socket的局面。但是我们期望的是一个socket连接在任一时刻都只被一个线程处理。这一点可以使用epoll的EPOLLONESHOT事件实现。
概念 1、EPOLLONESHOT事件的文件描述符注册后，操作系统最多触发其上注册的一个可读、可写或者异常事件，且只触发一次，除非我们使用epoll _ctl 函数重置该文件描述符上注册的EPOLLONESHOT事件。 2、注册了EPOLLONESHOT事件的socket一旦被某个线程处理完毕，该线程就应该立即重置这个socket上的EPOLLONESHOT事件，以确保这个 socket下一次可读时，其EPOLLIN事件能被触发，进而让其他工作线程有机会继续处理这个socket。 3、尽管一个 socket在不同时间可能被不同的线程处理，但同一时刻肯定只有一个线程在为它服务。这就保证了连接的完整性，从而避免了很多可能的竞态条件。
09.游戏中数据传输用啥协议（有没有改进的协议，基于UDP的可靠传输）
一、TCP协议
TCP协议是一种面向连接的协议，它通过三次握手建立连接，保证数据传输的可靠性。TCP协议主要用于游戏数据的传输，例如游戏中的聊天信息、玩家位置等。TCP协议能够保证数据的完整性和可靠性，但是由于需要建立连接，会增加网络延迟，影响游戏体验。
二、UDP协议
UDP协议是一种无连接的协议，它不需要建立连接，直接将数据包发送到目的地。UDP协议主要用于游戏的实时交互，例如游戏中的战斗、移动等。UDP协议具有传输速度快、延迟低等优点，但是由于没有保证数据的可靠性，会出现数据丢失的情况。
三、HTTP协议
HTTP协议是一种应用层协议，主要用于Web浏览器和Web服务器之间的数据传输。HTTP协议主要用于游戏的更新和下载等操作。HTTP协议具有简单、易用等优点，但是由于需要建立连接和传输大量数据，会增加网络延迟，影响游戏体验。
四、WebSocket协议
WebSocket协议是一种基于TCP协议的协议，它提供了双向通信的能力，可以实现实时交互。WebSocket协议主要用于游戏的实时通信，例如游戏中的多人对战等。WebSocket协议具有传输速度快、延迟低等优点，但是由于需要建立连接，会增加网络延迟。
综上所述，游戏中常用的网络协议有TCP协议、UDP协议、HTTP协议和WebSocket协议。不同的协议有不同的优缺点，游戏需要根据游戏的实际需求选择合适的协议。同时，游戏也可以结合多种协议，提高游戏的网络性能和用户体验。
10.项目架构（webserver）两种高并发模式（问的很细）
本文从网站架构层面介绍不同性能需求阶段，网络架构的演变和设计思考。
一、Nginx反向代理，实现负载均衡。
对于传统的低流量应用，基本够用，具有一定可扩展性。其中Nginx可以嵌套已经实现性能和服务扩展。
二，Varnish提升性能
为了方便画图，我只写了一个web，多数情况下都是多个web，其中增加了varnish对静态、动态资源进行缓存，以提高性能，大体可提供数倍的性能。Varnish也有反向代理的能力，但Nginx更优秀，所以建议采用两者配合的方式搭建架构。
三、缓存的使用以提升web性能
此处只是web服务本身性能提升，即图2中的web1服务，不涉及整体架构。架构设计中增加了缓存数据库，并不是每次访问都去数据库，从而大大提高效率，目前redis用的比较多，网上也很多对比资料，这里就不废话了。
四、消息中间件进一步提升web服务性能
ActiveMQ 是一个 MOM，具体来说是一个实现了 JMS 规范的系统间远程通信的消息代理。用于以分布式应用或系统中的异步、松耦合、可靠、可扩展和安全通信。这类的通讯组件很多，基本架构也大同小异，这里也不多说了，简单架构示意如下：
五、使用MongoDB
MongoDB 是一个基于分布式文件存储的数据库。旨在为 WEB 应用提供可扩展的高性能数据存储解决方案。应用后架构如下
六、应用MogileFS
MogileFS是一个开源的分布式文件存储系统,用来分担海量小文件的存取工作，架构如下：
七、总结
- 使用Ngnix做负载均衡，以应对高并发的访问
- 使用varnish和Memcached/redis来再不同层面做缓存，以提高性能
- 使用ActiveMQ来实现异步业务处理，来提高系统性能和可伸缩性。
- 使用MongoDB来支持海量数据处理，同时也提高系统可伸缩性。
- 使用MogileFS来支持海量小文件的存储。
11.除了Reactor模型，还有什么模型
网络IO模型包括：阻塞I/O、非阻塞I/O、I/O复用(select和poll)、信号驱动I/O(SIGNO)、异步I/O(Posix的aio_系列函数)
一、同步IO模型
1.1 阻塞I/O
1.2 非阻塞I/O
1.3 I/O复用(select和poll)
1.4 信号驱动I/O(SIGNO)
二、异步IO模型
2.1 异步I/O(Posix的aio_系列函数)
2.2 五种IO模型的比较
三、Reactor与Proactor
3.1 基本概念
两种I/O多路复用模式：Reactor和Proactor。
Reactor模式采用同步IO，Proactor采用异步IO。
事件、事件处理器(回调函数)、事件分离器。 开发人员预先注册需要处理的事件及其事件处理器(或回调函数)；事件分离器负责将请求事件传递给事件处理器。
3.2 Reactor实现读
1. 注册读就绪事件和相应的事件处理器；
2. 事件分离器等待事件；
3. 事件到来，激活分离器，分离器调用事件对应的处理器；
4. 事件处理器完成实际的读操作，处理读到的数据，注册新的事件，然后返回控制权。
3.3 Proactor实现读
-
处理器泛起异步读操作(注意：操作系统必须支持异步IO)。这种情况下，处理器无视IO就绪事件，它关注的是完成事件；
-
事件分离器等待操作完成事件；
-
在分离器等待过程中，操作系统利用并行的内核线程执行实际的读操作，并将结果数据存入用户自定义缓冲区，最后通知事件分离器读操作完成。
-
事件分离器呼唤处理器；
-
事件处理器完成实际的读操作，处理读到的数据，注册新的事件，然后返回控制权。
查看6道真题和解析
三七互娱公司福利 210人发布