编程Python

Python自定义哈希函数

字数统计: 901字   |   阅读时长: 3分
, , ,

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

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

本文我们以 leetcode 的一道题为例，看一下 Python 中需要自定义哈希函数时的写法。

题目链接

1128. 等价多米诺骨牌对的数量

题目描述

给你一个由一些多米诺骨牌组成的列表 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) 相等的条件。

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution1:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        counter = Counter()
        for x in dominoes:
            v0, v1 = x
            if v0 > v1:
                counter[v1 * 9 + v0] += 1
            else:
                counter[v0 * 9 + v1] += 1
        ans = 0
        for k in counter:
            cnt = counter[k]
            ans += cnt * (cnt - 1) // 2
        return ans

下面我们换一种实现方式，把 v0, v1 封装成一个对象，然后把哈希函数的逻辑放到 __hash__() 中，然后在将题目给定的等价条件放到 __eq__() 中，我门就可以在 Counter 中维护封装的对象了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Item:
    def __init__(self, l):
        self.v0 = l[0]
        self.v1 = l[1]

    def __eq__(self, item):
        return self.v0 == item.v0 and self.v1 == item.v1 \
                or self.v0 == item.v1 and self.v1 == item.v0

    def __hash__(self):
        if self.v0 > self.v1:
            return self.v1 * 10 + self.v0
        return self.v0 * 10 + self.v1

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        counter = Counter()
        for x in dominoes:
            counter[Item(x)] += 1
        ans = 0
        for k in counter:
            cnt = counter[k]
            ans += cnt * (cnt - 1) // 2
        return ans

哈希函数还可以用其它可行的方式实现，例如 tuple 自带的哈希函数，实现方式如下

1
2
3
4
def __hash__(self):
    if self.v0 > self.v1:
        return tuple.__hash__((self.v1, self.v0))
    return tuple.__hash__((self.v0, self.v1))

这种额外封装一层的方式会增加运行时间，但是思路会更清晰。

Share