C++容器之哈希和无序容器

高效检索数据：哈希

在介绍无序容器之前，哈希这个前置知识点是必须要了解的。有时候我们存储数据，不需要关心排列顺序，而是要实现高效的搜索操作。一个顺序容器搜索需要从头到尾的遍历，时间复杂度是O(N)，一个普通关联容器，例如map，其关键字查找的时间复杂度是O(\log N)。而接下来介绍的哈希，其时间复杂度达到了O(1)，在常数范围内就能实现数据的查询。这是怎么做到的？

哈希函数

哈希函数可以将一个输入数据生成一个固定大小的整数。最常见的哈希函数为散列除数法。

即对输入数据对m取余，这样的话所有的数据都能转换到[0, m)这个范围内。
哈希函数是整个哈希过程中的核心。一个好的哈希函数必须保证输入的数据能够均匀的散列在一个范围内，为什么要这样做，后面会讲到。现在观察上面的哈希函数，当输入数据无规律时，能够保证数据均匀散列。

还有其他一些简单的哈希函数，例如CRC32，MD5等。这些哈希函数因为其自身的一些特性应用在不同的场景中，这里不再介绍。

哈希表

哈希表是一种基于哈希函数的数据结构，用于存储键值对。哈希表由一个数组和一组哈希函数组成。数组的每一个位置被称为一个桶，用于存放键值对。

哈希冲突

哈希函数可以将关键字转换成固定范围内的数字，这个数字就是哈希表内桶的编号。这个桶可以存放对应的值。但是哈希函数并不能保证两个数据经过转换后是同一个编号。如果说两个关键字映射到了同一个桶，这种情况称为哈希冲突。

为了保证数据结构的有效性，我们不能用数据覆盖这个桶，需要考虑一些解决办法。常用的解决方法有：

• 链地址法：每个桶存储的是一个链表。如果发生冲突，则数据附加到这个桶的链表后面。
• 开发地址法：当发生冲突时，寻找下一个桶来存储。常见的方法由线性探测（依次往后面放数据），二次探测（二次函数的规律向下找桶）和双重哈希（用第二个哈希函数处理）。

哈希表是一个用空间换时间的操作。空间越大，其查找效率越高。

操作

哈希表支持的操作较少：

• 插入：计算键的哈希值，找到对应的桶，将键值对插入到桶中。
• 删除：计算键的哈希值，找到对应的桶，删除桶中的键值对。
• 查找：计算键的哈希值，找到对应的桶，查找桶中的键值对。

判断性能

计算哈希表的性能，可以用平均哈希冲突来大致判断，其计算方法如下：

• 计算负载因子\alpha：为存储元素数量和桶数量的比值。
• 平均哈希冲突：\alpha - 1

假设我们有具体的数据情况，则平均哈希冲突的计算方法如下：

1. 统计每个桶中的元素数量。
2. 计算每个桶中的冲突数：如果一个桶中有k个元素，那么该桶的冲突数为 k−1。
3. 求所有桶的冲突数之和。
4. 计算平均冲突数：总冲突数除以桶的数量。

C++中的无序容器

C++中有四个无序容器：unordered_map、unordered_set、unordered_multiset和unordered_multimap。有关map和set的基础使用方法可以参见：https://bg.littleao.top/archives/cpp_associative_container

管理桶

在上面我们得出结论，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。我们无法自定义哈希函数，但是可以通过管理桶来决定性能。

桶接口

• c.bucket_count()：正在使用的桶的数目。
• c.max_bucket_count()：容器最多能容纳的桶的数量。
• c.bucket_size(n)：第n个桶中有多少个元素。
• c.bucket(k)：关键字为k的元素在哪个桶中。

桶迭代

• local_iterator：访问桶中元素的迭代器类型。
• const_local_iterator：const类型的迭代器。
• c.begin()，c.end()：桶n的首元素迭代器和尾后迭代器。
• c.cbegin()、c.cend()：上一个类型的const版本。

哈希策略

• c.load_factor()：每个桶的平均元素数量。
• c.max_load_factor()：容器试图维护的平均桶大小。如果平均元素数量超出了，容器会添加新的桶。
• c.rehash(n)：重组存储，满足bucket_count>=n，并且bucket_count >= size/max_load_factor。
• c.reserve(n)：重组存储，使得c可以保存n个元素且不必rehash。

自定义类作为无序容器的关键字

为了生成不同类型的哈希值，标准库为自带的内置类型提供了hash模板。我们自己编写的类不能直接生成哈希值，需要我们定义一个哈希值计算函数才能实现自定义类作为关键字存入无序容器。此外，无序容器在插入时会进行比较操作，我们还需要定义一个判断相等的函数。

直接重载==运算符也可以。

#include <functional>
#include <unordered_set>

using namespace std;

class MyClass
{
public:
    MyClass(int v):val(v) {}

    int val;

    static size_t hasher(const MyClass& data)
    {
        return hash<int>()(data.val);
    }

    static bool is_equal(const MyClass& ld, const MyClass& rd)
    {
        return ld.val == rd.val;
    }

    bool operator==(const MyClass& rd)
    {
        return val == rd.val;
    }
};

int main()
{
    using MyClassSet = unordered_multiset<MyClass, decltype(MyClass::hasher)*, decltype(MyClass::is_equal)*>;
    MyClassSet exampleSet1(42, MyClass::hasher, MyClass::is_equal);
    // 重载了==可以这样做
    MyClassSet exampleSet2(42, MyClass::hasher);
}