HashMap traversal methods and performance analysis!

With the release of the JDK 1.8 Streams API, HashMap has more ways to traverse, but which way to traverse should you choose? Instead, it became a problem.

This paper starts with the traversal method of HashMap, and then analyzes the advantages and disadvantages of various traversal methods of HashMap from the aspects of performance, principle and security. The main content of this paper is as follows:

A HashMap traversal

HashMap traversal can be divided into the following four categories from a large perspective:

1. Iterator traversal;
2. For Each traversal;
3. Lambda expression traversal (JDK 1.8+);
4. Streams API traversal (JDK 1.8+).

However, each type has different implementation modes, so specific traversal modes can be divided into the following seven:

1. Iterator Iterator EntrySet traversal;
2. Iterator KeySet Iterator KeySet
3. Traversal using For Each EntrySet;
4. Traversal using For Each KeySet;
5. Traversal using Lambda expressions;
6. Use Streams API for single-threaded traversal;
7. Use Streams API for multi-threaded traversal.

Let’s look at the implementation code for each traversal.

1. EntrySet iterator

public class HashMapTest {
    public static void main(String[] args) {
        // Create and assign a HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1."Java");
        map.put(2."JDK");
        map.put(3."Spring Framework");
        map.put(4."MyBatis framework");
        map.put(5."Java Chinese Community");
        / / traverse
        Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()) { Map.Entry<Integer, String> entry = iterator.next(); System.out.println(entry.getKey()); System.out.println(entry.getValue()); }}}Copy the code

The execution results of the above programs are as follows:

1

Java

2

JDK

3

Spring Framework

4

MyBatis framework

5

Java Chinese Community

2. Iterator KeySet

public class HashMapTest {
    public static void main(String[] args) {
        // Create and assign a HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1."Java");
        map.put(2."JDK");
        map.put(3."Spring Framework");
        map.put(4."MyBatis framework");
        map.put(5."Java Chinese Community");
        / / traverse
        Iterator<Integer> iterator = map.keySet().iterator();
        while(iterator.hasNext()) { Integer key = iterator.next(); System.out.println(key); System.out.println(map.get(key)); }}}Copy the code

The execution results of the above programs are as follows:

1

Java

2

JDK

3

Spring Framework

4

MyBatis framework

5

Java Chinese Community

3.ForEach EntrySet

public class HashMapTest {
    public static void main(String[] args) {
        // Create and assign a HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1."Java");
        map.put(2."JDK");
        map.put(3."Spring Framework");
        map.put(4."MyBatis framework");
        map.put(5."Java Chinese Community");
        / / traverse
        for(Map.Entry<Integer, String> entry : map.entrySet()) { System.out.println(entry.getKey()); System.out.println(entry.getValue()); }}}Copy the code

The execution results of the above programs are as follows:

1

Java

2

JDK

3

Spring Framework

4

MyBatis framework

5

Java Chinese Community

4.ForEach KeySet

public class HashMapTest {
    public static void main(String[] args) {
        // Create and assign a HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1."Java");
        map.put(2."JDK");
        map.put(3."Spring Framework");
        map.put(4."MyBatis framework");
        map.put(5."Java Chinese Community");
        / / traverse
        for(Integer key : map.keySet()) { System.out.println(key); System.out.println(map.get(key)); }}}Copy the code

The execution results of the above programs are as follows:

1

Java

2

JDK

3

Spring Framework

4

MyBatis framework

5

Java Chinese Community

5.Lambda

public class HashMapTest {
    public static void main(String[] args) {
        // Create and assign a HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1."Java");
        map.put(2."JDK");
        map.put(3."Spring Framework");
        map.put(4."MyBatis framework");
        map.put(5."Java Chinese Community");
        / / traversemap.forEach((key, value) -> { System.out.println(key); System.out.println(value); }); }}Copy the code

The execution results of the above programs are as follows:

1

Java

2

JDK

3

Spring Framework

4

MyBatis framework

5

Java Chinese Community

6.Streams API single thread

public class HashMapTest {
    public static void main(String[] args) {
        // Create and assign a HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1."Java");
        map.put(2."JDK");
        map.put(3."Spring Framework");
        map.put(4."MyBatis framework");
        map.put(5."Java Chinese Community");
        / / traversemap.entrySet().stream().forEach((entry) -> { System.out.println(entry.getKey()); System.out.println(entry.getValue()); }); }}Copy the code

The execution results of the above programs are as follows:

1

Java

2

JDK

3

Spring Framework

4

MyBatis framework

5

Java Chinese Community

7.Streams API multithreading

public class HashMapTest {
    public static void main(String[] args) {
        // Create and assign a HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1."Java");
        map.put(2."JDK");
        map.put(3."Spring Framework");
        map.put(4."MyBatis framework");
        map.put(5."Java Chinese Community");
        / / traversemap.entrySet().parallelStream().forEach((entry) -> { System.out.println(entry.getKey()); System.out.println(entry.getValue()); }); }}Copy the code

The execution results of the above programs are as follows:

4

MyBatis framework

5

Java Chinese Community

1

Java

2

JDK

3

Spring Framework

The performance test

Next, we use JMH (Java Microbenchmark Harness) to test the performance of these 7 cycles.

First, we’ll import the JMH framework and add the following configuration to the POM.xml file:

<! -- https://mvnrepository.com/artifact/org.openjdk.jmh/jmh-core -->
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-core</artifactId>
    <version>1.23</version>
</dependency>
<! -- https://mvnrepository.com/artifact/org.openjdk.jmh/jmh-generator-annprocess -->
<dependency>
    <groupId>org.openjdk.jmh</groupId>
    <artifactId>jmh-generator-annprocess</artifactId>
    <version>1.23</version>
    <scope>provided</scope>
</dependency>
Copy the code

Then write the test code as follows:

@BenchmarkMode(Mode.AverageTime) // Test completion time
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 2, time = 1, timeUnit = TimeUnit.SECONDS) // Preheat 2 rounds, 1s each time
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS) // Test 5 rounds, 1s each time
@Fork(1) // start 1 thread
@State(Scope.Thread) // One instance per test thread
public class HashMapCycleTest {
    static Map<Integer, String> map = new HashMap() {{
        // Add data
        for (int i = 0; i < 100; i++) {
            put(i, "val:"+ i); }}};public static void main(String[] args) throws RunnerException {
        // Start the benchmark
        Options opt = new OptionsBuilder()
                .include(HashMapCycle.class.getSimpleName()) // The test class to import
                .output("/Users/admin/Desktop/jmh-map.log") // Output test result file
                .build();
        new Runner(opt).run(); // Execute the test
    }

    @Benchmark
    public void entrySet(a) {
        / / traverse
        Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()) { Map.Entry<Integer, String> entry = iterator.next(); Integer k = entry.getKey(); String v = entry.getValue(); }}@Benchmark
    public void forEachEntrySet(a) {
        / / traverse
        for(Map.Entry<Integer, String> entry : map.entrySet()) { Integer k = entry.getKey(); String v = entry.getValue(); }}@Benchmark
    public void keySet(a) {
        / / traverse
        Iterator<Integer> iterator = map.keySet().iterator();
        while(iterator.hasNext()) { Integer k = iterator.next(); String v = map.get(k); }}@Benchmark
    public void forEachKeySet(a) {
        / / traverse
        for(Integer key : map.keySet()) { Integer k = key; String v = map.get(k); }}@Benchmark
    public void lambda(a) {
        / / traverse
        map.forEach((key, value) -> {
            Integer k = key;
            String v = map.get(k);
        });
    }

    @Benchmark
    public void streamApi(a) {
        // single thread traversal
        map.entrySet().stream().forEach((entry) -> {
            Integer k = entry.getKey();
            String v = entry.getValue();
        });
    }

    public void parallelStreamApi(a) {
        // multithreaded traversalmap.entrySet().parallelStream().forEach((entry) -> { Integer k = entry.getKey(); String v = entry.getValue(); }); }}Copy the code

All methods with the @benchmark annotation will be tested. ParallelStream is the best multithreaded version of the method, so we will not test it. The other 6 methods are tested as follows:

The Score column represents the average execution time, and the ± symbol represents the error. As you can see from the above results, lambda expressions have similar performance to the two entrysets and are the fastest to execute, followed by stream and then the two keysets.

Note: The above results are based on test environment: JDK 1.8 / Mac Mini (2018)/Idea 2020.1

conclusion

For performance reasons, we should use lambda or entrySet as much as possible to traverse the Map collection.

Bytecode analysis

To understand the above test results, we need to compile all the traversal code into bytecode via Javac to see why.

After compiling, we use Idea to open the bytecode as follows:

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by Fernflower decompiler)
//

package com.example;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

public class HashMapTest {
    static Map<Integer, String> map = new HashMap() {
        {
            for(int var1 = 0; var1 < 2; ++var1) {
                this.put(var1, "val:"+ var1); }}};public HashMapTest(a) {}public static void main(String[] var0) {
        entrySet();
        keySet();
        forEachEntrySet();
        forEachKeySet();
        lambda();
        streamApi();
        parallelStreamApi();
    }

    public static void entrySet(a) {
        Iterator var0 = map.entrySet().iterator();

        while(var0.hasNext()) { Entry var1 = (Entry)var0.next(); System.out.println(var1.getKey()); System.out.println((String)var1.getValue()); }}public static void keySet(a) {
        Iterator var0 = map.keySet().iterator();

        while(var0.hasNext()) { Integer var1 = (Integer)var0.next(); System.out.println(var1); System.out.println((String)map.get(var1)); }}public static void forEachEntrySet(a) {
        Iterator var0 = map.entrySet().iterator();

        while(var0.hasNext()) { Entry var1 = (Entry)var0.next(); System.out.println(var1.getKey()); System.out.println((String)var1.getValue()); }}public static void forEachKeySet(a) {
        Iterator var0 = map.keySet().iterator();

        while(var0.hasNext()) { Integer var1 = (Integer)var0.next(); System.out.println(var1); System.out.println((String)map.get(var1)); }}public static void lambda(a) {
        map.forEach((var0, var1) -> {
            System.out.println(var0);
            System.out.println(var1);
        });
    }

    public static void streamApi(a) {
        map.entrySet().stream().forEach((var0) -> {
            System.out.println(var0.getKey());
            System.out.println((String)var0.getValue());
        });
    }

    public static void parallelStreamApi(a) { map.entrySet().parallelStream().forEach((var0) -> { System.out.println(var0.getKey()); System.out.println((String)var0.getValue()); }); }}Copy the code

As you can see from the result, except for the Lambda and Streams apis, EntrySet traversals through the iterator loop and for loop end up generating the same code, both of which create an Entry traversal object in the loop, as shown below:

public static void entrySet(a) {
    Iterator var0 = map.entrySet().iterator();
    while(var0.hasNext()) { Entry var1 = (Entry)var0.next(); System.out.println(var1.getKey()); System.out.println((String)var1.getValue()); }}public static void forEachEntrySet(a) {
    Iterator var0 = map.entrySet().iterator();
    while(var0.hasNext()) { Entry var1 = (Entry)var0.next(); System.out.println(var1.getKey()); System.out.println((String)var1.getValue()); }}Copy the code

The KeySet code iterated through iterators and for loops is the same, as shown below:

public static void keySet(a) {
    Iterator var0 = map.keySet().iterator();
    while(var0.hasNext()) { Integer var1 = (Integer)var0.next(); System.out.println(var1); System.out.println((String)map.get(var1)); }}public static void forEachKeySet(a) {
    Iterator var0 = map.keySet().iterator();
    while(var0.hasNext()) { Integer var1 = (Integer)var0.next(); System.out.println(var1); System.out.println((String)map.get(var1)); }}Copy the code

So when we use an iterator or EntrySet for a loop, their performance is the same, because the resulting bytecode is basically the same; Similarly, the two traversals of a KeySet are similar.

Performance analysis

EntrySet performs better than KeySet because the KeySet loops through map.get(key), which iterates through the map collection to find the value of the key. Why use the word “again”? That’s because the Map collection has already been traversed once by the iterator or for loop, so using the map.get(key) query is equivalent to traversing it twice.

Entry

Entry = iterator.next() puts the key and value of the object into the Entry object. Therefore, to obtain key and value values, you do not need to iterate through the Map collection, but only need to take values from the Entry object.
,>

So, EntrySet’s performance is twice as good as KeySet’s, because KeySet loops through the Map collection twice, while EntrySet loops through the Map collection once.

Safety testing

From the above performance test results and principle analysis, I think we should choose which traversal mode, already know, and next we will start from the “security” Angle, to analyze which traversal mode is safer.

We divided the above traversal into four types For testing: iterator mode, For loop mode, Lambda mode and Stream mode. The test code is as follows.

1. Iterator mode

Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, String> entry = iterator.next();
    if (entry.getKey() == 1) {
        / / delete
        System.out.println("del:" + entry.getKey());
        iterator.remove();
    } else {
        System.out.println("show:"+ entry.getKey()); }}Copy the code

The execution results of the above procedures:

show:0

del:1

show:2

Test result: Iterator loop deletes data safely.

2.For loop

for (Map.Entry<Integer, String> entry : map.entrySet()) {
    if (entry.getKey() == 1) {
        / / delete
        System.out.println("del:" + entry.getKey());
        map.remove(entry.getKey());
    } else {
        System.out.println("show:"+ entry.getKey()); }}Copy the code

The execution results of the above procedures:

Test result: Deleting data in the For loop is unsafe.

3. The Lambda method

map.forEach((key, value) -> {
    if (key == 1) {
        System.out.println("del:" + key);
        map.remove(key);
    } else {
        System.out.println("show:"+ key); }});Copy the code

The execution results of the above procedures:

Deleting data in a Lambda loop is unsafe

The correct way to delete a Lambda:

// Delete the map based on the key
map.keySet().removeIf(key -> key == 1);
map.forEach((key, value) -> {
    System.out.println("show:" + key);
});
Copy the code

The execution results of the above procedures:

show:0

show:2

As you can see from the code above, using Lambda’s removeIf first to remove excess data and then looping through it is the correct way to manipulate the collection.

4. The Stream

map.entrySet().stream().forEach((entry) -> {
    if (entry.getKey() == 1) {
        System.out.println("del:" + entry.getKey());
        map.remove(entry.getKey());
    } else {
        System.out.println("show:"+ entry.getKey()); }});Copy the code

The execution results of the above procedures:

Test result: Deleting data from Stream loop is not safe.

The correct way to Stream a loop:

map.entrySet().stream().filter(m -> 1! = m.getKey()).forEach((entry) -> {if (entry.getKey() == 1) {
        System.out.println("del:" + entry.getKey());
    } else {
        System.out.println("show:"+ entry.getKey()); }});Copy the code

The execution results of the above procedures:

show:0

show:2

As you can see from the above code, you can use the filter in the Stream to filter out unwanted data, and iterating through it is also a safe way to operate on the collection.

conclusion

We cannot use the collection map.remove() to remove data in traversal, which is unsafe, but we can use iterator.remove() on iterators to remove data, which is a safe way to remove collections. Similarly, we can use removeIf in Lambda to delete data ahead of time, or use the filter in Stream to filter out the data to be deleted, which is safe. We can also delete data before the for loop, which is thread-safe.

conclusion

In this article, we have described four ways to traverse a HashMap: iterators, for, lambda, and stream, as well as seven specific traversal methods. For overall performance and security, we should try to traverse a HashMap using entrySet, which is safe and efficient.

The last word

Original is not easy, if you think this article is useful to you, please click on a “like”, this is the biggest support and encouragement to the author, thank you.

Reference & acknowledgements

www.javaguides.net/2020/03/5-b…

Follow the public account “Java Chinese community” reply “dry goods”, obtain 50 original dry goods Top list.