哈希 Hash

ZaynPei Lv6
  2025-09-03 18:00 2025-09-03 18:00 Created   2025-11-10 18:56:57 2025-11-10 18:56:57 Updated      3.1k Words  13 Mins

哈希函数对象 (Hash Functor) – std::hash

std::hash 是 C++ 标准库中定义的一个类模板，位于 头文件中。它的主要作用是作为一个函数对象（Functor），为给定的数据类型计算一个唯一的、稳定的哈希值。

从本质上讲，std::hash 是一个提供了标准哈希计算接口的工具或者说算法(算子)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 主模板, 用于传入自定义类实现哈希函数
template<class Key> 
struct hash;

// 为int类型特化
template<>
struct hash<int> {
    size_t operator()(int value) const noexcept {
        // 对于整数，最简单的哈希就是其本身的值, 或者其他哈希算法。
        return static_cast<size_t>(value);
    }
};

// --- 为指针类型特化 ---
template<typename T>
struct hash<T*> {
    size_t operator()(T* ptr) const noexcept {
        // 指针的哈希值就是其内存地址的整数表示。
        return reinterpret_cast<size_t>(ptr);
    }
};

// --- 为字符串类型特化 ---
template<>
struct hash<std::string> {
    size_t operator()(const std::string& str) const noexcept {
        // 使用一个简单且经典的 djb2 字符串哈希算法。
        // 核心思想：遍历字符串，将每个字符融入一个不断变化的哈希值中。
        size_t hash_value = 5381;
        for (char c : str) {
            // hash = (hash * 33) + character_value
            hash_value = ((hash_value << 5) + hash_value) + c;
        }
        return hash_value;
    }
};

它的形式如上, 我们可以为不同的数据类型实例化它, 从而实现传入某个类型的数据, 返回计算得到的哈希值(size_t). 它也重载了 operator()并返回一个 size_t 类型的哈希值，使其可以像函数一样被调用。例如，std::hash<std::string>()("hello") 会返回字符串 “hello” 的哈希值。

std::hash<std::string>()("hello")是创建一个临时哈希对象并调用它的operator()函数, 等价于 auto hasher = std::hash<std::string>{}; size_t value = hasher("hello");

如何使用 std::hash

std::hash 的使用分为两种情况：对标准库内置支持的类型使用，以及对自定义类型使用。

对内置支持的类型使用

标准库已经为所有基本数据类型（如 int, char, float, double, bool）、指针、以及一些常用库类型（如 std::string, std::thread::id, std::shared_ptr 等）提供了 std::hash 的特化版本。因此可以直接使用它们， 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <string>
#include <functional> // 包含 std::hash

int main() {
    std::string s = "Hello, World!";
    int i = 12345;
    double d = 3.14159;

    // 创建不同类型的 hash 对象
    std::hash<std::string> string_hasher;
    std::hash<int> int_hasher;
    std::hash<double> double_hasher;

    // 调用 operator() 计算哈希值
    size_t string_hash = string_hasher(s);
    size_t int_hash = int_hasher(i);
    size_t double_hash = double_hasher(d);

    std::cout << "Hash of \"" << s << "\" is " << string_hash << std::endl;
    std::cout << "Hash of " << i << " is " << int_hash << std::endl;
    std::cout << "Hash of " << d << " is " << double_hash << std::endl;

    return 0;
}

对自定义类型使用

如果你想将自定义的类或结构体作为 std::unordered_map 的键或者哈希算子的参数，编译器默认是不知道如何计算其哈希值的。这时，你需要为你的自定义类型 特化（Specialize） std::hash 模板。

特化步骤主要是： - 定义你的自定义类型（例如 struct Student）。 - 在 std 命名空间内，为你的类型提供一个 std::hash 的模板特化版本。 - 在这个特化版本中，实现 operator()，它接受一个你的自定义类型的常量引用，并返回一个 size_t 类型的哈希值。 - 在实现 operator() 时，你需要设计一种算法，将对象的各个成员的哈希值组合成一个总的哈希值。

可以看出, 获得自定义对象的哈希值比较麻烦, 还需使用者来设计哈希算法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 一个自定义类型，用于展示如何为其提供哈希支持
struct Student {
    int id;
    std::string name;

    // 注意: 哈希容器还需要 operator== 来处理哈希冲突, 因此在自定义类中也要实现
    bool operator==(const Student& other) const {
        return id == other.id && name == other.name;
    }
};
namespace std{
    template<>
    struct hash<Student> {
        size_t operator()(const Student& s) const noexcept {
            // 核心思想：分别计算每个成员的哈希值，然后将它们组合起来。
            
            // 计算 id 的哈希值 (复用了上面的 hash<int>)
            size_t id_hash = SimpleHash::hash<int>{}(s.id);
            
            // 计算 name 的哈希值 (复用了上面的 hash<std::string>)
            size_t name_hash = SimpleHash::hash<std::string>{}(s.name);

            // 通过位运算将两个哈希值组合成一个，这是常用技巧。
            return id_hash ^ (name_hash << 1);
        }
    };
}

哈希表（Hash Table） 容器

对于哈希, 我们在平时使用更多的反而是根据哈希函数对象创建的哈希表容器. 这些容器包括：

  • std::unordered_map
  • std::unordered_set
  • std::unordered_multimap
  • std::unordered_multiset

主要使用的是前两者. multi 版本除了允许重复的键存在, 其他用法和接口基本相同, 因此这里不做赘述.

unordered_set

std::unordered_set 是一个基于哈希表实现的用于存储唯一元素的关联容器。它的主要设计目标是提供平均时间复杂度为 O(1) 的元素查找、插入和删除操作。可以把它想象成一个数学上的集合：一个无序的、包含唯一元素的集合.

与 std::set（基于红黑树实现，提供有序存储和 O(log N) 的操作复杂度）不同，std::unordered_set 更侧重于快速访问，但不保证元素的顺序。

相比 unordered_map, 它只存储键, 没有值, 因此它更多用于需要快速判断某个元素是否存在的场景。 也可以用于去除重复元素：将一个包含重复元素的列表（如 std::vector）转换为 std::unordered_set，可以快速得到一个不含重复元素的集合。 

1
2
3
4
vector<int> numbers = {1, 2, 5, 2, 1, 4};
// 直接用 vector 的开始和结束迭代器来构造 set
std::unordered_set<int> uniqueNumbers(numbers.begin(), numbers.end());
// uniqueNumbers 现在是 {1, 2, 4, 5}

函数签名如下: 

1
2
3
4
5
6
7
#include <unordered_set>
template<
    class T,
    class Hash = std::hash<T>,  // 默认使用 std::hash 作为哈希函数
    class KeyEqual = std::equal_to<T>,  // 默认使用 std::equal_to 作为键比较函数
    class Allocator = std::allocator<T>  // 默认分配器
> class unordered_set;
使用时一般只需要关注第一个模板参数 T 即可，表示元素的类型, 可以是任何可哈希的类型（如 int, std::string, 自定义类型等）, vector 等不可哈希类型不能作为元素类型.

基本接口
  1. 插入元素：
    • insert(key): 插入一个新元素。如果元素已存在，则插入失败, 返回一个 pair，包含指向该元素的迭代器和一个布尔值表示插入是否成功。
    • emplace(args…): 直接在容器内构造一个新元素，避免不必要的拷贝或移动。
  2. 查找元素：
    • find(key): 返回指向该元素的迭代器，如果不存在则返回 end()。
    • contains(key) (C++20): 直接返回一个布尔值，表示元素是否存在。
    • count(key): 返回元素的数量（0 或 1，因为元素是唯一的）。
  3. 删除元素：
    • erase(key): 删除指定值的元素。
    • clear(): 清空集合中的所有元素。
  4. 获取集合信息：
    • size(): 返回集合中元素的数量。
    • empty(): 检查集合是否为空。
    1. 迭代访问：
    • begin() 和 end(): 返回指向集合开头和结尾的迭代器，用于遍历所有元素。
    • 范围 for 循环也可以直接用于遍历。 此时每个元素是类型 T，可以直接使用。

下面是一个简单的示例，展示了如何使用 std::unordered_set： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <unordered_set>
#include <string>
int main() {
    // 创建一个 unordered_set，元素类型为字符串
    std::unordered_set<std::string> fruitSet;

    // 插入元素
    fruitSet.insert("apple");
    fruitSet.insert("banana");
    fruitSet.insert("orange");

    // 尝试插入重复元素
    auto result = fruitSet.insert("apple");
    if (!result.second) {  // 返回的 second 为 false 表示插入失败
        std::cout << "Element 'apple' already exists in the set." << std::endl;
    }

    // 获取集合的信息
    std::cout << "Total unique fruits: " << fruitSet.size() << std::endl;
    std::cout << "Is set empty? " << (fruitSet.empty() ? "Yes" : "No") << std::endl;

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

    // 使用 contains (C++20)
    if (fruitSet.contains("grape")) {
        std::cout << "'grape' is in the set." << std::endl;
    } else {
        std::cout << "'grape' not found." << std::endl;
    }
    // 遍历所有元素
    for (const auto& fruit : fruitSet) {
        std::cout << fruit << std::endl;
    }
    // 删除一个元素
    fruitSet.erase("orange");
    return 0;
}

unordered_map

std::unordered_map 是一个基于哈希表实现的关联容器，用于存储键值对 (Key-Value Pairs)。它的设计目标是提供平均时间复杂度为 O(1) 的元素查找、插入和删除操作。

对比 std::map（基于红黑树实现，提供有序存储和 O(log N) 的操作复杂度），std::unordered_map 更侧重于快速访问，但不保证元素的顺序。

函数签名如下: 

1
2
3
4
5
6
7
8
#include <unordered_map>
template<
    class Key,
    class T,
    class Hash = std::hash<Key>,  // 默认使用 std::hash 作为哈希函数
    class KeyEqual = std::equal_to<Key>,  // 默认使用 std::equal_to 作为键比较函数
    class Allocator = std::allocator< std::pair<const Key, T> >  // 默认分配器
> class unordered_map;
一般只需要关注前两个模板参数 Key 和 T 即可，分别表示键的类型和值的类型。哈希表映射的关键就在于键, 因此需要仔细考虑选择什么类型作为键, 以及它是否具有”唯一性”.

并且这里的 key 的类型必须是可哈希的 (Hashable) 和可判等的 (Equality Comparable)，以确保哈希表能够正确地存储和查找键值对, 例如 std::string, int, char, 指针等基本类型都是可以的, 但是 vector 不可以作为 key 类型

它的使用场景主要包括需要快速查找、插入和删除键值对的应用。例如，频繁查询某个键对应的值，或者需要动态更新键值对。

基本接口包括： 1. 检查是否存在某个键： - find(key): 返回指向该键值对的迭代器，如果不存在则返回 end()。 - contains(key) (C++20): 直接返回一个布尔值，表示键是否存在。 - count(key): 返回键的数量（0 或 1，因为键是唯一的）。 2. 插入或更新键值对： - insert({key, value}): 插入一个新的键值对，如果键已存在则插入失败。 - operator[key]: 访问或插入键对应的值。如果键不存在，会插入一个默认值。 3. 删除键值对： - erase(key): 删除指定键的键值对。 - clear(): 清空映射中的所有键值对。 4. 获取映射信息： - size(): 返回映射中键值对的数量。 - empty(): 检查映射是否为空。 5. 迭代访问： - begin() 和 end(): 返回指向映射开头和结尾的迭代器，用于遍历所有键值对。 - 范围 for 循环也可以直接用于遍历。此时每个元素是一个 std::pair<const Key, T>, 可以通过 first 和 second 访问键和值。

下面是一个简单的示例，展示了如何使用 std::unordered_map： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
    // 创建一个 unordered_map，键为字符串，值为整数
    std::unordered_map<std::string, int> wordCount;

    // 插入键值对
    wordCount["apple"] = 2;
    wordCount["banana"] = 3;

    // 更新键值对
    wordCount["apple"] += 1;  // apple 的计数变为 3

    // 获取map的信息
    std::cout << "Total unique words: " << wordCount.size() << std::endl;
    std::cout << "Is map empty? " << (wordCount.empty() ? "Yes" : "No") << std::endl;

    // 检查键是否存在
    if (wordCount.find("banana") != wordCount.end()) {
        std::cout << "Banana count: " << wordCount["banana"] << std::endl;
    }

    // 使用 contains (C++20)
    if (wordCount.contains("orange")) {
        std::cout << "Orange count: " << wordCount["orange"] << std::endl;
    } else {
        std::cout << "Orange not found." << std::endl;
    }

    // 遍历所有键值对
    for (const auto& pair : wordCount) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 删除一个键值对
    wordCount.erase("banana");

    return 0;
}

普通 map 和 set

普通的 std::map 和 std::set 是基于红黑树实现的关联容器，提供有序存储和 O(log N) 的操作复杂度。与哈希表容器不同，它们保证元素按照键的顺序排列。 这使得它们适用于需要有序遍历或范围查询的场景。例如，按字典顺序存储单词，或者需要查找某个范围内的元素。

他们可以获取元素的最小值和最大值, 以及进行范围查询等操作, 这是哈希表容器所不具备的功能.

On this page
哈希 Hash
  1. 哈希函数对象 (Hash Functor) – std::hash
    1. 如何使用 std::hash
      1. 对内置支持的类型使用
      2. 对自定义类型使用
  2. 哈希表（Hash Table） 容器
    1. unordered_set
      1. 基本接口
    2. unordered_map
  3. 普通 map 和 set