83 lines
3.0 KiB
Python
83 lines
3.0 KiB
Python
|
"""
|
|||
|
|
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)
|