Design a Hash Map

Design and implement a HashMap data structure that supports put, get, and remove operations with collision handling and dynamic resizing.

What is the Hash Map Problem?

Design and implement a HashMap (Hash Table) data structure that supports put(key, value), get(key), and remove(key) operations. The implementation should handle hash collisions using separate chaining or open addressing, dynamically resize when the load factor exceeds a threshold, and include a well-designed hash function.

In this problem, you’ll design the internal mechanics of a HashMap—balancing the tradeoff between memory usage and search speed.

Problem Overview

Implement a key-value store that provides average $O(1)$ time complexity for insertions, deletions, and lookups.

Core Requirements

Functional Requirements:

Basic Operations: Support put(key, value) (insert or update), get(key) (retrieve), and remove(key) (delete).
Collision Handling: Use separate chaining where each bucket contains a linked list of entries for colliding keys.
Dynamic Resizing: Automatically double capacity and rehash all entries when load factor exceeds 0.75.
Hash Function: Implement a function that uniformly distributes keys to minimize collisions.
Size Tracking: Track the current number of entries to calculate the load factor accurately.
Edge Handling: Gracefully handle non-existent keys and potentially null keys/values.

Non-Functional Requirements:

Average Performance: Operations must run in average O(1) time complexity.
Memory Management: Efficiently manage memory via resizing and proper bucket array management.
Modular OOD: Clear separation of concerns between HashMap, Bucket, Entry, and HashFunction classes.
Extensibility: Easy to swap collision strategies (Strategy Pattern) or hash function implementations.
Robustness: Handle edge cases like empty maps or repeated insertions/deletions accurately.

What’s Expected?

1. System Architecture

The HashMap uses an internal array of “Buckets” to store entries.

2. Key Classes to Design

classDiagram
    class MyHashMap {
        -Bucket[] table
        -int size
        -float loadFactor
        +put(key, value)
        +get(key)
        -rehash()
    }
    
    class Bucket {
        -List~Entry~ entries
        +add(entry)
        +find(key)
        +remove(key)
    }
    
    class Entry {
        -K key
        -V value
    }

    MyHashMap "1" *-- "many" Bucket
    Bucket "1" *-- "many" Entry

System Flow

`Put` and Resize Flow

Key Design Challenges

1. Collision Resolution: Chaining vs. Open Addressing

What happens when two keys hash to index 5?

Solution: Use Separate Chaining. Each index in the array points to a linked list (or balanced tree in modern Java) of entries. This is generally more robust than Open Addressing (probing), especially as the load factor increases.

2. Designing a Good Hash Function

A bad hash function that puts all keys into bucket 0 turns your $O(1)$ HashMap into an $O(N)$ LinkedList.

Solution: Use a combination of the key’s native hashCode() and a supplemental Bit Shifting/XOR “mixer” to ensure that the high-order bits of the hash are distributed into the low-order bits used for indexing.

3. The “Expensive” Resize

Doubling the capacity and moving all items (Rehashing) is an $O(N)$ operation.

Solution: Amortized Analysis. While a single put might be slow during a resize, the average cost over many operations remains $O(1)$. In critical real-time systems, you might use “Incremental Rehashing” (moving a few items on every get/put instead of all at once).

What You’ll Learn

By solving this problem, you’ll master:

✅ Bitwise Operations - Optimizing indices and hash distributions.
✅ Memory Management - Handling dynamic arrays and load factors.
✅ Search Complexity - Balancing time and space tradeoffs.
✅ Data Structure Internals - Understanding how modern libraries (Java HashMap, Python dict) work under the hood.

View Complete Solution & Practice

Ready to see the full implementation? Open the interactive playground to access:

🎯 Step-by-step guidance through the 8-step LLD approach
📊 Interactive UML builder to visualize your design
💻 Complete Code Solutions in Python, Java, C++, TypeScript, JavaScript, C#
🤖 AI-powered review of your design and code

🚀 View Solution in Playground

After mastering the Hash Map, try these similar problems:

LRU Cache - Combining a Map with a Linked List.
Trie (Prefix Tree) - Another specialized key-value structure.
Search Index - Building a reverse-lookup dictionary.