Java HashSet包含无法使用的功能 [英] Java HashSet contains function not working

问题描述

我正在编写一个简单的程序，如下所示:给定两个数字M和N，p来自[M，N]，q来自[1，p-1]，求出p/q的所有不可约分数. 我的想法是蛮力所有p，q的值.并使用HashSet避免重复分数.但是，以某种方式包含的功能不能按预期方式工作.

I am writing a simple program as follow: Given two numbers M and N, p is from [M,N] and q is from [1,p-1], find all irreducible fractions of p/q. My idea is brute force all possible value of p, q. And using HashSet to avoid duplicated fraction. However, somehow the contains function not working as expected.

我的代码

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分数重复.任何人都可以帮助我弄清楚为什么以及如何解决它. 非常感谢.

you can see the fraction 2/1 is duplicated. Anyone can help me figure out why and how to fix it. Many thanks.

推荐答案

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

Override the Object#equals and Object#hashCode methods in the Fraction class. These methods are used by HashSet to determine if two objects are the same. When you don't override them, the equals method tests equality of the objects' references rather that equality of their field values.

@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;
}

这篇关于Java HashSet包含无法使用的功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！