编程C++

【STL】无序关联容器自定义哈希函数

字数统计: 2.5k字   |   阅读时长: 10分
, , , ,

摘要: 本文介绍在 C++ STL 中，使用自定义对象作为无序关联容器的元素时，如何提供哈希函数和比较函数。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

无序关联容器

STL 中的无序关联容器有四种

  • unordered_map
  • unordered_multimap
  • unordered_set
  • unordered_multiset

它们都是在哈希表的基础上实现的。哈希表的其中一个重要的关注点是如何设计哈希函数。

在 STL 中，每种无序容器都指定了默认的 hash<key> 哈希函数和 equal_to<key> 比较规则，它们仅适用于存储基本类型(int、double、float、string 等)。

当关联容器的键是整数或者字符串时，不用提供哈希函数，STL 提供了默认的哈希函数。而当关联容器是自定义对象或者是其它容器(例如 pair<int, int>、vector<int>), 需要提供哈希函数和比较函数。此时 STL 标准库提供的 hash<key> 和 equal_to<key> 将不再适用。

哈希函数的作用: 根据各个键值对中键的值，计算出一个哈希值，哈希表可以根据该值判断出该键值对具体的存储位置。

比较函数的作用: 当键是自定义对象或容器时，定义什么叫两个键相等，两个不相等的键的哈希值可能是一样的，这是哈希冲突的来源。

1. 自定义哈希函数

STL 中的哈希函数不是普通函数，而是一个函数对象类。因此想要自定义哈希函数，需要自定义一个函数对象类。

例子：点类

有一个点类 Point，其中的 x, y 表示点的坐标，origin_x, origin_y 表示原点坐标，get_slope 返回点 $(x, y)$ 相对于 origin_x, origin_y 的斜率

1
2
3
4
5
6
7
8
9
10
11
12
13
class Point
{
public:
    Point(int x, int y, int origin_x, int origin_y): x(x), y(y), origin_x(origin_x), origin_y(origin_y) {}
    long double get_slope()
    {
        return (x - origin_x) / (y - origin_y);
    }

private:
    int x, y;
    int origin_x, origin_y;
};

在此基础上，假设我们想创建一个可存储 Point 类对象的 unordered_set 容器，因为 Point 为自定义的类型，因此默认的 hash<key> 哈希函数不再适用，这时就需要以函数对象类的方式自定义一个哈希函数。

1
2
3
4
5
6
7
// 注意，重载 () 运算符时，其参数必须为 const 类型，且该方法也必须用 const 修饰。
class MyHash {
public:
    long double operator()(const Point &A) const {
        return A.get_slope();
    }
};

利用 MyHash 函数对象类的 () 运算法重载，自定义了适用于 Point 类对象的哈希函数，该哈希函数接受一个 Point 对象，范围该对象的斜率。

默认的 hash<key> 哈希函数，底层也是以函数对象类的形式实现的。

在创建存储 Point 对象类的 unordered_set 容器时，可以将 MyHash 作为参数传递给该容器模板类中的 Pred 参数。

1
unordered_set<Point, MyHash> point_setting;

此时容器 point_setting 还不能使用，因为还没有定义比较函数，即定义什么叫两个 Point 对象相等。默认的 equal_to<key> 不适用该容器。

2. 自定义比较函数

和哈希函数一样，无论创建哪种无序容器，都需要为其指定一种可比较容器中各个元素是否相等的规则。

与 hash<key> 一样，默认的 equal_to<key> 比较规则也是一个函数对象类，底层实现如下

1
2
3
4
5
6
7
8
template<class T>
class equal_to
{
public:   
    bool operator()(const T& _Left, const T& _Right) const{
        return (_Left == _Right);
    }   
};

这里直接用了 == 来比较容器中任意两个元素是否相等。这提示了我们什么情况可以用默认的 equal_to<key> 比较规则：

如果容器中存储的元素类型，支持直接使用 == 运算符比较是否相等，则该容器可以用默认的 equal_to<key> 比较规则。否则不能使用。

例子：点类

还是点类的例子，point_setting 中存的是 Point 类对象，它不支持 == 运算符做比较，此时有两种方法

  1. 在 Point 类中重载 ==，这使得 equal_to<key> 中使用的 == 变得合法
  2. 以函数对象的形式自定义一个比较规则

例子: 人类

下面以人类为例子看一下两种实现自定义比较规则的写法，人类的定义如下。一个人类对象有姓名和年龄两个成员变量。在自定义哈希函数中直接返回人的年龄。

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
class Person 
{
public:
    Person(string name, int age) :name(name), age(age) {};
    string getName() const;
    int getAge() const;

private:
    string name;
    int age;
};

string Person::getName() const 
{
    return this->name;
}

int Person::getAge() const 
{
    return this->age;
}

class MyHash 
{
public:
    int operator()(const Person &A) const 
    {
        return A.getAge();
    }
};
  • 定义 Person 类的 == 函数

== 中直接比较两个 Person 类对象的年龄是否相等，若年龄相等，则两个 Person 类对象视为是相等的。

1
2
3
4
bool operator==(const Person &A, const Person &B) 
{
    return (A.getAge() == B.getAge());
}

创建 person_setting 容器，并初始化四个 Person 对象，比较规则 == 看的是年龄是否相等。

初始化的四个对象，前三个的年龄是相等的，即相当于只初始化了两个不同的对象，

所以 person_setting 容器中存的实际只是 {"zhangsan",40},{"lisi",30} 两个对象。

1
unordered_set<Person, MyHash> person_setting({{"zhangsan", 40},{"zhangsan", 40},{"lisi", 40},{"lisi", 30}});
  • 以函数对象类的方式自定义比较规则
1
2
3
4
5
6
7
8
class MyCmp 
{
public:
    bool operator()(const Person &A, const Person &B) const 
    {
        return (A.getName() == B.getName()) && (A.getAge() == B.getAge());
    }
};

同样创建 person_setting 容器，并初始化四个 Person 对象，此时比较规则 MyCmp 看的是姓名和年龄是否相等。

按照比较规则，初始化的四个对象中，前两个对象是相等的，因此相当于只初始化了三个不同的对象，

所以 person_setting 容器中存的实际只是 {"zhangsan", 40},{"lisi", 40},{"lisi", 30} 三个对象。

1
unordered_set<Person, MyHash, MyCmp> person_setting({{"zhangsan", 40},{"zhangsan", 40},{"lisi", 40},{"lisi", 30}});

3. leetcode 题目列表

由点对的斜率计算哈希值：

由点的横纵坐标做哈希值：

由点的距离计算哈希值：

例题

题目描述

给你一个由一些多米诺骨牌组成的列表 dominoes。

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。

形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

示例：
输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
输出：1

提示：

1
2
1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9

算法：哈希

我们最终要求的答案是 i < j 情况下的等价对 (i, j) 个数。如果我们有不考虑 i 和 j 的大小关系的情况下的等价对 (i, j) 个数 cnt，那最终答案其实就是 cnt / 2。

因此我们可以直接求等价对 (i, j) 的总的个数。具体的做法是枚举所有元素，将其放入不同的桶内，同一个桶内都是等价的元素，然后就统计各个桶内元素个数即可。

我们最好用一个整数来表示元素，也就是定义该元素的哈希函数，这样我们就可以在哈希表来维护各个桶了，也就是用 Counter 维护各个等价的元素的个数。

由于本题中元素的两个维度的值 v0, v1 均在 1 到 9 之间，所以用 v0 * 10 + v1 就可以唯一地表示每个元素了，不会存在冲突。同时基于题目给定的相等的条件，当 v0 > v1 时，哈希值用 v1 * 10 + v0 即可满足 (v0, v1) 与 (v1, v0) 相等的条件。

代码 (C++)

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
42
class Item 
{
public:
    Item(){}
    Item(const vector<int>& l)
    {
        v0 = l[0];
        v1 = l[1];
    }

    bool operator==(const Item& other) const
    {
        return (v0 == other.v0 && v1 == other.v1) || (v0 == other.v1 && v1 == other.v0);
    }

    int v0, v1;
};

class MyHash {
public:
    int operator()(const Item &A) const {
        if(A.v0 > A.v1)
            return A.v1 * 10 + A.v0;
        return A.v0 * 10 + A.v1;
    }
};

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<Item, int, MyHash> counter;
        for(const vector<int>& x: dominoes)
            counter[Item(x)] += 1;
        int ans = 0;
        for(const pair<Item, int>& kv: counter)
        {
            int cnt = kv.second;
            ans += cnt * (cnt - 1) / 2;
        }
        return ans;
    }
};

总结

当无序容器中存储的是基本类型（int、double、float、string）数据时，自定义哈希函数和比较规则，都只能以函数对象类的方式实现。

而当无序容器中存储的是用结构体或类自定义类型的数据时，自定义哈希函数的方式仍只有一种，即使用函数对象类的形式；而自定义比较规则的方式有两种

  1. 用默认的 equal_to<key> 规则，但前提是必须重载 == 运算符。
  2. 与自定义哈希函数一样，仍然用函数对象类的方式

相关文章

Share