腾讯云智后台开发

来源：https://www.nowcoder.com/discuss/542673225575096320

1、模板相关？

C++ 模板类是一种通用编程技术，允许你编写通用的数据结构和算法，不仅可以处理不同数据类型，还可以处理不同数据结构的数据。

为什么使用模板类？
- 模板类允许你编写通用的数据结构和算法，可以适用于不同的数据类型。
- 它提高了代码的重用性，因为你可以使用相同的类定义来处理不同类型的数据。
- C++ 标准库中的许多容器（例如 std::vector、std::list）和算法（例如 std::sort）都是使用模板类实现的。
模板类的声明和定义
- 模板类的声明以 template 关键字开始，后跟一个模板参数列表，使用 < > 括起来，通常包括类型参数。
- 类的定义使用模板参数来指定类的成员的类型。
- 类的成员函数可以在类内部定义，也可以在类外部定义。通常，成员函数的定义需要在类的模板声明之后提供。

c++

template <typename T>
class MyTemplateClass {
public:
    MyTemplateClass(T data);
    T getData();
private:
    T data_;
};

template <typename T>
MyTemplateClass<T>::MyTemplateClass(T data) : data_(data) {}

template <typename T>
T MyTemplateClass<T>::getData() {
    return data_;
}

模板类的使用
- 使用模板类时，你需要提供具体的数据类型，以实例化模板类。
- 这可以通过提供模板参数来实现。例如，MyTemplateClass<int> 实例化了一个处理整数的模板类。
- 可以创建多个不同数据类型的模板类实例。

c++

MyTemplateClass<int> intInstance(42);
MyTemplateClass<double> doubleInstance(3.14);

非类型模板参数
- 除了类型参数，模板还支持非类型模板参数，这些参数可以是常数值、枚举或指针。
- 非类型参数可以用于在编译时确定模板的一些属性。

c++

template <int Size>
class FixedArray {
public:
    int GetSize() { return Size; }
    // ...
};

模板的特化和偏特化：
- 可以对特定类型的参数创建特化版本的模板类。
- 偏特化允许你对模板参数的某些属性进行特化，以满足不同情况的需求。

c++

template <typename T>
class MyTemplateClass;

template <>
class MyTemplateClass<int> {
    // Specialized implementation for int
};

限定类型参数：
- 使用 typename 或 class 关键字可以指定模板参数的类型。
- 可以使用 typename 或 class 以及适当的约束来限制接受的模板参数类型。

c++

template <typename T>
void MyFunction(T value);

模板类的编译和实例化

C++ 中的模板类是在编译时实例化的。
编译器根据使用模板类的上下文为特定类型生成实例化的类。
这意味着只需提供一次模板定义，可以在不同地方和不同类型的数据上使用。

模板元编程
- 模板类不仅可以用于创建通用数据结构，还可以用于进行元编程，生成和处理代码。
- 使用模板元编程，你可以在编译时生成代码，以提高程序的性能和灵活性。

2、自己怎么实现优先级队列？

优先级队列通常可以使用堆（heap）数据结构，特别是二叉堆。

可以参照下边这个思路：

使用一个支持动态增长的数据结构来存储元素，例如动态数组（std::vector）或链表。
确保队列中的元素按照优先级排序。这可以通过在插入元素时，确保插入的位置是正确的来实现。这需要在插入元素时进行比较，并根据优先级的大小找到正确的位置。最小的元素应该在队列的前面，以便它可以很容易地被取出。
实现 push 操作以插入新元素，并确保它被正确排序。 push 操作需要在内部进行比较和移动元素，以保持队列的排序。
实现 pop 操作以移除并返回队列中的最小元素。这通常是队列中的第一个元素。
实现 top 操作以返回队列中的最小元素，而不移除它。

实现一个最小堆（小顶堆）优先级队列，示例代码：

c++

#include <iostream>
#include <vector>

template <typename T>
class PriorityQueue {
private:
    std::vector<T> heap;

    // 上浮元素以维护堆的性质
    void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[index] < heap[parentIndex]) {
                std::swap(heap[index], heap[parentIndex]);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 沉元素以维护堆的性质
    void heapifyDown(int index) {
        int leftChild, rightChild, minIndex;
        while (true) {
            leftChild = 2 * index + 1;
            rightChild = 2 * index + 2;
            minIndex = index;

            if (leftChild < heap.size() && heap[leftChild] < heap[minIndex]) {
                minIndex = leftChild;
            }
            if (rightChild < heap.size() && heap[rightChild] < heap[minIndex]) {
                minIndex = rightChild;
            }

            if (minIndex != index) {
                std::swap(heap[index], heap[minIndex]);
                index = minIndex;
            } else {
                break;
            }
        }
    }

public:
    // 插入元素并维持堆的性质
    void push(T value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    // 移除并返回队列中的最小元素
    void pop() {
        if (empty()) {
            std::cerr << "PriorityQueue is empty!" << std::endl;
            return;
        }
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }

    // 返回队列中的最小元素
    T top() {
        if (empty()) {
            std::cerr << "PriorityQueue is empty!" << std::endl;
            return T();
        }
        return heap[0];
    }

    // 检查队列是否为空
    bool empty() {
        return heap.empty();
    }

    // 获取队列大小
    size_t size() {
        return heap.size();
    }
};

int main() {
    PriorityQueue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

3、vector扩容，插入时间复杂度？

先来说说跟扩容有关的概念：

容量 (capacity)：std::vector 内部会维护一个容量，表示当前动态数组可以容纳的元素数量。容量通常大于或等于当前 std::vector 的大小（元素数量）。容量是动态调整的，当元素数量超过当前容量时，std::vector 会执行扩容操作。

Windows扩容底层（1.5倍）

Windows中堆管理系统会对释放的堆块进行合并，当堆管理器发现2个空闲块彼此相邻的时候，就会对堆块进行合并。因此，vs下的vector扩容机制选择使用1.5倍的方式扩容，这样多次扩容之后，就可以使用之前已经释放的空间。

Linux的扩容底层（2倍）

linux下主要使用glibc的ptmalloc来进行用户空间申请的，如果malloc的空间小于128KB，其内部通过brk()来扩张，如果大于128KB且arena中没有足够的空间时，通过mmap将内存映射到进程地址空间。rena是什么？我们可以理解为是一块内存区域

扩容倍数为2时，时间上占优势，扩容倍数为1.5时，空间上占优势。
vector在push_back以成倍增长可以在均摊后达到O(1)的事件复杂度，相对于增长指定大小的O(n)时间复杂度更好。
为了防止申请内存的浪费，现在使用较多的有2倍与1.5倍的增长方式，而1.5倍的增长方式可以更好的实现对内存的重复利用。

时间复杂度：

在最坏情况下，插入操作的时间复杂度是 O(n)，其中 n 表示当前 std::vector 中的元素数量。这是因为在插入元素时，如果需要移动已有元素，需要将后续的元素逐个后移。如果插入操作位于末尾，它的时间复杂度可以视为 O(1)。

需要注意的是，std::vector 的动态扩容会导致元素的重新分配和复制，这可能在频繁插入大量元素时引起性能问题。为了避免频繁扩容，可以在初始化 std::vector 时估算好元素数量（使用 reserve 函数预留一定容量），以减少扩容的次数。

4、内存分布？

五大分区

栈：栈是用于存储函数的局部变量和函数调用信息的内存区域。每当调用一个函数，系统会为其分配一个栈帧，包含局部变量和函数参数。当函数执行完毕，栈帧被弹出，释放相关内存。栈的分配和释放速度很快，但大小通常受限于系统。
堆：堆是用于动态内存分配的区域，通常由开发人员手动分配和释放。堆上的内存需要手动管理，因此需要小心避免内存泄漏和悬挂指针问题。堆的大小通常比栈大，但分配和释放速度较慢。
全局/静态存储区：这是用于存储全局变量和静态变量的区域。全局变量是在程序启动时创建的，持续到程序结束，而静态变量在它们首次访问时初始化，然后保持其值在函数调用之间保持不变。
自由存储区：就是那些由malloc等分配的内存块，他和堆是十分相似的，不过它是用free来结束自己的生命的。
常量存储区，这是一块比较特殊的存储区，他们里面存放的是常量，不允许修改（当然，你要通过非正当手段也可以修改，而且方法很多）

5、智能指针，原理，什么时候释放内存？

std::shared_ptr：
- 原理：std::shared_ptr 使用引用计数来管理内存。每当你将一个 std::shared_ptr 指向某个对象时，引用计数会增加。当引用计数达到零（没有任何 shared_ptr 指向该对象）时，对象的内存将被自动释放。
- 何时释放内存：当最后一个指向对象的 std::shared_ptr 被销毁或重置时，对象的内存会被释放。
std::unique_ptr：
- 原理：std::unique_ptr 使用独占所有权语义，确保只有一个指针可以拥有资源。它不使用引用计数，而是在 std::unique_ptr 被销毁时自动释放资源。
- 何时释放内存：当 std::unique_ptr 被销毁、离开其作用域或通过 std::move 转移资源时，资源会被释放。
std::weak_ptr：
- 原理：std::weak_ptr 是一种弱引用智能指针，它用于协助解决循环引用问题。它不会增加引用计数，仅用于监视 std::shared_ptr 的状态。
- 何时释放内存：std::weak_ptr 不会直接释放内存，它只是用于观察 std::shared_ptr 的生命周期。内存释放由相关的 std::shared_ptr 负责。
std::auto_ptr（已过时，不建议使用）：
- 原理：std::auto_ptr 具有独占所有权，类似于 std::unique_ptr。但它有一些缺陷，不支持复制操作，且没有移动语义。
- 何时释放内存：当 std::auto_ptr 被销毁时，它会释放其内存。然而，由于其缺陷，它容易导致不安全的内存管理。

6、指针和引用？

指针：

定义：指针是一个存储变量内存地址的变量。它包含了一个内存地址，可以指向其他变量。
声明方式：通过在变量类型前面加上*符号来声明指针。例如，int* ptr; 表示 ptr 是一个指向整数的指针。
空指针：指针可以具有空值（nullptr或NULL），表示它不指向任何有效的内存地址。
指针运算：可以使用指针进行各种运算，如指针加法和减法，以访问内存中的不同位置。
指针的修改：指针可以被重新赋值，指向不同的内存位置。
指针的优点：指针更加灵活，可以用于动态分配内存，以及通过指针修改变量的值。

引用：

定义：引用是一个别名，它代表了已经存在的变量。引用本身不占用内存空间，只是给变量起了一个别名。
声明方式：通过在类型前加上&符号来声明引用。例如，int x = 10; int& ref = x; 表示 ref 是 x 的引用。
不可空：引用必须在声明时初始化，且不能改变指向。一旦引用与某个变量关联，它将一直引用该变量，无法改变。
不可引用临时对象：引用不能绑定到临时对象（如表达式的结果）上，除非该临时对象是常量。
引用的优点：引用更加安全，可以避免指针的一些问题，如空指针、悬挂指针等。

区别：

使用场景：指针通常用于需要动态分配内存、通过函数参数传递对象等情况，而引用通常用于函数参数传递、避免拷贝大对象等情况。
空值：指针可以为空，引用不能。
指向：指针可以指向不同的对象，引用在创建时绑定到一个对象后不能改变。
操作：指针需要显式解引用（*）来访问变量，而引用可以直接使用。
安全性：引用相对更加安全，因为它通常不会导致空指针异常。

7、select和epoll，要拷贝几次？

select 每次调用都会拷贝文件描述符集合，所以会有多次拷贝。
- 每次调用 select 函数时需要拷贝传入的读、写和异常文件描述符集合。
- select 调用返回后，需要遍历几个文件描述符集合，处理就绪的文件描述符。
epoll 每次调用都不需要拷贝文件描述符集合。当你向 epoll 注册文件描述符时，你提供一个指向该文件描述符的指针，而不是拷贝文件描述符的集合。
性能
- select
  - 在大量文件描述符上调用 select 时，会有性能下降。
  - select 的时间复杂度是 O(n)，对于大数量的文件描述符会导致性能下降。
  - select 通常需要将大量文件描述符的状态通过遍历全部描述符来找到就绪的描述符，这也导致性能下降。
- epoll
  - epoll 的时间复杂度是 O(1)，不随文件描述符数量线性增加。
  - epoll 使用回调机制，只返回就绪的文件描述符，不需要遍历全部描述符。
  - epoll 支持水平触发和边缘触发两种模式，允许更精细的控制。

8、零拷贝，底层实现？

"零拷贝"中的"拷贝"是操作系统在I/O操作中，将数据从一个内存区域复制到另外一个内存区域。而"零"并不是指0次复制，更多的是指在用户态和内核态之间的复制是0次。

零拷贝的实现通常涉及以下几个主要组成部分：

内核缓冲区和 DMA：
- 零拷贝通常依赖于内核中的缓冲区，这些缓冲区通常称为内核缓冲区或页缓冲区。应用程序可以将数据写入这些内核缓冲区，而不需要中间的拷贝。
- DMA（Direct Memory Access）是一种机制，允许外围设备（如网卡或磁盘控制器）直接访问内存，而不需要通过 CPU，这有助于减少数据在内存中的不必要复制。
共享内存：
共享内存是一种 IPC（进程间通信）机制，它允许多个进程访问相同的物理内存区域。在零拷贝中，共享内存通常用于在应用程序和内核之间传递数据，避免复制操作。
scatter-gather I/O：
scatter-gather I/O 是一种 I/O 模型，它允许应用程序通过一个描述符列表（通常称为散射-聚集列表）来描述数据的位置，而不需要将数据连续存储。这使得从多个内存位置读取或写入数据更加高效。
文件映射（mmap）：
文件映射是一种技术，它将文件的内容映射到进程的地址空间，允许进程直接读取或写入文件，而不需要额外的数据复制。
splice 和 tee 系统调用：
splice 和 tee 是一些系统调用，它们可以直接在两个文件描述符之间传输数据，而不需要额外的数据拷贝。
网络套接字缓冲区：
零拷贝还可以在网络编程中发挥作用。套接字缓冲区的特性可以被配置为支持零拷贝操作。

9、进程地址空间，操作系统分配给进程100M，用完了要使用新的内存该怎么办？

当一个进程用尽了已分配的虚拟内存空间，需要继续分配更多的内存时，可以通过以下方式来处理：

内存页交换：
如果操作系统支持虚拟内存，当进程用尽了已分配的虚拟内存空间，但物理内存仍然足够，操作系统可以将进程的一部分数据移到磁盘上，以释放内存。当进程需要访问这些数据时，操作系统会将其重新加载到内存中。这个过程叫做内存页交换。
分配新的虚拟内存：
如果进程需要更多的虚拟内存空间，操作系统可以分配更多的虚拟内存页给该进程。这些新分配的虚拟内存页可以映射到物理内存或者磁盘上，具体取决于操作系统的实现。
内存映射文件：
另一种方法是使用内存映射文件的技术。进程可以将文件映射到其地址空间，允许文件的内容直接映射到内存中。当进程用完了已分配的虚拟内存空间，可以将文件的其他部分映射到内存中。这样，进程可以使用磁盘上的文件作为扩展内存。
动态内存分配：
进程可以使用动态内存分配函数（例如 malloc、new 等）来在运行时分配内存。这些函数会请求操作系统提供一块内存，并返回一个指向该内存的指针。进程可以根据需要多次调用这些函数，以扩展其内存使用。

10、内存换入换出是换出到哪里？

内存换出：当操作系统决定需要释放物理内存时，它会选择一个进程或一部分数据，并将其写入磁盘上的交换文件。这个过程确保了数据的持久性，因为数据被写入磁盘，即使计算机关机或崩溃，数据也不会丢失。通常，操作系统会选择不活跃的、长时间未使用的数据进行换出。
内存换入：当需要访问已经换出的数据时，操作系统会执行内存换入操作。这意味着从磁盘上的交换文件中将数据加载到物理内存中，以便进程可以再次使用它。这个过程可能会导致一些性能开销，因为从磁盘读取数据通常比从内存读取数据慢。

11、输入url到获得页面的过程？

用户输入URL：用户在浏览器的地址栏中输入URL（统一资源定位符），这是他们希望访问的网页的地址。
DNS解析：浏览器首先需要解析URL中的主机名部分，以确定目标服务器的IP地址。这个过程称为DNS解析。如果浏览器有缓存，它可能首先查看本地缓存以获取IP地址。如果不在缓存中，浏览器将向本地DNS服务器发出请求，以获取目标主机的IP地址。本地DNS服务器可以向根DNS服务器、顶级域名服务器和权威DNS服务器逐级查询，最终找到目标主机的IP地址。
建立TCP连接：一旦浏览器获得了目标服务器的IP地址，它将尝试建立到该服务器的TCP连接。这个过程通常涉及三次握手，即浏览器向服务器发送一个连接请求，服务器确认请求并回复，然后浏览器再次确认。一旦建立了TCP连接，数据可以在浏览器和服务器之间进行可靠的双向通信。
发起HTTP请求：一旦TCP连接建立，浏览器会构建一个HTTP请求，该请求包括用户想要获取的特定页面的信息。HTTP请求通常包括请求方法（如GET、POST等）、请求头部和请求主体。
服务器处理请求：服务器接收到浏览器发送的HTTP请求后，会根据请求的内容执行相应的操作。这可能涉及查询数据库、处理业务逻辑、生成动态内容等。
服务器发送HTTP响应：服务器会生成一个HTTP响应，该响应包含请求的内容（通常是HTML页面）、状态码（表示请求是否成功、重定向等）以及响应头部信息。服务器还将此HTTP响应发送回浏览器。
接收和渲染页面：一旦浏览器收到HTTP响应，它会解析响应的内容，并根据HTML、CSS和JavaScript等数据渲染页面。这包括呈现文本、图像、链接和其他媒体，以及执行JavaScript代码。
页面展示：最终，浏览器将渲染后的页面呈现给用户，用户可以与页面进行交互。
页面缓存：浏览器通常会将页面的一些资源（如图像、样式表、脚本等）缓存，以便在用户再次访问相同页面时能够更快地加载。

12、UDP用在哪些地方，直播怎么保证数据有序性？

UDP（用户数据报协议）是一种无连接的、不可靠的数据传输协议，与TCP相比，它不提供数据包的可靠性、顺序性和拥塞控制。

应用场景：

实时应用： UDP适用于对数据传输的实时性要求较高的应用，如VoIP（Voice over IP）电话通话、视频通话以及在线游戏等。这些应用程序更注重数据的及时传输，而不一定需要保证数据的可靠性和顺序性。
广播和多播： UDP支持多播和广播数据传输，适用于将数据一次性发送给多个接收方的场景，如在线直播、流媒体等。
DNS查询： DNS（Domain Name System）查询通常使用UDP进行域名解析，因为它的开销较小，可以快速获取解析结果。
监控和测量应用： UDP常用于监控和测量应用，它可以在一定程度上减小开销，允许快速传输数据。

在直播保证数据的有序性时需要下边措施：

序号和缓冲区：在直播数据包中，每个数据包通常都包含一个序号，表示它在有序序列中的位置。接收方使用这些序号来将数据包按正确的顺序组装起来。此外，接收方维护一个缓冲区，用于存储已经接收到但尚未按序的数据包。
重传机制：如果接收方检测到数据包丢失，它可以向发送方请求重传。这要求发送方支持重传请求，并可以根据需要重新发送数据包。
数据包排序：在直播服务器端，数据包可以被排序并按照正确的顺序发送。这可以通过重新排序数据包的序号来实现。
前向纠错：一些直播流采用前向纠错技术，允许接收方在丢失部分数据包的情况下仍然恢复数据。这通常会在数据包中添加冗余信息，以帮助纠正错误。
应用层处理：在一些应用中，接收方可以通过应用层协议来处理数据包的有序性。这可能需要更高的复杂性，但可以提供更大的灵活性。

13、用户级线程、内核级线程区别？

用户级线程：

线程管理在用户空间：用户级线程完全由应用程序或用户级库管理，而不需要内核的参与。线程的创建、切换、调度等操作都由用户级代码完成。
轻量级：用户级线程非常轻量级，创建、销毁和切换用户级线程的开销较低，因为这些操作不需要内核态切换。
快速：由于不涉及内核切换，用户级线程的创建和切换速度较快，适用于需要大量线程并且频繁切换的应用。
非阻塞：用户级线程在进行阻塞调用（如I/O操作）时，可能会阻塞整个进程，因为内核不知道用户级线程的存在，无法将控制返回给其他线程。

内核级线程（Kernel-Level Threads，KLTs）：

线程管理在内核空间：内核级线程由操作系统内核管理。线程的创建、销毁和调度等操作由内核完成，应用程序无法直接控制。
重量级：内核级线程相对重量级，因为线程的操作需要涉及内核态切换，涉及更多的上下文切换开销。
可靠：内核级线程对系统的可靠性有更好的支持，因为操作系统可以更好地处理阻塞和异步操作。
多核利用：内核级线程能够更好地利用多核处理器，因为操作系统可以将线程分配到不同的核心上，实现并行执行。

14、操作系统共享内存的实现方式？

共享内存（share memory）是一种最为高效的进程间通信方式，是因为进程能够直接对内存进行读写，且不需要进行数据的保存与复制。

为了实现在多个进程间高效的数据通信，linux内核特地留下一块内存区，该内存区能够被需要的进程映射到自身的内存空间。因此，进程便能够直接对这块内存区进行读写操作。

常见的有以下两种：

POSIX共享内存： POSIX兼容的操作系统提供了一种叫做“POSIX共享内存”的共享内存机制。它使用 shm_open 函数创建共享内存对象，然后使用 mmap 函数将共享内存对象映射到进程的地址空间。这种方式更加便于跨平台开发。
mmap内存共享映射：mmap本来的是存储映射功能。它可以将一个文件映射到内存中，在程序里就可以直接使用内存地址对文件内容进行访问，这可以让程序对文件访问更方便。

其相关调用API原型如下：

c++

#include <sys/mman.h>

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

int munmap(void *addr, size_t length);

由于这个系统调用的特性可以用在很多场合，所以Linux系统用它实现了很多功能，并不仅局限于存储映射。在这主要介绍的就是用mmap进行多进程的内存共享功能。Linux产生子进程的系统调用是fork，根据fork的语义以及其实现，我们知道新产生的进程在内存地址空间上跟父进程是完全一致的。所以Linux的mmap实现了一种可以在父子进程之间共享内存地址的方式，其使用方法是：

父进程将flags参数设置MAP_SHARED方式通过mmap申请一段内存。内存可以映射某个具体文件，也可以不映射具体文件（fd置为-1，flag设置为MAP_ANONYMOUS）。
父进程调用fork产生子进程。之后在父子进程内都可以访问到mmap所返回的地址，就可以共享内存了。

15、布隆过滤器的原理？

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。

工作原理：

数据结构：布隆过滤器通常由一个位数组（bit array）和一组哈希函数组成。位数组的大小取决于预期的元素数量和允许的错误率。
初始化：初始化时，所有位都被置为0。
插入元素：要向布隆过滤器中插入一个元素，首先将元素经过一系列哈希函数的计算，得到多个哈希值。通常会选择多个不同的哈希函数。这些哈希值用于确定位数组中的位置，将这些位置的位设置为1。
检查元素是否存在：要检查一个元素是否存在于布隆过滤器中，同样需要将元素经过相同的哈希函数计算，得到哈希值，然后检查位数组中相应位置的位。如果所有对应位置的位都为1，那么可以确定元素可能存在于集合中；如果有一个位置的位为0，那么可以确定元素一定不存在于集合中。
错误率：布隆过滤器存在一定的错误率，即有时它会误判一个元素存在于集合中，这被称为"假阳性"。错误率的大小取决于哈希函数的数量、位数组的大小和插入元素的数量。可以通过调整这些参数来控制错误率。

优点：

空间占用极小，因为本身不存储数据而是用比特位表示数据是否存在，某种程度有保密的效果。
插入与查询时间复杂度均为 O(k)，常数级别，k 表示散列函数执行次数。
散列函数之间可以相互独立，可以在硬件指令层加速计算。

缺点：

误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

16、本地手写LRUCache，get和set两个函数？

LRU（Least Recently Used）缓存是一种常用的缓存淘汰策略，它会保留最近使用的数据，而淘汰最久未使用的数据。为了实现一个LRU缓存，通常需要使用哈希表和双向链表。

定义数据结构：

定义一个数据结构来表示LRU缓存的节点。这个节点包括两个属性：key 和 value。同时，我们需要使用双向链表来维护节点的顺序，以及一个哈希表来实现快速查找。

c++

struct LRUCacheNode {
    int key;
    int value;
    LRUCacheNode* prev;
    LRUCacheNode* next;
    LRUCacheNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

初始化

在LRUCache的初始化过程中，我们需要指定缓存的容量大小，并创建一个双向链表和一个哈希表。

c++

class LRUCache {
public:
    LRUCache(int capacity) {
        size = capacity;
        head = new LRUCacheNode(-1, -1);
        tail = new LRUCacheNode(-1, -1);
        head->next = tail;
        tail->prev = head;
    }
};

添加节点

当向LRUCache中添加一个节点时，我们需要检查缓存是否已满。如果满了，我们需要淘汰最久未使用的节点，即删除链表尾部的节点，并从哈希表中移除。然后，我们将新节点添加到链表头部和哈希表中。

c++

void addNode(LRUCacheNode* node) {
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
}

获取节点

当获取节点时，我们需要查找哈希表，如果节点存在，我们将该节点移到链表头部，表示它是最近使用的节点。

c++

int get(int key) {
    if (cache.find(key) != cache.end()) {
        LRUCacheNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    return -1;
}

void moveToHead(LRUCacheNode* node) {
    removeNode(node);
    addNode(node);
}

移除节点

当淘汰节点或更新节点时，我们需要将节点从链表中删除，并从哈希表中移除。

c++

void removeNode(LRUCacheNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

淘汰节点

当LRUCache满了，需要淘汰最久未使用的节点。这通常意味着删除链表尾部的节点，并从哈希表中移除它。

c++

void removeLRU() {
    LRUCacheNode* last = tail->prev;
    removeNode(last);
    cache.erase(last->key);
    delete last;
}

更新节点

当更新节点时，我们首先查找哈希表，然后更新节点的值，并将它移到链表头部。

c++

void put(int key, int value) {
    if (cache.find(key) != cache.end()) {
        LRUCacheNode* node = cache[key];
        node->value = value;
        moveToHead(node);
    } else {
        if (cache.size() >= size) {
            removeLRU();
        }
        LRUCacheNode* newNode = new LRUCacheNode(key, value);
        cache[key] = newNode;
        addNode(newNode);
    }
}

微服务

文档

基础

腾讯云智后台开发 ​

1、模板相关？ ​

2、自己怎么实现优先级队列？ ​

3、vector扩容，插入时间复杂度？ ​

4、内存分布？ ​

5、智能指针，原理，什么时候释放内存？ ​

6、指针和引用？ ​

7、select和epoll，要拷贝几次？ ​

8、零拷贝，底层实现？ ​

9、进程地址空间，操作系统分配给进程100M，用完了要使用新的内存该怎么办？ ​

10、内存换入换出是换出到哪里？ ​

11、输入url到获得页面的过程？ ​

12、UDP用在哪些地方，直播怎么保证数据有序性？ ​

13、用户级线程、内核级线程区别？ ​

14、操作系统共享内存的实现方式？ ​

15、布隆过滤器的原理？ ​

16、本地手写LRUCache，get和set两个函数？ ​