Optimizing Nested Loops in Java with Map and Break

When matching data with the same ID across two collections, many developers use two nested for loops, which leads to poor performance. This article introduces three optimization techniques to speed up the lookup.

Scenario

Two nested for loops have a time complexity of O(n*m). When the data volume is large, the execution time grows dramatically.

Example

Assume two lists: userList and userMemoList . For each User we need to find the matching UserMemo by userId and process its content .

import lombok.Data;
import java.util.*;
import java.util.stream.Collectors;
import org.springframework.util.StringUtils;

@Data
class User {
    private Long userId;
    private String name;
}

@Data
class UserMemo {
    private Long userId;
    private String content;
}

public class NestedLoopOptimization {
    public static List
getUserTestList() {
        List
users = new ArrayList<>();
        for (int i = 1; i <= 50000; i++) {
            User user = new User();
            user.setName(UUID.randomUUID().toString());
            user.setUserId((long) i);
            users.add(user);
        }
        return users;
    }

    public static List
getUserMemoTestList() {
        List
userMemos = new ArrayList<>();
        for (int i = 30000; i >= 1; i--) {
            UserMemo userMemo = new UserMemo();
            userMemo.setContent(UUID.randomUUID().toString());
            userMemo.setUserId((long) i);
            userMemos.add(userMemo);
        }
        return userMemos;
    }
    // ... later code
}

Unoptimized Code

The straightforward implementation uses two nested for loops to match IDs.

public static void nestedLoop(List
userTestList, List
userMemoTestList) {
    for (User user : userTestList) {
        Long userId = user.getUserId();
        for (UserMemo userMemo : userMemoTestList) {
            if (userId.equals(userMemo.getUserId())) {
                String content = userMemo.getContent();
                // System.out.println("..." + content);
            }
        }
    }
}

Execution time: tens of thousands of milliseconds (5 × 10⁴ × 3 × 10⁴ iterations).

Break Optimization

If each userId appears only once in userMemoList , we can break the inner loop after a match.

public static void breakOptimizedLoop(List
userTestList, List
userMemoTestList) {
    for (User user : userTestList) {
        Long userId = user.getUserId();
        for (UserMemo userMemo : userMemoTestList) {
            if (userId.equals(userMemo.getUserId())) {
                String content = userMemo.getContent();
                // System.out.println("..." + content);
                break; // exit inner loop after finding the match
            }
        }
    }
}

Time improves slightly but still requires many iterations.

Map Optimization

By converting userMemoList into a Map<Long, String> , the lookup becomes O(1) and the overall complexity drops to O(n + m).

public static void mapOptimizedLoop(List
userTestList, List
userMemoTestList) {
    Map
contentMap = userMemoTestList.stream()
        .collect(Collectors.toMap(UserMemo::getUserId, UserMemo::getContent));

    for (User user : userTestList) {
        Long userId = user.getUserId();
        String content = contentMap.get(userId);
        if (StringUtils.hasLength(content)) {
            // System.out.println("..." + content);
        }
    }
}

Execution time: usually reduced to a few hundred milliseconds.

Principle

Nested loops have O(n*m) complexity. Using a Map changes the inner lookup to near O(1), resulting in O(n + m) overall. The HashMap.getNode() method performs a constant‑time hash table lookup, with worst‑case O(n) only when many keys collide.

final Node
getNode(int hash, Object key) {
    // ... (omitted)
    if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
        return first; // found node, return directly
    // ... (collision handling omitted)
}

Conclusion

Replacing nested loops with a Map lookup dramatically improves performance, especially for large data sets. The break technique offers a modest gain when each key is unique, while the Map approach provides the most significant speedup.