面试基础题

2024-10-16  本文已影响0人  血之君殇

哎，干的好好的，突然公司没钱了，被裁员了，被迫又走上了面试之路。

go语言slice和map底层实现原理

在 Go 语言中，slice 和 map 是非常常用的数据结构，它们的底层实现机制虽然隐藏在语言内部，但理解它们的原理对于优化性能、正确使用和避免一些潜在的问题是非常有帮助的。以下是 Go 语言中 slice 和 map 的底层实现原理。

Slice（切片）底层实现

slice 是 Go 中基于动态数组的抽象，它实际上是一个 动态数组的视图，能够动态调整长度。slice 并不存储元素本身，而是提供对底层数组的引用。其底层结构可以用一个简单的结构体来理解：

type Slice struct {
    array unsafe.Pointer  // 指向底层数组的指针
    len   int             // 切片的长度
    cap   int             // 切片的容量
}

  1. array：底层数组
    slice 实际上是对底层数组的引用，数组的大小是固定的。切片之所以可以动态扩展，是因为当容量不足时，会自动生成一个更大的数组，将原有数据复制到新的数组中。

  2. len：长度
    切片的长度表示当前切片中的有效元素个数，由 len() 函数返回。即使底层数组可能更大，len 只代表当前视图中可以访问的元素数。

  3. cap：容量
    容量是指从切片的第一个元素开始，到底层数组末尾的最大元素数。cap() 函数返回容量。当切片的长度超过容量时，Go 会自动扩容。

扩容机制

当切片的容量不足时，Go 会自动将切片扩容。扩容的策略通常是以 2 倍 的方式增长（也有例外，特别是大于 1024 的情况会使用不同的策略）。扩容时，会创建一个新的更大的底层数组，然后将旧数据拷贝到新的数组中。

底层数据共享

切片中的多个变量可能共享相同的底层数组。例如，当你通过 slice[a:b] 创建一个子切片时，新切片仍然引用原切片的底层数组。修改子切片中的元素可能会影响到原切片中的元素。

Map（映射）底层实现

map 是 Go 中的哈希表实现，底层通过 散列表（Hash Table）来实现，能够在常数时间内（O(1)）查找、插入和删除元素。

map 的底层结构可以简单地表示为：

type hmap struct {
    count     int            // map 中实际存储的键值对数量
    buckets   unsafe.Pointer // 指向 bucket 数组的指针
    B         uint8          // bucket 数组的大小是 2^B
    hash0     uint32         // 用于哈希函数的随机种子
    ...
}

核心概念

  1. buckets：桶（bucket）
    map 的核心是一个 bucket 数组，每个 bucket 存储多个键值对。通过哈希函数将键映射到某个 bucket，然后在该 bucket 中查找、插入或删除键值对。

  2. 哈希函数
    Go 使用哈希函数将键映射到 bucket 上。为了减少哈希冲突，Go 对每个 map 生成一个随机的种子 hash0，使得相同的键在不同的 map 中可能有不同的哈希值。

  3. 哈希冲突
    当多个键映射到同一个 bucket 时，会发生哈希冲突。Go 的 map 通过 链地址法（在 bucket 中存储多个键值对）处理冲突。

  4. 扩容机制
    当 map 中存储的元素过多时，会自动扩容。扩容时，Go 会创建一个新的、更大的 bucket 数组，并将所有的键重新分配到新的 bucket 中。这种操作被称为 rehashing，因为所有的键需要根据新的哈希值重新计算位置。

内存布局

性能注意事项

  1. 切片的扩容成本：当切片需要扩容时，会发生内存分配和元素复制操作，因此在高性能场景下，需要合理地初始化切片的容量，避免频繁的扩容。

  2. map 的扩容和哈希冲突：虽然 map 的查找、插入和删除操作的平均时间复杂度是 O(1)，但如果哈希冲突较多或者发生扩容，性能可能会下降。因此，合理的 map 大小初始化可以提高性能，特别是在高并发场景中使用时。

总结：

go语言协程调度原理，协程为什么快

Go 语言中的协程（goroutine）是 Go 并发编程的核心，其高效的调度机制使得 Go 能够在大规模并发程序中表现出色。相比传统的线程，Go 的协程更加轻量且高效，这源于其独特的 协程调度器 和 用户态线程模型。下面我们将详细探讨 Go 协程的调度原理以及它为何如此快速。

协程（goroutine）的特点

  1. 轻量级：相比操作系统线程，协程的创建和销毁开销很小，通常只占用几 KB 的内存。而操作系统线程通常需要更大的内存栈（例如 1 MB 左右），这使得 Go 可以在同一时间内调度大量协程。
  2. 协作式调度：Go 的协程由 Go 运行时（runtime）来管理，并通过调度器来进行协作式调度，而不是交由操作系统内核进行调度，这大大降低了上下文切换的开销。
  3. 动态栈大小：Go 的协程具有动态增长的栈，初始栈空间很小（通常是 2KB 左右），并且随着程序的需求自动增长和收缩，避免了大量内存的浪费。

Go 语言的协程调度模型

Go 的协程调度器实现了类似于 M:N 的用户级线程调度模型，其中：

Go 使用了一个叫做 GMP 模型来管理协程调度，其中包含三大核心组件：

GMP 模型的工作原理

  1. 调度器的结构
    Go 的调度器通过 G-P-M 模型 实现 Goroutine 的调度。每个 M（操作系统线程）都会绑定一个 P（执行上下文），并从 P 的运行队列中获取待执行的 Goroutine。M 和 P 是一对一绑定的，而多个 Goroutine 可以被放在 P 的本地队列中排队等待执行。

  2. 本地队列和全局队列
    每个 P 有一个本地队列，存放待执行的 Goroutine。调度器还维护了一个全局队列，如果 P 的本地队列中没有 Goroutine 可以运行，它就会从全局队列中取任务。如果一个 P 的 Goroutine 过多，它会将部分 Goroutine 偷偷移动到全局队列或其他空闲的 P 中。

  3. 抢占调度
    虽然 Go 的调度器大部分情况下是协作式的，但在 Go 1.14 中引入了 抢占式调度。这意味着 Goroutine 如果运行了太长时间（例如长时间没有发生函数调用），调度器可以强制其暂停并调度其他 Goroutine。这种机制防止了 Goroutine 长时间占用 CPU 而导致其他 Goroutine 饿死。

  4. M 和 P 的动态调整
    Go 运行时会根据负载情况动态调整 M（操作系统线程）的数量。通过 GOMAXPROCS 环境变量可以设置可以使用的 P 的数量，默认情况下，Go 会设置为逻辑 CPU 核心数。M 是与操作系统交互的实际执行线程，而 P 是调度 Goroutine 的核心单位。

协程为什么快？

  1. 轻量级的上下文切换
    相比操作系统级的线程上下文切换，Go 的协程上下文切换开销小得多。Go 协程上下文切换只需保存和恢复少量的栈和寄存器信息，完全在用户态完成，避免了陷入内核态带来的开销。而操作系统线程的上下文切换需要大量的状态保存和恢复，并且涉及到内核态的切换。

  2. 动态栈管理
    Go 的 Goroutine 初始栈空间非常小（2KB），并且会根据需要动态扩展到较大的栈（最高可以扩展到 1GB）。相比之下，操作系统线程通常会预先分配较大的栈空间（通常是 1MB）。Go 的动态栈避免了为每个 Goroutine 预分配大量内存的开销。

  3. 调度策略高效
    Go 的调度器采用协作式调度，减少了不必要的抢占调度。由于调度完全由用户态代码控制，减少了与操作系统内核的交互，进一步提高了调度效率。

  4. 资源复用与抢占调度
    在抢占式调度之前，协程调度依赖于协作式调度机制，即协程在进行 I/O 或系统调用时，主动交出 CPU。抢占调度机制加入后，长时间占用 CPU 的协程可以被强制中断，确保其他协程也能被及时调度，这种灵活的调度机制确保了 Go 可以处理大量的并发任务。

  5. 内存管理和垃圾回收
    Go 的垃圾回收机制（GC）经过多次优化，支持并发回收，使得内存管理在高并发场景下依旧高效。同时，Go 的栈内存管理基于 分段栈 模型，使得 Goroutine 可以在低内存消耗下高效运行，减少了内存压力。

Go 协程调度的优势总结

总结

Go 协程的快速性来源于它轻量级的设计、有效的用户态调度模型（GMP 模型）、抢占式调度、动态栈管理，以及调度器的高效运行机制。相比操作系统的线程，Go 的协程更加高效和灵活，尤其在大规模并发场景中表现出色，因此成为 Go 语言高并发编程的基础。

mysql索引分为几种（b+tree hash表）

MySQL 中的索引是一种用于加速数据检索的结构，它能够显著提高查询性能。常见的 MySQL 索引类型主要有 B+树索引 和 哈希索引，此外还有一些特殊类型的索引。每种索引在不同场景下都有其适用性和优缺点。

1. B+树索引

B+树索引 是 MySQL 中最常见的索引类型，主要应用在 InnoDB 和 MyISAM 存储引擎中。B+树是一种平衡的树形结构，能够快速定位记录。大部分情况下，B+树索引适用于范围查询、排序等操作。

特点：

适用场景：

B+树索引示例：

在 MySQL 中创建 B+树索引的方式：

-- 创建普通索引
CREATE INDEX idx_column ON table_name(column);

-- 创建联合索引（多列索引）
CREATE INDEX idx_columns ON table_name(column1, column2);

B+树索引的不足：

2. 哈希索引

哈希索引 是基于哈希表实现的一种索引类型，它只适用于 Memory 存储引擎。哈希索引通过对键进行哈希运算，将哈希值作为索引存储，这使得它能够非常快速地进行等值查找操作。

特点：

哈希索引示例：

MySQL 中，哈希索引主要应用于 Memory 存储引擎。可以通过以下方式创建哈希索引：

-- 在 Memory 表中创建哈希索引
CREATE TABLE memory_table (
    id INT PRIMARY KEY,
    name VARCHAR(50)
) ENGINE=Memory;

-- 将索引类型指定为哈希索引
CREATE INDEX idx_name ON memory_table(name) USING HASH;

哈希索引的不足：

3. 全文索引（Fulltext Index）

全文索引 是用于对大量文本数据进行搜索的索引类型，主要用于 InnoDB 和 MyISAM 存储引擎。在进行大量文本的模糊搜索或关键词匹配时，全文索引比普通的 LIKE 查询效率更高。

特点：

示例：

-- 创建全文索引
CREATE FULLTEXT INDEX idx_content ON articles(content);

-- 使用全文索引进行查询
SELECT * FROM articles WHERE MATCH(content) AGAINST('keyword');

全文索引的不足：

4. 空间索引（Spatial Index）

空间索引 是用于地理数据类型（如 POINT, LINESTRING, POLYGON 等）的索引，主要用于 MyISAM 存储引擎中，InnoDB 在 MySQL 5.7 开始支持空间索引。它通常用于地理信息系统（GIS）应用，用于处理二维空间的数据。

特点：

示例：

-- 创建空间索引
CREATE SPATIAL INDEX idx_location ON locations(geo_point);

空间索引的不足：

5. 聚簇索引（Clustered Index）

聚簇索引 是 InnoDB 中默认的索引类型，在聚簇索引中，表中的数据行实际上存储在 B+树的叶子节点上。InnoDB 的主键索引就是一种聚簇索引，每个表只能有一个聚簇索引。

特点：

聚簇索引的不足：

总结

MySQL 中常见的索引类型包括：

  1. B+树索引：用于大部分查询场景，支持范围查找和排序，是 MySQL 中最常用的索引类型。
  2. 哈希索引：用于高效的等值查询，但不支持范围查询，适合特定存储引擎。
  3. 全文索引：用于全文搜索和文本匹配，适用于大文本字段的搜索操作。
  4. 空间索引：适用于地理空间数据的查询，在 GIS 应用中较为常见。
  5. 聚簇索引：InnoDB 存储引擎中默认的索引类型，数据按主键顺序存储，支持高效的范围查询。

Redis是单线程的，但Redis为什么这么快

1、完全基于内存，绝大部分请求是纯粹的内存操作，非常快速。数据存在内存中，类似于HashMap，HashMap的优势就是查找和操作的时间复杂度都是O(1)；

2、数据结构简单，对数据操作也简单，Redis中的数据结构是专门进行设计的；

3、采用单线程，避免了不必要的上下文切换和竞争条件，也不存在多进程或者多线程导致的切换而消耗 CPU，不用去考虑各种锁的问题，不存在加锁释放锁操作，没有因为可能出现死锁而导致的性能消耗；

4、使用多路I/O复用模型，非阻塞IO；这里“多路”指的是多个网络连接，“复用”指的是复用同一个线程

5、使用底层模型不同，它们之间底层实现方式以及与客户端之间通信的应用协议不一样，Redis直接自己构建了VM 机制 ，因为一般的系统调用系统函数的话，会浪费一定的时间去移动和请求；

上一篇 下一篇

猜你喜欢

热点阅读