LeetCode-705.设计哈希集合

发表于 分类于

题目描述

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

实现 MyHashSet 类：

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

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
["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 ，（已移除）

提示：

  • 0 <= key <= 106
  • 最多调用 104 次 add、remove 和 contains

题解

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
38
39
40
41
42
43
44
45
46
47
class MyHashSet {
  let BASE = 769
  var data: [[Int]]
  init() {
    // 对应的key需要存到对应位置上的数组中，所以需要初始化BASE个元素
    data = Array.init(repeating: [Int](), count: BASE)
  }
  
  func add(_ key: Int) {
    let hash = hashValue(key)
    let keys = data[hash]
    for value in keys {
      if value == key  {
        return
      }
    }
    data[hash].append(key)
  }
  
  func remove(_ key: Int) {
    let hash = hashValue(key)
    var keys = data[hash]
    for (index, value) in keys.enumerated() {
      if value == key {
        // 一定要重新赋值或者直接用data[hash].remove(at: index)，因为swift中keys是data[hash]的一份copy副本
        keys.remove(at: index)
        data[hash] = keys
        return
      }
    }
  }
  
  func contains(_ key: Int) -> Bool {
    let hash = hashValue(key)
    let keys = data[hash]
    for value in keys {
      if value == key {
        return true
      }
    }
    return false
  }
  
  private func hashValue(_ from: Int) -> Int {
    return from % BASE
  }
}

​