# 哈希表：Set/Dict

## 哈希函数

哈希表又叫散列表，可以认为是更普遍意义上的数组，只不过“下标“不再是0,1,2,...而可能是任何形式的输入，比如说字符串。

用[拉链法](https://en.wikipedia.org/wiki/Hash_table#Open_addressing)的话，创造N个桶，没个桶装着一条链表。把输入通过哈希函数 $$\text{hash}(input) ∈ (0, N-1)$$ 来找到它的位置。如果出现碰撞就在那条链表继续查找时间复杂度退化到O(L)，其中L是链表的平均长度。

选择基数（数组大小）为一个较大的素数，这样就可以减少哈希碰撞。比如当元素是有规律的等差数列时，并且和基数最大公约数不为1时，就会造成哈希映射时冲突变高，而数组某些位置永远不会有值。

## List拉链法实现哈希集合\[[LC 705](https://leetcode-cn.com/problems/design-hashset/)]

哈希集合可以看作哈希映射的特例，只不过键值对的值是“是否存在“。

主要功能：

* `add(key)`：O(1)插入一个元素\
  实现：在第 $$\text{hash}(key) % M$$ 的列表尾部O(1)加入元素，若已经含有key则返回
* `remove(key)`：O(1)删除一个元素\
  实现：若`contains(key)=True`，则在第 $$\text{hash}(key) % M$$ 的列表中O(L)删除元素
* `contains(key)`：O(1)判断是否还有元素\
  实现：判断第 $$\text{hash}(key) % M$$ 的列表是否为空，若不空则O(L)逐个查找

```python
class MyHashSet:
    def __init__(self, M=2069, hashfunc=hash):
        self.M = M
        self.lists = [[] for _ in range(M)]
        self.hashfunc = hashfunc
    
    def hashCode(self, key: int) -> None:
        return self.hashfunc(key) % self.M
        
    def add(self, key: int) -> None:
        if self.contains(key): return
        self.lists[self.hashCode(key)].append(key)

    def remove(self, key: int) -> None:
        if not self.contains(key): return
        self.lists[self.hashCode(key)].remove(key)

    def contains(self, key: int) -> bool:
        hc = self.hashCode(key)
        return len(self.lists[hc])>0 and \
            key in self.lists[hc]
```

## List拉链法实现哈希映射\[[LC 706](https://leetcode-cn.com/problems/design-hashmap/)]

哈希映射的结构很类似。

主要功能：

* `put(key, value)`：O(1)插入一个键值对\
  实现：在第 $$\text{hash}(key) % M$$ 的列表尾部O(1)加入键值对，若已经含有key则更新
* `get(key)`：O(1)查找一个键值对\
  实现：在第 $$\text{hash}(key) % M$$ 的列表中O(L)找到含有key的键值对，若不含key则返回特殊值
* `remove(key)`：O(1)删除一个键\
  实现：在第 $$\text{hash}(key) % M$$ 的列表中O(L)找到并删除含有key的键值对，若不含key则返回
* `contains(key)`：O(1)判断是否含有键\
  实现：在$$\text{hash}(key) % M$$ 的列表中O(L)查找是否含有key的键值对

```python
class MyList:
    def __init__(self):
        self.data = []
    
    def keys(self):
        return [k for k, _ in self.data]
    
    def contains(self, key):
        return key in self.keys()
    
    def get(self, key):
        if not self.contains(key): return -1
        return self.data[self.keys().index(key)][1]
    
    def remove(self, key):
        if not self.contains(key): return
        del self.data[self.keys().index(key)]
    
    def update(self, key, value):
        if not self.contains(key):
            self.data.append((key, value))
        self.data[self.keys().index(key)] = (key, value)

class MyHashMap:
    def __init__(self, M=2069):
        self.M = M
        self.lists = [MyList() for _ in range(M)]

    def hashCode(self, key: int) -> None:
        return key % self.M

    def put(self, key: int, value: int) -> None:
        self.lists[self.hashCode(key)].update(key, value)

    def get(self, key: int) -> int:
        return self.lists[self.hashCode(key)].get(key)

    def remove(self, key: int) -> None:
        if not self.contains(key): return
        return self.lists[self.hashCode(key)].remove(key)
    
    def contains(self, key: int) -> bool:
        return self.lists[self.hashCode(key)].contains(key)
```