CODEWITHSUNDEEP
javahashmapiteration
Stephan Rozinsky
Stephan Rozinsky

Reputation: 623

Fastest way to iterate over ordered pairs of HashMap entries

The below code uses O(N^2) time to process all ordered pairs of a HashMap. In this example I can not use another data structure such as a TreeMap so wondering if it is possible to improve the iteration time? Java 8 idioms are welcomed. I thought maybe to use a months filter by condition logic where condition could be expressed using lambda notation as months filter ( (l, r) -> (l < r) ). If data was stored in a sorted ArrayList, then this iteration would take O(N^2 / 2) which is faster by a factor of 2 and also the best-time complexity.

Map<String, Integer> months = new HashMap<String, Integer>();
months.put("January", 1);
months.put("February", 2);
months.put("March", 3);
months.put("April", 4);
months.put("May", 5);
months.put("June", 6);
months.put("July", 7);
months.put("August", 8);
months.put("September", 9);
months.put("October", 10);
months.put("November", 11);
months.put("December", 12);
for (Map.Entry<String, Integer> entry : months.entrySet()) {
    String month = entry.getKey();
    Integer index = entry.getValue();
    for (Map.Entry<String, Integer> entry2 : months.entrySet()) {
        Integer index2 = entry2.getValue();
        if (index < index2) {
            // process ordered pair of months
            String month2 = entry2.getKey();
            System.out.println(month + " " + month2);
        }
    }
}

EDIT: I have found my soluttion - I need to useLinkedHashMap which preserves the order months are inserted that is I can get all pairs with O(N^2 / 2) like if I was using ArrayList.

Upvotes: 0

Views: 499

Answers (1)

Stephen C
Stephen C

Reputation: 718788

The time complexity is identical. Specifically,

O(N2)

and

O(N2 / 2)

are the same complexity class. This is a mathematically provable fact.

It is also true that even though N2 is greater than N2 / 2 ... but this is not the characterization that "Big O" notation is explaining.

The other thing to consider is that cost of sorting the list is often going to be more than your saving of N^2 / 2. Either way, you need to include that cost in your overall calculations.

My gut feeling is that you would be better of implementing the alternatives (in your larger application) and measuring the performance1. You are asking for advice that goes beyond "ordinary" complexity analysis, and that takes us quickly into the realm of behaviours of specific library methods, compilers, etcetera. AFAIK, there is no practical way to get answers that you can rely on ... other than by empirical measurement.

But before you do that, you should profile your application to make sure that you aren't wasting your time optimizing something that has no significant impact on overall performance.

1 - Especially since your latest comments have thrown multi-threaded performance into an already too-complicated problem.

Upvotes: 2

Related Questions