705. 设计哈希集合

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 520 阅读时长 ≈ 2 分钟

考点

  • 哈希表与链表的综合

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MyHashSet {
	private:
		vector<list<int>> hashSet;
		int getHash(int &key) {
			return (key ^ (key >> 16)) % 13331;
		}
	public:
    	//这里必须初始化vector，否则会导致空指针错误
		MyHashSet(): hashSet(13331) {}
		void add(int key) {
			int h = getHash(key);
			for (auto it = hashSet[h].begin(); it != hashSet[h].end(); it++) {
				if (*it == key) return;
			}
			hashSet[h].emplace_front(key);
		}

		void remove(int key) {
			int h = getHash(key);
			for (auto it = hashSet[h].begin(); it != hashSet[h].end(); it++) {
				if (*it == key) {
					hashSet[h].erase(it);
					return;
				}
			}
		}

		bool contains(int key) {
			int h = getHash(key);
			for (auto it = hashSet[h].begin(); it != hashSet[h].end(); it++) {
				if (*it == key) {
					return true;
				}
			}
			return false;
		}
};

思路

C++最原生的哈希表，就是数组，下标即为键

参考Java的HashMap源码，设置一个桶数组，每个下标即为数据的哈希值；下标对应的值为双向链表，用以存储哈希值一样的数据

使用一个非常简陋的办法计算数据的哈希值。在学习字符串哈希的时候提到过，数据求余大质数有利于减少哈希碰撞

最简单的办法就是

数据 % 大质数

考虑到这里的数据是int类型，共32位；可以令高16位与低16位异或，增加混淆度。得到最终的样子

(数据 ^ (数据 >> 16)) % 大质数

如果有位运算的基础，这道题也能使用BitMap位图来处理

题目的需求就是判断元素是否存在，而每种元素只有存在或不存在两种情况

一个int类型是32位，106+1个元素只需要(106+1)/32≈31251长度空间的int数组即可存储所有元素的存在状态

每次元素/32就是数组下标，元素%32即元素对应在该32位中的状态

取余有小技巧，a%2n = a & (2n-1)，只有求余2的幂次才有用哟！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MyHashSet {
	private:
		const static int len = 32;
		int bitMap[31251];
	public:
		MyHashSet(): bitMap{0} {}
		void add(int key) {
			bitMap[key / len] |= 1 << (key & (len - 1));
		}

		void remove(int key) {
			bitMap[key / len] &= ~(1 << (key & (len - 1)));
		}

		bool contains(int key) {
			return (bitMap[key / len] & (1 << (key & (len - 1)))) != 0;
		}
};