I Interview questions and analysis

1. Today's interview question

What do you know about the traversal method of Map collection?

If there is a large amount of data, which method do you use to traverse?

......

2. Topic analysis

Today's interview topic actually examines our mastery of Map set API methods, especially those related to traversal, because we know that traversal is a common function of set operation. On the whole, today's interview questions are not difficult. We just need to remember a few common traversal methods. However, when we are developing, we may not be very clear about which traversal method is more efficient, so I have done several experiments to compare the advantages and disadvantages of several traversal methods.

II Experimental case

Experiment Description:

In this experiment, I stored 1 million pieces of data in the Map, and then carried out traversal. Except for different traversal methods, the other operations are basically the same. In order to reduce the time consumption of string splicing, I use the StringBuilder method with the highest performance to splice strings, so as to reduce additional interference.

In addition, according to different machines, the results of each experiment are different. Even if the same traversal method is repeated for 5 times, the results of each experiment will be different. Therefore, for the experimental results here, I take the optimal results of many experiments as a reference. When you conduct your own experiments, the results may be different from mine. Please pay attention to this!

1. The first traversal mode

1.1 case code

    public static void main(String[] args) {
        //Create a Map set, in which 100w pieces of initial data are stored
        Map<Integer, String> map = new HashMap<>(16);
        for (int i = 0; i < 1000000; i++) {
            map.put(i, String.valueOf(i));
        }

        //The first traversal method: through map Keyset traverses key and value
        System.out.println("The first traversal method: through Map.keySet ergodic key and value");
        Date now = Date.from(Instant.now());
        for (Integer key : map.keySet()) {
            StringBuilder sb=new StringBuilder();
            //First use map Keyset() gets all key s;
            //Then get the value corresponding to each key
            sb.append(key);
            sb.append(" = ");
            sb.append(map.get(key));
            System.out.println(sb.toString());
        }
        Date end = Date.from(Instant.now());
        System.out.println("time1 = " + (end.getTime() - now.getTime()));       
    }

1.2 implementation results

2. The second traversal mode

2.1 case code

    public static void main(String[] args) {
        //Create a Map set, in which 100w pieces of initial data are stored
        Map<Integer, String> map = new HashMap<>(16);
        for (int i = 0; i < 1000000; i++) {
            map.put(i, String.valueOf(i));
        }

          //The second traversal method: through map Entryset traverses key and value
        System.out.println("The second traversal method: through Map.entrySet ergodic key and value");
        Date now = Date.from(Instant.now());
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            //map.entrySet() returns the Set view of the mapping relationship in this mapping
            StringBuilder sb=new StringBuilder();
            //First use map Keyset() gets all key s;
            //Then get the value corresponding to each key
            sb.append(entry.getKey());
            sb.append(" = ");
            sb.append(entry.getValue());
            System.out.println(sb.toString());
        }
        Date end = Date.from(Instant.now());
        System.out.println("time2 = " + (end.getTime() - now.getTime()));

    }

2.2 implementation results

3. The third traversal mode

3.1 case code

    public static void main(String[] args) {
        //Create a Map set, in which 100w pieces of initial data are stored
        Map<Integer, String> map = new HashMap<>(16);
        for (int i = 0; i < 1000000; i++) {
            map.put(i, String.valueOf(i));
        }

        //The third traversal method: through map The iterator of entryset traverses key and value Recommended, especially for large volume data
        System.out.println("The third traversal method: through Map.entrySet of iterator ergodic key and value");
        Date now = Date.from(Instant.now());
        Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<Integer, String> entry = it.next();
            //map.entrySet() returns the Set view of the mapping relationship in this mapping
            StringBuilder sb=new StringBuilder();
            //First use map Keyset() gets all key s;
            //Then get the value corresponding to each key
            sb.append(entry.getKey());
            sb.append(" = ");
            sb.append(entry.getValue());
            System.out.println(sb.toString());
        }
        Date end = Date.from(Instant.now());
        System.out.println("time3 = " + (end.getTime() - now.getTime()));

    }

3.2 implementation results

4. The fourth traversal mode

4.1 case code

    public static void main(String[] args) {
        //Create a Map set, in which 100w pieces of initial data are stored
        Map<Integer, String> map = new HashMap<>(16);
        for (int i = 0; i < 1000000; i++) {
            map.put(i, String.valueOf(i));
        }

        //The fourth traversal method: through map Values() traverses all value s, but not key s
        System.out.println("The fourth traversal method: through Map.values()Traverse all value，But it cannot be traversed key");
        Date now = Date.from(Instant.now());
        for (String v : map.values()) {
            StringBuilder sb=new StringBuilder();
            //Get each value
            sb.append("value= ");
            sb.append(v);
            System.out.println(sb.toString());
        }
        Date end = Date.from(Instant.now());
        System.out.println("time4 = " + (end.getTime() - now.getTime()));
    }

4.2 implementation results

5. The fifth traversal mode

5.1 case code

    public static void main(String[] args) {
        //Create a Map collection
        Map<Integer, String> map = new HashMap<>(16);
        for (int i = 0; i < 1000000; i++) {
            map.put(i, String.valueOf(i));
        }

        //The fifth traversal method: traversal through the new features of JDK 8
        System.out.println("The fifth traversal method: through Map.values()Traverse all value，But it cannot be traversed key");
        Date now = Date.from(Instant.now());
        map.forEach((key, value)->{
        	StringBuilder sb=new StringBuilder();
            sb.append(key);
            sb.append(" = ");
            sb.append(value);
            System.out.println(sb.toString());
        });
        Date end = Date.from(Instant.now());
        System.out.println("time5 = " + (end.getTime() - now.getTime()));
    }

5.2 implementation results

6. Experimental conclusion

Through multiple execution verification of the above five traversal methods, based on my machine environment, I get the following experimental results:

The first traversal method is through map Keyset: first get the key, and then get the value from the key. The minimum traversal time in 100w data is 8444 milliseconds;

The second traversal method is through map The entryset traversal directly obtains the key and value. The minimum traversal time of 100w data is 8185 milliseconds;

The third traversal method is through map The Iterator of entryset traverses to get the key and value. In this traversal mode, the minimum traversal time of 100w data is 7891 milliseconds;

The fourth traversal method is through map Values() traverses all value s. In this way, the minimum traversal time of 100w data is 8177 milliseconds;

The fifth traversal method is through map. In JDK 8 Foreach () has a new feature of traversal to get all key s and value s. In this way, the minimum traversal time of 100w data is 8442 milliseconds;

From the above experimental conclusions, Yige can give you a roughly correct conclusion. Among the traversal methods of Map collection with large amount of data, the faster traversal method is to use Map The Iterator iterator of entryset performs traversal. The shortest traversal time and longer time-consuming is Map Traversal mode of keyset.

In addition, the traversal efficiency of the Iterator itself is a little higher than that of the for loop. Moreover, if the elements of the Map set are deleted and added in the foreach loop, concurrent modificationexception will be generated. Therefore, if you need to delete the elements in the collection when traversing the collection, you can use the traversal mode of Iterator. The remove() method of Iterator will not cause concurrent exceptions.

To sum up, the five traversal modes are sorted as follows according to their performance:

Map. Iterator iterator of entryset > map values() > Map.entrySet directly gets the key and value > map foreach() > Map. Keyset traversal, first get the key, then get the value

Why is this roughly correct conclusion? Because Yige didn't do a lot of experiments, he didn't dare to say it confidently, map The Iterator iterator method of entryset must be optimal. After all, you should be modest and cautious.

III epilogue

Today's interview question is basically not difficult. You can simply remember the usage of these traversal methods according to the experimental code of Yige, and then roughly know which traversal method is better.