哈希表：Set/Dict

哈希函数

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

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

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

List拉链法实现哈希集合[LC 705]

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

主要功能：

• 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)逐个查找

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]

哈希映射的结构很类似。

主要功能：

• 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的键值对

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)