LeetCode 705：设计哈希集合 Design HashSet
- 2019 年 10 月 7 日
- 笔记
题目：
不使用任何内建的哈希表库设计一个哈希集合
具体地说，你的设计应该包含以下的功能
add(value)：向哈希集合中插入一个值。contains(value)：返回哈希集合中是否存在这个值。remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
Design a HashSet without using any built-in hash table libraries.
To be specific, your design should include these functions:
add(value): Insert a value into the HashSet.contains(value): Return whether the value exists in the HashSet or not.remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.
示例:
MyHashSet hashSet = new MyHashSet(); hashSet.add(1); hashSet.add(2); hashSet.contains(1); // 返回 true hashSet.contains(3); // 返回 false (未找到) hashSet.add(2); hashSet.contains(2); // 返回 true hashSet.remove(2); hashSet.contains(2); // 返回 false (已经被删除)
注意：
- 所有的值都在
[1, 1000000]的范围内。 - 操作的总数目在
[1, 10000]范围内。 - 不要使用内建的哈希集合库。
Note:
- All values will be in the range of
[0, 1000000]. - The number of operations will be in the range of
[1, 10000]. - Please do not use the built-in HashSet library.
解题思路：
题目明确限定了数据大小和数据集大小，都在int整型范围内，所以最简单的解法就是，以一个长度为10000001的布尔类型 数组，索引位置就是数据值大小。True、False代表哈希集合内是否有该数。这应该是最简单的哈希散列函数了：y = x
代码：
Java：
class MyHashSet { private boolean[] hashSet; /** * Initialize your data structure here. */ public MyHashSet() { this.hashSet = new boolean[10000001]; } public void add(int key) { hashSet[key] = true; } public void remove(int key) { hashSet[key] = false; } /** * Returns true if this set contains the specified element */ public boolean contains(int key) { return hashSet[key]; } }
Python：
class MyHashSet: def __init__(self): """ Initialize your data structure here. """ self.hash_set = [False]*1000001 def add(self, key: int) -> None: self.hash_set[key] = True def remove(self, key: int) -> None: self.hash_set[key] = False def contains(self, key: int) -> bool: """ Returns true if this set contains the specified element """ return self.hash_set[key]
