C++ 数据结构：哈希表原理与 STL 实现

哈希表

首先要理解哈希和哈希表有什么不同。哈希就是映射，是一种算法思想。哈希表就是映射表，是利用映射这种思想写出的一种数据结构。

所有的哈希表的算法流程都是类似的——拿到一个 key，利用哈希函数进行 hasher(key)，得到的空间位置存放我们想要存放的数据 Value。

或者——拿到一个 key，利用哈希函数进行 hasher(key)，从得到的空间位置取出我们想要查找的数据 Value。

理解哈希表

理解哈希表，我们可以分为三层去学习。第一层是理解哈希值，第二层是学习各种哈希函数，第三层是解决哈希冲突。

为什么要这么学习，因为 STL 哈希表中的底层哈希函数，其实都是对哈希值去进行 Hash。这个哈希值是一个整形，整形它本身就是哈希值；其他的自定义类型不管你 Key 的类型是 string，还是 vector。这些自定义类型，想要存储到哈希表中，上层最终都要让它们能够转为哈希值。

所以我们要先得到哈希值。然后再去使用哈希函数进行 hash 得到对应的映射位置。

另外，其实最基本的哈希表，逻辑上可以看作是一个数组。既然是数组，那么他就一定有大小。有大小，那么就一定存在 hash 的数据太多，数组空间不够的情况。这时再 hash，就有了哈希冲突。更不用提两个不同的自定义类型的数量远远大于哈希值的数量，自定义类型可能哈希值相同，就更会存在哈希冲突。所以，哈希是哈希表的功能。哈希冲突，是这个功能产生的一种可能存在的结果。所以两者存在因果的关系。

所以我们的理解链应该是：哈希值——》哈希函数——》哈希冲突

哈希值（整形）

为什么要有哈希值？是因为哈希函数都是对一个整形进行哈希，比如直接定址、除留余数、平方取中，基数转换等等。最重要的是 STL 里面使用的也是除留余数（只不过不是传统的除留余数，有其他优化）。

我们在用 STL 的时候，如果想要对一个自定义类型进行哈希，那么就必须提供这个自定义类型向哈希值的转换方法。本篇文章中我们以后称为'转换策略'。

有了这个转换策略，就可以将自定义类型转化为一个哈希值。然后再将这个哈希值交给 STL 底层的哈希函数进行哈希。得到的结果经过哈希冲突的处理得到映射位置，这个映射位置就是最后这一次哈希要存储的位置了。

转化哈希值一般要定义为一个仿函数，然后作为 unordered_map 的第三个模板参数传进去。这样就能让一个任意类型能够去进行哈希了。

要注意转化哈希值要注意速度快，离散高。常见的转化策略比如 string 类型向整形转化的 BKDR 哈希，DJB 哈希、多成员复杂结构，结构中含有整形和 string 的 hash_combine、以及对含少量成员的异或组合。里面有嵌套容器的递归哈希等等。

这里挑选熟悉的演示：

BKDR 哈希

优点：实现简单，计算快；离散高，冲突少；不同种子可以计算出不同哈希值。

实现方法是选取一个种子 seed，然后对字符串里面的每一个字符进行处理：

size_t BKDRHash(const string &str) {
    size_t seed = 131; // 31 131 1313 13131 131313
    size_t hash = 1;
    for (auto e : str) {
        hash *= seed;
        hash += e;
    }
    return hash & 0x7FFFFFFF; // 确保返回正数
}

这个种子的值可以是 31，131，1313，13131，131313...

异或组合

优点：实现简单，计算快。缺点：冲突率高

struct PointHash {
      {
         hash = ;
         ( e : vec) {
            hash ^= (e << );
        }
         hash;
    }
};