CODEWITHSUNDEEP
javahashhashcodehashset
Liverpool
Liverpool

Reputation: 131

Java HashSet contains function not working

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.

Upvotes: 6

Views: 9850

Answers (3)

Niels Billen
Niels Billen

Reputation: 2199

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

Upvotes: 11

molenzwiebel
molenzwiebel

Reputation: 916

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

Upvotes: 0

Predrag Maric
Predrag Maric

Reputation: 24423

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.

Upvotes: 3

Related Questions