Map which allows to provide the equals-comparator and the hashing function separately

Question

While trying to model polynomials, in particular their multiplication, I run into the following problem. During the multiplication, the individual monomials of the two polynomials are multiplied and of course in can happen that I have (3x^2 y + 5x y^2) * (x + y). The result contains 3x^2 y^2 and 5 x^2 y^2, which I want to combine by addition right away.

Naturally I would like to use the part x^2 y^2 of the monomial as a key in a (hash) map to add up the different coefficients (3 and 5 in the example). But the monomial object as I envisage it should naturally also contain the coefficient, which should not be part of the map key.

Of course I could write equals/hashcode of the monomial object such that they ignore the coefficient. But this feels just so wrong, because mathematically a monomial clearly is only equal to another one if also the coefficients are equal.

Introducing a coefficient-free monomial object for intermediate operations does also not look right.

Instead of using the map, I could use a list and use a binary search with a dedicated comparator that ignores the coefficient.

Short of implementing a map which does not use the keys' equals/hashcode, but a dedicated one, are there any better ideas of how to fuse the monomials?

Answer 1

Since the JDK implementation of [Linked]HashMap does not permits you to override the equals/hashCode implementation, the only other ways are:

• a wrapping object like this:

    class A {
      private final String fieldA; // equals/hashCode based on that field.
      private final String fieldB; // equals/hashCode based on that field.
    }
  
    class B {
      private A a;
      public int hashCode() {return a.fieldA.hashCode();} 
      public boolean equals(Object o) {... the same ... }
    }
  
    Map<B, Value> map = new HashMap<B, Value>();
    map.put(new B(new A("fieldA", "fieldB")), new Value(0));
  

  Well, with more getters/constructors.

  This can be annoying, and perhaps there exists some library (like Guava) that allows an equals/hashCode method to be given like you can give a Comparator to TreeMap.

  You'll find below a sample implementation that point out what to do to decorate an existing map.

• use a TreeMap with a specific Comparator. The other answer point it, but I'd say you'll need to correctly define a Comparator because this could lead to problems: if you compareTo method returns 0 when equality is reached, and 1 in other case, this means there is no natural ordering. You should try to find one, or use the wrapper object.

---

If you want to take the challenge, you can create a basic implementation using delegation/decoration over another HashMap (this could be another kind of map, like LinkedHashMap):

public class DelegatingHashMap<K,V> implements Map<K,V> {
  private final BiPredicate<K,Object> equalsHandler;
  private final IntFunction<K> hashCodeHandler;
  private final Map<Wrapper<K>,V> impl = new HashMap<>();

  public DelegatingHashMap(
    BiPredicate<K,Object> equalsHandler,
    IntFunction<K> hashCodeHandler
  ) {
    this.equalsHandler = requireNonNull(equalsHandler, "equalsHandler");
    this.hashCodeHandler= requireNonNull(hashCodeHandler, "hashCodeHandler");
  }

  public Object get(K key) {
    Wrapper<K> wrap = new Wrapper<>(key);
    return impl.get(wrap);
  }  

  ...

  static class Wrapper<K2> {
    private final K2 key;
    private final BiPredicate<K> equalsHandler;
    private final IntFunction<K> hashCodeHandler;
    public int hashCode() {return hashCodeHandler.apply(key);}
    public boolean equals(Object o) {
      return equalsHandler.test(key, o);
    }
  }
}

And the code using the map:

DelegatingHashMap<String, Integer> map = new DelegatingHashMap<>(
  (key, old) -> key.equalsIgnoreCase(Objects.toString(o, "")),
  key -> key.toLowerCase().hashCode()
);
map.put("Foobar", 1);
map.put("foobar", 2);

System.out.println(map); // print {foobar: 2}

But perhaps the best (for the memory) would be to rewrite the HashMap to directly use the handler instead of a wrapper.

Answer 2

You could use a TreeMap with a custom comparator:

TreeMap(Comparator<? super K> comparator)

Constructs a new, empty tree map, ordered according to the given comparator.

(Source)