Boost Java Loop Performance: From Nested Loops to Map Lookup

Many developers use two nested for loops to find matching id values between two collections, which is inefficient. This article presents an optimization case for that scenario.

The situation involves two lists: a User list and a UserMemo list. For each User we need to retrieve the corresponding content from UserMemo based on userId and process the data.

Class definitions:

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

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

Simulated data: 50,000 User objects and 30,000 UserMemo objects.

A typical naïve implementation iterates the User list and, for each element, scans the entire UserMemo list to find a matching userId. This results in 5 W × 3 W iterations and takes about 26,857 ms.

If each userId appears only once in UserMemo, adding a break after the match reduces the time to roughly 10,000 ms.

A far better solution is to pre‑process the UserMemo list into a Map<Long, String> (key = userId, value = content) and then perform O(1) lookups while iterating the User list.

public static void main(String[] args) {
    List<User> userTestList = getUserTestList();
    List<UserMemo> userMemoTestList = getUserMemoTestList();
    StopWatch stopWatch = new StopWatch();
    stopWatch.start();
    // Build map from memo list
    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 optimized version drops the execution time to around 1,000 ms, a dramatic improvement.

The reason is the change in time complexity: the nested loops have O(n²) complexity, while the map lookup approach is O(n) overall, with average‑case map access close to O(1) due to hashing.

With Java 8’s hash algorithm, collisions are rare, so the map provides near‑constant‑time retrieval. Only in the pathological case where all keys collide would performance degrade to O(n), which is unlikely in practice.