【3.13】LeetCode每日一题· 设计哈希集合

2021年03月13日 13时33分

标签： LeetCode 哈希表

## 题目描述
不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。
	bool contains(key) 返回哈希集合中是否存在这个值 key 。
	void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

#### 示例
	输入：
	["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
	[[], [1], [2], [1], [3], [2], [2], [2], [2]]
	
	输出：
	[null, null, null, true, false, null, true, null, false]
	
	解释：
	MyHashSet myHashSet = new MyHashSet();
	myHashSet.add(1);      // set = [1]
	myHashSet.add(2);      // set = [1, 2]
	myHashSet.contains(1); // 返回 True
	myHashSet.contains(3); // 返回 False ，（未找到）
	myHashSet.add(2);      // set = [1, 2]
	myHashSet.contains(2); // 返回 True
	myHashSet.remove(2);   // set = [1]
	myHashSet.contains(2); // 返回 False ，（已移除）

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/design-hashset/ "题目链接")

## 解题思路
使用链地址法实现。开辟一个长度为**MOD**的指针数组，数组的每个元素相当于链表的表头。对于要插入的值`key`，将其插入到第`key % MOD`个链表的尾部（注意题目要求实现的是集合，因此如果遍历到和key相同的元素，则直接退出函数）。删除、查询也做类似操作即可。在这里

$$\text{hash}(key) = key \quad \text{mod} \quad  MOD,$$

称为**哈希函数**。

为了尽可能减少碰撞，需要选择**MOD**为一个大的素数。在这里选择**MOD=769**能达到较好的时间复杂度和空间复杂度表现。

时间复杂度：$$O(\frac{n}{b})$$，其中$n$为哈希表中的元素数量，$$b$$为链表的数量。由于假设哈希值均匀分布，因此每个链表长度平均为$$\frac{n}{b}$$，即时间复杂度为$$O(\frac{n}{b})$$。

空间复杂度：$$O(n+b)$$

## 代码
	class MyHashSet {
	private:
		struct node{
			int value;
			node* next;
		};

public:
		/** Initialize your data structure here. */
		int MOD;
		vector<node> set;
		MyHashSet() {
			MOD = 769;
			set.resize(MOD);
		}

void add(int key) {
			node* now = new node;
			now->value = key;
			now->next = nullptr;

node* p = &set[key%MOD];
			while(p->next){
				p = p->next;
				if(p->value == key){
					delete now;
					return;
				}
			}
			p->next = now;

}

void remove(int key) {
			node* p = &set[key%MOD];
			while(p->next && p->next->value != key) p = p->next;
			if(p->next){
				p->next = p->next->next;
			}
		}

/** Returns true if this set contains the specified element */
		bool contains(int key) {
			node* p = set[key%MOD].next;
			while(p){
				if(p->value == key){
					return true;
				}
				p = p->next;
			}
			return false;
		}

// void print(int key){
		//     node* p = set[key%MOD].next;
		//     while(p){
		//         printf("%d -> ", p->value);
		//         p = p->next;
		//     }
		//     printf("null\n");
		// }
	};

/**
	 * Your MyHashSet object will be instantiated and called as such:
	 * MyHashSet* obj = new MyHashSet();
	 * obj->add(key);
	 * obj->remove(key);
	 * bool param_3 = obj->contains(key);
	 */

### 用时和内存
> 执行用时：108 ms，在所有 C\++提交中击败了74.50%的用户
> 内存消耗：39.8 MB，在所有 C\++提交中击败了71.84%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.13】LeetCode每日一题· 设计哈希集合

所有评论

暂无评论

新增评论