When to use HashMap instead of Loop Part 2

In the previous Article When to use HashMap instead of Loop, I discussed how HashMap could be effective instead of a loop or filter

In this part 2, we discuss a practical use case where HashMap applies.

A Practical Use Case

Given users and tasks, each user has exactly one task. The goal is to group users by tasks.
Imagine there are n users and t tasks, and you need to group users based on the tasks. As an output, every task will have a list of users who are assigned the task.

Input

• users: [ {id: 101, name: "Josh", taskId: 10}]
• tasks: [ {id: 10, title: "Clean House"} ]

Output: { 10 => [ { id: 101, name: 'Josh', taskId: 10 } ] }

Using Arrays

const users = [
    {id: 101, name: "Josh", taskId: 10},
    {id: 102, name: "Mosh", taskId: 10},
    {id: 103, name: "Eli", taskId: 11},
    {id: 104, name: "Jad", taskId: 12},
    {id: 105, name: "Susan", taskId: 12}
];

const tasks = [
    {id: 10, title: "Clean House"},
    {id: 11, title: "Deploy App"},
    {id: 12, title: "Learn Coding"}
]

let usersByTask = new Map();

for(let i = 0; i < users.length; i++){
    let user = users[i];
    for(let j = 0; j < tasks.length; j++){
        let task = tasks[j];
        if(task.id === user.taskId){
            if(usersByTask.has(task.id)){
                usersByTask.get(task.id).push(user);
            }
            else{
                usersByTask.set(task.id, [user]);
            }
            break;
        }
    }
}
console.log(usersByTask)

In the above solution, we explore all the tasks for each user to see if the task belongs to the user. Time complexity is O(n*t) where n and t are numbers of users and tasks, respectively.

Identifying the bottleneck

Why should HashMap be considered?

If you look closely, we are unnecessarily searching for tasks; note we must access all the users, so the first loop cannot be optimized (since we need to check for all the users)

Is there a better way to find which task a user belongs to without visiting all the tasks?

Yes, there is! Represent the tasks as a HashMap instead of an Array. Task id will be the key, and task object will be the value.This means that given a user u, we can find the task that belongs to u without visiting all the tasks.

A Better solution

const users = [
    {id: 101, name: "Josh", taskId: 10},
    {id: 102, name: "Mosh", taskId: 10},
    {id: 103, name: "Eli", taskId: 11},
    {id: 104, name: "Jad", taskId: 12},
    {id: 105, name: "Susan", taskId: 12}
];

const tasks = new Map();
tasks.set(10, {id: 10, title: "Clean House"});
tasks.set(11, {id: 11, title: "Deploy App"});
tasks.set(12, {id: 12, title: "Learn Coding"});

let usersByTask = new Map();
for(let i = 0; i < users.length; i++){
    let user = users[i];
    let taskId = user.taskId;
    if(usersByTask.has(taskId)){
        usersByTask.get(taskId).push(user);
    }
    else{
        usersByTask.set(taskId, [user]);
    }
}
console.log(usersByTask)

Once we identified the bottleneck, the bottleneck was repeatedly searching tasks.

We resolved the bottleneck by storing tasks into a HashMap instead of the Array.

If you are a beginner at HashMap, I encourage you to read and understand the code and be patient.

Conclusion: HashMap is very handy. Once you identify the bottleneck when searching in a list or Array next step is to convert the Array into HashMap for quick access.

Check the first part if you have not.
When to use HashMap instead of Loop

That's it. If you found this helpful, feel free to reach out on Twitter @kaleemniz