TestForNull Card Performance

Question

Referring to the previous answer to the question about SO, there is a method used called TestForNull. This was my original code before I was told that I can make it more efficient:

My source code:

for (int i = 0; i < temp.length; i++) { if (map.containsKey(temp[i])) map.put(temp[i], map.get(temp[i]) + 1); else map.put(temp[i], 1); 

In this passage, I take three views of the map. I was told that this can only be done in one search, so I decided to find the answer in SO and found the related answer and changed my code to look like this:

Modified Code:

 for (int i = 0; i < temp.length; i++) { Integer value = map.get(temp[i]); if (value != null) map.put(temp[i], value + 1); else map.put(temp[i], 1); } 

Even if it seems better, it looks like two looks at me, not one. I was wondering if there is an implementation that uses only one, and if it can be done without using third-party libraries. If this helps, I use HashMap for my program.

Answer 1

Java 8 added several default methods to the Map interface, which might help, including merge :

 map.merge(temp[i], 1, v -> v + 1); 

And compute :

 map.compute(temp[i], (k, v) -> v == null ? 1 : v + 1); 

HashMap implementations of these methods are properly optimized to efficiently perform only one key search. (Curiously, the same cannot be said for TreeMap .)

Answer 2

@ John Kugelman's answer is the best (as long as you can use java 8).

The first example has the worst case of 3 card calls (in the case of an existing value):

• ContainsKey
• receive
• to place

The second example always has exactly 2 calls (and zero check):

• receive
• to place

So you basically trade containsKey for a zero check.

In a HashMap these operations are approximately constant time, assuming a good distribution of the hash code (and that the distribution works well with the size of the HashMap ). Other Map implementations (e.g. TreeMap ) have log (n) runtimes. Even with HashMap null check will be faster than containsKey , making the second option a winner. However, you are unlikely to have a measurable difference if you have insufficiently distributed hash codes (or this is the only thing your application does) or poorly performing equal checks.