LeetCode 706: Design HashMap (Separate Chaining with Fixed Buckets)
LeetCode 706DesignHash TableToday we solve LeetCode 706 - Design HashMap.
Source: https://leetcode.com/problems/design-hashmap/
English
Problem Summary
Implement a HashMap without using built-in hash table libraries, supporting:
put(key, value), get(key), and remove(key).
Key Insight
Use a fixed number of buckets and map each key to idx = key % bucketCount.
Each bucket keeps a small list of (key, value) pairs (separate chaining), so collisions are handled naturally.
Algorithm
1) Initialize an array of buckets (lists).
2) put: locate the bucket; if key exists update value, otherwise append pair.
3) get: scan bucket and return value if found, else -1.
4) remove: scan bucket and delete matching key pair.
Complexity Analysis
Average time per operation: O(1).
Worst-case per operation (all keys collide): O(n).
Space: O(n + B), where B is bucket count.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class MyHashMap {
private static final int SIZE = 2069;
private final List[] buckets;
public MyHashMap() {
buckets = new ArrayList[SIZE];
for (int i = 0; i < SIZE; i++) buckets[i] = new ArrayList<>();
}
private int hash(int key) {
return key % SIZE;
}
public void put(int key, int value) {
List bucket = buckets[hash(key)];
for (int[] p : bucket) {
if (p[0] == key) {
p[1] = value;
return;
}
}
bucket.add(new int[]{key, value});
}
public int get(int key) {
List bucket = buckets[hash(key)];
for (int[] p : bucket) {
if (p[0] == key) return p[1];
}
return -1;
}
public void remove(int key) {
List bucket = buckets[hash(key)];
for (int i = 0; i < bucket.size(); i++) {
if (bucket.get(i)[0] == key) {
bucket.remove(i);
return;
}
}
}
} type pair struct {
k int
v int
}
type MyHashMap struct {
buckets [][]pair
}
const size = 2069
func Constructor() MyHashMap {
b := make([][]pair, size)
return MyHashMap{buckets: b}
}
func (m *MyHashMap) hash(key int) int {
return key % size
}
func (m *MyHashMap) Put(key int, value int) {
i := m.hash(key)
for j := range m.buckets[i] {
if m.buckets[i][j].k == key {
m.buckets[i][j].v = value
return
}
}
m.buckets[i] = append(m.buckets[i], pair{key, value})
}
func (m *MyHashMap) Get(key int) int {
i := m.hash(key)
for _, p := range m.buckets[i] {
if p.k == key {
return p.v
}
}
return -1
}
func (m *MyHashMap) Remove(key int) {
i := m.hash(key)
bucket := m.buckets[i]
for j := range bucket {
if bucket[j].k == key {
m.buckets[i] = append(bucket[:j], bucket[j+1:]...)
return
}
}
}class MyHashMap {
private:
static const int SIZE = 2069;
vector<vector<pair<int,int>>> buckets;
int hash(int key) {
return key % SIZE;
}
public:
MyHashMap() : buckets(SIZE) {}
void put(int key, int value) {
auto& bucket = buckets[hash(key)];
for (auto& p : bucket) {
if (p.first == key) {
p.second = value;
return;
}
}
bucket.push_back({key, value});
}
int get(int key) {
auto& bucket = buckets[hash(key)];
for (auto& p : bucket) {
if (p.first == key) return p.second;
}
return -1;
}
void remove(int key) {
auto& bucket = buckets[hash(key)];
for (int i = 0; i < (int)bucket.size(); i++) {
if (bucket[i].first == key) {
bucket.erase(bucket.begin() + i);
return;
}
}
}
};class MyHashMap:
SIZE = 2069
def __init__(self):
self.buckets = [[] for _ in range(self.SIZE)]
def _hash(self, key: int) -> int:
return key % self.SIZE
def put(self, key: int, value: int) -> None:
bucket = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key: int) -> int:
bucket = self.buckets[self._hash(key)]
for k, v in bucket:
if k == key:
return v
return -1
def remove(self, key: int) -> None:
bucket = self.buckets[self._hash(key)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket.pop(i)
returnvar MyHashMap = function() {
this.SIZE = 2069;
this.buckets = Array.from({ length: this.SIZE }, () => []);
};
MyHashMap.prototype.hash = function(key) {
return key % this.SIZE;
};
MyHashMap.prototype.put = function(key, value) {
const bucket = this.buckets[this.hash(key)];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value;
return;
}
}
bucket.push([key, value]);
};
MyHashMap.prototype.get = function(key) {
const bucket = this.buckets[this.hash(key)];
for (const [k, v] of bucket) {
if (k === key) return v;
}
return -1;
};
MyHashMap.prototype.remove = function(key) {
const bucket = this.buckets[this.hash(key)];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1);
return;
}
}
};中文
题目概述
不使用内置哈希表库，实现一个 HashMap，支持：
put(key, value)、get(key)、remove(key)。
核心思路
使用固定数量桶（bucket），通过 idx = key % bucketCount 把 key 映射到桶。
每个桶里维护一个键值对列表（拉链法），冲突时就在同一桶内线性查找。
算法步骤
1）初始化桶数组。
2）put：在对应桶中查找 key，存在则更新，不存在则追加。
3）get：扫描桶，找到返回 value，否则返回 -1。
4）remove：扫描桶并删除匹配 key 的键值对。
复杂度分析
平均每次操作时间复杂度：O(1)。
最坏情况（全部冲突）：O(n)。
空间复杂度：O(n + B)，B 为桶数量。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class MyHashMap {
private static final int SIZE = 2069;
private final List[] buckets;
public MyHashMap() {
buckets = new ArrayList[SIZE];
for (int i = 0; i < SIZE; i++) buckets[i] = new ArrayList<>();
}
private int hash(int key) {
return key % SIZE;
}
public void put(int key, int value) {
List bucket = buckets[hash(key)];
for (int[] p : bucket) {
if (p[0] == key) {
p[1] = value;
return;
}
}
bucket.add(new int[]{key, value});
}
public int get(int key) {
List bucket = buckets[hash(key)];
for (int[] p : bucket) {
if (p[0] == key) return p[1];
}
return -1;
}
public void remove(int key) {
List bucket = buckets[hash(key)];
for (int i = 0; i < bucket.size(); i++) {
if (bucket.get(i)[0] == key) {
bucket.remove(i);
return;
}
}
}
} type pair struct {
k int
v int
}
type MyHashMap struct {
buckets [][]pair
}
const size = 2069
func Constructor() MyHashMap {
b := make([][]pair, size)
return MyHashMap{buckets: b}
}
func (m *MyHashMap) hash(key int) int {
return key % size
}
func (m *MyHashMap) Put(key int, value int) {
i := m.hash(key)
for j := range m.buckets[i] {
if m.buckets[i][j].k == key {
m.buckets[i][j].v = value
return
}
}
m.buckets[i] = append(m.buckets[i], pair{key, value})
}
func (m *MyHashMap) Get(key int) int {
i := m.hash(key)
for _, p := range m.buckets[i] {
if p.k == key {
return p.v
}
}
return -1
}
func (m *MyHashMap) Remove(key int) {
i := m.hash(key)
bucket := m.buckets[i]
for j := range bucket {
if bucket[j].k == key {
m.buckets[i] = append(bucket[:j], bucket[j+1:]...)
return
}
}
}class MyHashMap {
private:
static const int SIZE = 2069;
vector<vector<pair<int,int>>> buckets;
int hash(int key) {
return key % SIZE;
}
public:
MyHashMap() : buckets(SIZE) {}
void put(int key, int value) {
auto& bucket = buckets[hash(key)];
for (auto& p : bucket) {
if (p.first == key) {
p.second = value;
return;
}
}
bucket.push_back({key, value});
}
int get(int key) {
auto& bucket = buckets[hash(key)];
for (auto& p : bucket) {
if (p.first == key) return p.second;
}
return -1;
}
void remove(int key) {
auto& bucket = buckets[hash(key)];
for (int i = 0; i < (int)bucket.size(); i++) {
if (bucket[i].first == key) {
bucket.erase(bucket.begin() + i);
return;
}
}
}
};class MyHashMap:
SIZE = 2069
def __init__(self):
self.buckets = [[] for _ in range(self.SIZE)]
def _hash(self, key: int) -> int:
return key % self.SIZE
def put(self, key: int, value: int) -> None:
bucket = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key: int) -> int:
bucket = self.buckets[self._hash(key)]
for k, v in bucket:
if k == key:
return v
return -1
def remove(self, key: int) -> None:
bucket = self.buckets[self._hash(key)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket.pop(i)
returnvar MyHashMap = function() {
this.SIZE = 2069;
this.buckets = Array.from({ length: this.SIZE }, () => []);
};
MyHashMap.prototype.hash = function(key) {
return key % this.SIZE;
};
MyHashMap.prototype.put = function(key, value) {
const bucket = this.buckets[this.hash(key)];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value;
return;
}
}
bucket.push([key, value]);
};
MyHashMap.prototype.get = function(key) {
const bucket = this.buckets[this.hash(key)];
for (const [k, v] of bucket) {
if (k === key) return v;
}
return -1;
};
MyHashMap.prototype.remove = function(key) {
const bucket = this.buckets[this.hash(key)];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1);
return;
}
}
};
Comments