ReviseAlgo Logo

Hash Maps & Sets

HashMap Fundamentals

Master the hashing mechanism, collision resolution strategies (chaining vs open addressing), load factor thresholds, and rehashing.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is a HashMap?

A HashMap (or Hash Table) is an associative data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found in average O(1) time.

Why is it Important?

Before HashMaps, looking up an element in a collection required O(N) linear scans or O(log N) binary searches. HashMaps offer O(1) average-case insertion, deletion, and lookup time by directly converting key identities into memory addresses.

Where is it Used?

  • Web Caches: Storing HTTP page responses indexed by request URL.
  • Symbol Tables: Compilers checking variable definitions and scopes by name.
  • Database Indexing: Resolving primary key lookups.

    • 2. Mental Model: The Post Office Mailboxes

    Imagine a post office sorting room with a wall of mailboxes:

  • When a letter arrives for "Jane Smith", the clerk runs Jane's name through a code machine (the hash function) which outputs the number 3.
  • The clerk walks directly to Box #3 and places the letter inside.
  • When Jane comes to retrieve her mail, the clerk runs her name through the same machine, gets 3, and looks only in Box #3.
  • Collisions: If "John Smith" also hashes to 3, both letters end up in Box #3. The clerk must look through all letters in Box #3 (usually a linked list of envelopes) to find the correct recipient.

    • 3. Core Hashing Concepts

    1. The Hashing Process

    For a key K: 1. Hash Code: The key is converted to an integer: hashCode = hash(K). 2. Compressor: The code is compressed to fit the bucket array capacity M:
    Index = hashCode \pmod M

    2. Collision Resolution

    When two distinct keys map to the same bucket index, we have a collision. There are two primary resolution strategies:

    #### A. Separate Chaining (Open Hashing) Each bucket contains a pointer to a linked list (or chain) of elements. When a collision occurs, the new element is appended to the list.

  • Java 8+ Optimization: If a chain length exceeds 8 and bucket capacity is ≥ 64, Java converts the linked list to a balanced Red-Black Tree to prevent worst-case O(N) lookups, bringing it down to O(log N).

    • #### B. Open Addressing (Closed Hashing) All elements are stored within the bucket array itself. If a collision occurs, we probe subsequent slots according to a sequence:

  • Linear Probing: Inspect the next slot (index + 1) % M. (Can cause clustering).
  • Quadratic Probing: Inspect slots at quadratic intervals (index + i^2) % M.
  • Double Hashing: Probing interval is computed by a second hash function.

    • 3. Load Factor & Rehashing

    The Load Factor (\alpha) represents the ratio of elements N to bucket capacity M:
    \alpha = \frac{N}{M}
  • When \alpha exceeds a threshold (typically 0.75), the map resizes (doubles capacity) and rehashes all keys to their new bucket indices.
  • Rehashing takes O(N) time, but because it happens infrequently, the amortized cost per insertion remains O(1).

    • 4. Visualizing Separate Chaining

    Below is a schematic of a HashMap with separate chaining collision handling:

    5. Real-World Applications

  • Caching & Session Stores: Redis stores session tokens as keys mapping to JSON user profiles.
  • DNS Resolution: Mapping domain names (keys) to IP addresses (values).

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test your structural understanding of hashing:
  • "What happens when two keys return the same hash code in a HashMap?" -> Explain separate chaining and the Red-Black tree upgrade in Java.
  • "Why should keys be immutable?" -> If a key's properties change after insertion, its hashCode() changes. Searching for it will hash to a different bucket index, making the value un-retrievable.

    • Common Mistakes

    Warning: 1. Worst-Case Complexity Fallback: Assuming HashMap lookups are always O(1). If the hash function is poorly written (e.g., always returning 1), all keys collide in a single bucket, degrading lookups to O(N).
    > 2. Modifying Map Keys: Modifying properties of an object used as a map key (like changing a field in a custom User class key) will break bucket lookups.

    7. Summary

  • Complexity: Average time is O(1) for operations; space complexity is O(N).
  • Collisions: Managed by separate chaining (linked list/tree) or open addressing (probing).
  • Load Factor: Trigger for rehashing (resizing), typically when capacity is 75\% full.
  • Immutable Keys: Crucial to maintain constant hash code values.

    • 8. Quiz

    Question 1: What is the time complexity of looking up a key in a HashMap in the absolute worst case? Answer: O(N) (or O(log N) in Java 8+ if the chain is converted to a tree). This happens when all elements collide into the exact same bucket.
    Question 2: Why does Java 8 convert linked lists in buckets to balanced trees? Answer: To prevent Denial of Service (DoS) attacks. If an attacker knows the hash function, they can craft thousands of inputs that collide at the same bucket, turning O(1) operations into slow O(N) operations. Trees guarantee a safe O(log N) worst-case limit.
    Question 3: What does the load factor threshold of 0.75 represent? Answer: It is the threshold of capacity occupancy before resizing is triggered. At 75\% capacity, the trade-off between memory waste and collision frequency is balanced optimally.
    Question 4: True or False: If two keys are equal (a.equals(b)), they must have the same hash code. Answer: True. This is the hashCode contract. If two objects are equal, their hash codes must be identical so they resolve to the same bucket index.
    Question 5: Can you use a custom class as a HashMap key without overriding any methods? Answer: Technically yes, but practically no. Without overriding hashCode() and equals(), Java uses object memory references. Two separate instances with identical field values would be treated as completely different keys.