社保网站上怎么做减员,免费网站建设大全,海外房产网站建设,注册资本1000万的公司需要多少钱文章目录 哈希表及其碰撞解决策略1. 引言2. 哈希表简介3. 哈希函数4. 碰撞解决策略4.1 分离链接法#xff08;拉链法#xff09;4.2 开放寻址法4.2.1 线性探测4.2.2 二次探测4.2.3 双重哈希 5. 总结 哈希表及其碰撞解决策略
1. 引言
哈希表是一种高效的数据结构#xff0c… 文章目录 哈希表及其碰撞解决策略1. 引言2. 哈希表简介3. 哈希函数4. 碰撞解决策略4.1 分离链接法拉链法4.2 开放寻址法4.2.1 线性探测4.2.2 二次探测4.2.3 双重哈希 5. 总结 哈希表及其碰撞解决策略
1. 引言
哈希表是一种高效的数据结构用于将键映射到值也称为表或映射抽象数据类型/ADT。哈希表利用哈希函数将大的或非整数键映射到一个小的整数索引范围通常是 [0..hash_table_size-1]。由于哈希函数可能会将不同的键映射到相同的索引这就引发了碰撞问题。本文将介绍几种常见的碰撞解决策略包括开放寻址法线性探测、二次探测和双重哈希和闭散列法分离链接。
2. 哈希表简介
哈希表通过哈希函数将键映射到数组中的索引从而实现快速的数据存储和检索。这个过程包括两个主要步骤
哈希函数计算键的哈希值。索引计算将哈希值映射到数组的索引范围内。
公式表示为
index hash_function(key) % hash_table_size哈希表在计算机软件中广泛应用如关联数组、数据库索引、缓存和集合等。它们的主要优点是能够在平均情况下以常数时间复杂度O(1)进行插入、删除和查找操作。
3. 哈希函数
哈希函数需要满足以下条件
快速计算时间复杂度为O(1)。最小冲突尽可能减少碰撞。均匀分布键均匀地分散到哈希表中。
一个常用的哈希函数是取模运算
h(v) v % M其中M是哈希表的大小通常设为一个大素数。这样可以减少冲突并确保均匀分布。哈希函数的选择非常重要因为一个好的哈希函数能够有效减少冲突提高哈希表的性能。
如果负载因子α N/MN是键的数量M是哈希表大小保持在一个小常数范围内所有操作的时间复杂度均为O(1)。负载因子越小碰撞的概率就越低链表的平均长度也就越短从而提高了操作效率。
4. 碰撞解决策略
当两个不同的键通过哈希函数映射到相同的索引时就会发生碰撞。为了解决这个问题常见的碰撞解决策略包括分离链接法和开放寻址法。
4.1 分离链接法拉链法
分离链接法Separate Chaining简称SC是最简单的碰撞解决方法之一。每个哈希表位置都包含一个链表所有碰撞到同一位置的键值对都存储在这个链表中。这种方法将冲突键值对存储在链表中避免了冲突带来的问题。
搜索v遍历链表检查是否存在v。插入v将v插入链表尾部。删除v遍历链表删除v。
class Node:def __init__(self, value: int):self.value valueself.next: Node Noneclass SeparateChaining:def __init__(self, size: int, same: boolTrue):self.size sizeself.same sameself.nums 0self.table: List[Node] [Node(None) for _ in range(self.size)] # 初始化哨兵节点def hash_func(self, value: int) - int:return value % self.sizedef add(self, value: int) - None:node self._search(value, self.same)new_node Node(value)node.next, new_node.next new_node, node.nextdef remove(self, value: int) - None:node self._search(value, False)if node.next and node.next.value value:node.next node.next.nextdef search(self, value: int) - bool:if self._search(value, False).next:return Truereturn Falsedef _search(self, value: int, same: boolTrue) - Node:index self.hash_func(value)node self.table[index]while node.next:next_node node.nextif not same and next_node.value value:breaknode next_nodereturn nodedef __repr__(self) - str:out []for node in self.table:s []while node:s.append(node.value)node node.nextout.append(f{s !r})return f{out !r}if __name__ __main__:sc SeparateChaining(25, True)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:sc.add(i)print(sc)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:sc.remove(i)print(sc)# print输出
[[None], [None, 76], [None, 2], [None, 53], [None], [None], [None], [None, 7, 57], [None, 33], [None], [None], [None], [None], [None, 88, 38], [None, 89], [None, 40], [None, 41, 16], [None, 42, 42, 42], [None], [None, 19], [None, 45, 95], [None, 71], [None, 72], [None], [None]]
[[None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None], [None]] 4.2 开放寻址法
开放寻址法Open Addressing通过探测序列来解决碰撞。常见的探测方法有线性探测、二次探测和双重哈希。 它们的差别是使用的hash函数不相同下面是它们之间的公共的基类其中包含了搜索、插入、和删除的公共方法
from abc import abstractmethod
from typing import Listclass Probing:def __init__(self, size: int, max_collision: int 10, sameTrue):self.size size # 最大的存储容量self.table: List[int] [None] * size # hash表self.max_collision max_collision # 最大的hash碰撞次数self.nums 0 # 有效元素的个数self.same same # 在插入的时候是否容忍具有相同的元素存在abstractmethoddef hash_func(self, value: int, step: int 0) - int:...def _search(self, value: int, sameTrue) - int:# 搜寻该元素value可用的槽位而不是搜寻该元素在不在step: int 0first_none -1while step self.max_collision:_hash self.hash_func(value, step)if self.table[_hash] is None:# 可能这个位置的值已经被删除了并不一定后续没有所以需要继续查找而不是返回None# 记录第一次为空的位置如果要插入一个元素就可以插入到这里if first_none -1:first_none _hashelse:# 不许相同遇到相同值if not same and self.table[_hash] value:return _hash#否则继续寻找直到找到None或者超出hash碰撞最大值step 1# first_none为-1 说明超出hash碰撞最大值return first_nonedef search(self, value: int) - int:# 搜寻元素所以遇到该元素就返回return self._search(value, sameFalse)propertydef alpha(self) - float:return self.nums / self.sizedef add(self, value: int) - None:# 搜寻槽位index self._search(value, self.same)if index -1:raise ValueError(超出hash碰撞的最大次数)if self.table[index] value:returnself.table[index] valueself.nums 1def remove(self, value: int) - None:# 搜寻该元素index self._search(value, False)if index -1 or self.table[index] is None:returnself.table[index] Noneself.nums - 1def __repr__(self) - str:return fProbing({self.table !r}), nums:{self.nums}, alpha:{self.alpha}4.2.1 线性探测
线性探测Linear Probing采用固定步长进行探测
i (base step * 1) % M其中base是初始哈希值step为当前探测步骤。探测序列为
h(v)基地址(h(v) 1 * 1) % M(h(v) 2 * 1) % M… 下面是线性探测的具体实现代码
class LinearProbing(Probing):def __init__(self, size: int, max_collision: int 10):super().__init__(size, max_collision)def hash_func(self, value: int, step: int 0) - int:return (value step * 1) % self.sizedef __repr__(self) - str:return fLinearProbing({self.table !r}), nums:{self.nums}, alpha:{self.alpha}
if __name__ __main__:lp LinearProbing(25, 20)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:lp.add(i)print(lp)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:lp.remove(i)print(lp)
# print 输出
LinearProbing([16, 89, 2, 53, 76, None, None, 7, 57, 33, None, None, None, 88, 38, 40, 41, 42, 42, 19, 45, 71, 72, 42, 95]), nums:20, alpha:0.8
LinearProbing([None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]), nums:0, alpha:0.0
线性探测的优点是实现简单但容易出现主聚类Primary Clustering问题即连续的空闲槽位被逐渐填满导致探测序列变长性能下降。
4.2.2 二次探测
二次探测Quadratic Probing采用平方步长进行探测step 为碰撞次数
i (base step * step) % M探测序列为
h(v)基地址(h(v) 1 * 1) % M(h(v) 2 * 2) % M(h(v) 3 * 3) % M…
class QuadraticProbing(Probing):def __init__(self, size: int, max_collision: int 10):super().__init__(size, max_collision)def hash_func(self, value: int, step: int 0) - int:return (value step * step) % self.sizedef __repr__(self) - str:return fQuadraticProbing({self.table !r}), nums:{self.nums}, alpha:{self.alpha}
if __name__ __main__:qp QuadraticProbing(25, 20)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:qp.add(i)print(qp)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:qp.remove(i)print(qp)#print输出
QuadraticProbing([16, 42, 2, 53, None, 76, None, 7, 57, 33, None, None, None, 88, 38, 40, 41, 42, 42, 19, 45, 71, 72, 89, 95]), nums:20, alpha:0.8
QuadraticProbing([None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]), nums:0, alpha:0.0 也可以是用左右平方步长探测
i (base (-1)**step * ((step1)//2)**2) % M探测序列为
h(v)基地址(h(v) 1 * 1) % M(h(v) - 1 * 1) % M(h(v) 2 * 2) % M(h(v) - 2 * 2) % M…
class QuadraticProbing2(Probing):def __init__(self, size: int, max_collision: int 10):super().__init__(size, max_collision)def hash_func(self, value: int, step: int 0) - int:return (value ((-1) ** step) * (((step1) // 2) ** 2)) % self.sizedef __repr__(self) - str:return fQuadraticProbing2({self.table !r}), nums:{self.nums}, alpha:{self.alpha}if __name__ __main__:qp2 QuadraticProbing2(25, 20)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:qp2.add(i)print(qp2)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:qp2.remove(i)print(qp2)# print输出
QuadraticProbing2([16, 76, 2, 53, None, None, 57, 7, 42, 33, None, None, 38, 88, 89, 40, 41, 42, 42, 19, 45, 71, 72, None, 95]), nums:20, alpha:0.8
QuadraticProbing2([None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]), nums:0, alpha:0.0如果负载因子α 0.5且M是一个质数前M/2个二次探测索引都是唯一的。二次探测减少了主聚类问题但仍可能出现次聚类Secondary Clustering问题即哈希值相同但初始位置不同的键会形成新的聚类。
4.2.3 双重哈希
双重哈希Double Hashing采用两个哈希函数进行探测
i (base step * secondary) % M其中secondary smaller_prime - key % smaller_primesmaller_prime是小于M的质数。探测序列为
h(v)基地址(h(v) 1 * h2(v)) % M(h(v) 2 * h2(v)) % M(h(v) 3 * h2(v)) % M…
双重哈希通过引入第二个哈希函数来决定探测步长从而有效减少了主聚类和次聚类问题使得探测序列更加分散。常见的第二哈希函数为
h2(v) smaller_prime - (v % smaller_prime)其中smaller_prime通常设为小于哈希表大小的质数这样可以确保h2(v)的值在[1..smaller_prime]范围内。
class DoubleProbing(Probing):def __init__(self, size: int, max_collision: int 10):super().__init__(size, max_collision)def hash_func(self, value: int, step: int 0) - int:h1 value % self.sizesmaller_prime 23h2 smaller_prime - (value % smaller_prime)return (h1 step * h2) % self.sizedef __repr__(self) - str:return fDoubleProbing({self.table !r}), nums:{self.nums}, alpha:{self.alpha}if __name__ __main__:dp DoubleProbing(25, 20)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:dp.add(i)print(dp)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:dp.remove(i)print(dp)#print输出
DoubleProbing([42, 76, 2, 53, 42, None, 57, 7, 33, None, 95, None, 38, 88, 89, 40, 41, 42, None, 19, 45, 71, 72, 16, None]), nums:20, alpha:0.8
DoubleProbing([None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]), nums:0, alpha:0.0 5. 总结
哈希表是一种高效的数据结构通过哈希函数将键映射到值。碰撞是哈希表中的一个重要问题常用的解决策略包括分离链接法和开放寻址法。选择合适的哈希函数和碰撞解决策略可以大大提高哈希表的性能和效率。本文详细介绍了几种常见的碰撞解决方法及其优缺点希望能帮助读者更好地理解和应用哈希表。
在实际应用中根据具体需求和数据特点选择合适的哈希表实现方式可以有效提升程序的性能和稳定性。无论是分离链接法还是开放寻址法都有其独特的优点和适用场景合理运用这些技术可以使哈希表在各种情况下发挥最佳性能。 完整代码如下
from abc import abstractmethod
from typing import Listclass Probing:def __init__(self, size: int, max_collision: int 10, same: boolTrue):self.size sizeself.table: List[int] [None] * sizeself.max_collision max_collisionself.nums 0self.same sameabstractmethoddef hash_func(self, value: int, step: int 0) - int:...def _search(self, value: int, same: boolTrue) - int:step: int 0first_none -1while step self.max_collision:_hash self.hash_func(value, step)if self.table[_hash] is None:# 可能这个位置的值已经被删除了并不一定后续没有需要查找的值# 记录第一次为空的位置if first_none -1:first_none _hashelse:# 不许相同遇到相同值if not same and self.table[_hash] value:return _hash#否则继续寻找直到找到None或者超出hash碰撞最大值step 1# -1超出hash碰撞最大值return first_nonedef search(self, value: int) - int:return self._search(value, sameFalse)propertydef alpha(self) - float:return self.nums / self.sizedef add(self, value: int) - None:index self._search(value, self.same)if index -1:raise ValueError(超出hash碰撞的最大次数)if self.table[index] value:returnself.table[index] valueself.nums 1def remove(self, value: int) - None:index self._search(value, False)if index -1 or self.table[index] is None:returnself.table[index] Noneself.nums - 1def __repr__(self) - str:return fProbing({self.table !r}), nums:{self.nums}, alpha:{self.alpha}class LinearProbing(Probing):def __init__(self, size: int, max_collision: int 10):super().__init__(size, max_collision)def hash_func(self, value: int, step: int 0) - int:return (value step * 1) % self.sizedef __repr__(self) - str:return fLinearProbing({self.table !r}), nums:{self.nums}, alpha:{self.alpha}class QuadraticProbing(Probing):def __init__(self, size: int, max_collision: int 10):super().__init__(size, max_collision)def hash_func(self, value: int, step: int 0) - int:return (value step * step) % self.sizedef __repr__(self) - str:return fQuadraticProbing({self.table !r}), nums:{self.nums}, alpha:{self.alpha}class QuadraticProbing2(Probing):def __init__(self, size: int, max_collision: int 10):super().__init__(size, max_collision)def hash_func(self, value: int, step: int 0) - int:return (value ((-1) ** step) * (((step1) // 2) ** 2)) % self.sizedef __repr__(self) - str:return fQuadraticProbing2({self.table !r}), nums:{self.nums}, alpha:{self.alpha}class DoubleProbing(Probing):def __init__(self, size: int, max_collision: int 10):super().__init__(size, max_collision)def hash_func(self, value: int, step: int 0) - int:h1 value % self.sizesmaller_prime 23h2 smaller_prime - (value % smaller_prime)return (h1 step * h2) % self.sizedef __repr__(self) - str:return fDoubleProbing({self.table !r}), nums:{self.nums}, alpha:{self.alpha}class Node:def __init__(self, value: int):self.value valueself.next: Node Noneclass SeparateChaining:def __init__(self, size: int, same: boolTrue):self.size sizeself.same sameself.nums 0self.table: List[Node] [Node(None) for _ in range(self.size)] # 初始化哨兵节点def hash_func(self, value: int) - int:return value % self.sizedef add(self, value: int) - None:node self._search(value, self.same)new_node Node(value)node.next, new_node.next new_node, node.nextdef remove(self, value: int) - None:node self._search(value, False)if node.next and node.next.value value:node.next node.next.nextdef search(self, value: int) - bool:if self._search(value, False).next:return Truereturn Falsedef _search(self, value: int, same: boolTrue) - Node:index self.hash_func(value)node self.table[index]while node.next:next_node node.nextif not same and next_node.value value:breaknode next_nodereturn nodedef __repr__(self) - str:out []for node in self.table:s []while node:s.append(node.value)node node.nextout.append(f{s !r})return f{out !r}if __name__ __main__:lp LinearProbing(25, 20)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:lp.add(i)print(lp)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:lp.remove(i)print(lp)qp QuadraticProbing(25, 20)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:qp.add(i)print(qp)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:qp.remove(i)print(qp)qp2 QuadraticProbing2(25, 20)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:qp2.add(i)print(qp2)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:qp2.remove(i)print(qp2)dp DoubleProbing(25, 20)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:dp.add(i)print(dp)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:dp.remove(i)print(dp)sc SeparateChaining(25, True)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:sc.add(i)print(sc)for i in [72, 7, 53, 71, 40, 2, 45, 41, 42, 19, 42, 88, 42, 95, 38, 57, 16, 33, 89, 76]:sc.remove(i)print(sc)
