706. Design HashMap

At a Glance

Topic: system-design-coding
Pattern: Bucket array with chaining
Difficulty: Easy
Companies: Amazon, Google, Microsoft, Bloomberg, Apple
Frequency: High
LeetCode: 706

Problem (one-liner)

Implement a hash map supporting put, get, remove for nonnegative keys and positive values without language map primitives for storage.

Recognition Cues

Fixed modulus + collision chaining list per bucket
Rehash optional — small modulus acceptable for problem constraints

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Open addressing — probe sequences — tricky clustering.
Optimal — array of buckets (slice of {key,value} pairs) — simple interview solution.

Optimal Solution

Go

package main

const bucketCount = 997

type pair struct {
	key   int
	value int
}

// MyHashMap API:
// - Constructor()
// - void put(key int, value int)
// - int get(key int)
// - void remove(key int)

type MyHashMap struct {
	buckets [bucketCount][]pair
}

func Constructor() MyHashMap {
	return MyHashMap{}
}

func (hashMap *MyHashMap) Put(key int, value int) {
	bucketIndex := key % bucketCount
	bucket := hashMap.buckets[bucketIndex]
	for index := range bucket {
		if bucket[index].key == key {
			bucket[index].value = value
			hashMap.buckets[bucketIndex] = bucket
			return
		}
	}
	hashMap.buckets[bucketIndex] = append(hashMap.buckets[bucketIndex], pair{key: key, value: value})
}

func (hashMap *MyHashMap) Get(key int) int {
	bucketIndex := key % bucketCount
	for _, entry := range hashMap.buckets[bucketIndex] {
		if entry.key == key {
			return entry.value
		}
	}
	return -1
}

func (hashMap *MyHashMap) Remove(key int) {
	bucketIndex := key % bucketCount
	bucket := hashMap.buckets[bucketIndex]
	for index := range bucket {
		if bucket[index].key == key {
			bucket = append(bucket[:index], bucket[index+1:]...)
			hashMap.buckets[bucketIndex] = bucket
			return
		}
	}
}

JavaScript

const BUCKET_COUNT = 997;

class MyHashMap {
	constructor() {
		this.buckets = Array.from({ length: BUCKET_COUNT }, () => []);
	}

	_hash(key) {
		return key % BUCKET_COUNT;
	}

	put(key, value) {
		const bucket = this.buckets[this._hash(key)];
		for (const entry of bucket) {
			if (entry.key === key) {
				entry.value = value;
				return;
			}
		}
		bucket.push({ key, value });
	}

	get(key) {
		const bucket = this.buckets[this._hash(key)];
		for (const entry of bucket) {
			if (entry.key === key) {
				return entry.value;
			}
		}
		return -1;
	}

	remove(key) {
		const bucket = this.buckets[this._hash(key)];
		const foundIndex = bucket.findIndex((entry) => entry.key === key);
		if (foundIndex >= 0) {
			bucket.splice(foundIndex, 1);
		}
	}
}

Walkthrough

put(1,1) lands in bucket 1 % 997. get(1) scans that short chain. remove(1) splices the pair out.

Invariant: each key appears at most once per bucket list.

Edge Cases

Key 0 and large keys — modulus normalizes
Overwrite same key

Pitfalls

Using key as negative — problem says nonnegative keys; if not, use abs or offset
O(n) per op if all keys collide — choose larger prime or dynamic resize (follow-up)

Variants

Linear probing with tombstones.
Load factor rehashing for production quality.

Mind-Map Tags

#hash-table #separate-chaining #mod-prime #collision-handling