Java HashSet contains function not working

Question

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.

My code

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

}

Here is the output of program

4/3
3/1
4/1
2/1
3/2
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.

Answer 1

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