When you need to call a HashMap's get on the same value a few times within a for loop, would it be more efficient to store it in a variable or to make the call two or three times?
5 Answers
Retrieving a value from a HashMap is an O(1) operation, assuming your keys have a reasonable implementation of hashCode().
If you're only retrieving this object a couple of times it may be a micro-optimization (read: premature optimization) to store it in a local variable, but you probably won't notice any difference either way. The real reason to store such an object in a local variable is to avoid duplicating boiler-plate code that checks the key really exists in the map, the value isn't null, etc.
1 Comment
Stephen P
+1 - however, even though a HashMap is O(1) there is unavoidable overhead, as you say "checks the key really exists in the map" and computing the hashcode itself. I've "fixed" other peoples code where they retrieve the value from the map in a loop, and that is (IMO) clearly a reason to store it in a (
final) variable. Another reason I like is being able to name the variable appropriately.Accessing data in HashMap is O(1), so in general it's quite fast. However, if you initiate a variable with the proper value from the HashMap it would be a little bit faster. If you are accessing HashMap with some key, firstly hashCode method of the key is called. If you call that once - it would be faster.
My experience shows that preparing a variable for such cases is a better solution not only because of performance purposes but also because of refactoring. If it happened you had to change some code, you made one change in HashMap call instead of many in different lines, leaving often one line unchanged (which leads to a bug).
Comments
HashMap get runs in constant time. So from efficiency point of view, it doesn't matter. Although storing the value in a variable is more cleaner.
Comments
Calling hashmap.get() creates an indirection, therefor it's will be slower than a direct variable reference. The fact that hashmap.get() has O(1) complexity has absolutely nothing to do with the answer to this question, because O(1) complexity only means that the execution complexity of the algorithm does not increase with a growing number of elements, but, it does not say anything about how many cpu cycles a run takes, it only states that it's constant. Storing the result in a variable would probably be the most performant.
Comments
I've made a simple test with HashMap<String, String>, where both keys and values are random-generated 64-character strings. It uses 1.000.000 records in the map and goes through each of them in 2 for-loops: First is calling get() once and saving it to variable. Second is calling get() 3 times. This is done in 5 iterations.
Results (in milliseconds):
1 2 3 4 5 avg
Store in a variable: 125 126 103 104 102 | 112
Call 3 times: 151 135 137 134 152 | 142
So, for this configuration (map of string-string), calling get() once and storing result in a variable is more effective.
Code of the test:
ArrayList<String> keys;
HashMap<String, String> data;
void run() {
generateData(1_000_000);
long start, end;
for (int i = 0; i < 5; ++i) {
start = System.nanoTime();
for (String key : keys) {
String value = data.get(key);
}
end = System.nanoTime();
System.out.println("Store in a variable: " + ((end - start) / 1000 / 1000) + "ms");
start = System.nanoTime();
for (String key : keys) {
data.get(key);
data.get(key);
data.get(key);
}
end = System.nanoTime();
System.out.println("Call 3 times: " + ((end - start) / 1000 / 1000) + "ms");
}
}
void generateData(int size) {
keys = new ArrayList<>(size);
data = new HashMap<>(size);
for (int i = 0; i < size; ++i) {
String key = getRandomString(64);
keys.add(key);
data.put(key, getRandomString(64));
}
}
String getRandomString(int length) {
StringBuilder str = new StringBuilder();
for (int i = 0; i < length; ++i) {
str.append((char) ThreadLocalRandom.current().nextInt(128));
}
return str.toString();
}
final Person accountHolder = accounts.get(acctNumber);