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

  |  

摘要: 本文介绍在 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