---

一、散列函数设计

散列函数设计-折叠法

• 基本步骤：将数据项按照位数分为若干段，再将几段数字相加，最后对散列表大小求余，得到散列值
• 例如：电话号码62767255，可以两位两位分为4段（62、76、72、55），相加（62+76+72+55=265），散列表包括11个槽，那么就是265%11=1，所以h(62767255)=1
• 有时候折叠法还会包括一个隔数反转的步骤，作为一种微调手段。比如（62、76、72、55）隔数反转为（62、67、72、55）

python">def remainder(lst, table_size):"""散列函数设计-折叠法"""# 每两位一组grouped_lst = [lst[i : i + 2] for i in range(0, len(lst), 2)]# 求和total = sum([int(i) for i in grouped_lst])# 求余return total % table_sizetest_lst = "62767255"
print(remainder(test_lst, 11))### 输出结果
1

散列函数设计-平方取中法

• 基本步骤：首先将数据项做平方运算，然后取平方数的中间两位，再对散列表的大小求余
• 例如：对44进行散列，首先44*44=1936，然后取中间的93，对散列表大小11求余，93%11=5

def mid_square(num, table_size):"""散列函数设计-平方取中法"""num_square = num**2s = str(num_square)mid = len(s) // 2# 取中间两位mid_s = s[mid - 1 : mid + 1]return int(mid_s) % table_sizetest_num = 44
print(mid_square(test_num, 11))### 输出结果
5

散列函数设计-非数项

• 基本步骤：把字符串中的每个字符看作ASCII码，再将这些整数累加，对散列表大小求余
• 例如：cat，ord(‘c’)==99, ord(‘a’)==96, ord(‘t’)==116，和为312，结果312%11=4

python">def str_hash(s, table_size):total = sum([ord(i) for i in s])return total % table_sizetest_str = "cat"
print(str_hash(test_str, 11))### 输出结果
4

散列函数设计原则

• 散列函数不能成为存储过程和查找过程的计算负担

二、冲突解决方案

冲突解决方案-开放定址Open Addressing

• 如果两个数据项被散列映射到同一个槽，需要一个系统化的方法在散列表中保存第二个数据项，这个过程称为“解决冲突”
• 基本步骤：当发生冲突时，从冲突的槽开始往后扫描，直到碰到一个空槽，然后把冲突的数据项保存到该空槽。
• 这种寻找空槽的技术称为“开放定址open addressing”。向后逐个槽寻找的方法则是开放定址技术中的**“线性探测linear probing“**
• 采用线性探测方法来解决散列冲突的话，则散列表的查找也遵循同样的规则。如果在散列位置没有找到查找项的话，就必须向后做顺序查找。直到找到查找项，或者碰到空槽（查找失败）。

示例：把44、55、20逐个插入到散列表中。h(44)=0，0#槽已被占据，向后找到并放到1#槽; h(55)=0同样；h(20)=9，向后，再从头开始找到3#槽保存。

冲突解决方案- 线性探测的改进

• 线性探测法的一个缺点是有 聚 集 （clustering）的趋势。即如果同一个槽冲突的数据项较多的话，这些数据项就会在槽附近聚集起来，从而连锁式影响其它数据项的插入。
• 改进方法一：从逐个探测改为跳跃式探测。例如以+3的步长向后寻找空槽。
• 改进方法二：再散列rehashing。跳跃式探测的再散列通式是：rehash(pos)= (pos+skip)% sizeoftable。注意skip的取值，不能被散列表大小整除。
• 改进方法三：二次探测quadratic probing。不再固定skip的值，而是逐步增加skip值，如1、3、5、7、9。

冲突解决方案- 数据项链Chaining

• 将容纳单个数据项的槽扩展为容纳数据项集合（或者对数据项链表的引用）。
• 散列表中的每个槽可以容纳多个数据项，如果有散列冲突发生，只需要简单地将数据项添加到数据项集合中。查找数据项时则需要查找同一个槽中的整个集合。

三、映射

映射 Map

• 映射是键key-值data关联的无序集合，关键码key具有唯一性，通过关键码key可以唯一确定一个数据值
• 使用映射的优势在于，给定关键码key，能够很快得到关联的数据值data。为了达到快速查找的目标，使用散列表来实现，这样查找可以达到最快O(1)的性能

抽象数据类型-映射 Map

方法/操作	描述
Map()	创建一个空映射，返回空映射对象
put(key, val)	将key-val关联对加入映射中，如果key已存在，将val替换旧关联值。加入或更新成功返回True，否则返回False
get(key)	给定key，返回关联的数据值，如不存在，则返回None
del	通过del map[key]的语句形式删除key-val关联
len()	返回映射中key-val关联的数目
in	通过key in map的语句形式，返回key是否存在于关联中，布尔值

Python实现抽象数据类型-映射

• 散列表的大小，虽然可以是任意数，但考虑到要让冲突解决算法能有效工作，应该选择为素数。

python">class MyMap:def __init__(self, size=11):self.size = size  # 整个散列表的大小# 初始化slots列表用于保存keyself.slots = [None] * self.size# 初始化data列表用于保存数据项self.data = [None] * self.sizedef put(self, key, val):hash_val = self.hash_func(key)# 槽位为空if self.slots[hash_val] == None:self.slots[hash_val] = keyself.data[hash_val] = valreturn True# key已存在，更新valif self.slots[hash_val] == key:self.data[hash_val] = valreturn Trueposition = hash_valwhile True:# 再散列向后查找position = self.re_hash(position)# 槽位为空if self.slots[position] == None:self.slots[position] = keyself.data[position] = valreturn True# key已存在，更新valif self.slots[position] == key:self.data[position] = valreturn True# 找了一圈，没找到key或空的槽位if hash_val == position:return Falsedef get(self, key):start_slot = self.hash_func(key)# 没有冲突并且找到if self.slots[start_slot] == key:return self.data[start_slot]position = start_slotwhile True:# 再散列向后查找position = self.re_hash(position)# 遇到空的槽位或已经找了一圈，查找失败返回Noneif self.slots[position] == None or position == start_slot:return None# 找到返回if self.slots[position] == key:return self.data[position]def len(self):"""数据项的数量"""count = 0for i in self.slots:if i != None:count += 1return countdef hash_func(self, key):"""散列函数：采用简单求余方法"""return key % self.sizedef re_hash(self, old_hash):"""再散列函数：冲突解决则采用线性探测“加1”"""return (old_hash + 1) % self.size# 通过特殊方法实现[]访问def __getitem__(self, key):return self.get(key)def __setitem__(self, key, val):return self.put(key, val)

示例：使用上述定义的映射数据类型，进行测试并输出结果

python">h = MyMap()
h[54] = "cat"
h[26] = "dog"
h[93] = "lion"
h[17] = "tiger"
h[77] = "bird"
h[31] = "cow"
h[44] = "goat"
h[55] = "pig"
h[20] = "chicken"
print(h.len())
print(h.slots)
print(h.data)
print(h[20])
print(h[17])
h[20] = "duck"
print(h[20])
print(h[99])### 输出结果
9
[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
chicken
tiger
duck
None

映射-算法分析

• 在最好的情况下，可以提供O(1)常数级时间复杂度的查找性能。其它情况下，需要使用负载因子λ进行评估。如果λ较小，散列冲突的几率就小；否则，冲突的几率就大。
  • 采用线性探测的开放定址法来解决冲突，λ在0~1之间：成功的查找，平均需要比对次数为1/2(1+1/(1-λ))；不成功的查找，平均比对次数为1/2(1+1/((1-λ)^2))
  • 采用数据链来解决冲突，λ可大于1：成功的查找，平均需要比对次数为1+λ/2；不成功的查找，平均比对次数为λ

---

您正在阅读的是《数据结构与算法Python版》专栏！关注不迷路~