Optimizing Nested Loop Data Matching in Java with HashMap to Reduce Time Complexity

Many developers write nested for loops to find matching IDs between two lists, which is inefficient for large data sets; this article presents a performance‑optimizing case study.

The scenario involves a User list and a UserMemo list, where each UserMemo contains a userId and a content that must be processed for the corresponding User.

Data classes:

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

The naïve nested loop iterates over every User and then over every UserMemo, resulting in about 5 × 10⁴ × 3 × 10⁴ ≈ 1.5 billion comparisons and takes roughly 26 seconds.

Adding a break after finding the matching memo halves the time to about 10 seconds, because the inner loop stops early.

A much better solution is to pre‑process the UserMemo list into a Map<Long, String> (keyed by userId) and then perform O(1) lookups for each user:

public static void main(String[] args) {
    List<User> userTestList = getUserTestList();
    List<UserMemo> userMemoTestList = getUserMemoTestList();

    StopWatch stopWatch = new StopWatch();
    stopWatch.start();
    // Build map: userId -> 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());
}

This approach reduces the total execution time to a few hundred milliseconds, because the hashmap provides near‑constant‑time retrieval (average O(1)).

The dramatic improvement stems from changing the algorithmic complexity from O(n²) to O(n) and leveraging the efficient hash‑based lookup of Java’s HashMap, where collisions are rare under the default JDK 8 hash function.