又遇百度，能否 hold 住？

# 先秀战绩 > 最近经过我们内推进百度的人特别多，感兴趣的小伙伴可以联系我试试  最新面经出炉！今天分享的是粉丝朋友在**百度区块链**的面试，有考察到**go中数据结构的底层原理，、数据库、操作系统、计网以及代码题**，涉及面还挺广的，看看你能否`hold`住： # 百度区块链一面 ### 介绍一下 map 以及底层原理 #### 一、map 概述 - **定义与功能**：在计算机科学中，map 是由`<key, value>`对组成的抽象数据结构，同一`key`仅出现一次，具备“增删查改”操作，即增加、删除、修改和查询`key - value`对，其设计被称为 “The dictionary problem”。 - **实现方式**：主要通过哈希查找表和搜索树实现。哈希查找表用哈希函数将`key`分配到桶，有链表法和开放地址法处理碰撞；搜索树法常用自平衡搜索树如 AVL 树、红黑树，二者在搜索效率、遍历顺序等方面各具特点。 #### 二、哈希查找表实现 map ##### （一）哈希冲突处理 Go 语言采用哈希查找表实现 map，运用链表法解决哈希冲突。当不同`key`哈希至同一桶时，将新`key - value`对插入桶链表，以此维持数据存储与检索的有效性。 ##### （二）map 内存模型 - **`hmap`结构体**：`hmap`掌控 map 运行，`count`记录元素数，`flags`示状态，`B`定桶数（`buckets`数组长为`2^B`），`noverflow`估溢出桶数，`hash0`为哈希种子，`buckets`指向桶数组，`oldbuckets`助扩容，`nevacuate`标扩容进度，`extra`管溢出桶额外信息。 - **`bmap`结构体**：`bmap`为桶结构，编译前含`tophash`数组存`key`哈希高 8 位，后扩充为含`topbits`、`keys`、`values`、`pad`与`overflow`（链下溢桶），最多存 8 个`key - value`对，优化内存且利检索。 #### 三、map 操作原理 ##### （一）创建 map - **语法与底层**：语法上用`make`创建 map，如`ageMp := make(map[string]int)`，指定容量则`ageMp := make(map[string]int, 8)`。底层由`makemap`函数初始化`hmap`各字段，依数据规模算`B`、设`hash0`，按需分配`buckets`与`extra`内存。 ##### （二）哈希函数选择 程序启动测 CPU，依结果选 aes hash 或 memhash 计算`key`哈希值，并按`key`类型设`_type`结构体`alg`字段的`hash`与`equal`函数，如`string`类型有特定`hash`与`equal`函数，适配数据类型提升处理效率。 ##### （三）key 定位过程 - **桶定位**：64 位机里，`key`哈希后取最后`B`位作桶编号（类似取余，位操作优化）定桶位置，如`B = 5`时桶数`32`，哈希低 5 位导`key`入桶。 - **桶内 key 定位**：用哈希高 8 位在桶内找`key`，无则循`overflow`桶链表续寻。`mapaccess`系列函数（如`mapaccess1`）执行查找，先查 map 有效性与冲突，算哈希定桶址，处理扩容，再桶内、溢出桶遍历找`key`，依`alg.equal`判等定位`value`，无果返零值。 ### HTTP 和 HTTPS 的工作过程及 HTTPS 如何保证安全 #### HTTP 工作过程 HTTP（超文本传输协议）是一种用于在网络上请求和接收网页的通信协议。它的工作流程大致如下： 1. **客户端发起请求**：当用户在浏览器中输入网址或点击链接时，浏览器作为客户端会向服务器发送一个HTTP请求。 2. **建立TCP连接**：客户端与服务器之间通过三次握手建立TCP连接。 3. **发送HTTP请求**：一旦TCP连接建立完成，客户端就会通过这个连接发送HTTP请求给服务器。 4. **服务器响应**：服务器接收到请求后处理，并根据请求的内容返回相应的HTML页面或其他资源。 5. **关闭连接**：数据传输完毕后，通常情况下，客户端和服务器之间的TCP连接会被关闭。 #### HTTPS 工作过程 HTTPS（超文本传输安全协议）是在HTTP基础上增加了SSL/TLS加密层的安全版本。其主要目的是确保数据传输的安全性和完整性。以下是HTTPS的基本工作流程： 1. **客户端发起HTTPS请求**：用户访问一个以`https://`开头的网站，浏览器作为客户端将尝试与服务器建立安全连接。 2. **TLS握手阶段**： - 客户端发送一个“Client Hello”消息给服务器，其中包含支持的加密套件列表等信息。 - 服务器回应“Server Hello”，选择双方都支持的一种加密算法，并提供自己的数字证书。 - 客户端验证服务器提供的数字证书是否有效（由可信赖的CA颁发）。如果证书有效，则继续下一步；否则终止连接。 - 客户端生成一个随机数（预主密钥），用服务器公钥加密后发送给服务器。 - 服务器用自己的私钥解密得到预主密钥，并基于此计算出对称密钥。 - 双方使用相同的算法根据预主密钥生成最终的对称密钥，用于后续的数据加密。 3. **建立安全通道**：通过上述步骤协商好的对称密钥来加密所有后续的通信内容，确保信息传输过程中不会被窃听或篡改。 4. **发送HTTPS请求/响应**：在这个安全的加密通道上，客户端发送HTTPS请求，服务器处理请求并返回响应。 5. **结束会话**：数据交换完成后，可以正常关闭TCP连接，也可以保持连接以供未来的请求复用。 #### HTTPS 如何保证安全 HTTPS 通过以下几种方式来保证数据传输的安全性： - **信息加密**：使用对称加密技术（如AES）对实际传输的数据进行加密，防止中间人攻击者获取明文信息。而为了安全地交换对称加密所需的密钥，HTTPS 使用非对称加密（如RSA）来进行首次密钥交换。 - **身份认证**：通过数字证书机制确认服务器的身份。客户端可以验证服务器提供的证书是否是由可信的证书授权机构（CA）签发的，从而避免连接到假冒的服务器。 - **数据完整性**：利用哈希函数（如SHA-256）为每条消息创建一个唯一的摘要，确保即使是很小的信息更改也能被检测出来。此外，还会应用HMAC（基于密钥的消息认证码）进一步增强安全性。 - **防止重放攻击**：通过加入时间戳或者其他唯一标识符，使得每次请求都是独一无二的，阻止攻击者简单地重复之前捕获的有效请求。 ### 证书为什么安全，用了哪些算法 数字证书是用于在网络通信中验证身份的一种电子文档。它由可信赖的第三方——证书授权机构（Certificate Authority, CA）签发。每个证书包含以下信息： - **主体名称**：通常是拥有该证书的个人、组织或服务的身份标识。 - **公钥**：与证书持有者的私钥配对的公开密钥。 - **有效期**：证书的有效时间段。 - **颁发者信息**：签发证书的CA的信息。 - **签名**：由CA使用其私钥对证书内容进行数字签名的结果。 #### 安全性的原因 证书之所以被认为是安全的，主要因为以下几个方面： - **信任链**：用户设备上预装了一系列根CA的公钥。当一个网站提供它的证书时，浏览器会检查这个证书是否由已知且可信的根CA直接或间接地签署。这种层级结构被称为“信任链”。 - **非对称加密**：在PKI体系中，使用了非对称加密技术，即一对相关的密钥——公钥和私钥。只有证书所有者知道私钥，而任何人都可以通过对应的公钥来验证证书的真实性。如果能够成功解密用证书中的公钥加密的数据，则证明该证书有效。 - **数字签名**：为了确保证书没有被篡改，CA会在证书上添加一个数字签名。这个签名是通过将证书的内容哈希后，再用CA的私钥加密生成的。接收方可以使用相应的CA公钥解密并验证签名，从而确认证书自颁发以来未被修改过。 #### 使用的关键算法 - **非对称加密算法**：如RSA、ECC（椭圆曲线密码学）。这些算法用于生成公私钥对，并允许一方用另一方的公钥加密消息，只有持有对应私钥的人才能解密。例如，在TLS握手过程中，客户端利用服务器提供的公钥来加密会话密钥。 - **哈希函数**：如SHA-256、SHA-384等。哈希函数用于创建固定长度的消息摘要，即使输入有微小变化也会导致完全不同的输出。它们广泛应用于数字签名过程，以保证数据完整性。 - **数字签名算法**：如RSA-PSS、ECDSA（基于椭圆曲线的数字签名算法）。这些算法结合了哈希函数和非对称加密，为文档或消息提供不可否认性和完整性保护。CA使用自己的私钥对证书进行数字签名，而任何人都可以用CA的公钥验证这个签名。 - **证书格式标准**：X.509 是最常用的数字证书格式规范，定义了证书应该包含哪些字段及其编码方式。它还规定了如何处理证书撤销列表（CRLs）和在线证书状态协议（OCSP），以确保不再有效的证书不会被误认为是可靠的。 ### Https底层用了什么加密算法 HTTPS 的底层加密机制主要包括了对称加密、非对称加密以及哈希函数。具体使用的算法可以取决于服务器和客户端之间的协商，通常包括但不限于： - **非对称加密**：如 RSA 或 ECC（椭圆曲线密码学），用于安全地交换对称密钥。 - **对称加密**：如 AES（高级加密标准），用于实际的数据传输加密。 - **哈希函数**：如 SHA-256 或 SHA-384，用于创建消息认证码（MAC）以保证数据完整性。 ### 读写锁互斥锁底层如何实现的 读写锁（Read-Write Lock，也称为共享-独占锁或RWLock）是一种同步原语，它允许多个线程同时读取共享资源（即读操作可以并发进行），但当有线程需要写入时，必须获得独占访问权限（即写操作期间不允许其他任何读或写）。 在Go语言中，`sync`包提供了`RWMutex`类型来实现读写锁。 #### 底层实现原理 读写锁的底层实现依赖于操作系统提供的同步原语以及编程语言本身的特性： 1. **基于互斥锁和条件变量**： - 使用一个互斥锁保护内部状态。 - 使用两个条件变量分别管理等待读取和等待写入的线程队列。 - 维护读者计数器：如果计数器大于0，则表示当前有活跃的读取者；如果等于0，则没有活跃的读取者。 - 写者请求锁时，会检查是否有活跃的读取者或者写者存在，如果有则阻塞自己直到所有活跃的读取者完成操作并且没有其他写者持有锁。 2. **公平性策略**： - 为了防止饥饿问题（即某些线程永远无法获得锁），实现可能会采用某种形式的公平调度算法，例如先来先服务（FIFO）队列来决定下一个应该被授予锁的线程。 3. **自旋锁优化**： - 对于轻量级竞争的情况，一些实现可能会使用自旋锁代替阻塞式的等待，以减少上下文切换带来的开销。不过这种方法适用于低争用率的情形。 ### Char和varchar的区别 `CHAR` 和 `VARCHAR` 是数据库中用于存储字符数据的两种常见数据类型，它们之间有一些关键的区别。 #### CHAR - **固定长度**：`CHAR(n)` 类型定义了一个固定长度为 `n` 的字符串字段。无论实际存储的数据有多长，都会占用 `n` 个字符的空间。如果输入的数据短于 `n`，则会用空格填充到指定长度。 - **存储效率**：对于总是或几乎总是具有相同长度的数据（如邮政编码、国家代码等），使用 `CHAR` 可能更有效，因为它减少了每次插入或更新时确定实际数据长度的开销。 - **性能**：在某些情况下，由于其固定的存储大小，`CHAR` 可能在索引和比较操作上表现出更好的性能，特别是在处理大量短字符串时。 #### VARCHAR - **可变长度**：`VARCHAR(n)` 定义了一个最大长度为 `n` 的字符串字段，但只占用实际需要的空间加上一个额外的小开销（通常是1到4个字节，用来记录实际使用的长度）。因此，它适合存储长度变化较大的文本数据。 - **存储效率**：当存储的字符串长度差异较大时，`VARCHAR` 能够节省存储空间，因为它不会为未使用的字符分配空间。 - **性能**：虽然 `VARCHAR` 在插入和更新时可能稍微慢一些，因为需要计算实际的数据长度，但在大多数现代数据库系统中，这种差异非常小，通常可以忽略不计。此外，`VARCHAR` 对于长字符串的搜索和排序操作同样高效。 ### 僵尸进程如何产生，以及如何解决，原因是什么 **僵尸进程是指一个子进程在其父进程中结束之后，仍然存在于进程表中的一种状态**。 这种状态下的进程实际上已经完成了它的所有任务并且释放了其占用的资源，但是它在进程表中的条目尚未被删除。 造成这种情况的原因主要是因为父进程还没有调用 `wait` 或者 `waitpid` 系统调用来获取子进程的退出状态信息。 #### 僵尸进程产生的原因 1. **父进程未调用 wait/waitpid**：当子进程终止时，操作系统不会立即清除进程表中的相关信息，而是等待父进程通过调用 `wait` 或 `waitpid` 来收集子进程的状态。如果父进程忽略了这一点，那么即使子进程已经完成工作，它依然会保持在僵尸状态下，直到父进程读取了它的退出码。 2. **父进程崩溃或意外终止**：如果父进程在子进程之前崩溃或者异常退出，而没有机会去调用 `wait` 或 `waitpid`，那么子进程就会变成孤儿进程，并且由 init 系统（PID 为1的进程，在现代Linux系统中通常是 systemd）接管。虽然 init 会定期清理这些孤儿进程，但在某些情况下，它们可能暂时成为僵尸进程。 3. **信号处理不当**：如果父进程对 SIGCHLD 信号进行了不正确的处理（例如忽略了该信号），这可能导致它无法及时响应子进程的结束事件，从而导致僵尸进程的出现。 4. **编程错误**：程序员可能会忘记在代码中正确处理子进程的状态，尤其是在多线程或多进程环境中，容易忽略一些细节问题。 #### 解决方法 1. **调用 wait 或 waitpid**：最直接的方法是在父进程中确保每次创建子进程后都正确地调用了 `wait` 或 `waitpid` 函数来回收子进程的状态。这样可以避免子进程进入僵尸状态。 ```c pid_t pid; int status; pid = wait(&status); ``` 2. **使用 signal(SIGCHLD, SIG_IGN)** ：如果你不需要关心子进程的退出状态，可以在父进程中设置忽略 SIGCHLD 信号。这样做可以让操作系统自动回收子进程的资源，防止它们变成僵尸进程。 ```c signal(SIGCHLD, SIG_IGN); ``` 3. **使用 sigaction 设置 SA_NOCLDWAIT 标志**：另一种方法是使用 `sigaction` 函数来安装 SIGCHLD 信号处理器，并设置 `SA_NOCLDWAIT` 标志，这将使子进程在终止时不留下僵尸进程。 ```c struct sigaction sa; sa.sa_handler = SIG_IGN; sa.sa_flags = SA_NOCLDWAIT; sigemptyset(&sa.sa_mask); sigaction(SIGCHLD, &sa, NULL); ``` 4. **采用双叉策略**：对于需要频繁创建和销毁子进程的应用程序，可以考虑使用双重分叉（double fork）技术。第一次分叉生成一个中间进程，第二次分叉生成实际的工作子进程。然后让中间进程退出，使得工作子进程成为孤儿进程，由 init 进程收养并负责清理。 5. **定期检查与清理**：在某些复杂的情况下，可以通过编写脚本或程序定时扫描系统中的僵尸进程，并采取适当的措施（如重启相关服务）以减少它们的影响。 6. **使用守护进程框架**：许多高级语言和框架提供了更简便的方式来管理子进程，例如 Python 的 `subprocess` 模块、Node.js 的 `child_process` API 等，它们通常内置了对僵尸进程的有效管理机制。 ### 操作系统如何启动一个线程 一般就这几个流程： 1. **创建线程结构** - **分配资源**：操作系统首先需要为新线程分配必要的系统资源，比如栈空间、线程本地存储（TLS）等。每个线程都有自己的独立栈，用于保存函数调用时的局部变量和返回地址。 - **初始化线程控制块 (TCB)** ：每个线程都有一个对应的线程控制块，其中包含了描述线程状态所需的各种信息，如线程ID、优先级、调度策略、寄存器上下文（包括程序计数器PC）、内存映射信息等。 2. **注册到调度器** - **加入就绪队列**：一旦线程被创建并成功初始化后，它会被添加到操作系统的调度器所维护的一个或多个就绪队列中。调度器负责决定何时以及哪个线程应该获得CPU时间片来运行。 - **设置初始状态**：根据创建线程的方式，可能会将线程置于可运行状态或者等待某个条件满足后再变为可运行状态。 3. **启动执行** - **加载上下文**：当调度器选择该线程执行时，会通过上下文切换机制将线程的寄存器值和其他必要信息加载到CPU中。这一步骤使得线程可以从上次停止的地方继续执行。 - **跳转到起始点**：最后，CPU会跳转到线程入口函数的起始地址开始执行。这个入口函数通常是由程序员提供的，并且包含了线程要完成的任务逻辑。 ### 代码题（go 实现） - 定义三个不同的goroutine，其中第一个goroutine固定打印"A"，第二个goroutine固定打印"B"，第三个 goroutine固定打印"C"现有一个输入n，表示循环"ABC"字符串的数量，请按照期望输出指定的结果。 - 例如: - 输入:1 ，输出:"ABC"； - 输入:3 ，输出:"ABCABCABC" >看到这里的小伙伴可以思考一下这一题，**把思路发到评论区和大家一起讨论**，如果需要答案的小伙伴可以私信我。