Map traversal methods and performance tests in Java
- 2020-04-01 03:36:53
- OfStack
1. In this paper, the
For traversal of maps in Java, many articles recommend using entrySet, which is considered much more efficient than keySet. The entrySet method gets all the keys and values at once. KeySet only gets the set of keys, and for each key, we need to find the value in the Map once more, thus reducing the overall efficiency. So what's the reality?
To understand the real gaps in traversal performance, including differences in different scenarios such as traversing key+value, traversing key, traversing value, etc., I tried to do some comparative tests.
2. Contrast test
I was puzzled by the fact that keySet performed better after a simple test at first. Isn't it true that entrySet is significantly better than keySet? For further verification, different test data were used for more detailed comparison tests.
2.1 test data
2.1.1 HashMap test data
Hashmap-1, size 1 million, key and value are strings, key values are 1, 2, 3... 1000000:
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, size 1 million, key and value are strings, key values are 50, 100, 150, 200... , 50000000:
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, with size of 1 million, key and value of String, key of 1, 2, 3...... 1000000:
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 strings, the value of key is 50, 100, 150, 200... , 50000000, more discrete:
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 scenarios
Different ways of writing keySet, entrySet, and values are used to test three scenarios: the scenario of traversing key+value, traversing key, and traversing value.
2.2.1 traversal key + value
KeySet traverses key+value (type 1) :
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
key = iter.next();
value = map.get(key);
}
KeySet traverses key+value (type 2) :
for (String key : map.keySet()) {
value = map.get(key);
}
EntrySet traverses key+value (type 1) :
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 (type 2) :
for (Entry<String, String> entry: map.entrySet()) {
key = entry.getKey();
value = entry.getValue();
}
2.2.2 traversal key
KeySet traverses key (method 1) :
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
key = iter.next();
}
KeySet traverses key (type 2) :
for (String key : map.keySet()) {
}
EntrySet traversal key (method 1) :
Iterator<Entry<String, String>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
key = iter.next().getKey();
}
EntrySet traversal key (type 2) :
for (Entry<String, String> entry: map.entrySet()) {
key = entry.getKey();
}
2.2.3 traverse the value
KeySet traverses value (method 1) :
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
value = map.get(iter.next());
}
KeySet traverses value (type 2) :
The same code at the page code block index 5
EntrySet traversal value (type 1) :
Iterator<Entry<String, String>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
value = iter.next().getValue();
}
EntrySet traversal value (method 2) :
for (Entry<String, String> entry: map.entrySet()) {
value = entry.getValue();
}
Values traversal value (type 1) :
Iterator<String> iter = map.values().iterator();
while (iter.hasNext()) {
value = iter.next();
}
Values traversal value (type 2) :
for (String value : map.values()) {
}
2.3 test results
2.3.1 HashMap test results
|
Units: milliseconds |
HashMap-1 |
HashMap-2 |
| keySet traverse key+value (writing 1 ) |
39 |
93 |
| keySet traverse key+value (writing 2 ) |
38 |
87 |
| entrySet traverse key+value (writing 1 ) |
43 |
86 |
| entrySet traverse key+value (writing 2 ) |
43 |
85 |
|
Units: milliseconds |
HashMap-1 |
HashMap-2 |
| keySet traverse key (writing 1 ) |
27 |
65 |
| keySet traverse key (writing 2 ) |
26 |
64 |
| entrySet traverse key (writing 1 ) |
35 |
75 |
| entrySet traverse key (writing 2 ) |
34 |
74 |
|
Units: milliseconds |
HashMap-1 |
HashMap-2 |
| keySet traverse value (writing 1 ) |
38 |
87 |
| keySet traverse value (writing 2 ) |
37 |
87 |
| entrySet traverse value (writing 1 ) |
34 |
61 |
| entrySet traverse value (writing 2 ) |
32 |
62 |
| values traverse value (writing 1 ) |
26 |
48 |
| values traverse value (writing 2 ) |
26 |
48 |
2.3.2 TreeMap test results
|
Units: milliseconds |
TreeMap-1 |
TreeMap-2 |
| keySet traverse key+value (writing 1 ) |
430 |
451 |
| keySet traverse key+value (writing 2 ) |
429 |
450 |
| entrySet traverse key+value (writing 1 ) |
77 |
84 |
| entrySet traverse key+value (writing 2 ) |
70 |
68 |
|
Units: milliseconds |
TreeMap-1 |
TreeMap-2 |
| keySet traverse key (writing 1 ) |
50 |
49 |
| keySet traverse key (writing 2 ) |
49 |
48 |
| entrySet traverse key (writing 1 ) |
66 |
64 |
| entrySet traverse key (writing 2 ) |
65 |
63 |
|
Units: milliseconds |
TreeMap-1 |
TreeMap-2 |
| keySet traverse value (writing 1 ) |
432 |
448 |
| keySet traverse value (writing 2 ) |
430 |
448 |
| entrySet traverse value (writing 1 ) |
62 |
61 |
| entrySet traverse value (writing 2 ) |
62 |
61 |
| values traverse value (writing 1 ) |
46 |
46 |
| values traverse value (writing 2 ) |
45 |
46 |
Conclusion 3.
3.1 if you use a HashMap
1. When traversing key and value at the same time, the performance difference between keySet and entrySet method depends on the specific situation of key, such as complexity (complex object), dispersion, conflict rate, etc. In other words, it depends on the overhead of a HashMap lookup value. An entrySet operation that takes out all keys and values at once has a performance overhead, and when this loss is less than the cost of HashMap lookup value, the performance advantage of entrySet will be realized. For example, in the above comparison test, when the key was the simplest numeric string, the keySet might instead be more efficient, taking 10% less time than the entrySet. EntrySet is generally recommended. Because when the key is simple, its performance may be slightly lower than that of the keySet, but it is manageable; As the key becomes more complex, the advantages of entrySet will be obvious. Of course, we can choose according to the actual situation
2. The keySet method is more appropriate when only traversing the key, because entrySet also takes out unused value, wasting performance and space. In the above test results, keySet took 23% less time than the entrySet method.
3. When traversing only value, the vlaues method is the best choice, and entrySet is slightly better than keySet method.
4. In different traversal writing methods, it is recommended to use the following writing method, which is slightly more efficient:
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. Unlike HashMap, entrySet performs much better than keySet when traversing key and value at the same time. This is determined by the query efficiency of TreeMap, that is, the cost of finding value in TreeMap is higher than that of taking all the keys and values out of entrySet at once. Therefore, the entrySet method is highly recommended when traversing a TreeMap.
2. The keySet method is more appropriate when only traversing the key, because entrySet also takes out unused value, wasting performance and space. In the above test results, keySet took 24% less time than the entrySet method.
3. When traversing only value, vlaues method is the best choice, and entrySet is obviously better than keySet method.
4. In different traversal writing methods, it is recommended to use the following writing method, which is slightly more efficient:
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()) {
}