An interchangeable key/value HashMap Set structure

Question

Background

Create a series of SQL JOIN statements using two operands: primary and secondary. The generic form of the JOIN statement is:

JOIN primary primary ON (secondary.id == primary.id)

Problem

The code currently iterates over a list of primary and secondary operands, as follows:

for( Bundle primaryOperand : bundleComparators ) {
  for( Bundle secondaryOperand : sortedBundles ) {

The problem is that the nested loop generates the following:

JOIN primary primary ON (secondary.id == primary.id)
JOIN secondary secondary ON (primary.id == secondary.id)

The second join is superfluous and, in this case, causes an error. The duplication can be eliminated with the following hypothetical data structure:

if( !interchangeableMap.contains( primaryOperand, secondaryOperand ) ) {
    interchangeableMap.put( primaryOperand, secondaryOperand );

    outputJoin( primaryOperand, secondaryOperand );
}

Where interchangeableMap.contains(...) will return true if primaryOperand is mapped to secondaryOperand or secondaryOperand is mapped to primaryOperand.

Questions

Does such a data structure exist in the Java libraries?
If not, what data structures would you use for its implementation?

Ideas

My first thought is to create a class that contains two HashMaps. Checking for containment queries the two HashMaps to see if one map contains the primary and secondary operands or the other map contains the secondary and primary operands. Insertions put the two operand combinations into their respective HashMaps.

Thank you!

Itay Maman · Accepted Answer · 2011-04-29T07:23:44.430

Here is a solution based on @roland's suggestion:

public final class Pair {
  private final Object a;
  private final Object b;

  public Pair(Object a, Object b) {
    this.a = a; 
    this.b = b;
  }

  @Override public boolean equals(Object o) {
    if(o == null || !(o instanceof Pair)) 
      return false;

    Pair that = (Pair) o;
    return this.a.equals(that.a) && this.b.equals(that.b) 
      || this.a.equals(that.b) && this.b.equals(that.a);
  }

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

Then:

Set<Pair> set = new HashSet<Pair>();
for(Bundle primaryOperand : bundleComparators) {
  for(Bundle secondaryOperand : sortedBundles) {
    Pair p = new Pair(primaryOperand.id, secondaryOperand.id);
    if(set.contains(p)) 
      continue;

    set.add(p);
    outputJoin(primaryOperand, secondaryOperand);
  }
}

A subtle point about the solution: you must also override the hashCode() method (hash value must reflect the equality relation), but you must do it in a symmetric way, that is: the hash value of <a,b> must be == to that of <b,a>

Thank you. Unless I am mistaken, the `Map` interface does not define a `contains( object, object )` method. There is `containsKey()` and `containsValue()`, but I cannot use them independently. — Dave Jarvis, Apr 29 '11 at 06:40
The `swap` method and conditional can be removed by checking the swapped values in `equals`? (Also, the `new Pair` can be removed, then.) — Dave Jarvis, Apr 29 '11 at 06:58

score 1 · Answer 2 · edited May 23 '17 at 11:55

1

Another idea would be to define a new Class OperatorPair that overrides equals() and use a Set of those, again to be checked with contains(). But your solution should work well, too.

(Also, if you do this, you should override hashCode() as well, for example you could calculate it based on the names of the operands... see e.g. this question for details.)

edited May 23 '17 at 11:55

Community

1
1

answered Apr 29 '11 at 06:29

Roland Ewald

4,630
3
35
49

score 1 · Answer 3 · answered Apr 29 '11 at 06:58

I hope I'm not completely wrong: You can use a HashMap and put each mapping twice: (primary, secondary) and (secondary, primary). For a lookup you would not check for contains but (get(primary) == seconday) or (get(secondary) == primary).

The apache commons library contains the BidiMap which allows a "bidirectional lookup between key and values". So you use this one too, to avoid the double insert

An interchangeable key/value HashMap Set structure

Background

Problem

Questions

Ideas

3 Answers3

Linked