5

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?

5

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.

  • 1
    Why xor the hashes? Can I simply add them, or perform 'and' or 'or'? – user4205580 Apr 3 '16 at 21:47
  • @user4205580 In principle, any commutative operation can be used to combine the hashes. This includes | and &, but with those operations the ones or zeroes in the bit pattern would dominate, leading to low entropy in your hash function. The ^ avoids this, but would produce zero if the hashes of a,b are the same. It might actually be preferable to check for that: int ah = a.hashCode(); int bh = b.hashCode(); if (ah == bh) return ah; return ah ^ bh;. – amon Apr 4 '16 at 6:16
  • Arithmetic operations + and * are other candidates. Addition seems feasible because unsigned add is just xor with carry. But if hashes are evenly distributed, 50% are negative integers, meaning our result tends towards zero rather than being evenly distributed. Multiplication has a different problem: if a number has a 50% chance of being a multiple of 2, multiplying two such random numbers has a 75% chance, and so on for all other factors. Again, this reduces entropy. Since it doesn't skew the output distribution or reduces entropy for any bit, xor is the preferred mechanism to combine hashes. – amon Apr 4 '16 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.