382

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.

Improve this question
2
  • 8
    "hence and exception occurs" - what exception? This won't be from java.util.HashMap... Commented Sep 2, 2010 at 12:06
  • One can simply use map.get(key) in this case. If the map does not contain the key, then it will return null. Commented Feb 1, 2024 at 9:43

12 Answers 12

Reset to default
598

Do you ever store a null value? If not, you can just do:

Foo value = map.get(key); if (value != null) { ... } else { // No such key }

Otherwise, you could just check for existence if you get a null value returned:

Foo value = map.get(key); if (value != null) { ... } else { // Key might be present... if (map.containsKey(key)) { // Okay, there's a key but the value is null } else { // Definitely no such key } }
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

@Samuel: Only when null is a possible value. If you definitely don't have null values in the map, just get is fine, and avoids doing two look-ups when you need the value as well.
Although this is probably clearer as an example, you could also write if(value!=null || map.containsKey(key)) for the second part. At least if you want to do the same thing either way -- no repeated code. It'll work due to short circuiting.
78

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 :

Improve this answer

4 Comments

What is the point in showing one specific implementation of these methods?
To explain that in most cases, checking that the key exists will take about the same time than getting the value. So it won't optimize anything to check the key actually exists before getting the value. I know it's a generalization but it can help to understand.
A good link is grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/… (OpenJDK is very strongly derived from the Sun code) and it seems that I'm wrong. I was comparing the version for Java5 with Java6; they work differently in this area (but both are correct, as are the snippets you posted).
As pointed out in the accepted answer, this snawer is plain wrong. Of course you DO gain something by checking for key existance ofer comparing values - you can differentiate non-existing keys from keys that exist but are mapped to null as a value.
59

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.

Improve this answer

3 Comments

Yeah. Or subclass the HashMap to prevent storing null alltogether.
1+ for primitive types as value unnecessary cast is not required using this answer
It is also more fluent to write .containsKey() than check for null. We should worry more about being easy to read, which saves developers time, than about some minor optimization, in most cases. At least not optimize before it becomes necessary.
30

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.

Improve this answer

Comments

9

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.

Improve this answer

Comments

6

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! 👍

Improve this answer

2 Comments

Did you try this code?. Does two add() work?
@Yahya It dosen't work since computeifAbsent returns a boolean.
3 
if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))
Improve this answer

Comments

1

Since java 1.8, you can simply use:

var item = mapObject.getOrDefault(key, null); if(item != null)
Improve this answer

Comments

0

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

Improve this answer

Comments

0
  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.
Improve this answer

Comments

0

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.

Improve this answer

Comments

0

If the map does not contains the key we are looking for, map.get(key) will return null. The below code block will return Key : null

 Map<String,String> map = new HashMap<>(); map.put("a","A"); System.out.println("Key : " +map.get("b"));
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.