Category Archives: data structure

Most efficient way to increment a Map value in Java — Only search the key once

This question may be considered too basic, but is frequently asked in the forums. In this post, I will discuss one way that only searches the key in Map ONCE.

Let’s first look at an example. Say I’m creating a string frequency list, using a Map, where each key is a String that is being counted and the value is an Integer that’s incremented each time a String is added. A straightforward way of achieving it is

int count = map.containsKey(string) ? map.get(string) : 0;
map.put(string, count + 1);

This piece of code runs quite slowly because it contains three potentially expensive operations on a map, namely containsKey(), get(), and put(). Each requires to search the key in the map. Now let’s refactor the code for better performance.

Integer vs MutableInteger vs AtomicInteger

One important reason that we have to invoke three expensive operations is using Integer for counting. In Java, Integer is immutable. It prevents us modifing the integer value after construction. Therefore, to increment a counter, we have to first get the integer from the map, then create another new integer by adding one, and put it back to the map.

To make the counter mutable, there are several ways. One is to simply create your own MutableInteger, like what I showed below.

public class MutableInteger {

  private int val;

  public MutableInteger(int val) {
    this.val = val;

  public int get() {
    return val;

  public void set(int val) {
    this.val = val;

Another way might be using AtomicInteger in Java, which is used in applications such as atomically incremented counters. But the main choice for AtomicInteger is if you want to achieve thread safety with the operations on the integer. Therefore it cannot be used as a replacement for an Integer. Based on this, if thread-safety is not a strong consideration of your project, I won’t recommend using AtomicInteger.

Search the key only once

After using the MutableInteger, we can change the above code to

if (map.containsKey(string)) {
  MutableInteger count = map.get(string);
  count.set(count.get() + 1);
} else {
  map.put(string, new MutableInteger(1));


MutableInteger count = map.get(string); if (count != null) { count.set(count.get() + 1); } else { map.put(string, new MutableInteger(1)); } read more