Map traversal method and performance test in Java

1. Explanation

Regarding the Map traversal method in Java, many articles recommend the use of entrySet, which is considered to be much more efficient than keySet. The reason is: the entrySet method gets the set of all keys and values ​​at once; while the keySet gets only the set of keys. For each key, the value must be searched for in the Map one more time, thus reducing the overall efficiency. So what is the actual situation?

In order to understand the real gap in traversal performance, including the differences in different scenarios such as traversing key+value, traversing key, traversing value, etc., I tried to conduct some comparative tests.

2. Comparative testing

At first, only a simple test was conducted, but the results showed that the performance of keySet was better, which puzzled me. Don't they all say that entrySet is obviously better than keySet? In order to further verify, different test data were used for more detailed comparative testing.

2.1 Test data

2.1.1 HashMap test data

HashMap-1, the size is 1 million, the key and value are both String, the key value is 1, 2, 3...1000000:
Copy the code code as follows:
Map<String, String> map = new HashMap<String, String>();
String key, value;
for (i = 1; i <= num; i++) {
key = "" + i;
value = "value";
map.put(key, value);
}

HashMap-2, the size is 1 million, the key and value are both String, the key value is 50, 100, 150, 200,..., 50000000:
Copy the code code as follows:
Map<String, String> map = new HashMap<String, String>();
String key, value;
for (i = 1; i <= num; i++) {
key = "" + (i * 50);
value = "value";
map.put(key, value);
}

2.1.2 TreeMap test data

TreeMap-1, the size is 1 million, the key and value are both String, the key value is 1, 2, 3...1000000:
Copy the code code as follows:
Map<String, String> map = new TreeMap<String, String>();
String key, value;
for (i = 1; i <= num; i++) {
key = "" + i;
value = "value";
map.put(key, value);
}

TreeMap-2, the size is 1 million, the key and value are both String, the key values ​​are 50, 100, 150, 200,..., 50000000, more discrete:
Copy the code code as follows:
Map<String, String> map = new TreeMap<String, String>();
String key, value;
for (i = 1; i <= num; i++) {
key = "" + (i * 50);
value = "value";
map.put(key, value);
}

2.2 Test scenario

Use various writing methods of keySet, entrySet, and values ​​to test three scenarios: traversing key+value, traversing key, and traversing value.

2.2.1 Traverse key+value

keySet traverses key+value (writing method 1):
Copy the code code as follows:
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
key = iter.next();
value = map.get(key);
}

keySet traverses key+value (writing method 2):
Copy the code code as follows:
for (String key : map.keySet()) {
value = map.get(key);
}

entrySet traverses key+value (writing method 1):
Copy the code code as follows:
Iterator<Entry<String, String>> iter = map.entrySet().iterator();
Entry<String, String> entry;
while (iter.hasNext()) {
entry = iter.next();
key = entry.getKey();
value = entry.getValue();
}

entrySet traverses key+value (writing method 2):
Copy the code code as follows:
for (Entry<String, String> entry: map.entrySet()) {
key = entry.getKey();
value = entry.getValue();
}

2.2.2 Traverse key

keySet traverses key (writing method 1):
Copy the code code as follows:
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
key = iter.next();
}

keySet traverses key (writing method 2):
Copy the code code as follows:
for (String key : map.keySet()) {
}

entrySet traverses key (writing method 1):
Copy the code code as follows:
Iterator<Entry<String, String>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
key = iter.next().getKey();
}

entrySet traverses key (writing method 2):
Copy the code code as follows:
for (Entry<String, String> entry: map.entrySet()) {
key = entry.getKey();
}

2.2.3 Traverse value

keySet traverses value (writing method 1):
Copy the code code as follows:
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
value = map.get(iter.next());
}

keySet traverses value (writing method 2):
Copy the code code as follows:
for (String key : map.keySet()) {
value = map.get(key);
}

entrySet traverses value (writing method 1):
Copy the code code as follows:
Iterator<Entry<String, String>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
value = iter.next().getValue();
}

entrySet traverses value (writing method 2):
Copy the code code as follows:
for (Entry<String, String> entry: map.entrySet()) {
value = entry.getValue();
}

values ​​traverses value (writing method 1):
Copy the code code as follows:
Iterator<String> iter = map.values().iterator();
while (iter.hasNext()) {
value = iter.next();
}

values ​​traverses value (writing method 2):
Copy the code code as follows:
for (String value : map.values()) {
}

2.3 Test results

2.3.1 HashMap test results

2.3.2 TreeMap test results

3. Conclusion

3.1 If you use HashMap

1. When traversing key and value at the same time, the performance difference between keySet and entrySet methods depends on the specific conditions of the key, such as complexity (complex objects), discreteness, conflict rate, etc. In other words, it depends on the cost of looking up value in HashMap. The operation of entrySet to retrieve all keys and values ​​at once has a performance overhead. When this loss is less than the overhead of HashMap looking for value, the performance advantage of entrySet will be reflected. For example, in the above comparison test, when the key is the simplest numerical string, keySet may be more efficient, taking 10% less time than entrySet. Generally speaking, it is recommended to use entrySet. Because when the key is very simple, its performance may be slightly lower than keySet, but it is controllable; as the key becomes more complicated, the advantages of entrySet will be clearly reflected. Of course, we can choose according to the actual situation
2. When only traversing keys, the keySet method is more appropriate, because entrySet also takes out useless values, which wastes performance and space. In the above test results, keySet takes 23% less time than the entrySet method.
3. When only traversing value, using vlaues method is the best choice, entrySet is slightly better than keySet method.
4. Among different traversal writing methods, it is recommended to use the following writing method, which is slightly more efficient:
Copy the code code as follows:
for (String key : map.keySet()) {
value = map.get(key);
}

for (Entry<String, String> entry: map.entrySet()) {
key = entry.getKey();
value = entry.getValue();
}
for (String value : map.values()) {
}

3.2 If you use TreeMap

1. When traversing key and value at the same time, unlike HashMap, the performance of entrySet is much higher than that of keySet. This is determined by the query efficiency of TreeMap. In other words, the cost of searching for value in TreeMap is relatively large, which is significantly higher than the cost of retrieving all keys and values ​​at once from entrySet. Therefore, it is highly recommended to use the entrySet method when traversing a TreeMap.
2. When only traversing keys, the keySet method is more appropriate, because entrySet also takes out useless values, which wastes performance and space. In the above test results, keySet takes 24% less time than the entrySet method.
3. When only traversing value, using the vlaues method is the best choice, and entrySet is also obviously better than the keySet method.
4. Among different traversal writing methods, it is recommended to use the following writing method, which is slightly more efficient:
Copy the code code as follows:
for (String key : map.keySet()) {
value = map.get(key);
}
for (Entry<String, String> entry: map.entrySet()) {
key = entry.getKey();
value = entry.getValue();
}
for (String value : map.values()) {
}