C++代码中使用哈希表

目录

一、什么是哈希表

        哈希表（Hash Table）是一种数据结构，也被称为散列表。它通过将键（Key）映射到存储位置，以提高数据的访问效率。哈希表使用哈希函数将键转换为对应的存储位置，这个位置通常称为哈希桶（Hash Bucket）或槽（Slot），在这个位置存储对应的值（Value）。

二、C++代码中如何使用哈希表

Header：#include <unordered_map>

示例代码：

#include <iostream>
#include <unordered_map>

int main() {
    // 创建一个 unordered_map
    std::unordered_map<std::string, int> myMap;

    // 插入键值对
    myMap["apple"] = 10;
    myMap["orange"] = 7;
    myMap["banana"] = 5;

    // 访问元素
    std::cout << "Number of apples: " << myMap["apple"] << std::endl;

    // 遍历哈希表
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 检查某个键是否存在
    if (myMap.count("banana") > 0) {
        std::cout << "Banana exists in the map" << std::endl;
    }

    // 删除某个键值对
    myMap.erase("orange");

    // 清空哈希表
    myMap.clear();

    return 0;
}

结果展示：

三、哈希表的优缺点

优点：
        查找速度快：unordered_map 使用哈希表实现，通过哈希函数将键映射到索引位置，使得查找操作的时间复杂度接近 O(1)。
        适用于大数据量的键值对：unordered_map 在处理大量数据时可以提供更好的性能，因为它的查找效率高。
        不会自动排序：unordered_map 的键是无序的，不会根据键的顺序进行排序，这在某些场景下可以提高性能。

缺点：
        占用更多内存：由于 unordered_map 使用哈希表，需要维护哈希桶，可能会占用较多的额外内存。
        迭代顺序不确定：由于 unordered_map 的键是无序的，迭代器输出的顺序是不确定的。这在需要按照键的顺序进行遍历操作时可能造成困扰。

四、std::map优缺点

优点：
         有序：map 内部以红黑树实现，键值对按照键的大小进行有序存储，可以方便地按照键的顺序进行迭代、查找等操作。
        内存占用较少：相对于 unordered_map，map 不需要额外的哈希桶，占用的内存较少。

缺点：
         查找速度相对较慢：由于使用红黑树，map 的查找操作的时间复杂度为 O(logN)，其中 N 是元素数目。
        不适合大数据量的键值对：相比 unordered_map，map 在大量数据处理时性能较差。
        插入和删除操作相对较慢：由于需要维护红黑树的平衡性，执行插入和删除操作可能会比 unordered_map 更慢。

五、查找效率对比

示例代码：

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>

int main() {
    std::map<int, int> m;
    std::unordered_map<int, int> um;

    // 添加大量的键值对到std::map和哈希表中
    for (int i = 0; i < 1000000; ++i) {
        m[i] = i;
        um[i] = i;
    }

    // 测试查找效率
    int target = 500000;
    std::chrono::steady_clock::time_point start, end;

    // 使用std::map进行多次查找并记录时间
    start = std::chrono::steady_clock::now();
    for (int i = 0; i < 100000; ++i) {
        auto it = m.find(target);
    }
    end = std::chrono::steady_clock::now();
    std::chrono::duration<double> mapTime = end - start;

    // 使用哈希表进行多次查找并记录时间
    start = std::chrono::steady_clock::now();
    for (int i = 0; i < 100000; ++i) {
        auto it = um.find(target);
    }
    end = std::chrono::steady_clock::now();
    std::chrono::duration<double> unorderedMapTime = end - start;

    // 输出查找时间
    std::cout << "std::map time: " << mapTime.count() << " s\n";
    std::cout << "unordered_map time: " << unorderedMapTime.count() << " s\n";

    return 0;
}

 结果展示：

六、总结

        unordered_map 适用于需要快速查找和处理大量数据的场景，而 map 适用于需要有序存储、按键顺序访问的场景。选择使用哪个容器，应根据具体的需求和性能考虑做出合适的选择。

七、扩展 chrono

        #include <chrono> 是 C++ 标准库中提供的用于时间和时间点操作的头文件。它包含了一组模板类和函数，用于测量时间、计算时间差、sleep 等。

以下是一些常见的 chrono 头文件中的类和函数：

        std::chrono::duration：表示时间段，即时间的差异。它的单位可以是纳秒、微秒、毫秒、秒、分钟、小时等。可以使用 std::chrono::duration 进行时间运算、比较和转换。

        std::chrono::time_point：表示具体的时间点。它可以与 steady_clock、system_clock 等时钟相关联，通过 now() 函数获取当前时刻的时间点。

        std::chrono::steady_clock：稳定时钟，用于测量时间间隔，递增但不一定与真实时间相关联。

        std::chrono::system_clock：系统时钟，用于获取当前时间和日期，可能与真实时间相关联。

        时间运算和转换函数：std::chrono::duration_cast 用于类型换，std::chrono::time_point_cast 用于将某个时间点转换为另一个时间点类型。

示例代码：

#include <iostream>
#include <chrono>
#include <thread>


int main() {
    // 获取当前时间点
    std::chrono::system_clock::time_point now = std::chrono::system_clock::now();

    // 获取当前时间的时间戳，以秒为单位
    std::time_t timestamp = std::chrono::system_clock::to_time_t(now);
    std::cout << "current time: " << timestamp << std::endl;

    // 定义一个时间段，以秒为单位
    std::chrono::seconds duration(10);

    // 将时间段转换为毫秒
    std::chrono::milliseconds milliseconds = std::chrono::duration_cast<std::chrono::milliseconds>(duration);
    std::cout << "The time period is converted to milliseconds: " << milliseconds.count() << " ms" << std::endl;

    // 运行时间延迟
    std::this_thread::sleep_for(std::chrono::seconds(5));

    // 获取经过的时间
    std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed = end - now;
    std::cout << "long uptime: " << elapsed.count() << " s" << std::endl;

    return 0;
}

结果展示：