Map Iteration and Performance: One Size Does Not Fit All

Riddle me this, Batman!

Question: Given the hypothetical types Foo and Bar, and a Java variable declared as Map<Foo, Bar> map, and a method that performs some operation involving the map’s keys, values, or both: what is the optimal method for iterating over the map?  (And newbies be like, “there’s more than one way to iterate over a map?”)

Answer: It depends.  (And yes, Virginia, there are many ways to iterate over a Map.)

If you’re still reading, my guess is that you may have never considered this question.  And that’s not surprising; the typical introductory Java textbook will more than likely show you exactly one way to iterate over a Map, and hey, if it ain’t broke, don’t fix it, right?  Hold that thought.  By the time you finish this article, you will have seen at least three ways to iterate over a Map, and when faced with a Map iteration problem of your own, you should be able to analyze the problem and discern which method is the most efficient for the problem at hand.

O Map, O Map, How Do I Iterate Over Thee?

Let us count the ways!  Here are the basic algorithms for map iteration.

  1. Iterate over the keys.
    for(Foo foo : map.keySet()) { . . . }
  2. Iterate over the values.
    for(Bar bar : map.values()) { . . . }
  3. Iterate over the entries.
    for(Map.Entry<Foo, Bar> entry : map.entrySet()) { . . . }

What’s the Big O?

If you have studied computer science, you have probably heard of Big-O notation.  Simply put, Big O notation is a way to measure and compare the efficiency of algorithms and is often used by programmers to determine the best algorithm to use for solving a particular problem involving large datasets.

Big-O values are generally expressed in terms of the number of operations, on average, that an algorithm takes to run, given the size n of the dataset that they operate over.  For example, looping through a one-dimensional array of size n would require on the order of n operations, so we would say that its Big-O value is O(n).  Likewise, looping through a two-dimensional array having dimensions (m,n) would require on the order of m*iterations, and since for very large datasets, Big-O treats all constants more or less as equals, this nested loop gets a score of O(n2).

Let’s examine each of the three iteration methods listed above in terms of their Big-O time efficiencies in performing various tasks.  As a reference, we’ll use the Big-O CheatSheet by Eric Rowell in order to help us calculate the Big-O values.

Task 1: Print all the keys

This one seems like a no-brainer.  You are accessing only the keys, so let’s choose algorithm 1 from above.

public void printKeys(Map<Foo, Bar> map) {
  for(Foo foo : map.keySet()) {
    System.out.println(foo);
  }
}

Since all we are doing is iterating over the map’s keys, the Big-O for this method is O(n).

Task 2: Print all the values

This one also is a no-brainer.  You are accessing only the values, so let’s choose algorithm 2.

public void printValues(Map<Foo, Bar> map) {
  for(Bar bar : map.values()) {
    System.out.println(bar);
  }
}

Again this method completes in O(n) time.

Task 3: Print all the key-value pairs

Here’s where things get a little sticky.  If use naive algorithm 1, we get the following:

Naive method:

public void printValuesNaively(Map<Foo, Bar> map) {
  for(Foo foo : map.keySet()) {
    System.out.println(foo + "," + map.get(foo));
  }
}

The downside to this approach is that in addition to iterating through the map at O(n), we are calling the get method within the body of the loop, resulting an additional n get operations.

Now, for a HashMap, this is really not all that bad in terms of Big-O, since the get operation has O(1).  We end up with O(n) for the iteration, plus n* O(1) for the get operations, for a total of O(n) + O(n) = 2O(n) = O(2n) = O(n).  Still, it is not as efficient as it could be, as we’ll see.

However if we have a TreeMap, whose get operation has O(log n), now we end up with O(n) for the iteration, plus n* O(log n) for the get operations, for a total of:
O(n) + n*O(log n) = O(n) + O(n log n) = O(n log n).

Better method:

By using algorithm 3, we can avoid the additional n get operations that were performed in the body of the naive method.

public void printValuesMoreEfficiently(Map<Foo, Bar> map) {
  for(Map.Entry<Foo, Bar> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "," + entry.getValue());
  }
}

As a result, we are back to a simple iteration, for O(n), regardless of map type.

O Map, Where Art Thou?

Now you have seen three basic algorithms for map iteration, and you now know that the choice of iteration algorithm depends primarily on whether you need to access just the keys, just the values, or both.

References

Big-O CheatSheet
The Idiot’s Guide to Big(O) Notation
Java Collections – Performance (Time Complexity) from Information Technology Gems

Code to Interfaces, Not to Implementations

A common mantra of object-oriented development is that one should code to the interface, not the implementation.  But what does it mean?  What does it look like in Java?  And why does it matter?  Let’s explore this mantra in detail and see why it is considered a best practice.

What does it mean?

Quite simply, it means that your code should be “class inclusive” rather than “class exclusive”.  In other words, don’t be a class snob.  When specifying a method parameter or return value — even if you think you know what class you will eventually instantiate or return during your implementation, or what class others are likely to pass in to your method — if that class is one of many implementing a common interface (or extending an abstract class), then it is better to declare the field or variable as an instance of the lowest level interface or abstract class upon whose behaviors your code depends, rather than as an instance of the implementation type.  Think of it like finding the least common denominator when simplifying fractions in math class, or finding the simplest tool needed to perform a certain task.

Here’s a real-world analogy: suppose you’re on vacation, and when you arrive at the hotel, you realize that you’ve forgotten to pack your turbo-charged, battery-operated electric toothbrush with spinning heads, and that you will need to brush your teeth at some point before you return home.  Do you really need to go out and buy another turbo-charged, battery-operated electric toothbrush with spinning heads?  Of course not.  You really just need a toothbrush.  It’s the minimum tool that you need in order to perform the task of brushing your teeth.

What Does it Look Like in Java?

Let’s first take a look at an example of what not to do.  Have you ever had to maintain or review someone else’s code and they did something like this?

public void printWords(ArrayList<String> words) {
  for(String word : words) {
     System.out.println(word);
  }
}

public void printKeys(HashMap<Integer, String> pairs) {
  for(Integer key : pairs.getKeys()) {
    System.out.println(key);
  }
}

Did you immediately get the feeling that the code just didn’t look right?  Did you cringe as soon as you saw it?  Could you smell it?  If you answered “yes”, then you are already well on your way to understanding this basic principle.  If you answered “no”, read on.

Suppose you want to print a list of words that is stored in a LinkedList?  Or print all the keys in a TreeMap?  You can’t use the above methods as written, because a LinkedList is not a descendant of ArrayList, and TreeMap is not a descendant of HashMap.

Now look at the implementations above.  Does the printWords method perform any operations on its parameter that are exclusive to an ArrayList?  Or does printKeys perform any operations on its parameter that are exclusive to a HashMap?  The answer is clearly no in both cases.  Here is a better way to write these methods that is inclusive of more common types:

public void printWords(List<String> words) {
  for(String word : words) {
    System.out.println(word);
  }
}

public void printKeys(Map<Integer, String> pairs) {
  for(Integer key : pairs.getKeys()) {
    System.out.println(key);
  }
}

Toothbrushes Revisited…

To further illustrate this principle, let’s revisit the toothbrush analogy.  The following is a sample class interface and class hierarchy fitting the scenario described above:

public interface Toothbrush {
  void brushTeeth();
}

public interface ElectricToothbrush extends Toothbrush {
  void charge();
}

public interface BatteryPoweredToothbrush 
            extends ElectricToothbrush {
  void replaceBattery();
}

public class BasicToothbrush implements Toothbrush {
  public void brushTeeth() {
    . . .
  }
}

public class TurboChargedBatteryPoweredSpinningToothbrush
            implements ElectricToothbrush {
  public void brushTeeth() {
      . . .
  }
  public void charge() {
      . . .
  }
  public void replaceBattery() {
      . . .
  }
}

And here is a simplistic example showing how one might use the Toothbrush interface and class hierarchy in everyday life and while on vacation.

A Day in the Life…

public class DayInTheLife() {
  public void getUp() {
      . . .
  }
  public void brushYourTeeth(Toothbrush brush) {
      brush.brushTeeth();
  }
  public void takeShower() {
      . . .
  }
  public void writeAwesomeJavaCode(int hours) {
      . . .
  }
  public void eat(Meal meal) {
      . . .
  }
  public void chill(int hours) {
      . . .
  }
  public void sleep(int hours) {
      . . .
  }
  public void doFunStuff(int hours) {
      . . .
  }
  public void buyStuff(Object... obj) {
      . . .
  }
}

Today, a Regular Day…

public class RegularDayAtHome() {
  private Meal breakfast;
  private Meal secondBreakfast;
  private Meal lunch;
  private Meal dinner;
  public RegularDayAtHome(Meal[] meals) {
      //instantiate Meal fields
  }
  public void main() {
      DayInTheLife today = new DayInThLife();
      today.getUp();
      today.takeShower();
      today.eat(breakfast);
      Toothbrush tb = 
          new TurboChargedBatteryPoweredSpinningToothbrush();
      today.brushYourTeeth(tb);
      today.writeAwesomeJavaCode(2);
      today.eat(secondBreakfast);  //hobbits
      today.sleep(1);  //power nap
      today.writeAwesomeJavaCode(3);
      today.buyStuff(lunch);
      today.eat(lunch);
      today.writeAwesomeJavaCode(3);
      today.eat(dinner);
      today.writeAwesomeJavaCode(1);
      today.chill(4);
      today.sleep(8);  //good night
  }
}

Vacation Day!

public class VacationDay() {
  private Meal brunch;
  private Meal dinner;
  public VacationDay(Meal[] meals) {
      //instantiate Meal fields
  }
  public void main() {
      DayInTheLife someday = new DayInThLife();
      someday.getUp();
      someday.takeShower();
      someday.eat(brunch);
      //oops, I forgot my toothbrush
      Toothbrush tb = new BasicToothbrush();
      someday.buyStuff(tb);  //buy a toothbrush
      someday.brushYourTeeth(tb);
      someday.doFunStuff(5);
      someday.buyStuff(souvenirs);
      someday.sleep(3);  //I need a nap!
      someday.doFunStuff(2);
      someday.eat(dinner);
      someday.chill(2);
      someday.sleep(10);  //good night
  }
}

Why does it matter?

Coding to interfaces increases the reusability of your code.  When it comes down to specifying a method parameter, you are primarily interested in its behaviors and its potential use as a parameter to be passed to another method.  Don’t paint yourself into a corner by unnecessarily restricting the classes your methods will accept.

Recap

Learning to consistently code to interfaces is an important part of a developer’s arsenal and is one of many techniques that separate senior developers from junior or entry-level developers. I could write an entire book chapter on this subject, with lots of examples, but I think I’ve hit the main points.  So when designing and writing a piece of code, remember the following:

  • Be inclusive rather than exclusive!
  • Don’t be a class snob!
  • Reusability is king!

Welcome!

Hello, and welcome to Coherent Java!  I started this site in order to share some important lessons in Java development that I have learned over the past fourteen years, and to enhance my own understanding of the Java language.  My goal is to provide a valuable resource for both novice and experienced Java developers.  My vision for Coherent Java is for it to become a place where developers can sharpen each other, just as iron sharpens iron, through the sharing of relevant experiences related to the topics contained herein.

As for what topics and what kinds of articles you can expect to see on Coherent Java, I plan to introduce articles on best practices, design patterns, and Spring, and to keep the articles concise and on point, with just enough coding examples to convey the main idea without leaving too many mysteries for the reader to solve on his/her own.

And although this site centers around software development, I have many other interests that you may see featured here from time to time.  These include Batman, mathematical and logical puzzles, and flash fiction (see my flash fiction blog at Farce Positive).

Best regards,
Kevin Gilmore