面经--相关

C++腾讯

1、map和unordered_map底层，解释下哈希碰撞，如何使用哈希设计出类似红黑树的效果

哈希函数 hashFunction = hashCode(类型) % tableSize，为了保证映射出的索引数值都落在哈希表上，我们再对数值做一个取模的操作。

哈希碰撞发生在两个不同的键通过哈希函数映射到了相同的哈希值，即映射到了哈希表的同个位置。

拉链法：每个哈希表的槽位中存储一个链表，所有哈希到同一槽位的元素都存储在这个链表中。

线性探测法：当发生碰撞时，从碰撞位置开始，逐个检查后续位置直到找到一个空槽位。

利用哈希表实现快速定位，每个桶内存储一个有序链表，在链表中按照一定规则（如键的自然顺序）插入和删除元素。这种设计在大多数情况下能提供快速查找和插入，同时通过扩容和重新哈希保持整体效率。通过哈希表的扩容和重新哈希操作，维持整体性能，类似于红黑树通过旋转和颜色变化维持平衡。有序链表保证了元素的顺序性，类似于红黑树中元素按顺序排列的性质。

2、TCP滑动窗口、拥塞控制

滑动窗口：在确认应答策略中，对每一个发送的数据段，都要给一个ACK确认应答，收到ACK后再发送下一个数据段，这样性能较差，使用滑动窗口，就可以一次发送多条数据，从而就提高了性能。

• 滑动窗口机制用于控制数据包的流动，使得接收方能够处理并确认数据包。
• 窗口大小（窗口容量）决定了发送方在等待确认之前可以发送的数据量。
• 当窗口满了，发送方必须等待接收方的确认，以释放窗口空间，继续发送数据。

拥塞控制：在网络出现拥堵时，如果继续发送大量数据包，可能会导致数据包时延、丢失等，这时 TCP 就会重传数据，但是一重传就会导致网络的负担更重，于是会导致更大的延迟以及更多的丢包。通过拥塞控制，避免发送方数据填满整个网络。

拥塞控制用于防止网络阻塞，主要包括以下几种算法

• 慢启动：从一个小的初始拥塞窗口开始，逐步增加发送数据量。
• 拥塞避免：当慢启动达到一定阈值后，进入拥塞避免阶段，缓慢增加发送数据量。
• 快速重传和快速恢复：在检测到数据包丢失时，快速重传丢失的数据，并进入快速恢复阶段，避免拥塞窗口过度减小。

3、窗口满的情况，write函数的阻塞和非阻塞分别返回什么

在阻塞模式下，write 函数会阻塞等待滑动窗口有空间，数据才能写入，避免数据丢失。

在非阻塞模式下，write 函数会立即返回，如果滑动窗口满了，会返回 -1 并设置相应的 errno。这要求程序设计需要处理 EAGAIN 或 EWOULDBLOCK 错误(errno的标记，资源暂时不可用，非阻塞IO中出现)，通过合适的重试机制或者选择合适的时机重新尝试写入。

4、MySQL索引，B+树，Mysql存储引擎，查询优化

MySQL索引类似书籍的目录，提高查询速度。

B+树：所有叶子节点在同一层，非叶子节点存储键值，叶子节点存储数据记录。在插入、删除和更新操作后会自动重新平衡。B+树的叶子节点链表是双向的，为了实现倒序遍历或排序。

B+树和B树区别：

在B+树中，数据都存储在叶子节点上，而非叶子节点只存储索引信息；

而B树的非叶子节点既存储索引信息也存储部分数据。

B+树的叶子节点使用链表相连，便于范围查询和顺序访问；

B树的叶子节点没有链表连接。

B+树的查找性能更稳定，每次查找都需要查找到叶子节点；而B树的查找可能会在非叶子节点找到数据，性能相对不稳定。

在Mysql中，索引的存储方式与存储引擎有关，包括InnoDB和MyISAM。

Mysql默认InnoDB,在事务支持、并发性能、崩溃恢复方面具有优势。

事务支持：可以进行ACID(原子性Atomicity、一致性Consistency、隔离性Isolation、持久性Durability)属性操作。MyISAM不支持事务。

并发性能：InnDB采用了行级锁定的机制，可以提供更好的并发性能，MyISAM存储引擎只支持表锁，锁的粒度较大。

崩溃恢复：InnoDB通关redlog日志实现崩溃恢复，可以在数据库发生异常情况时，通关日志文件进行恢复，保证数据的持久性和一致性。MyISAM是不支持崩溃恢复的。

索引结构：InnoDB是聚簇索引，MyISAM是非聚簇索引，聚簇索引的数据文件和索引文件存储在一起，数据按主键顺序存储。非聚簇索引的数据文件和索引文件分开存储。每个 MyISAM 表存储为三个文件：.frm（表定义文件）、.MYD（数据文件）、.MYI（索引文件）。

InnoDB：适用于需要事务支持、高并发写操作、数据一致性要求高的场景，如金融系统、电商平台等。

MyISAM：适用于读操作多、写操作少、不需要事务支持的场景，如数据仓库、日志分析等

查询优化：

1.优化SQL、索引，选择合适的索引列(经常作为查询条件、排序的列)。2.使用Redis缓存高频查询结果。3.使用数据库连接池，一般访问数据库需要先和MySQLServer创建连接，然后发送SQL语句，再把结果通过网络返回给应用，然后关闭MysqlServer的连接，因此大量的数据库访问，消耗的TCP三次握手和四次挥手所花费时间很多。一般连接池维护以下资源：1、连接池里面保持固定数量的活跃TCP连接，供应用使用。 2、如果应用瞬间访问MySQL的量比较大，那么连接池会实时创建更多的连接给应用使用。 3、当连接池里面的TCP连接一段时间内没有被用到，连接池会释放多余的连接资源，保留它设置的最 大空闲连接量就可以了。

6、RPC和微服务的理解

RPC（Remote Procedure Call） 是一种通信协议，允许一个程序调用另一个地址空间（通常在远程服务器上）中的过程或方法，就像调用本地过程一样。RPC 的目的是简化分布式计算，使得程序员不需要关注底层的网络通信细节。

微服务架构 是一种软件架构风格，将应用程序分解为小的、独立部署的服务。每个服务运行在自己的进程中，并通过轻量级的通信机制（通常是 HTTP/HTTPS、消息队列等）进行通信。微服务架构的核心思想是将单一的大型应用程序拆分成多个小的、松耦合的服务，以便于独立开发、部署和扩展。

7、进程、线程、协程

进程是操作系统资源分配和调度的基本单位，它拥有自己的独立内存空间和系统资源。每个进程都有独立的堆和栈，不与其他进程共享。

线程是任务调度和执行的基本单位，线程共享进程的内存空间，包括堆和全局变量。

协程是一种用户态的轻量级线程，其调度完全由用户程序控制，而不需要内核的参与。协程拥有自己的寄存器上下文和栈，但与其他协程共享堆内存。

8、值传递、指针传递、引用传递

值传递：将一个值传递给函数时，函数会创建该值的副本，并在函数内部使用这个副本，这意味着函数对该值的修改不会影响到原始值。

指针传递：指针传递是通过将参数的内存地址传递给函数来实现的，函数可以通过指针来直接访问和修改原始值。

引用传递：引用传递是将参数的引用传递给函数，函数可以通过引用直接访问和修改原始值，而无需创建副本。

9、智能指针的使用和原理，C++内存管理

程序内存分区：

栈：编译器管理分配和回收，存放局部变量和函数参数。(stack)

堆：程序员使用new、malloc、delete、free进行堆内存的分配和释放。(heap)

全局/静态区：存储全局变量和静态变量。未初始化全局区(.bss),已初始化全局(.data)

常量区：存储常量数据。(.rodata)

代码区：存放程序的代码。(.text)

内存泄漏：程序未能释放掉不再使用的内存。

如何防止内存泄漏：将内存的分配封装在类中，构造函数分配内存、析构函数释放内存。使用智能指针。

智能指针包括：

auto_ptr，C++11已经抛弃，存在内存崩溃问题。

unique_ptr(独占智能指针)：保证同一时间内只有一个智能指针可以指向该对象。

shared_ptr(共享智能指针)：多个智能指针可以指向相同对象。该对象和相关资源在最后一个引用被销毁时释放，使用引用计数机制表明资源被几个指针共享。调用release时，当前指针会释放资源所有权，计数减一。当计数等于0时，资源会被释放。

weak_ptr(弱引用智能指针)：指向一个shared_ptr管理的对象。如果两个shared_ptr相互引用，那么这两个指针的引用计数永远不可能下降为0，资源永远不会释放。把其中一个shared_ptr改为weak_ptr即可解决shared_ptr相互引用时的死锁问题。