Iterating over 2 maps in java

Question

I have a situation whereby I looping over a map twice, not particularly happy with my algorithm and was wondering if there was another way to achieve this. This is a dummed down version of something I am trying to achieve.

import java.util.*;

public class DummyTest{

     public static void main(String []args){
         Map<String, String> someMap = new HashMap<>();
         someMap.put("Key1", "Value1");
         someMap.put("Key2", "Value2");
         someMap.put("Key3", "Value3");

         for (final Map.Entry<String, String> entry : someMap.entrySet()) {

            // I think this is a code smell - Is there a way to avoid this inner
            // loop and still get the same output?
            for (final Map.Entry<String, String> innerLoop : someMap.entrySet())
            {
                if (entry.getValue() != innerLoop.getValue()) {
                    System.out.println(entry.getValue() + " " +
                    innerLoop.getValue());
                }
            }
         }
     }
}

Desired Output

Value2 Value1
Value2 Value3

Value1 Value2
Value1 Value3

Value3 Value2
Value3 Value1

Is the line `Value2 Value3` meant to be a different comparison than `Value3 Value2`? — Jason Sperske, Apr 30 '14 at 20:41
Are you trying to compare every `value` with every other `value`? — merlin2011, Apr 30 '14 at 20:43
Actually I just spoke to somebody about it. It was more about efficiency issue and trying to run away from an `N^2` algorithm — tawheed, Apr 30 '14 at 20:50
See this question http://stackoverflow.com/questions/1741364/efficient-cartesian-product-algorithm — cementblocks, Apr 30 '14 at 20:52
@cementblocks excellent link! :) This one line sums it up perfectly: `The complexity of cartesian product is O(n2), there is no shortcut.` — Jason Sperske, Apr 30 '14 at 20:56
@tawheed After some searching, I managed to find [the question this reminded me of](http://stackoverflow.com/questions/22109043/loop-i-and-j-where-i-j/22109081#comment33539251_22109081). Depending on the order in which you need your data, this is a sort-of shortcut. — MirroredFate, Apr 30 '14 at 21:20

DwB · Accepted Answer · 2014-04-30T21:01:15.713

My solution is equally inefficient, but differently inefficient. Try this:

... setup someMap however you want.

List<String> leftKeyList = new LinkedList<String>();
List<String> rightKeyList = new LinkedList<String>();

leftKeyList.addAll(someMap.keySet());
Collections.sort(leftKeyList); // you seem to want the keys sorted.

for (final String leftKey : leftKeyList)
{
    Set<String> rightKeySet = someMap.keySet());

    rightKeySet.remove(leftKey);

    rightKeyList.clear();
    rightKeyList.addAll(rightKeySet);
    Collections.sort(rightKeySet); // you seem to want these keys sorted as well.

    for (final String rightKey : rightSeyList)
    {
        System.out.println(leftKey + "   " + rightKey);
    }
}

Edit: As noted below, the above is N^2. I believe that any time you have to do something (print above) with one key from a set of keys paired with every other key from the same set, you are stuck with n^2. The inefficiency will not kill you for small sets of keys. 100 or less keys and you should not have terrible performance.

Edit2: The question you pose is interesting in that it mirrors a classic SQL join error that results from joining two tables but not using a join column. Here is an example sql:

select
    a.blah, b.hoot
from
    a, b

Depending on the project details, it may be worth while to store your map in a table then just join it to itself like this (in the example the table name is blammy):

select
   a.key, b.key
from
   blammy a,
   blammy b
where
   a.key != b.key

Thanks, was trying to run away from an `N^2` operation but looks like I have no option — tawheed, Apr 30 '14 at 20:52
This is a great opportunity to take a harder look at your data type now that you know how you are trying to traverse it :) — Jason Sperske, Apr 30 '14 at 20:53

Iterating over 2 maps in java

1 Answers1