How to apply memoization in a GCD function in Java?

Question

I have to calculate gcd of many pair of numbers, so for optimization I intend to apply memoization to my function.

Pair class:

class Pair{
     private long a;
     private long b;
    
    Pair(long a,long b){
        this.a = a;
        this.b = b;
    }
}

My hashmap (which is a static variable)

public static Map<Pair, Long> hashmap = new HashMap<>();

My gcd function:

public static long gcd(long a,long b) {
        
        if(hashmap.containsKey(new Pair(a,b))) {
            return hashmap.get(new Pair(a,b));
        }
        
        if(hashmap.containsKey(new Pair(b,a))) {
            return hashmap.get(new Pair(b,a));
        }
        
        if(a == 0) {
            return b;
        }
        
        long GCD = gcd(b%a,a);
        
        if(hashmap.containsKey(new Pair(a,b)) || hashmap.containsKey(new Pair(b,a))) {
            return GCD;
        }
        
        hashmap.put(new Pair(a,b),GCD);
        return GCD;
        
    }

However, when I print keys and values of my hashmap, it contains duplicates. This means that my function is not able to apply memoization, instead it is putting pair in the hashmap.

Answer 1

I can see some corrections to be made in your code.

• You don't have a hashCode defined for your Pair class. You could use the method described here to implement a hashCode for pair of longs.

• You don't have an equals method. You can just write this.a == other.a && this.b == other.b as the condition of equality. And other is an instance of Pair.

• This statement :

  if(hashmap.containsKey(new Pair(a,b)) || hashmap.containsKey(new Pair(b,a))) { return GCD; }

  is not needed. You already check it before invoking the recursive gcd

• Actually it shouldn't matter if the key is Pair(a,b) or Pair(b,a) the equals and hashCode should return the same and therefore you don't need to check

if(hashmap.containsKey(new Pair(b,a))) { return hashmap.get(new Pair(b,a)); }