Storing pairs in a map

Question

If I have a Pair class like this:

class Pair<K, L>{
   public final K a;
   public final L b;


   public Pair(K obj1, L obj2){this.a = obj1; this.b = obj2;}
   //...
}

I want to associate a Float with every pair of objects. They happen to be of the same type, so the Pair object will be Pair<SomeType, SomeType>. It's quite natural to put them in a Map<Pair<SomeType, SomeType>, Float>.

The thing is I don't want the order of objects in this pair to matter. I mean, once I've inserted a Pair<SomeType, SomeType> myPair such that myPair.a = obj1, myPair.b = obj2 in the Map, I'd like to be able to retrieve the same value with inverted Pair object, such that a = obj2, b = obj1.

Is it okay to insert two Pairs to the map in both orders in this case, that is new Pair(a, b) and new Pair(b, a)? That way I'm sure no matter how the objects are ordered in the Pair, I will get the correct value. However it takes twice as much space and creates issues when attempting to remove a key-value pair from the map (I need to remove both). Maybe it's good to create a method that will take care of inserting and removing both pairs from the map?

Answer 1

If the Map is a HashMap, it will use the Pair's hashCode() and equals() methods to determine equality. These methods can be overridden. The important part is making sure that the order of items doesn't matter. For hashCode(), this can be achieved by xor-ing the hash codes of the pair elements. For equals(), the items must be pairwise equal, or pairwise equal when flipped.

class UnorderedPair<A> {
  public final Pair<A, A> pair;
  ...

  @Override int hashCode() { return pair.a.hashCode() ^ pair.b.hashCode(); }

  @Override boolean equals(Object o) {
    ...
    UnorderedPair<A> other = (UnorderedPair<A>) o;
    return (a.equals(other.a) && b.equals(other.b))
        || (a.equals(other.b) && b.equals(other.a));
  }
}

You would then use a Map<UnorderedPair<SomeType>, Float>. This requires you to wrap each Pair in another object to provide the custom equality, but I find this to be cleaner than subclassing, since we decorate a pair with new equality semantics for the purpose of your Map. If you create extra methods for the insert/delete operations of your map, they would only wrap/unwrap the given Pair into an UnorderedPair.