题目描述

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); // returns true hashSet.contains(3); // returns false (not found) hashSet.add(2); hashSet.contains(2); // returns true hashSet.remove(2); hashSet.contains(2); // returns false (already removed)

其他

• 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.

解题思路

这道题不涉及什么具体算法，就是单纯设计一个哈希表，代码部分不算特别难所以就不附了大致讲一下数据结构中设计哈希表的思路：

1. 简单数组 最简单的方法无非就是创建一个能放进所有数字的数组，在这道题是1000000，对每一个位置用一个 bool 判定是否存入即可；所有操作时间复杂度O(1), 空间复杂度O(1000000); Leetcode 对空间复杂度要求不高所以这种方法也能过，但一般学习哈希表的时候不会这么设计，因为空间消耗太大。

2. 常规哈希表设计思路 这个讲起来太复杂是一堂课的内容了所以这里简单讲一下思路：用一个短得多的数组（100或者1000）作为初始存放，对每一个存入值计算一个 HashKey 一般可以是对数组长度取模，这样可以保证对同样的的值每次计算出同一个 HashKey；然后在对应 HashKey 存入；显然这样的话会遇到很多值有同一个 HashKey，这就涉及遇到冲突的时候怎么解决，这里由可以分成两种思路：

   1. 链表法：对每一个位置我们用一个链表来存储所有拥有相同 HashKey 的值；
   2. 偏置法：当我们要插入的位置已经有值的时候，我们对位置偏置一个固定值，当新位置没有插入值的时候将值存进去；

   通过这两种方法不难看出，但存入的值比较多的时候，哈希表的操作时间复杂度会增加，最极端的情况是当采用链表法的时候，如果插入所有值都在同一个位置时，操作的时间复杂度会变成O(n)，针对这种情况我们可以用一个变量 load_factor 来表示当前存入值的数量和数组长度的比值，表示当前数组的相对存储量，并根据存储量改变数组的长度以改变值的重新分布使其均匀。

结语

这里讲的只是最基本的思路，关于数据结构的详细学习，推荐一下 UCB 的 CS61B Data Structures～课件和讲课视频都比较齐，而且还有作业和自动批改系统，很适合自学。