Java HashSet содержит функцию, которая не работает

Question

Я пишу простую программу следующим образом: учитывая два числа M и N, p из [M, N] и q из [1, p-1], найдем все неприводимые доли р/д. Моей идеей является грубая сила всего возможного значения 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 дублируется. Любой может помочь мне выяснить, почему и как это исправить. Большое спасибо.

Answer 1

Перезаписать Fraction#equals и Fraction#hashCode. Они используются внутри, чтобы определить, совпадают ли два объекта. Я предполагаю, что когда вы не перезаписываете их, метод 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; 
} 

Answer 2

Вам необходимо реализовать Fraction#equals() и Fraction#hashcode(), поскольку это используется для определения погоды, когда набор содержит определенное значение или нет. Без него сравниваются ссылки на объекты, что не даст вам желаемого результата.

Answer 3

Ваш Fraction класс не переопределяет hashCode и equals. A HashMap содержит попытки найти ключ с тем же hashCode (и равным), как тот, который вы предоставили. Когда вы создаете новый экземпляр 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; 
}