"""
hash map 是将数据项映射到列表中的对应位置，由于有这样的映射关系，
可以使用 hash map 实现哈希查找，查找复杂度为 O(1)

计算映射的方式就是 hash 函数，一般采用对列表长度取余的方式

hash 表重要指标：负载，表示已被占用的空间/总空间，该比值也被称谓负载因子。
当负载因子太大时，需要扩容，

hash 函数，例如使用项值直接对一个数取余，会存在几个项取余的结果相同，这样就带来了冲突，
也就是一个槽对应了多个值

冲突解决：
1. 最简单的方法是从原哈希冲突处开始，以顺序方式移动槽，直到遇到第一个空槽。
遇到末尾后可以循环从头开始查找，这种冲突解决方法被称为开放寻址法。线性查找的缺点是数据项聚集。

2. 处理数据项聚集的一种方式是扩展开放寻址技术，发生冲突时不是顺序查找下一个开放
槽，而是跳过若干个槽，从而更均匀地分散引起冲突的项。比如每次隔三个槽来查看。

在冲突后寻找另一个槽的过程叫重哈希（重散列, rehash），
其计算方法如下：rehash(pos) = (pos + n)%size

要注意，跳过的大小必须使得表中的所有槽最终都能被访问。为确保这一点，建议表大
小是素数，这也为什么示例中要使用 11。

3. 解决冲突的另一种方法是拉链法，也就是说对每个冲突的位置，我们设置一个链表来保
存数据项，如图（5.5）。
    - 查找时，发现冲突后就再到链上顺序查找，复杂度为 O(n)。当然，
    冲突链上的数据可以排序，然后再借助二分查找，这样哈希表复杂度为 O(log2(n))。
    - 拉链法是许多编程语言内置的哈希表数据结构解决冲突的默认实现

4. 如果采用扩容来解决冲突，需要将原来表中的键值对重新计算
"""


class HashMap:

    def __init__(self, size: int):
        self.size = size
        self.slot_used = 0
        self.data: list[int | None] = [None for _ in range(self.size)]
        self.slot: list[int | None] = [None for _ in range(self.size)]

    def hash(self, key: int) -> int:
        return key % self.size

    def rehash(self, key: int) -> int:
        return (key + 3) % self.size

    def load(self):
        return self.slot_used / self.size

    def expand(self):
        self.slot += [None for _ in range(self.size)]
        self.data += [None for _ in range(self.size)]
        self.size *= 2



    def insert(self, key: int, value: int):
        if self.load() >= 0.75:
            self.expand()

        pos = self.hash(key)
        if not self.slot[pos]:
            self.slot[pos] = key
            self.data[pos] = value
        else:
            while self.slot[pos]:
                pos = self.rehash(pos)

            self.slot[pos] = key
            self.data[pos] = value

        self.slot_used += 1


    def remove(self, key: int) -> int | None:
        if self.slot_used == 0:
            return None

        pos = self.hash(key)