Java HashSet中的contains函数无法正常工作

Question

我正在编写一个简单的程序，内容如下：给定两个数M和N，p范围在[M，N]之间，q范围在[1，p-1]之间，找到p/q的所有不可约分数。 我的想法是用暴力方法枚举p，q的所有可能值。并使用HashSet来避免重复的分数。但是，一些情况下contains函数无法按照预期工作。

我的代码如下：

import java.util.HashSet;
import java.util.Set;

public class Fraction {
    private int p;
    private int q;

    Fraction(int p, int q) {
        this.p = p;
        this.q = q;
    }

    public static int getGCD(int a, int b) {
        if (b == 0)
            return a;
        else 
            return getGCD(b, a % b);
    }

    public static Fraction reduce(Fraction f) {
        int c = getGCD(f.p, f.q);
        return new Fraction(f.p / c, f.q / c);
    }

    public static HashSet<Fraction> getAll(int m, int n) {
        HashSet<Fraction> res = new HashSet<Fraction>();
        for (int p = m; p <= n; p++)
            for (int q = 1; q < p; q++) {
                Fraction f = new Fraction(p,q);
                Fraction fr = reduce(f);
                if (!res.contains(fr))
                    res.add(fr);
            }
        return res;
    }

    public static void print(Fraction f) {
        System.out.println(f.p + "/" + f.q);
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        HashSet<Fraction> res = getAll(2, 4);
        for (Fraction f : res)
            print(f);
    }

}

以下是程序的输出结果

4/3
3/1
4/1
2/1
3/2
2/1

你可以看到分数2/1被重复了。有人能帮我解决这个问题并告诉我如何修复吗？非常感谢。

- Liverpool

Answer 1

在Fraction类中覆盖Object#equals和Object#hashCode方法。这些方法被HashSet用于确定两个对象是否相同。如果不覆盖它们，equals方法将测试对象引用的相等性而不是它们字段值的相等性。

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + p;
    result = prime * result + q;
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Fraction other = (Fraction) obj;
    if (p != other.p)
        return false;
    if (q != other.q)
        return false;
    return true;
}

- Niels Billen

---

我只想补充一下，这些函数通常可以由您的IDE自动实现，您不需要编写它们。除非您想要特定的行为，否则IDE提供的行为通常对大多数情况足够了。 - ordago

@ordago，没错，上述实现是由Eclipse自动生成的。 - Niels Billen

Answer 2

您需要实现 Fraction#equals() 和 Fraction#hashcode()，因为它们用于确定集合中是否包含某个值。如果没有实现，将会比较对象引用，这不会给您想要的结果。

- Predrag Maric

---

不要忘记hashCode()方法：在Java中覆盖equals和hashCode时应考虑哪些问题？ - Pshemo

Answer 3

你的 Fraction 类没有覆盖 hashCode 和 equals 方法。一个 HashMap 会尝试寻找与你提供的键具有相同 hashCode（和 equals）的键。由于你创建了一个新的 Fraction 实例，它永远不会与已经在 HashMap 中的实例相同。以下是如何实现 hashCode 和 equals 的方法：

@Override
public int hashCode() {
    return super.hashCode() + p * 24 + q * 24;
}

@Override
public boolean equals(Object other) {
    if (!(other instanceof Fraction)) return false;
    return ((Fraction) other).p == this.p && ((Fraction) other).q == this.q;
}

- molenzwiebel