Using Java, how can I compare every entry in HashMap to every other entry in the same HashMap without duplicating comparisons?

Question

I am currently using 2 for loops to compare all entries but I am getting duplicate comparisons. Because HashMaps aren't ordered, I can't figure out how to eliminate comparisons that have already been made. For example, I have something like:

    for(Entry<String, String> e1: map.entrySet())
    { 
        for(Entry<String, String> e2: map.entrySet())
        {    
          if (e1.getKey() != e2.getKey())
            {
           //compare e1.getValue() to e2.getValue() 
            }
        }
     }

The problem with this is that the first entry will be compared to the second entry and then the third entry and so on. But then the second entry will again be compared to the first entry and so on. And then the third entry will be compared to the first entry, then the second entry, then the 4th entry, etc. Is there a better way to iterate through HashMaps to avoid doing duplicate comparisons?

Additional information:

To be more specific and hopefully answer your questions, the HashMap I have is storing file names (the keys) and file contents (the values) - just text files. The HashMap has been populated by traversing a directory that contains the files I will want to compare. Then what I am doing is running pairs of files through some algorithms to determine the similarity between each pair of files. I do not need to compare file 1 to file 2, and then file 2 to file 1 again, as I only need the 2 files to be compared once. But I do need every file to be compared to every other file once. I am brand new to working with HashMaps. agim’s answer below might just work for my purposes. But I will also try to wrap my brain around both Evgeniy Dorofeev and Peter Lawrey's solutions below. I hope this helps to explain things better.

Solution 1

If you are not careful, the cost of eliminating duplicates could higher than the cost of redundant comparisons for the keys at least.

You can order the keys using System.identityHashCode(x)

for(Map.Entry<Key, Value> entry1: map.entrySet()) {
   Key key1 = entry1.getKey();
   int hash1 = System.identityHashCode(key1);
   Value value1 = entry1.getValue();
   for(Map.Entry<Key, Value> entry2: map.entrySet()) {
       Key key2 = entry2.getKey();
       if (key1 > System.identityHashCode(key2)) continue;

       Value value2 = entry1.getValue();
       // compare value1 and value2;
   }
}

Solution 2

How about this solution:

String[] values = map.values().toArray(new String[map.size()]);
for (int i = 0; i < values.length; i++) {
  for (int j = i+1; j<values.length; j++) {
    if (values[i].equals(values[j])) {
      // ...
    }
  }
}

Solution 3

Try

    HashMap<Object, Object> map = new HashMap<>();
    Iterator<Entry<Object, Object>> i = map.entrySet().iterator();
    while (i.hasNext()) {
        Entry next = i.next();
        i.remove();
        for (Entry e : map.entrySet()) {
            e.equals(next);
        }
    }

Note that there is no sense comparing keys in a HashMap they are always not equal. That is we could iterate / compare values only

Comments

[Lani1234]

This solution would work for me. If I were to also create an array to hold the keys, would the keys be stored in its array in the same order as the values are stored in its array?

[user949300]

+1. Classic and simple. You could also use an ArrayList (instead of the String[]). i.e. ArrayList values = new ArrayList(map.values); and then use size and get instead of length and [].

[user949300]

@Peter - I think there's a typo in line 7. Shouldn't it be if (hash1 > System.identityHashcode(key2)) ????

[Vishy]

@user949300 Thank you. It should be identityHashCode

[Lani1234]

@Peter - And line 6 should be Key key2 = entry2.getKey();, right? I like this solution more and more, the more times I read it through.

[Vishy]

@user1665884 Thank you. There is a very small risk that two objects have the same key, but I assume this doesn't matter too much.

[Nikhil PV]

should value of value2 = entry1.getValue(); be value2 = entry2.getValue(); ?

[Stephen Rauch]

How does this differ from the 5 other, 4 year old solutions?