Java自定义哈希函数

  |  

摘要: 本文介绍在 Java 中,使用自定义对象作为哈希映射容器的元素时,如何提供哈希函数和比较函数。

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


在文章 【STL】无序关联容器自定义哈希函数Python自定义哈希函数 中,我们以题目 1128. 等价多米诺骨牌对的数量 为例,讲解了用 C++ 和 Python 如何给自定义的类中添加哈希函数和比较函数,使得该类的对象可以作为映射容器的元素。

本文我们依然以本题为例,看一下 Java 中需要自定义哈希函数时的写法。


题目描述

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) 的总的个数。具体的做法是枚举所有元素,将其放入不同的桶内,同一个桶内都是等价的元素,然后就统计各个桶内元素个数即可。

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

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

代码 (Java)

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
43
44
45
46
47
48
49
50
51
52
53
54
class Item {
public Item(){}
public Item(int[] l) {
this.v0 = l[0];
this.v1 = l[1];
}

public boolean equals(Object otherObject) {
// 判断两个对象是否是同一个对象
if(this == otherObject)
return true;

// 判断 otherObject 是否为空
if(otherObject == null)
return false;

// 判断类型是否匹配
if(getClass() != otherObject.getClass())
return false;

// 此时 otherObject 是一个非空的 Item 类对象,记为 other
Item other = (Item) otherObject;

// this 和 other 的相等条件
return (v0 == other.v0 && v1 == other.v1) || (v0 == other.v1 && v1 == other.v0);
}

public int hashCode() {
if(v0 > v1) {
return v1 * 10 + v0;
}
return v0 * 10 + v1;
}

public int v0;
public int v1;
};

class Solution {
public int numEquivDominoPairs(int[][] dominoes) {
HashMap<Item, Integer> counter = new HashMap<Item, Integer>();
for(int[] x: dominoes) {
Item item = new Item(x);
counter.putIfAbsent(item, 0);
counter.put(item, counter.get(item) + 1);
}
int ans = 0;
for(HashMap.Entry <Item, Integer> entry: counter.entrySet()) {
int cnt = entry.getValue();
ans += cnt * (cnt - 1) / 2;
}
return ans;
}
}

Share