编程Java

Java自定义哈希函数

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

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