🦄 GroveMap: Simple HashMap

Difficulty: Advanced Tags: hashmap, design, data structures Series: Data Structures I

Problem

In the enchanted grove, magical maps store key-value pairs using a special hashing technique. Your task is to implement a simple HashMap that supports three fundamental operations:

• put(key, value) - Store a key-value pair
• get(key) - Retrieve the value for a given key (return -1 if not found)
• remove(key) - Delete a key-value pair

The HashMap must handle collisions using separate chaining (each bucket contains a list of key-value pairs). Your implementation should return the results of all get operations in order.

Real-World Application

HashMaps are the foundation of countless real-world systems: - Caching systems use hashmaps for O(1) lookups - Databases use hash indexes for fast queries - Compilers use symbol tables (hashmaps) to track variables - Network routers use hashmaps for fast IP address lookups

Understanding how hashmaps work internally is crucial for technical interviews and building efficient systems.

Input

data = {
    'ops': list  # List of operations like [['put',key,val], ['get',key], ['remove',key]]
}

Output

list[int]  # Results of all get operations in order

Constraints

• Number of operations ≤ 50,000
• All keys and values are integers
• Choose a reasonable number of buckets (prime number near expected size)
• Must handle hash collisions properly

Examples

Example 1: Basic Operations

Input:

ops = [
    ['put', 1, 1],
    ['put', 2, 2],
    ['get', 1],
    ['get', 3],
    ['put', 2, 1],  # Update existing key
    ['get', 2],
    ['remove', 2],
    ['get', 2]
]

Output: [1, -1, 1, -1]

Explanation: 1. put(1, 1) - Store key 1 with value 1 2. put(2, 2) - Store key 2 with value 2 3. get(1) → returns 1 4. get(3) → returns -1 (key not found) 5. put(2, 1) - Update key 2 to value 1 6. get(2) → returns 1 (updated value) 7. remove(2) - Delete key 2 8. get(2) → returns -1 (key was removed)

Example 2: Many Keys (Collision Handling)

Input:

ops = [
    ['put', 0, 0],
    ['put', 7, 49],
    ['put', 13, 169],
    ['put', 49, 2401],
    ['get', 0],
    ['get', 7],
    ['get', 13],
    ['get', 49]
]

Output: [0, 49, 169, 2401]

Explanation: Multiple keys may hash to the same bucket (collision). Your separate chaining implementation must correctly store and retrieve all values.

Example 3: Empty HashMap

Input:

ops = [
    ['get', 1],
    ['get', 2],
    ['remove', 3]
]

Output: [-1, -1]

Explanation: Getting from an empty HashMap returns -1. Removing non-existent keys should be handled gracefully.

What You'll Learn

• How hash functions distribute keys across buckets
• Managing collisions with separate chaining (linked lists)
• The trade-off between bucket count and performance
• Why prime numbers are often used for bucket counts

Why This Matters

Technical interviews frequently ask candidates to implement hash tables to verify they understand: - How Python's dict works under the hood - Big O complexity of hash operations - Collision resolution strategies - Memory vs speed trade-offs

Starter Code

def challenge_function(data):
    """
    Implement a simple HashMap with put, get, and remove operations.

    Args:
        data: dict with 'ops' key containing list of operations
              Each operation is [op_type, key, ...] where:
              - ['put', key, value] stores key-value pair
              - ['get', key] retrieves value for key
              - ['remove', key] deletes key-value pair

    Returns:
        list: Results of all get operations in order
    """
    # Your implementation here
    pass