C++哈希的概念及STL中有关哈希容器的使用

哈希（Hash）是计算机科学中一种高效的数据存储和检索技术。哈希函数将输入的数据映射到一个固定范围的值，通过这个值可以快速定位数据。哈希表（Hash Table）是一种基于哈希函数的数据结构，可以在平均情况下实现常数时间的查找、插入和删除操作。

在C++的标准模板库（STL）中，哈希容器主要包括std::unordered_map和std::unordered_set。

std::unordered_map

std::unordered_map是一个基于哈希表实现的关联容器，用于存储键值对。每个键都唯一且与一个值相关联，可以通过键快速检索对应的值。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> umap;

    // 插入元素
    umap[1] = "one";
    umap[2] = "two";
    umap[3] = "three";

    // 访问元素
    std::cout << "Key 1: " << umap[1] << std::endl;

    // 遍历
    for (const auto& pair : umap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    // 查找元素
    auto it = umap.find(2);
    if (it != umap.end()) {
        std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    return 0;
}

std::unordered_set

std::unordered_set是一个基于哈希表实现的集合容器，用于存储唯一的元素，提供高效的插入、删除和查找操作。

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> uset;

    // 插入元素
    uset.insert(1);
    uset.insert(2);
    uset.insert(3);

    // 检查元素是否存在
    if (uset.find(2) != uset.end()) {
        std::cout << "2 is in the set" << std::endl;
    } else {
        std::cout << "2 is not in the set" << std::endl;
    }

    // 遍历
    for (const auto& elem : uset) {
        std::cout << elem << std::endl;
    }

    // 删除元素
    uset.erase(2);

    return 0;
}

哈希容器的特点

1. 快速访问：哈希容器的主要优势在于快速访问，可以在常数时间内完成插入、删除和查找操作。

2. 无序存储：与有序容器（如std::map和std::set）不同，哈希容器不维护元素的顺序。

3. 负载因子和重新哈希：当哈希表中的元素数量超过一定阈值时，表会自动重新哈希（rehash），以保持高效的操作性能。

哈希容器在需要快速查找的场景中非常有用，但由于内部结构的无序性，对于需要排序或顺序访问的场景，其他有序容器可能更为适合。