Hash Maps for Lookup

Hash maps are the structure engineers reach for when the product question is: given this key, find the associated value quickly. They power caches, indexes, permission checks, joins, counters, deduplication, routing tables, feature flags, and almost every high-throughput service you use.

Lookup as a Product Operation

An array is excellent when order and traversal dominate. A hash map is excellent when direct access by identity dominates. The shift is simple but important: instead of asking the system to scan until it finds the right object, you build a structure that says where that object should be found.

Scenario: Joining Orders With Users

A commerce dashboard receives a list of orders and a list of users. Each order has a userId, and the UI must show the buyer name beside every order. The naive approach scans the users list for every order. That is a nested join hidden inside application code.

type User = { id: string; name: string };
type Order = { id: string; userId: string; total: number };

function attachBuyerNames(orders: Order[], users: User[]) {
  return orders.map((order) => ({
    ...order,
    buyerName: users.find((user) => user.id === order.userId)?.name ?? "Unknown",
  }));
}

If there are o orders and u users, the repeated find operation can become O(o x u). A hash map changes the shape of the work: build userById once in O(u), then attach buyer names in O(o) expected time.

Same Pattern in Java, Python, and JavaScript

The language changes, but the engineering idea stays the same: create a dictionary from the lookup key to the record, then make every repeated lookup direct.

import java.util.*;

record User(String id, String name) {}
record Order(String id, String userId, int total) {}
record OrderView(String id, String buyerName, int total) {}

class OrderJoin {
    static List<OrderView> attachBuyerNames(List<Order> orders, List<User> users) {
        Map<String, User> userById = new HashMap<>();
        for (User user : users) {
            userById.put(user.id(), user);
        }

        List<OrderView> result = new ArrayList<>();
        for (Order order : orders) {
            User user = userById.get(order.userId());
            String buyerName = user == null ? "Unknown" : user.name();
            result.add(new OrderView(order.id(), buyerName, order.total()));
        }
        return result;
    }
}

Key Design Is the Real Skill

Many hash-map bugs are not caused by the map itself. They are caused by bad keys. A key must represent exactly the identity you intend to retrieve. If usernames are case-insensitive, the key must be normalized. If tenant data is isolated, the key must include tenant identity. If an event can be retried, the idempotency key must survive retries.

Hash Map Cost Model

In normal engineering discussions, hash-map insert, get, and delete are treated as expected O(1). The word expected matters. Hashing, collisions, resizing, object overhead, and memory locality affect real performance. You do not need to become a hash-table implementer yet, but you must avoid saying O(1) as if it means free.

When Not to Use a Hash Map

• You need sorted order by key; use a sorted map/tree or sort the keys explicitly.
• You need prefix search; use a trie or an index built for prefixes.
• You need range queries; use prefix sums, trees, segment trees, database indexes, or sorted structures.
• You need stable rendering order and will traverse the whole list every time; an array may be the primary structure.
• The input is tiny, the lookup is rare, and the map makes the code harder to read.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Given an unsorted integer array and a target, return indexes of two numbers whose sum equals the target.
• Given orders with user IDs and users with names, return order views containing the buyer name without nested scanning.
• A payment API may receive the same request multiple times. Return the previous result for the same idempotency key instead of charging again.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class TwoSum {
    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (indexByValue.containsKey(need)) {
                return new int[] { indexByValue.get(need), i };
            }
            // Store after checking so the same index is not reused.
            indexByValue.put(nums[i], i);
        }
        return new int[0];
    }
}

import java.util.*;

record User(String id, String name) {}
record Order(String id, String userId) {}
record OrderView(String orderId, String buyerName) {}

class JoinOrders {
    static List<OrderView> join(List<Order> orders, List<User> users) {
        Map<String, User> userById = new HashMap<>();
        for (User user : users) userById.put(user.id(), user);

        List<OrderView> result = new ArrayList<>();
        for (Order order : orders) {
            User user = userById.get(order.userId());
            result.add(new OrderView(order.id(), user == null ? "Unknown" : user.name()));
        }
        return result;
    }
}

import java.util.*;

record PaymentResult(String status, String chargeId) {}

class PaymentService {
    private final Map<String, PaymentResult> resultByKey = new HashMap<>();

    PaymentResult charge(String idempotencyKey, int amountCents) {
        if (resultByKey.containsKey(idempotencyKey)) {
            return resultByKey.get(idempotencyKey);
        }

        PaymentResult result = performCharge(amountCents);
        resultByKey.put(idempotencyKey, result);
        return result;
    }

    private PaymentResult performCharge(int amountCents) {
        return new PaymentResult("succeeded", UUID.randomUUID().toString());
    }
}

Solved modelWorked Interview Answer

Join orders with users by user ID without scanning the full users list for every order. Build a map from user ID to user record once, then perform expected O(1) lookup for each order. This changes O(orders x users) repeated scans into O(orders + users) expected work.

import java.util.*;

record User(String id, String name) {}
record Order(String id, String userId) {}
record OrderView(String orderId, String buyerName) {}

class JoinOrders {
    static List<OrderView> join(List<Order> orders, List<User> users) {
        Map<String, User> userById = new HashMap<>();
        for (User user : users) userById.put(user.id(), user);

        List<OrderView> result = new ArrayList<>();
        for (Order order : orders) {
            User user = userById.get(order.userId());
            result.add(new OrderView(order.id(), user == null ? "Unknown" : user.name()));
        }
        return result;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Saying O(1) without explaining expected behavior, hashing, equality, or collisions.
• Choosing a key that does not match the product identity rule.
• Forgetting to normalize user-controlled keys such as email, username, or token text.
• Rebuilding the map inside every loop iteration instead of building once.
• Ignoring memory growth, stale values, duplicate keys, or missing records.

Execution guardrailQuick-Start Checklist

• Name the repeated lookup.
• Define the key and value precisely.
• Build the map once before repeated reads.
• Handle missing keys and duplicate keys deliberately.
• State build cost, lookup cost, memory cost, and consistency risk.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Study hash map joins in application code and database hash joins conceptually.
• Review cache key design, invalidation, and tenant isolation.
• Practice Two Sum, group by key, idempotency, and lookup-index problems.