705. 设计哈希集合

705. 设计哈希集合

题目

不使用任何内建的哈希表库设计一个哈希集合（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 ，（已移除）

提示：

• 0 <= key <= 10^6
• 最多调用 10^4 次 add、remove 和 contains

题解

我看到这题的第一想法，就是用一个10^6大小的数组来储存情况。
但是面试这样说估计会被毒打一顿，想了想，写了个插入排序，这样查找是，但插入和删除都是的复杂度。

class MyHashSet:

    def __init__(self):
        self.hash_table = list()

    def find(self, key: int) -> int:
        left = 0
        right = len(self.hash_table)-1
        if self.hash_table[right] == key:
            return right
        if self.hash_table[left] == key:
            return left
        while right-left > 1:
            middle = left+(right-left)//2
            if self.hash_table[middle] == key:
                return middle
            if self.hash_table[middle] < key:
                left = middle
            else:
                right = middle
        return -1*left-1

    def add(self, key: int) -> None:
        if len(self.hash_table) == 0:
            self.hash_table.append(key)
            return
        place = self.find(key)
        if place < 0:
            place = -1*place-1
            self.hash_table.append(0)
            for i in range(len(self.hash_table)-1, place+1, -1):
                self.hash_table[i] = self.hash_table[i-1]
            self.hash_table[place+1] = key
        print(x.hash_table)

    def remove(self, key: int) -> None:
        if len(self.hash_table) == 0:
            return
        place = self.find(key)
        if place >= 0:
            for i in range(place, len(self.hash_table)-1):
                self.hash_table[i] = self.hash_table[i+1]
            self.hash_table.pop()

    def contains(self, key: int) -> bool:
        return len(self.hash_table) > 0 and self.find(key) >= 0

这属于脑子不太清醒：如果真要查找的话，用二叉查找树也是，并且插入和删除也是。
而且这题的思路明显是用哈希做，还是说明自己不够熟练。

标准解法——拉链法

详解 HashSet 的设计：在时间和空间上做权衡

class MyHashSet:
    def __init__(self):
        self.buckets = 1999
        self.table = [[] for _ in range(self.buckets)]

    def hash(self, key):
        return key % self.buckets

    def add(self, key: int) -> None:
        hash_key = self.hash(key)
        if key in self.table[hash_key]:
            return
        else:
            self.table[hash_key].append(key)

    def remove(self, key: int) -> None:
        hash_key = self.hash(key)
        if key in self.table[hash_key]:
            self.table[hash_key].remove(key)

    def contains(self, key: int) -> bool:
        hash_key = self.hash(key)
        return key in self.table[hash_key]