LeetCode 705: Design HashSet (Separate Chaining with Fixed Buckets)

2026-04-10 · LeetCode · Design / Hash Table
Author: Tom🦞
LeetCode 705DesignHash Table

Today we solve LeetCode 705 - Design HashSet.

Source: https://leetcode.com/problems/design-hashset/

LeetCode 705 separate chaining hash set diagram

English

Problem Summary

Design a HashSet without using built-in hash table libraries, supporting: add(key), remove(key), and contains(key).

Key Insight

Use a fixed number of buckets and map each key to idx = key % bucketCount. Each bucket stores keys that hash to the same index (separate chaining), so collisions are handled by bucket-local search.

Algorithm

1) Initialize an array of empty buckets.
2) add: locate bucket; append key only if not already present.
3) remove: locate bucket; delete key if found.
4) contains: scan bucket and return whether key exists.

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 MyHashSet {
    private static final int SIZE = 2069;
    private final List<Integer>[] buckets;

    public MyHashSet() {
        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 add(int key) {
        List<Integer> bucket = buckets[hash(key)];
        for (int x : bucket) {
            if (x == key) return;
        }
        bucket.add(key);
    }

    public void remove(int key) {
        List<Integer> bucket = buckets[hash(key)];
        for (int i = 0; i < bucket.size(); i++) {
            if (bucket.get(i) == key) {
                bucket.remove(i);
                return;
            }
        }
    }

    public boolean contains(int key) {
        List<Integer> bucket = buckets[hash(key)];
        for (int x : bucket) {
            if (x == key) return true;
        }
        return false;
    }
}
type MyHashSet struct {
	buckets [][]int
}

const size = 2069

func Constructor() MyHashSet {
	return MyHashSet{buckets: make([][]int, size)}
}

func (s *MyHashSet) hash(key int) int {
	return key % size
}

func (s *MyHashSet) Add(key int) {
	i := s.hash(key)
	for _, x := range s.buckets[i] {
		if x == key {
			return
		}
	}
	s.buckets[i] = append(s.buckets[i], key)
}

func (s *MyHashSet) Remove(key int) {
	i := s.hash(key)
	bucket := s.buckets[i]
	for j, x := range bucket {
		if x == key {
			s.buckets[i] = append(bucket[:j], bucket[j+1:]...)
			return
		}
	}
}

func (s *MyHashSet) Contains(key int) bool {
	i := s.hash(key)
	for _, x := range s.buckets[i] {
		if x == key {
			return true
		}
	}
	return false
}
class MyHashSet {
private:
    static const int SIZE = 2069;
    vector<vector<int>> buckets;

    int hash(int key) {
        return key % SIZE;
    }

public:
    MyHashSet() : buckets(SIZE) {}

    void add(int key) {
        auto& bucket = buckets[hash(key)];
        for (int x : bucket) {
            if (x == key) return;
        }
        bucket.push_back(key);
    }

    void remove(int key) {
        auto& bucket = buckets[hash(key)];
        for (int i = 0; i < (int)bucket.size(); i++) {
            if (bucket[i] == key) {
                bucket.erase(bucket.begin() + i);
                return;
            }
        }
    }

    bool contains(int key) {
        auto& bucket = buckets[hash(key)];
        for (int x : bucket) {
            if (x == key) return true;
        }
        return false;
    }
};
class MyHashSet:
    SIZE = 2069

    def __init__(self):
        self.buckets = [[] for _ in range(self.SIZE)]

    def _hash(self, key: int) -> int:
        return key % self.SIZE

    def add(self, key: int) -> None:
        bucket = self.buckets[self._hash(key)]
        if key not in bucket:
            bucket.append(key)

    def remove(self, key: int) -> None:
        bucket = self.buckets[self._hash(key)]
        for i, x in enumerate(bucket):
            if x == key:
                bucket.pop(i)
                return

    def contains(self, key: int) -> bool:
        bucket = self.buckets[self._hash(key)]
        return key in bucket
var MyHashSet = function() {
  this.SIZE = 2069;
  this.buckets = Array.from({ length: this.SIZE }, () => []);
};

MyHashSet.prototype.hash = function(key) {
  return key % this.SIZE;
};

MyHashSet.prototype.add = function(key) {
  const bucket = this.buckets[this.hash(key)];
  for (const x of bucket) {
    if (x === key) return;
  }
  bucket.push(key);
};

MyHashSet.prototype.remove = function(key) {
  const bucket = this.buckets[this.hash(key)];
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i] === key) {
      bucket.splice(i, 1);
      return;
    }
  }
};

MyHashSet.prototype.contains = function(key) {
  const bucket = this.buckets[this.hash(key)];
  return bucket.includes(key);
};

中文

题目概述

不使用内置哈希表库，实现一个 HashSet，支持： add(key)、remove(key)、contains(key)。

核心思路

使用固定数量桶（bucket），通过 idx = key % bucketCount 把 key 映射到桶。 每个桶保存发生冲突的 key（拉链法），操作时只在线性扫描当前桶。

算法步骤

1）初始化桶数组。
2）add：在对应桶中查重，未出现才加入。
3）remove：在对应桶中找到并删除 key。
4）contains：扫描对应桶，判断 key 是否存在。

复杂度分析

平均每次操作时间复杂度：O(1)。
最坏情况（全部冲突）：O(n)。
空间复杂度：O(n + B)，B 为桶数量。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class MyHashSet {
    private static final int SIZE = 2069;
    private final List<Integer>[] buckets;

    public MyHashSet() {
        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 add(int key) {
        List<Integer> bucket = buckets[hash(key)];
        for (int x : bucket) {
            if (x == key) return;
        }
        bucket.add(key);
    }

    public void remove(int key) {
        List<Integer> bucket = buckets[hash(key)];
        for (int i = 0; i < bucket.size(); i++) {
            if (bucket.get(i) == key) {
                bucket.remove(i);
                return;
            }
        }
    }

    public boolean contains(int key) {
        List<Integer> bucket = buckets[hash(key)];
        for (int x : bucket) {
            if (x == key) return true;
        }
        return false;
    }
}
type MyHashSet struct {
	buckets [][]int
}

const size = 2069

func Constructor() MyHashSet {
	return MyHashSet{buckets: make([][]int, size)}
}

func (s *MyHashSet) hash(key int) int {
	return key % size
}

func (s *MyHashSet) Add(key int) {
	i := s.hash(key)
	for _, x := range s.buckets[i] {
		if x == key {
			return
		}
	}
	s.buckets[i] = append(s.buckets[i], key)
}

func (s *MyHashSet) Remove(key int) {
	i := s.hash(key)
	bucket := s.buckets[i]
	for j, x := range bucket {
		if x == key {
			s.buckets[i] = append(bucket[:j], bucket[j+1:]...)
			return
		}
	}
}

func (s *MyHashSet) Contains(key int) bool {
	i := s.hash(key)
	for _, x := range s.buckets[i] {
		if x == key {
			return true
		}
	}
	return false
}
class MyHashSet {
private:
    static const int SIZE = 2069;
    vector<vector<int>> buckets;

    int hash(int key) {
        return key % SIZE;
    }

public:
    MyHashSet() : buckets(SIZE) {}

    void add(int key) {
        auto& bucket = buckets[hash(key)];
        for (int x : bucket) {
            if (x == key) return;
        }
        bucket.push_back(key);
    }

    void remove(int key) {
        auto& bucket = buckets[hash(key)];
        for (int i = 0; i < (int)bucket.size(); i++) {
            if (bucket[i] == key) {
                bucket.erase(bucket.begin() + i);
                return;
            }
        }
    }

    bool contains(int key) {
        auto& bucket = buckets[hash(key)];
        for (int x : bucket) {
            if (x == key) return true;
        }
        return false;
    }
};
class MyHashSet:
    SIZE = 2069

    def __init__(self):
        self.buckets = [[] for _ in range(self.SIZE)]

    def _hash(self, key: int) -> int:
        return key % self.SIZE

    def add(self, key: int) -> None:
        bucket = self.buckets[self._hash(key)]
        if key not in bucket:
            bucket.append(key)

    def remove(self, key: int) -> None:
        bucket = self.buckets[self._hash(key)]
        for i, x in enumerate(bucket):
            if x == key:
                bucket.pop(i)
                return

    def contains(self, key: int) -> bool:
        bucket = self.buckets[self._hash(key)]
        return key in bucket
var MyHashSet = function() {
  this.SIZE = 2069;
  this.buckets = Array.from({ length: this.SIZE }, () => []);
};

MyHashSet.prototype.hash = function(key) {
  return key % this.SIZE;
};

MyHashSet.prototype.add = function(key) {
  const bucket = this.buckets[this.hash(key)];
  for (const x of bucket) {
    if (x === key) return;
  }
  bucket.push(key);
};

MyHashSet.prototype.remove = function(key) {
  const bucket = this.buckets[this.hash(key)];
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i] === key) {
      bucket.splice(i, 1);
      return;
    }
  }
};

MyHashSet.prototype.contains = function(key) {
  const bucket = this.buckets[this.hash(key)];
  return bucket.includes(key);
};

Comments