Design HashMap - Solution & Explanation

Q: Is Design HashMap easy or hard?

Design HashMap is labeled Easy on LeetCode but still tests core hash table concepts such as hashing, collision handling, and bucket management. The logic is straightforward once you understand how arrays and linked lists combine to implement a hash table.

Q: How to solve Design HashMap in O(1)?

Use a hash table with a deterministic hash function such as key % bucketCount. Map the key to a bucket and handle collisions using either a linked list (separate chaining) or probing (double hashing). Each operation becomes constant-time on average because only a small portion of the structure is accessed.

Q: What is the best approach for Design HashMap?

Separate chaining with an array of buckets is the most common approach. Each bucket stores a linked list of key–value pairs, and a simple hash function maps keys to indices. With a good distribution, put, get, and remove run in O(1) average time and O(n) space for stored elements.

Q: Is Design HashMap asked at Google/Amazon/Meta?

Hash table design problems appear frequently in interviews at companies like Amazon, Google, and Meta because they test understanding of hashing, collision handling, and data structure design. Variants of this question are common in system design and data structure rounds.

Q: What data structure is used in Design HashMap?

The implementation typically uses an array as the primary storage structure combined with either linked lists for separate chaining or probing techniques for open addressing. These structures support fast key indexing and efficient collision resolution.

Q: What is the time complexity of Design HashMap?

Both separate chaining and double hashing provide O(1) average time complexity for put, get, and remove operations. In worst-case scenarios with many collisions, operations can degrade to O(n), but proper hashing and bucket sizing keep this rare in practice.

Q: Design HashMap Python or Java solution approach?

The standard approach in Python or Java uses an array of buckets and stores key–value pairs in linked lists for collisions. Each operation computes the bucket index using a hash function, scans the bucket for the key, and inserts, retrieves, or deletes accordingly in O(1) average time.

EasyArray Hash Table Linked List Design20 min readAsked at: Amazon, Microsoft, Apple +10

Practice this problem

Problem Statement

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:

0 <= key, value <= 10⁶
At most 10⁴ calls will be made to put, get, and remove.

Approach Overview

Problem Overview: Design a HashMap from scratch that supports put(key, value), get(key), and remove(key) without using built-in hash table libraries. Keys are integers, so you control the hashing strategy, collision handling, and storage structure.

Approach 1: Array with Separate Chaining (Average O(1) time, O(n) space)

This design uses a fixed-size array as the main bucket table. A simple hash function (for example key % size) maps each key to a bucket index. Each bucket stores a small linked list of key–value pairs. When two keys hash to the same bucket, the pair is appended to the list instead of overwriting existing data.

Operations are straightforward. For put, compute the index, iterate through the bucket’s list, and update the value if the key already exists; otherwise append a new node. For get or remove, traverse the linked list and match the key. With a well-distributed hash function and enough buckets, the average bucket length stays small, giving O(1) average time per operation and O(n) space for stored elements.

This approach directly combines an array for indexing and a linked list for collision handling. It is the most common educational implementation of a hash map and mirrors how many real hash tables handle collisions internally.

Approach 2: Double Hashing (Average O(1) time, O(n) space)

Double hashing uses open addressing instead of linked structures. The table is a single array where each slot stores one key–value pair. When a collision occurs, a second hash function calculates the step size used to probe the next index. The probing sequence typically follows index = (hash1(key) + i * hash2(key)) % size.

Insertion probes until an empty slot appears. Lookup follows the same probe sequence until the key is found or an unused slot stops the search. Deletion marks a slot as deleted so probing chains remain intact. With good hash functions and a low load factor, the expected complexity remains O(1) average time for put, get, and remove, while space stays O(n).

This approach avoids pointer overhead and keeps memory contiguous, which can improve cache performance. However, it requires careful handling of deleted slots and load factor limits to prevent clustering.

Recommended for interviews: Separate chaining is usually the safest explanation. It is easier to implement, clearly demonstrates collision handling, and maps directly to how production hash tables work. Mentioning double hashing shows deeper understanding of hash table design and probing strategies, which interviewers appreciate for system-level discussions.

Approach 1: Approach 1: Array with Separate Chaining

This method employs an array of linked lists (chaining) to handle collisions. Each index represents a hash code, and if multiple keys hash to the same index, we store them in a linked list at that index. This helps us efficiently manage key collisions.

The above C code initializes a simple hash table with separate chaining using linked lists. Each bucket of our hash table is a linked list to handle collisions.

hashFunction computes the index for a given key.
createNode initializes a new linked list node.
myHashMapPut inserts or updates a key-value pair.
myHashMapGet retrieves the value for a corresponding key or returns -1 if not found.
myHashMapRemove deletes a key and its associated value.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: For each operation (put, get, remove), it is O(n) in the worst case, where n is the number of keys stored at a particular index.
Space Complexity: O(N) where N is the number of distinct keys inserted into the hash map.

Try this approach in the editor →

Approach 2: Approach 2: Double Hashing

Double hashing avoids the clustering problem by calculating two hash functions. If a collision occurs, a second hash determines the step size for probing.

This C solution uses open addressing with double hashing. The second hash function provides an alternative probe sequence in case of collisions.

primaryHash and secondaryHash calculate indices.
myHashMapPut uses the hashes to determine entry positions.
myHashMapGet uses double hashing to locate the desired key.
myHashMapRemove marks an entry as unoccupied upon deletion.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(1) on average for put, get, and remove due to effective hashing; O(n) in worst-case.
Space Complexity: O(N) for storing entries with keys and values.

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Array with Separate Chaining	Time Complexity: For each operation (put, get, remove), it is O(n) in the worst case, where n is the number of keys stored at a particular index. Space Complexity: O(N) where N is the number of distinct keys inserted into the hash map.
Approach 2: Double Hashing	Time Complexity: O(1) on average for put, get, and remove due to effective hashing; O(n) in worst-case. Space Complexity: O(N) for storing entries with keys and values.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Array with Separate Chaining	O(1) average, O(n) worst	O(n)	Most common design for hash maps; easy to implement and explain in interviews
Double Hashing (Open Addressing)	O(1) average, O(n) worst	O(n)	When you want a contiguous array structure without linked lists and controlled probing

Video Solution

Design Hashmap - Leetcode 706 - Python • NeetCodeIO • 73,346 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design HashMap easy or hard?

Design HashMap is labeled Easy on LeetCode but still tests core hash table concepts such as hashing, collision handling, and bucket management. The logic is straightforward once you understand how arrays and linked lists combine to implement a hash table.

How to solve Design HashMap in O(1)?

Use a hash table with a deterministic hash function such as key % bucketCount. Map the key to a bucket and handle collisions using either a linked list (separate chaining) or probing (double hashing). Each operation becomes constant-time on average because only a small portion of the structure is accessed.

What is the best approach for Design HashMap?

Separate chaining with an array of buckets is the most common approach. Each bucket stores a linked list of key–value pairs, and a simple hash function maps keys to indices. With a good distribution, put, get, and remove run in O(1) average time and O(n) space for stored elements.

Is Design HashMap asked at Google/Amazon/Meta?

Hash table design problems appear frequently in interviews at companies like Amazon, Google, and Meta because they test understanding of hashing, collision handling, and data structure design. Variants of this question are common in system design and data structure rounds.

What data structure is used in Design HashMap?

The implementation typically uses an array as the primary storage structure combined with either linked lists for separate chaining or probing techniques for open addressing. These structures support fast key indexing and efficient collision resolution.

What is the time complexity of Design HashMap?

Both separate chaining and double hashing provide O(1) average time complexity for put, get, and remove operations. In worst-case scenarios with many collisions, operations can degrade to O(n), but proper hashing and bucket sizing keep this rare in practice.

Design HashMap Python or Java solution approach?

The standard approach in Python or Java uses an array of buckets and stores key–value pairs in linked lists for collisions. Each operation computes the bucket index using a hash function, scans the bucket for the key, and inserts, retrieves, or deletes accordingly in O(1) average time.

Ready to solve this problem?

Practice Design HashMap with our built-in code editor and test cases.

Practice on FleetCode

Design HashSet

Design Skiplist

Problem Info

DifficultyEasy

Acceptance66.5%

Approaches3

Reading time20 min

Asked at

Amazon Microsoft Apple Goldman Sachs Meta

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Array with Separate Chaining

Code

Complexity

Approach 2: Approach 2: Double Hashing

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents