Optimizing Nested Loops in Java: From O(N²) to O(N) Using HashMap

The problem scenario is a typical backend task: given a List<User> and a List<UserMemo>, each user must be matched with its memo by userId and processed. The naïve implementation uses a nested for loop, resulting in roughly 5 × 10⁴ × 3 × 10⁴ iterations and a runtime of about 26 seconds.

Code for the data models:

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

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

Test data generation (50 000 users, 30 000 memos):

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;
}

Naïve nested‑loop implementation:

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 业务处理......" + content);
        }
    }
}

Adding a break after the first match cuts the runtime roughly in half (≈ 13 seconds) because the inner loop stops once the matching memo is found.

The most effective optimization is to replace the inner loop with a constant‑time map lookup. By converting the memo list into a Map<Long, String> using Java 8 streams, each user’s memo can be retrieved in O(1) time, reducing total execution time to about 1 second.

public static void main(String[] args) {
    List<User> userTestList = getUserTestList();
    List<UserMemo> userMemoTestList = getUserMemoTestList();
    StopWatch stopWatch = new StopWatch();
    stopWatch.start();
    // Build a map from userId to content
    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());
}

The dramatic speedup stems from the hash‑based lookup’s average O(1) complexity, compared to the O(N) scan performed by the inner loop. Even with occasional hash collisions, performance remains far superior to the quadratic approach.

In summary, for backend Java code that repeatedly matches items across two large collections, converting one collection to a HashMap (or any hash‑based map) and using direct key lookups is a simple yet powerful technique to avoid nested loops and achieve near‑linear runtime.