tools boy 2021/3/8 21:52:32 对了 tools boy 2021/3/8 21:52:41 鹅厂还是比较注重基础的 tools boy 2021/3/8 21:52:51 类似STL的原理跟网络数据库 tools boy 2021/3/8 21:52:58 还是会问的比较多 tools boy 2021/3/8 21:53:15 算法题的话一般easy+medium难度吧 even 2021/3/8 21:54:26 好的，STL这些没问题，网络数据库我的程度不知道行不行，最近没有面试，算法应该还可以幸福 even 2021/3/8 21:54:44 我这段时间准备下吧 even 2021/3/8 21:55:23 谢谢告知 tools boy 2021/3/8 21:55:55 我简单说个看看 tcp的三次握手四次断开，滑动窗口,time_wait,拥塞控制算法。。还有innodb与myisam的差别，为何索引使用b+树等。。 tools boy 2021/3/8 21:56:02 STL也会深入源码问的 tools boy 2021/3/8 21:56:28 比如std::sort的实现。type_traits以及map与unordermap的实现差异 even 2021/3/8 21:57:24 那还是比较深入的 even 2021/3/8 21:58:32 那需要好好准备下 even 2021/3/8 21:59:27 tcp握手挥手知道，其他的可能只有一点概念，需要准备下 even 2021/3/8 22:00:56 stl我仿写过侯捷那个版本的STL，再复习下应该可以 tools boy 2021/3/8 22:01:48 嗯嗯。最好知道。不要是懂非懂。。经常问std::sort实现，有人张口就使用快排。。。 tools boy 2021/3/8 22:01:53 这种就基本gg 【话唠】tools boy(53600134) 2021/3/11 18:14:39 不知道，不一定指的是群里的，那面试官说的，三次握手部分人可以答出来，流量控制，拥塞避免没人答的出来 【话唠】tools boy(53600134) 2021/3/11 18:14:56 最基本的epoll select都没用过 ## map与unordered_map的实现差异 map: 底层数据结构是红黑树，使用二叉搜索树存储，使用中序遍历就可以将键值从小到大遍历出来。 unordered_map: 内部实现了一个哈希表，将键值映射到hash表一个位置来访问，查找时间复杂度为O(1)，是无序的。 ## std::sort的实现 https://www.cnblogs.com/ygh1229/articles/9806398.html 1. 在数据量很大时采用正常的快速排序，此时效率为O(NlogN) 2. 一旦分段后的数据量小于某个阈值（16），就改用插入排序，因为此时这个分段是基本有序的，这时效率可达O(N) 3. 在递归过程中，如果递归层次过深，分隔行为有恶化倾向时，它能自动检测出来，使用堆排序来处理，在此情况下，使其效率维持在堆排序的O(NlogN) 综合各家之长的算法 函数调用会有额外开销，返回指针，参数压栈、出栈等 ## innodb与myisam的差别 https://www.zhihu.com/question/20596402 1. InnoDB支持事务，MyISAM不支持事务。这是MySQL将默认存储引擎从MyISAM变成InnoDB的重要原因之一； 2. InnoDB支持外键，而MyISAM不支持。 3. InnoDB 是聚集索引，MyISAM 是非聚集索引。 4. InnoDB不保存表的行数，执行select count(*) from table时需要全表扫描。而MyISAM用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快。 5. InnoDB最小的锁粒度是行锁，MyISAM最小是表锁，一个更新语句会锁住整张表，导致其他查询和更新受阻，并发访问受限。这也是MySQL将默认存储引擎从MyISAM变成InnoDB的重要原因之一。 ## 为何索引使用b+树 https://www.cnblogs.com/tiancai/p/9024351.html ## 滑动窗口，拥塞控制算法 https://blog.csdn.net/zhangdaisylove/article/details/47294315 1. 流量控制：就是让发送方的发送速率不要太快，要让接收方来得及接收 2. 接收窗口rwnd  ## 拥塞控制 拥塞窗口：cwnd 发送窗口：swnd 在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络性能就要变坏。这种情况叫做拥塞。 若出现拥塞而不进行控制，整个网络的吞吐量就将随输入负荷的增大而下降。  RTT：往返时延 TCP的四种拥塞控制算法： 1. 慢开始 2. 拥堵避免 3. 快重传 4. 快恢复     TCP发送方一开始使用慢开始算法，让拥塞窗口cwnd的值从1开始按指数规律增长，当拥塞窗口cwnd的值增长到初始的慢开始门限值时，停止使用慢开始算法，转而执行拥塞避免算法，让拥塞窗口cwnd的值按线性加一的规律增长，当发生超时重传时，就判断网络可能出现了拥塞，采取相应的措施，一方面将慢开始门限值更新为发生拥塞时的拥塞窗口cwnd的一半，另一方面，将拥塞窗口cwnd的值减少为1，并重新开始执行慢开始算法，拥塞窗口cwnd的值又从1开始按指数规律增长，当增长到新的慢开始门限值时，停止使用慢开始算法，转而执行拥塞避免算法，让拥塞窗口cwnd的值按线性加一的规律增长，当发送方收到三个重复确认时，就进行快重传和快恢复，也就是更新慢开始门限值为当前拥塞窗口cwnd的一半，并将拥塞窗口cwnd的值也取为新慢开始门限值，转而执行拥塞避免算法，让拥塞窗口cwnd的值按线性加一的规律增长。  ## 为何索引使用b+树 https://www.cnblogs.com/kismetv/p/11582214.html 最后，总结一下各种树解决的问题以及面临的新问题： 1. 二叉查找树(BST)：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表； 2. 平衡二叉树(AVL)：通过旋转解决了平衡的问题，但是旋转操作效率太低； 3. 红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多； 4. B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题； 5. B+树：在B树的基础上，将非叶子节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶子节点使用指针连接成链表，范围查询更加高效。 ## select epoll https://www.bilibili.com/video/BV1qJ411w7du?from=search&seid=14380802369448777628  #### epoll https://www.erlo.vip/share/15/70833.html #### epoll epoll有EPOLLLT和EPOLLET两种触发模式，分别为水平模式和边缘模式，LT是默认模式。LT模式下，只要这个fd还有数据可读，每次epoll_wait都会返回它的事件，提醒用户程序去操作，而ET模式中，它只提示一次，直到下次再有数据流之前都不会有提示。 #### epoll优点 1. 没有最大并发连接限制，能打开的fd的上限远大于1024（1G内存能监听约10万个端口） 2. 效率提升，不是轮询的方式，不会随fd数目的增加效率下降。只有活跃可用的fd才会调用callback函数； 3. 即epoll最大的优点就在于它只管你”活跃“的连接，跟连接总数无关，因此在实际的网络环境中，epoll的效率就会远远高于select和poll； 4. 内存拷贝，利用mmap()文件映射内存加速与内核空间的消息传递；即epoll使用mmap减少复制开销。 #### select缺点 （1）每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多事会很大 （2）同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多事会很大 （3）select支持的文件描述符数量太小了，默认是1024 #### poll实现 poll实现和select非常相似，只是描述fd集合的方式不同，poll使用pollfd结构体而不是select的fd_set结构，其他的都差不多，管理多个描述符也是进行轮询，根据描述符的状态进行处理，但是poll没有最大文件描述符数量的限制。poll和select同样存在一个缺点就是，包含大量文件描述符的数组被整体复制于用户态和内核态的地址空间之间，而不论这些文件描述符是否就绪，它的开销随着文件描述符数量的增加而线性增大。