Hash Function Strategy

此文主要为总结自己之前用到的一些 Hash 策略以及最近所学到的一个利用 C++ 模板元编程实现的万用 hash function，以及对 Hash 冲突解决方式对时间常数的影响的相关对比。

我的 Hash 策略

在做算法题时，自己有一些小的 tricks，用于减少时间常数或者使得某些类型能被标准库容器容纳（即自定义其 hash function）。

整型哈希

这种策略通常用于整型的哈希，为了避免容器的分配带来的开销。定义为一个 unsigned long 类型作为 hash_val，再根据题目中的数据范围来具体实施哈希，具体见下述例子。

#include <cassert>
const int n = 1e5;
int x = 1e4 + 2e3;
int y = 2e4 + 6e2;
unsigned long hash_val = x * n + y;
int a = hash_val / n;
int b = hash_val % n;
assert(x == a);
assert(y == b);

这种方式被称作简单映射可能会比较合适，使用场景有限。

std::pair 的哈希

C++标准库并没有为std::pair 提供特化版本的 hash function，最主要的原因使 std::pair 是个模板类，模板参数很有可能为自定义类型，这难以协调。此外，标准库提供了偏特化版本的类型具体可见¹。

如果真的要在 std::unorderd_map 或 std::unordered_set 等类似的关联容器中使用 std::pair 的话，借助标准库为其定义一个简单易写的 hash function 即可。

下列代码中 std::unordered_set 类模板的第二个模板参数，即自定义的 hash function 参数，写了一个简单的哈希策略，

#include <iostream>
#include <unordered_set>
using namespace std;

struct MyHash
{
  size_t operator() (const pair<int,int>& p) const
  {
    return hash<long long>()( (static_cast<long long>(x.first) ) 
    ^ ( (static_cast<long long>(x.first))<<32) );
  }
};

ostream& operator<<(ostream& os, const pair<int, int>& p)
{
    return os << p.first << "\t" << p.second << endl;
}

int main()
{
    unordered_set<pair<int,int>, MyHash> pset;
    pset.emplace(1, 2);
    pset.emplace(1, 2);
    pset.emplace(2, 2);
    pset.emplace(9788, 243);
    pset.emplace(354, 25467);
    pset.emplace(354, 25467);
    
   for (size_t i = 0; i < pset.bucket_count(); ++i) {
        cout << "bucket #" << i << "  is :    " << endl;
        for (auto it = pset.begin(i); it != pset.end(i); ++it)
            cout << *it;
        cout << endl;
    }
    
    return 0;
}

这种方式不仅适用于 std::pair，还适用于几乎所有自定义类型，问题的关键是选择恰当的散列方式，使得冲突尽可能的减少。

加快 `std::unorderd_map` 的速度

为了避免动态改变哈希表的大小，可以预估容器中带插入元素的数量，并且预先申请好内存空间，避免动态分配过程中造成的 rehash 现象。

例如，我会预先调用 reverse 成员函数预先分配内存空间，以及设置好最大填充因子。

unordered_map<int,int> hash;
mp.reserve(1024);
mp.max_load_factor(0.25);

万用 Hash Function

下列代码中的 hash_combine 函数模板 boost² 库中实现的，是下面整个 hash function 中最核心的部分。

此外，定义了三组 hash_val 函数模板，其中两组是采用了 C++ 11 中的可变长参数模板，三组函数连续调用，直至不存在可变长参数为止。基本调用的步骤如下：

入口函数为，size_t hash_val(const Types&... args) ，seed 首先设置为0，seed即为最后的返回的散列值。然后将所有的变长参数传递给 void hash_val(size_t& seed, const T& val, const Types&... args)
void hash_val(size_t& seed, const T& val, const Types&... args) 去除变长参数中的第一个，调用 hash_combine 来生成第一个参数生成的 seed 值。
然后再递归调用本体，如果变长参数仅仅剩下一个，则调用 void hash_val(size_t& seed, const T& val) ，完成整个过程。
最后返回的 seed 即为最终的散列值。

这个利用可变长参数模板重载的 trick 实现一个万用的 hash function 实在是高明，实在是令人拍案叫绝，以后一定要好好学习下模板元编程。

关于这个万用 hash function 更多的信息，可见³。

#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

template <typename T>
inline void hash_combine(size_t& seed, const T& val)
{
    seed ^= std::hash<T>()(val) + 0X9E3779B9 + (seed << 6) + (seed >> 2);
}

template <typename T>
inline void hash_val(size_t& seed, const T& val)
{
    hash_combine(seed, val);
}

template <typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Types&... args)
{
    hash_combine(seed, val);
    hash_val(seed, args...);
}

template <typename... Types>
inline size_t hash_val(const Types&... args)
{
    size_t seed = 0;
    hash_val(seed, args...);
    return seed;
}

class MyObject{
public:
    string a;
    char b;
    unsigned c;
    bool operator==(const MyObject& rhs) const
    {
        return a == rhs.a && b == rhs.b && c == rhs.c;
    }

    bool operator!=(const MyObject& rhs) const
    {
        return !operator==(rhs);
    }

    friend ostream& operator<<(ostream& os, const MyObject& ptr)
    {
        return os << ptr.a << "   " << ptr.b << "   " << ptr.c << endl;
    }
};

class MyHashFunction{
public:
    std::size_t operator()(const MyObject& obj) const {
        return hash_val(obj.a, obj.b, obj.c);
    }
};


int main()
{
    unordered_set<MyObject, MyHashFunction> objset;
    MyObject m1{"aaa", 'c', 12345};
    MyObject m2{"aaeeertya", 'c', 44634455};
    MyObject m3{"aaa", 'c', 1234457375};
    MyObject m4{"aaeeta", 'b', 1234785};
    MyObject m5{"aaaawrrsgdf", 'd', 1234657};
    objset.insert(m1);
    objset.insert(m2);
    objset.insert(m3);
    objset.insert(m4);
    objset.insert(m5);
    for (size_t i = 0; i < objset.bucket_count(); ++i) {
        cout << "bucket #" << i << "  is :    ";
        for (auto it = objset.begin(i); it != objset.end(i); ++it)
            cout << *it;
        cout << endl;
    }
    cout << objset.size() <<endl;
}

`std::unordered_map` 的性能问题

这一方向的想法来自于我看过的一个 youtuber 的视频⁴。该 youtuber 对标准库的 std::unordered_map 以及 Google 开源的 abesil flat hash map ，和其他的一些个人爱好者的实现做出了基准测试，发现了Google 实现的版本速度更优。

标准库的实现是采用的拉链法的策略来解决哈希碰撞，即 hash_val 对应了一个 bucket，每个bucket 后面跟随了一条链表，链表的节点上则存储着我们的键值对。当容器中的总元素超出了填充因子时，容器会重新申请更大的内存扩充桶的数量，然后重新哈希。

Google 则采用了开放寻址法中最简单的线性探测方法来解决哈希碰撞，取得了更快的速度。

为什么Google 的方法更为优秀呢？从硬件的角度考虑，如果我们的程序如果是顺序处理连续的内存，那么 CPU 会把我们正在处理的内存附近的内容读到他自己的缓存当中，下次如果 CPU 需要处理已经在缓存中的内容时，它就不需要从系统的主存重新读取相同的内容。因为 Google 的哈希表用没有使用链表，而是采用开发寻址法加上一个 array 保存所有的键值对的方案，所以它的性能才远好于使用了传统的基于链表的实现。

Reference

https://www.cplusplus.com/reference/functional/hash/ “std::hash” ↩︎
https://www.boost.org/doc/libs/1_75_0/doc/html/hash/combine.html “Combining hash values” ↩︎
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf “Convenience Functions to Combine Hash Values” ↩︎
https://www.youtube.com/watch?v=nx5g5bwtUuA “为啥 std::unordered_map 有点慢？” ↩︎

我的 Hash 策略#

整型哈希#

std::pair 的哈希#

加快 std::unorderd_map 的速度#

万用 Hash Function#

std::unordered_map 的性能问题#

Reference#