[java] Key existence check in HashMap

Is checking for key existence in HashMap always necessary?

I have a HashMap with say a 1000 entries and I am looking at improving the efficiency. If the HashMap is being accessed very frequently, then checking for the key existence at every access will lead to a large overhead. Instead if the key is not present and hence an exception occurs, I can catch the exception. (when I know that this will happen rarely). This will reduce accesses to the HashMap by half.

This might not be a good programming practice, but it will help me reduce the number of accesses. Or am I missing something here?

[Update] I do not have null values in the HashMap.

Better way is to use containsKey method of HashMap. Tomorrow somebody will add null to the Map. You should differentiate between key presence and key has null value.

1. If key class is your's make sure the hashCode() and equals() methods implemented.
2. Basically the access to HashMap should be O(1) but with wrong hashCode method implementation it's become O(n), because value with same hash key will stored as Linked list.

I usually use the idiom

Object value = map.get(key);
if (value == null) {
    value = createValue(key);
    map.put(key, value);
}

This means you only hit the map twice if the key is missing

if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))

The Jon Skeet answer addresses well the two scenarios (map with null value and not null value) in an efficient way.

About the number entries and the efficiency concern, I would like add something.

I have a HashMap with say a 1.000 entries and I am looking at improving the efficiency. If the HashMap is being accessed very frequently, then checking for the key existence at every access will lead to a large overhead.

A map with 1.000 entries is not a huge map.
As well as a map with 5.000 or 10.000 entries.
Map are designed to make fast retrieval with such dimensions.

Now, it assumes that hashCode() of the map keys provides a good distribution.

If you may use an Integer as key type, do it.
Its hashCode() method is very efficient since the collisions are not possible for unique int values :

public final class Integer extends Number implements Comparable<Integer> {
    ...
    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }

    public static int hashCode(int value) {
        return value;
    }
    ...
}

If for the key, you have to use another built-in type as String for example that is often used in Map, you may have some collisions but from 1 thousand to some thousands of objects in the Map, you should have very few of it as the String.hashCode() method provides a good distribution.

If you use a custom type, override hashCode() and equals() correctly and ensure overall that hashCode() provides a fair distribution.
You may refer to the item 9 of Java Effective refers it.
Here's a post that details the way.

Do you mean that you've got code like

if(map.containsKey(key)) doSomethingWith(map.get(key))

all over the place ? Then you should simply check whether map.get(key) returned null and that's it. By the way, HashMap doesn't throw exceptions for missing keys, it returns null instead. The only case where containsKey is needed is when you're storing null values, to distinguish between a null value and a missing value, but this is usually considered bad practice.

Just use containsKey() for clarity. It's fast and keeps the code clean and readable. The whole point of HashMaps is that the key lookup is fast, just make sure the hashCode() and equals() are properly implemented.

You can also use the computeIfAbsent() method in the HashMap class.

In the following example, map stores a list of transactions (integers) that are applied to the key (the name of the bank account). To add 2 transactions of 100 and 200 to checking_account you can write:

HashMap<String, ArrayList<Integer>> map = new HashMap<>();
map.computeIfAbsent("checking_account", key -> new ArrayList<>())
   .add(100)
   .add(200);

This way you don't have to check to see if the key checking_account exists or not.

• If it does not exist, one will be created and returned by the lambda expression.
• If it exists, then the value for the key will be returned by computeIfAbsent().

Really elegant!

You won't gain anything by checking that the key exists. This is the code of HashMap:

@Override
public boolean containsKey(Object key) {
    Entry<K, V> m = getEntry(key);
    return m != null;
}

@Override
public V get(Object key) {
    Entry<K, V> m = getEntry(key);
    if (m != null) {
        return m.value;
    }
    return null;
}

Just check if the return value for get() is different from null.

This is the HashMap source code.

Resources :

• HashMap source code Bad one
• HashMap source code Good one