我们采用散列技术将记录存储在一块连续的存储空间中,这块连续的存储空间即称为哈希表(散列表)。而散列技术实际上就是 映射+存储 的过程。
映射过程
在函数中,一个 x 只能对应一个 y ,但一个 y 可以对应多个 x 。而哈希表中一个 key 同样只能对应一个 value,而一个 value 同样可以对应多个 key。简单来说,key 是唯一的,但 value 不唯一。
而要注意的是,key —> value 这个过程是单向的,无法反推。因为 value 可能对应多个 key。
存储过程
通过映射,我们输入的多个 key,可以得到若干个 value,这里的 value 一般是 key 储存的位置,然后我们把 key 存入数组对应的 value 位中,这样就完成了哈希表的存储。散列主要是面向查找的存储结构,通过 key ,得到 value,通过表中的 value 位置,查看里面是否为 key。
我们为什么要那么麻烦,得专门做从 key --> value 的转化呢?或者说哈希表的作用是什么呢?
当我们要判断现有数据集合中是否有某个元素,或者是否有满足条件的元素,如果我们使用数组的遍历去查找是否有某个元素,那么时间复杂度是 O(n)。而 Hash 算法通过 key --> value 的映射,得到哈希表中 key 存储的位置,然后再看里面的值是否为 key,这样它的时间复杂度为 O(1),因为数组中指定位置的查找的时间复杂度为 O(1) 。所以使用哈希表能大大减少我们查找的时间复杂度。
从 key --> value 的方法有多种,我们介绍一种常用的方法:取余法。
公式:value = key mod p
这里的 p 可以当成我们给哈希表设置的最大长度,而 p 的设定,关乎我们的查找效率。p 太小,就很容易发生哈希冲突。而 p 太大又会增加消耗,p 的选取并没有什么特定的规范。
我们在映射的时候说过:哈希表中一个 key 同样只能对应一个 value,而一个 value 可以对应多个 key。所以不同的 key 可以得到相同的 value ,这时候存储就会遇到问题(即哈希表中的 value 位置已经被占用),这个现象我们称为哈希冲突。
哈希冲突有多个解决方法,这里我们只介绍一种:建立公共溢出区。
我们将哈希表分为基本表和溢出表,将发生冲突的都存放在溢出表中。溢出表的本质就是一个普通数组。这时候,我查找的方式就发生了转变,先查哈希表,哈希表对应位置找不到,就直接在溢出表中遍历查找。
而哈希表的查找也不是万能的查找,存在一定的缺陷:
散列技术一般不适合存在太多的哈希冲突使用。
因为这会降低查找效率,体现不出哈希表查找效率高的优点,并且如果一定要在这个情况下使用的话,还需要想办法消除冲突,这将花费大量时间,那么就失去了 O(1) 时间复杂度的优势,所以在存在大量的冲突情况下,我们就要弃用哈希表。
散列方法也不适用于范围查找,比如以下两个情况。
查找最大值或者最小值
因为哈希表的值是类似函数的,映射函数一个变量只能对应一个值,不知道其他值,也不能查找最大值、最小值,RMQ(区间最值问题)。
查找范围记录
比如查找小于 N 的数有多少个,是不能实现的,原因也是映射函数一个变量只能对应一个值,不知道其他值。
我们还是通过这个实例来了解一下,哈希表的定义和使用。
小发明家弗里想创造一种新的语言,众所周知,发明一门语言是非常困难的,首先你就要克服一个困难就是,有大量的单词需要处理,现在弗里求助你帮他写一款程序,判断是否出现重复的两个单词。
第 1 行,输入 N,代表共计创造了多少个单词。
第 2 行至第 N+1 行,输入 N 个单词。
1≤ N ≤10^4,保证字符串的总输入量不超过 10^6。
输出仅一行。若有重复的单词,就输出重复单词,没有重复单词,就输出 NO
,多个重复单词输出最先出现的。
输入
6
1fagas
dsafa32j
lkiuopybncv
hfgdjytr
cncxfg
sdhrest
输出
NO
输入
5
sdfggfds
fgsdhsdf
dsfhsdhr
sdfhdfh
sdfggfds
输出
sdfggfds
查找是否存在重复单词,这已经是很明显使用哈希表的题目了,因为哈希表可以判断是否存在某个元素。所以,这里使用哈希表来解题。
这里 p 设置为相对较大的数就可以,但像 10001,10002 这些也不是不行,但设的太小会增加公共溢出区的查找,更容易发生哈希冲突。冲突后得去公共溢出区查找,由于公共溢出区每次需要从头开始遍历查找元素,时间消耗会变大。所以 p 设一个比较大的数可以减少公共溢出区的使用。
p = 999999 # 设置相对较大的数,减少冲突
value = ['']*p # 哈希表
buffer = ['']*p # 溢出区
buffer_number = 0 # 溢出区的个数
这里介绍一个 python 中的内置函数—— hash。因为我们数据是字符串,我们需要做映射的话,需要将字符串数字化,这里自己写也还好,但我们直接用 hash() 可以。hash 函数在每一次程序使用同一个字符串运行的值大不一样,但同一个程序运行出来的值时相等的。我们只要把 hash 得到的值当成是随机值即可,但同个变量的每一次运行自身的随机值相等。
hash 函数的演示:
if __name__ == '__main__':
a1 = 'abs'
a2 = 'abs'
print(hash((a1)))
print(hash((a2)))
第一次运行:
第二次运行:
由取余法可以得到映射的位置 n ,数据在插入时,我们需要判断此时哈希表中位置 n 是否有值,如果值等于 key,说明该值重复,return False 。如果值是空的,就在这个位置插入 key,而还有一种情况就是位置上的值不是空的,但也不等于 key(发生了哈希冲突),这时候我们要到公共溢出区进行插入。
公共溢出区的插入需要先查找有没有重复元素,如果找到,也是 return False。如果当前公共溢出区都找不到,那么就需要插入,插入后,溢出区的个数需要加1。
所以整体思路就是:先查哈希再公共溢出区,有重复退出,没重复插入。
def insTable(name):
global buffer_number
n = hash(name)%p # 映射的位置
if value[n] == name: # 不用插入
return False
elif value[n] == "":
value[n] = name
return True
else: # 产生哈希冲突
for i in range(buffer_number):
if buffer[i] == name:
return False
# 过循环 --> 要增加溢出区元素个数
buffer[buffer_number] = name
buffer_number += 1
return True
if __name__ == '__main__':
n = int(input())
while n >0:
n-=1
res = 'NO'
word = input() # 输入单词
flag = insTable(word) # flag判断是否插入成功,插入成功:1,插入失败(重复):0
if not flag: # 重复
res = word # 结果替换,跳出循环
break
print(res)
可在 我的仓库免费查看,如果无法使用可以及时私信我或在评论区指出,谢谢。
本文主要参考蓝桥杯省赛14天夺奖冲刺营,有兴趣的可以自己在蓝桥杯官网搜索
如有错误,敬请指正,欢迎交流🤝,谢谢♪(・ω・)ノ