Optimizing Nested Loop Data Matching with a Map in Java

When two tables need to be joined by a common id , many developers write a nested for loop, which has poor performance for large data sets. The article presents a typical scenario: matching a User list with a UserMemo list.

Data classes used in the example:

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

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

Test data is generated with 50,000 User objects and 30,000 UserMemo objects:

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

The naïve nested‑loop implementation iterates over every User and, for each, scans the entire UserMemo list to find a matching userId . With the test data this takes about 26,857 ms.

Adding a break after the first match reduces the time to roughly 10,000 ms, because the inner loop stops early once the needed record is found.

The recommended optimization builds a Map<Long, String> from UserMemo objects (keyed by userId ) before the main loop, then performs a single pass over the User list, looking up the content in O(1) time:

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

    StopWatch stopWatch = new StopWatch();
    stopWatch.start();
    // Build map: userId -> content
    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 业务处理......" + content);
        }
    }

    stopWatch.stop();
    System.out.println("最终耗时" + stopWatch.getTotalTimeMillis());
}

Running this version shows a dramatic speedup (only a few hundred milliseconds), because the overall time complexity drops from O(n × m) to O(n + m), and the hash‑based map provides near‑constant‑time lookups.

The article also explains that, with Java 8’s hash algorithm, collisions are rare, and even in the worst case the lookup degrades to O(n), which is still far better than the original nested loops.