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.

score 11 · Accepted Answer · edited Aug 23 '19 at 07:23

11

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

edited Aug 23 '19 at 07:23

Stephen C

698,415
94
811
1,216

answered Jan 12 '15 at 15:07

Niels Billen

2,189
11
12

1

I only wanted to add that these functions can be usually implemented automatically by your IDE and you don't need to code them. Unless you want to have a specific behaviour, the one provided by the IDE are usually enough for most cases. – ordago Aug 23 '19 at 07:32
1

@ordago, true, the above implementation was automatically generated by Eclipse – Niels Billen Jan 14 '20 at 12:47

score 3 · Answer 2 · answered Jan 12 '15 at 15:06

3

You need to implement Fraction#equals() and Fraction#hashcode(), because that is used for determining weather the set contains certain value or not. Without it, object references are compared, which will not give you the desired result.

answered Jan 12 '15 at 15:06

Predrag Maric

23,938
5
52
68

2

Lets not forget about `hashCode()` method as well: [What issues should be considered when overriding equals and hashCode in Java?](http://stackoverflow.com/questions/27581/what-issues-should-be-considered-when-overriding-equals-and-hashcode-in-java) – Pshemo Jan 12 '15 at 15:07

score 0 · Answer 3 · answered Jan 12 '15 at 15:08

Your Fraction class does not override hashCode and equals. A HashMap contains tries to find a key with the same hashCode (and equals) as the one you provided. As you create a new instance of Fraction, it will never be the same as the one already in the HashMap. Here is how you would do hashCode and 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;
}

Java HashSet contains function not working

3 Answers3

Linked

Related