面试常见问题

一、static用法：

1. 静态局部变量

在函数内部声明的静态局部变量，其生命周期贯穿整个程序运行期间，但作用域仅限于该函数。静态局部变量只会被初始化一次，即使函数多次调用，变量的值也会保留。

静态局部变量存储在 全局/静态存储区（也称为数据段）。

• 生命周期：从程序开始运行到程序结束。

• 初始化：在第一次执行到声明处时初始化，且只初始化一次。

• 作用域：仅限于声明它的函数内部。

void func() {
    static int count = 0; // 静态局部变量
    count++;
    std::cout << "Count: " << count << std::endl;
}

int main() {
    func(); // 输出: Count: 1
    func(); // 输出: Count: 2
    func(); // 输出: Count: 3
    return 0;
}

2. 静态成员变量

在类中声明的静态成员变量属于类本身，而不是类的某个实例。所有类的实例共享同一个静态成员变量。静态成员变量需要在类外进行定义和初始化。

静态成员变量也存储在 全局/静态存储区。

• 生命周期：从程序开始运行到程序结束。

• 初始化：需要在类外定义和初始化。

• 作用域：属于类本身，所有类的实例共享。

class MyClass {
public:
    static int staticVar; // 静态成员变量声明
};

int MyClass::staticVar = 0; // 静态成员变量定义和初始化

int main() {
    MyClass obj1;
    MyClass obj2;

    obj1.staticVar = 10;
    std::cout << obj2.staticVar << std::endl; // 输出: 10

    MyClass::staticVar = 20;
    std::cout << obj1.staticVar << std::endl; // 输出: 20

    return 0;
}

3. 静态成员函数

静态成员函数属于类本身，而不是类的某个实例。静态成员函数只能访问静态成员变量和其他静态成员函数，不能访问非静态成员变量或非静态成员函数。

静态成员函数存储在 代码段（text segment）。

• 作用域：属于类本身，可以通过类名直接调用。

class MyClass {
public:
    static void staticFunc() {
        std::cout << "Static function called" << std::endl;
    }
};

int main() {
    MyClass::staticFunc(); // 输出: Static function called
    return 0;
}

4. 静态全局变量

在全局作用域中声明的静态变量，其作用域仅限于定义它的文件（即文件作用域）。其他文件无法访问该变量。

静态全局变量存储在 全局/静态存储区。

• 生命周期：从程序开始运行到程序结束。

• 作用域：仅限于定义它的文件（文件作用域）。

// file1.cpp
static int globalVar = 0; // 静态全局变量，只能在file1.cpp中访问

void func() {
    globalVar++;
}

// file2.cpp
extern int globalVar; // 错误：无法访问file1.cpp中的静态全局变量

5. 静态函数

在全局作用域中声明的静态函数，其作用域仅限于定义它的文件。其他文件无法调用该函数。

静态函数本身是代码，存储在 代码段（text segment）。

• 作用域：仅限于定义它的文件。

// file1.cpp
static void staticFunc() {
    std::cout << "Static function" << std::endl;
}

// file2.cpp
extern void staticFunc(); // 错误：无法访问file1.cpp中的静态函数

总结

• 静态局部变量：在函数内部声明，生命周期贯穿整个程序，但作用域仅限于函数内部。

• 静态成员变量：属于类本身，所有实例共享，需要在类外定义和初始化。

• 静态成员函数：属于类本身，只能访问静态成员变量和静态成员函数。

• 静态全局变量：作用域仅限于定义它的文件。

• 静态函数：作用域仅限于定义它的文件。

二、进程、线程、协程的区别

1. 进程（Process）

• 定义：进程是操作系统分配资源的基本单位，拥有独立的内存空间和系统资源。

• 特点：

  • 独立性：进程之间相互隔离，一个进程崩溃不会影响其他进程。

  • 资源开销：创建和切换进程的开销较大，因为涉及内存、文件句柄等资源的分配。

  • 通信：进程间通信（IPC）需要通过特定机制，如管道、消息队列、共享内存等。

• 适用场景：适合需要高隔离性和独立资源管理的任务。

2. 线程（Thread）

• 定义：线程是进程内的执行单元，共享进程的内存和资源。

• 特点：

  • 共享资源：同一进程内的线程共享内存和文件句柄等资源。

  • 轻量级：创建和切换线程的开销比进程小。

  • 通信：线程间通信可以直接通过共享内存进行，但需注意同步问题（如使用锁、信号量等）。

  • 并发性：适合需要高并发和资源共享的任务。

• 适用场景：适合需要高并发且资源共享的任务，如多任务处理。

3. 协程（Coroutine）

• 定义：协程是一种用户态的轻量级线程，由程序员控制调度。

• 特点：

  • 用户态调度：协程的调度由程序控制，不依赖操作系统。

  • 极轻量：创建和切换协程的开销极小，通常只需保存和恢复少量寄存器状态。

  • 非抢占式：协程主动让出执行权，适合协作式多任务。

  • 高并发：适合I/O密集型任务，能高效处理大量并发操作。

• 适用场景：适合I/O密集型任务和高并发场景，如网络服务器。

对比总结

总结

• 进程：适合需要高隔离性和独立资源管理的任务。

• 线程：适合需要高并发和资源共享的任务。

• 协程：适合I/O密集型和高并发任务，能高效处理大量并发操作。

三、图的深度搜索和广度搜索

图的深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图遍历算法，用于访问图中的所有节点或寻找特定节点。

1. 深度优先搜索（DFS）

DFS 是一种递归或栈实现的算法，沿着一条路径尽可能深入，直到无法继续为止，然后回溯并探索其他路径。

步骤：

1. 从起始节点开始，标记为已访问。

2. 访问当前节点的未访问邻居节点，递归进行DFS。

3. 若当前节点没有未访问的邻居，回溯到上一个节点继续搜索。

4. 重复上述过程，直到所有节点被访问。

伪代码：

def DFS(graph, node, visited):
    if node not in visited:
        print(node)  # 访问节点
        visited.add(node)
        for neighbor in graph[node]:
            DFS(graph, neighbor, visited)

应用：

• 拓扑排序

• 连通分量检测

• 路径查找

2. 广度优先搜索（BFS）

BFS 使用队列实现，从起始节点开始，逐层访问所有邻居节点。

步骤：

1. 从起始节点开始，标记为已访问并加入队列。

2. 从队列中取出一个节点并访问。

3. 将该节点的未访问邻居节点加入队列并标记为已访问。

4. 重复上述过程，直到队列为空。

伪代码：

from collections import deque

def BFS(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node)  # 访问节点
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

应用：

• 最短路径（无权图）

• 层级遍历

• 连通分量检测

3. 对比

• DFS：适合深入搜索，可能陷入无限循环（未标记已访问节点时）。

• BFS：适合寻找最短路径，需要更多内存（存储队列）。

4. 示例

假设有图：

A -- B -- C
|    |
D -- E

DFS 可能访问顺序：A → B → C → E → D
BFS 可能访问顺序：A → B → D → C → E

5. 总结

• DFS：递归或栈实现，适合深入搜索。

• BFS：队列实现，适合寻找最短路径。

根据具体需求选择合适的算法。

四、 详细介绍快速排序：

1. 原理

快速排序（Quick Sort）是一种基于分治法的排序算法。它的核心思想是通过选择一个基准元素（pivot），将数组分为两部分：一部分小于基准元素，另一部分大于基准元素。然后递归地对这两部分进行排序，最终完成整个数组的排序。

具体步骤如下：

1. 选择基准元素：从数组中选择一个元素作为基准（pivot）。

2. 分区：将数组重新排列，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。基准元素最终位于正确的位置。

3. 递归排序：对基准左边和右边的子数组递归地进行快速排序。

2. C++ 实现

#include <iostream>
#include <vector>

using namespace std;

// 分区函数
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1; // i 是小于基准的元素的最后一个位置

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]); // 将基准元素放到正确的位置
    return i + 1; // 返回基准元素的位置
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 获取分区点
        quickSort(arr, low, pi - 1); // 递归排序左子数组
        quickSort(arr, pi + 1, high); // 递归排序右子数组
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();
    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

3. 最好时间复杂度

• 最好情况：每次分区都能将数组均匀地分成两部分，即每次选择的基准元素都能将数组分成两个大小相等的子数组。

• 时间复杂度：O(n log n)

• 计算方法：每次分区的时间复杂度为 O(n)，递归树的深度为 log n，因此总时间复杂度为 O(n log n)。

4. 最坏时间复杂度

• 最坏情况：每次分区都极度不均匀，例如数组已经有序或所有元素相同，导致每次分区只能减少一个元素。

• 时间复杂度：O(n^2)

• 计算方法：每次分区的时间复杂度为 O(n)，递归树的深度为 n，因此总时间复杂度为 O(n^2)。

5. 稳定性

• 是否稳定：快速排序不是稳定的排序算法。

• 原因：在分区过程中，相等的元素可能会因为交换而改变相对顺序。

6. 优化策略

• 随机化选择基准：通过随机选择基准元素，可以减少最坏情况发生的概率。

• 三数取中法：选择数组的第一个、中间和最后一个元素的中位数作为基准，以减少最坏情况的发生。

7. 总结

• 优点：平均时间复杂度为 O(n log n)，且在实际应用中通常比其他 O(n log n) 算法更快。

• 缺点：最坏情况下时间复杂度为 O(n^2)，且不是稳定排序。

通过合理选择基准元素和优化策略，可以显著提高快速排序的性能。

五、介绍红黑树

1. 二叉搜索树的基本性质

• 二叉搜索树是一种有序的树结构，满足以下性质：

  • 对于树中的任意节点：

    • 左子树中的所有节点的值都小于该节点的值。

    • 右子树中的所有节点的值都大于该节点的值。

  • 这一性质使得二叉搜索树的中序遍历结果是一个有序序列。

• 红黑树是一种特殊的二叉搜索树，完全继承了这一性质。

2. 红黑树的有序性

• 红黑树在二叉搜索树的基础上增加了颜色规则和平衡性约束，但这些规则并不改变二叉搜索树的有序性。

• 红黑树仍然满足：

  • 左子树 < 根节点 < 右子树。

  • 通过中序遍历红黑树，可以得到一个严格递增的有序序列。

3. 红黑树的平衡性

• 红黑树通过以下规则保持平衡：

  1. 每个节点是红色或黑色。

  2. 根节点是黑色。

  3. 所有叶子节点（NIL节点）是黑色。

  4. 红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。

  5. 从任一节点到其每个叶子节点的路径上，黑色节点的数量相同。

• 这些规则确保了红黑树的高度始终为 O(log n)，从而保证了高效的查找、插入和删除操作。

• 尽管红黑树通过颜色和旋转操作来维持平衡，但这些操作不会破坏二叉搜索树的有序性。

4. 红黑树与普通二叉搜索树的区别

• 普通二叉搜索树在极端情况下可能退化为链表（例如，插入有序数据时），导致操作时间复杂度退化为 O(n)。

• 红黑树通过颜色规则和旋转操作，始终保持树的平衡，确保操作时间复杂度为 O(log n)。

• 尽管红黑树增加了平衡性约束，但它仍然是一个有序的二叉搜索树。

5. 红黑树比AVL树内存效率高的原因

5.1. 平衡性要求较低

• 红黑树：

  • 红黑树是一种弱平衡的二叉搜索树，只要求从根节点到叶子节点的最长路径不超过最短路径的两倍。

  • 这种较宽松的平衡性要求使得红黑树在插入和删除时需要的旋转操作较少。

• AVL树：

  • AVL树是一种强平衡的二叉搜索树，要求左右子树的高度差不超过 1。

  • 这种严格的平衡性要求使得AVL树在插入和删除时可能需要更多的旋转操作。

结果：红黑树的旋转操作更少，维护平衡的开销更小，内存效率更高。

5.2. 存储的额外信息较少

• 红黑树：

  • 每个节点只需要存储 1 个额外的比特位来表示颜色（红色或黑色）。

  • 不需要存储高度或平衡因子。

• AVL树：

  • 每个节点需要存储高度或平衡因子（通常是一个整数，占用更多内存）。

  • 在 32 位系统中，一个整数占用 4 字节；在 64 位系统中，一个整数占用 8 字节。

结果：红黑树每个节点占用的内存更少，整体内存效率更高。

5.3. 旋转操作的开销更小

• 红黑树：

  • 由于平衡性要求较低，插入和删除时需要的旋转操作较少。

  • 旋转操作的开销较小，对性能的影响较小。

• AVL树：

  • 由于平衡性要求严格，插入和删除时可能需要更多的旋转操作。

  • 旋转操作的开销较大，对性能的影响较大。

结果：红黑树的旋转操作更少，内存和性能开销更小。

5.4. 实际应用中的表现

• 红黑树：

  • 更适合频繁插入和删除的场景（如操作系统的任务调度、关联容器等）。

  • 由于内存效率高，适合内存敏感的环境（如操作系统内核）。

• AVL树：

  • 更适合查找密集的场景（如数据库索引）。

  • 由于需要存储更多信息，内存开销较大。

5.5. 具体数据对比

• 假设一个红黑树和一个AVL树都存储 n 个节点：

  • 红黑树每个节点需要存储 1 个颜色比特位。

  • AVL树每个节点需要存储 1 个整数（4 或 8 字节）。

• 对于大规模数据，AVL树的内存开销可能是红黑树的数倍。

总结

红黑树比AVL树的内存效率更高，主要原因包括：

1. 平衡性要求较低：红黑树的旋转操作更少，维护平衡的开销更小。

2. 存储的额外信息较少：红黑树只需要存储颜色信息，而AVL树需要存储高度或平衡因子。

3. 旋转操作的开销更小：红黑树的旋转操作更少，对性能的影响更小。

这些特性使得红黑树在内存敏感的场景中表现更优，尤其是在需要频繁插入和删除的动态数据集中。

六、HashMap介绍

HashMap 是一种基于哈希表的数据结构，用于存储键值对（key-value pairs）。它通过哈希函数将键映射到哈希表中的特定位置，从而实现高效的插入、删除和查找操作。HashMap 的平均时间复杂度为 O(1)，但在最坏情况下可能退化到 O(n)。

核心概念

1. 键值对（Key-Value Pair）：HashMap 存储的是键值对，每个键对应一个值。

2. 哈希函数（Hash Function）：将键映射到哈希表中的索引位置。

3. 哈希表（Hash Table）：存储键值对的数组，每个位置称为“桶”（bucket）。

4. 冲突（Collision）：当两个不同的键通过哈希函数映射到同一个索引时，称为冲突。

哈希函数

哈希函数是 HashMap 的核心，它将任意大小的数据映射到固定大小的值（通常是整数）。好的哈希函数应具备以下特性：

1. 一致性：相同的键总是映射到相同的索引。

2. 均匀分布：键应均匀分布在哈希表中，减少冲突。

3. 高效计算：哈希函数应快速计算。

常见的哈希函数包括：

• 除留余数法：hash(key) = key % table_size

• 乘法哈希：hash(key) = floor(table_size * (key * A % 1))，其中 0 < A < 1

• MD5、SHA-1 等加密哈希函数（适用于分布式系统）

冲突解决方法

当两个键映射到同一个索引时，HashMap 需要解决冲突。常见的冲突解决方法包括：

1. 链地址法（Separate Chaining）

• 原理：每个桶存储一个链表（或其他数据结构），所有映射到同一索引的键值对都存储在该链表中。

• 插入：通过哈希函数找到索引，将键值对插入链表。

• 查找：通过哈希函数找到索引，遍历链表查找键。

• 删除：通过哈希函数找到索引，遍历链表删除键值对。

优点：

• 实现简单。

• 哈希表可以动态增长。

缺点：

• 链表过长时，查找效率下降。

• 需要额外的存储空间存储链表指针。

2. 开放地址法（Open Addressing）

• 原理：所有键值对都存储在哈希表中，冲突时通过探测方法寻找下一个空闲位置。

• 常见探测方法：

  • 线性探测：hash(key) = (hash(key) + i) % table_size，其中 i 是探测次数。

  • 二次探测：hash(key) = (hash(key) + c1 * i + c2 * i^2) % table_size。

  • 双重哈希：hash(key) = (hash1(key) + i * hash2(key)) % table_size。

优点：

• 不需要额外的存储空间。

• 缓存友好，数据连续存储。

缺点：

• 容易产生聚集（clustering），影响性能。

• 删除操作复杂，通常使用标记删除。

3. 再哈希（Rehashing）

• 原理：当哈希表负载因子（load factor）超过阈值时，创建一个更大的哈希表，并将所有键值对重新哈希到新表中。

• 负载因子：load_factor = number_of_entries / table_size，通常设置为 0.75。

优点：

• 保持哈希表的高效性。

• 自动调整哈希表大小。

缺点：

• 再哈希过程耗时。

• 需要额外的存储空间。

各种解决方法的查找方式

链地址法

• 查找步骤：

  1. 计算键的哈希值，找到对应的桶。

  2. 遍历链表，查找与键匹配的节点。

  3. 找到则返回对应的值，否则返回 null。

开放地址法

• 查找步骤：

  1. 计算键的哈希值，找到初始位置。

  2. 如果该位置的键与目标键匹配，返回对应的值。

  3. 如果不匹配，根据探测方法查找下一个位置，直到找到匹配的键或遇到空桶。

再哈希

• 查找步骤：

  1. 计算键的哈希值，找到对应的桶。

  2. 如果该位置的键与目标键匹配，返回对应的值。

  3. 如果不匹配，继续查找，直到找到匹配的键或遇到空桶。

  4. 如果负载因子超过阈值，触发再哈希，重新查找。

Java 中的 HashMap

在 Java 中，HashMap 使用了 链地址法 来解决哈希冲突。当链表长度超过一定阈值（默认为 8）时，链表会转换为红黑树，以提高查找效率。

总结

• 链地址法：适用于频繁插入和删除的场景，实现简单。

• 开放地址法：节省空间，但容易产生聚集现象。

• 再哈希法：有效减少冲突，但扩容耗时。

• 建立公共溢出区：适用于冲突较少的场景。

在使用 链地址法 解决哈希冲突的哈希表中，通过一个 key 找到对应的 value 的过程如下：

查找过程

1. 计算哈希值：

   • 使用哈希函数对 key 进行计算，得到其对应的哈希值。

   • 公式：hashValue = hashFunction(key)

2. 确定槽位（Bucket）：

   • 根据哈希值确定 key 应该存储在哈希表的哪个槽位（bucket）。

   • 公式：bucketIndex = hashValue % tableSize，其中 tableSize 是哈希表的大小。

3. 遍历链表（或红黑树）：

   • 如果该槽位是一个链表（或红黑树），则遍历链表中的每个节点，比较节点的 key 和目标 key。

   • 比较时通常使用 key 的 equals() 方法来判断是否相等。

4. 返回对应的 value：

   • 如果找到 key 相等的节点，则返回该节点中存储的 value。

   • 如果遍历完链表仍未找到，则说明 key 不存在，返回 null。

示例代码（Java）

以下是使用链地址法实现的哈希表中查找 value 的伪代码：

public class HashMap<K, V> {
    private static final int TABLE_SIZE = 16; // 哈希表大小
    private Node<K, V>[] table; // 哈希表数组

    // 节点类
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    // 构造函数
    public HashMap() {
        table = new Node[TABLE_SIZE];
    }

    // 哈希函数
    private int hashFunction(K key) {
        return key.hashCode() % TABLE_SIZE;
    }

    // 查找方法
    public V get(K key) {
        int bucketIndex = hashFunction(key); // 计算槽位
        Node<K, V> currentNode = table[bucketIndex]; // 获取链表头节点

        // 遍历链表
        while (currentNode != null) {
            if (currentNode.key.equals(key)) { // 找到目标 key
                return currentNode.value; // 返回对应的 value
            }
            currentNode = currentNode.next; // 继续遍历
        }

        return null; // 未找到，返回 null
    }
}

查找过程的时间复杂度

1. 理想情况：

   • 如果没有哈希冲突，每个槽位只有一个节点，查找的时间复杂度为 O(1)。

2. 最坏情况：

   • 如果所有 key 都哈希到同一个槽位，链表长度为 n，查找的时间复杂度为 O(n)。

   • 在 Java 的 HashMap 中，当链表长度超过阈值（默认为 8）时，链表会转换为红黑树，此时查找的时间复杂度为 O(log n)。

七、线程的生成方式、守护线程和普通线程

在Java中，线程的生成方式主要有两种：继承Thread类和实现Runnable接口。守护线程（Daemon Thread）是一种特殊的线程，它在后台运行，通常用于执行一些辅助任务。守护线程与普通线程的主要区别在于它们的行为和生命周期。

线程的生成方式

1. 继承Thread类：

   class MyThread extends Thread {
       public void run() {
           System.out.println("Thread is running");
       }
   }
   
   public class Main {
       public static void main(String[] args) {
           MyThread thread = new MyThread();
           thread.start();
       }
   }

2. 实现Runnable接口：

   class MyRunnable implements Runnable {
       public void run() {
           System.out.println("Thread is running");
       }
   }
   
   public class Main {
       public static void main(String[] args) {
           Thread thread = new Thread(new MyRunnable());
           thread.start();
       }
   }

如何成为守护线程

要将一个线程设置为守护线程，可以在启动线程之前调用setDaemon(true)方法。守护线程通常在后台运行，为其他线程提供服务。

public class Main {
    public static void main(String[] args) {
        Thread daemonThread = new Thread(() -> {
            while (true) {
                System.out.println("Daemon thread is running");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });

        daemonThread.setDaemon(true); // 设置为守护线程
        daemonThread.start();

        System.out.println("Main thread is finished");
    }
}

守护线程和普通线程的区别

1. 生命周期：

   • 普通线程：JVM会等待所有普通线程执行完毕才会退出。

   • 守护线程：JVM不会等待守护线程执行完毕。当所有普通线程结束时，JVM会立即退出，守护线程也会随之终止。

2. 用途：

   • 普通线程：通常用于执行主要的业务逻辑。

   • 守护线程：通常用于执行后台任务，如垃圾回收、监控等。

3. 优先级：

   • 普通线程：默认情况下，普通线程的优先级是NORM_PRIORITY。

   • 守护线程：守护线程的优先级通常较低，但可以通过setPriority()方法手动设置。

4. 异常处理：

   • 普通线程：如果普通线程抛出未捕获的异常，线程会终止，但不会影响其他线程。

   • 守护线程：如果守护线程抛出未捕获的异常，线程会终止，但不会影响JVM的退出。

总结

• 守护线程通过setDaemon(true)设置，通常用于后台任务。

• JVM不会等待守护线程执行完毕，当所有普通线程结束时，JVM会立即退出。

• 守护线程和普通线程在生命周期、用途、优先级和异常处理等方面有显著区别。

 八、乐观锁和悲观锁：

1. 悲观锁（Pessimistic Locking）

定义：悲观锁假设在事务执行过程中，其他事务很可能会修改数据，因此在访问数据时直接加锁，确保数据不会被其他事务修改。

实现方式：

• 数据库中的行级锁、表级锁等。

• 编程语言中的互斥锁（Mutex）、读写锁（ReadWriteLock）等。

特点：

• 优点：简单直接，能有效避免冲突。

• 缺点：加锁会导致性能下降，尤其是在高并发场景下，容易造成阻塞。

适用场景：

• 数据竞争激烈的环境。

• 事务冲突频繁的情况。

2. 乐观锁（Optimistic Locking）

定义：乐观锁假设事务执行过程中冲突较少，因此在访问数据时不加锁，只在提交时检查数据是否被其他事务修改过。

实现方式：

• 版本号机制：每次更新时检查版本号，若不一致则拒绝提交。

• 时间戳机制：通过时间戳判断数据是否被修改。

特点：

• 优点：减少加锁开销，提升并发性能。

• 缺点：冲突较多时，重试操作会增加开销。

适用场景：

• 数据竞争较少的环境。

• 读多写少的场景。

3. 对比

4. 选择依据

• 悲观锁：适合冲突频繁的场景，如银行交易。

• 乐观锁：适合冲突较少的场景，如社交网络点赞。

九、 C++中常见容器的底层实现以及内存扩展方式

在 C++ 中，常见的容器（如 vector、list、deque、queue、stack、map、set、unordered_map、unordered_set）的底层实现和内存不足时的扩展方式各不相同。以下是它们的详细说明：

1. std::vector

• 底层实现：动态数组，使用连续的内存块存储元素。

• 内存扩展方式：

  • 当内存不足时，vector 会分配一个更大的内存块（通常是当前容量的 2 倍）。

  • 将原有元素复制到新内存块中，释放旧内存块。

  • 这个过程称为 重新分配（reallocation）。

• 特点：

  • 随机访问效率高（O(1)）。

  • 插入和删除元素在尾部高效（O(1)），但在中间或头部效率较低（O(n)）。

2. std::list

• 底层实现：双向链表，每个节点包含指向前后节点的指针。

• 内存扩展方式：

  • 内存不足时，只需分配一个新节点并插入到链表中。

  • 不需要重新分配整个容器。

• 特点：

  • 插入和删除元素在任何位置都很高效（O(1)）。

  • 随机访问效率低（O(n)）。

3. std::deque

• 底层实现：双端队列，由多个固定大小的内存块（缓冲区）组成，通过一个中央映射表（map）管理。

• 中央映射表的结构

1. 指针数组：中央映射表是一个指针数组，每个指针指向一个缓冲区。

2. 缓冲区：每个缓冲区是一个固定大小的数组，存储实际的元素。

3. 动态扩展：当 std::deque 需要扩展时，会分配新的缓冲区，并将其地址添加到中央映射表中。

• 内存扩展方式：

  • 当内存不足时，分配一个新的缓冲区，并将其添加到中央映射表中。

  • 不需要像 vector 那样复制所有元素。

• 特点：

  • 在两端插入和删除元素效率高（O(1)）。

  • 随机访问效率较高（O(1)），但比 vector 稍慢。

4. std::queue

• 底层实现：queue 是一个容器适配器，默认使用 deque 作为底层容器。

• 内存扩展方式：

  • 依赖于底层容器（如 deque）的内存扩展方式。

• 特点：

  • 先进先出（FIFO）的数据结构。

  • 只允许在队尾插入元素，在队头删除元素。

5. std::stack

• 底层实现：stack 是一个容器适配器，默认使用 deque 作为底层容器。

• 内存扩展方式：

  • 依赖于底层容器（如 deque）的内存扩展方式。

• 特点：

  • 后进先出（LIFO）的数据结构。

  • 只允许在栈顶插入和删除元素。

6. std::map

• 底层实现：基于红黑树（一种自平衡二叉搜索树）实现。

• 内存扩展方式：

  • 插入新元素时，红黑树会根据需要进行旋转和重新着色以保持平衡。

  • 内存不足时，只需分配一个新节点并插入到树中。

• 特点：

  • 元素按键值有序存储（默认升序）。

  • 插入、删除和查找的效率为 O(log n)。

7. std::set

• 底层实现：基于红黑树实现，与 map 类似，但只存储键值（没有键值对）。

• 内存扩展方式：

  • 与 map 相同，插入新元素时保持树的平衡。

• 特点：

  • 元素按值有序存储（默认升序）。

  • 插入、删除和查找的效率为 O(log n)。

8. std::unordered_map

• 底层实现：基于哈希表实现，使用哈希函数将键映射到桶（bucket）中，每个桶可以存储多个元素（通常是一个链表）。

• 内存扩展方式：

  • 当哈希表的负载因子（元素数量与桶数量的比值）超过阈值时，会进行 重新哈希（rehashing）。

  • 分配更多的桶，并将所有元素重新分配到新的桶中（通常桶的数量会翻倍）。

• 特点：

  • 元素无序存储。

  • 插入、删除和查找的平均效率为 O(1)，最坏情况下为 O(n)。

9. std::unordered_set

• 底层实现：基于哈希表实现，与 unordered_map 类似，但只存储键值（没有键值对）。

• 内存扩展方式：

  • 与 unordered_map 相同，当负载因子超过阈值时进行重新哈希。

• 特点：

  • 元素无序存储。

  • 插入、删除和查找的平均效率为 O(1)，最坏情况下为 O(n)。

总结对比

选择容器的建议

• 如果需要高效随机访问，使用 vector 或 deque。

• 如果需要频繁在中间插入或删除元素，使用 list。

• 如果需要有序存储，使用 map 或 set。

• 如果需要快速查找且不关心顺序，使用 unordered_map 或 unordered_set。

• 如果需要 FIFO 或 LIFO 结构，使用 queue 或 stack。

十、new和malloc的区别

new 和 malloc 都用于动态内存分配，但它们在C++中有显著区别：

1. 语言

• new: C++ 运算符。

• malloc: C 标准库函数，C++ 中也可用。

2. 内存分配与初始化

• new: 分配内存并调用构造函数初始化对象。

• malloc: 仅分配内存，不调用构造函数。

3. 返回类型

• new: 返回对象类型的指针。

• malloc: 返回 void*，需显式类型转换。

4. 内存大小计算

• new: 自动计算所需内存大小。

• malloc: 需手动计算并传入字节数。

5. 失败处理

• new: 抛出 std::bad_alloc 异常。

• malloc: 返回 NULL。

6. 释放内存

• new: 使用 delete 释放，并调用析构函数。

• malloc: 使用 free 释放，不调用析构函数。

7. 重载

• new: 可以重载。

• malloc: 不能重载。

8. 使用场景

• new: 适用于 C++ 对象。

• malloc: 适用于 C 或需要与 C 兼容的代码。

示例

// 使用 new
int* p = new int(10);  // 分配并初始化
delete p;              // 释放

// 使用 malloc
int* q = (int*)malloc(sizeof(int));  // 仅分配
*q = 10;                             // 手动初始化
free(q);                              // 释放

总结

• new 更适合 C++，自动管理构造和析构。

• malloc 更底层，适合 C 或需要手动控制内存的场景。