Boost Java Loop Performance: Replace Nested Loops with Map Lookups

When you need to match data from two lists—such as a User list and a UserMemo list—many developers write nested for loops, which is inefficient for large collections.

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

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

Example test data: 50,000 User objects and 30,000 UserMemo objects are generated with random values.

public static List<User> getUserTestList() {
    List<User> 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<UserMemo> getUserMemoTestList() {
    List<UserMemo> 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;
}

The naïve nested‑loop implementation iterates over every User and, for each, scans the entire UserMemo list to find a matching userId. This results in about 5 × 10⁴ × 3 × 10⁴ ≈ 1.5 billion comparisons, taking roughly 26,857 ms on the test data.

Because each User only needs one matching UserMemo, we can break out of the inner loop once a match is found. Adding a break reduces the runtime to about 10,000 ms, roughly halving the execution time.

A more powerful optimization is to replace the inner loop with a HashMap that stores userId → content pairs. Building the map once (O(n)) allows O(1) lookups for each User, turning the overall complexity from O(n²) to O(n).

public static void main(String[] args) {
    List<User> userTestList = getUserTestList();
    List<UserMemo> userMemoTestList = getUserMemoTestList();
    StopWatch stopWatch = new StopWatch();
    stopWatch.start();
    // Build map for fast lookup
    Map<Long, String> 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 业务处理......" + content);
        }
    }
    stopWatch.stop();
    System.out.println("最终耗时" + stopWatch.getTotalTimeMillis());
}

Running this version shows a dramatic reduction in execution time (the exact figure is displayed in the chart below), confirming that the hashmap lookup is effectively O(1) for most cases.

The reason for this improvement is the change in time complexity: the original double loop performs a linear scan for each element (O(n²)), while the hashmap provides constant‑time access (O(1)) after a single preprocessing pass. In Java 8’s hash implementation, collisions are rare, so the average lookup cost remains near O(1). Only in the pathological case where all keys hash to the same bucket would performance degrade to O(n), which is unlikely in typical applications.