【数据结构Python】查找与哈希算法-爱代码爱编程
顺序查找
#以随机数生成1~150之间的80个整数,然后实现顺序查找
import random
val=0
data=[0]*80
for i in range(80):
data[i]=random.randint(1,150)
while val!=-1:
find=0
val=int(input('请输入查找键值(1-150),输入-1离开:'))#会一直在循环里执行查找操作,除非val=-1
for i in range(80):
if data[i]==val:
print('在第 %3d个位置找到键值 [%3d]' %(i+1,data[i]))
find+=1
if find==0 and val !=-1 :
print('######没有找到[%3d]######' %val)
print('数据内容为:')
for i in range(80):
print('[%3d]' %data[i],end='')
if i%10==0:
print('')
二分查找
#以随机数生成1~150之间按/*顺序排列的*/50个整数,然后实现二分查找
import random
def bin_search(data,val):
low=0
high=len(data)-1 #长度要减一才是列表的下标
while low <= high and val !=-1:
mid=int((low+high)/2)
if val<data[mid]:
high=mid-1 #如果要找的值比中间值小,那就让上限为中间位置(不包括中间位置)
elif val>data[mid]:
low=mid+1 #如果要找的值比中间值大,那就让下限为中间位置(不包括中间位置)
else:
return [mid,data[mid]]
return -1
val=1
data=[0]*50
for i in range(50):
data[i]=val
val=val+random.randint(1,5)
while True: #输入数的循环
val=int(input('请输入查找键值(1-150),输入-1结束:'))
if val ==-1:
break
num=bin_search(data,val)
if num==-1:
print('##### 没有找到[%3d] #####' %val)
else:
print('在%3d找到%3d' %(num[0],num[1]))
print('数据内容为:')
for i in range(50):
print('[%3d]' % data[i], end='')
if i % 10 == 0:
print('')
哈希算法
- 哈希法是使用哈希函数来计算一个键值所对应的地址,进而建立哈希表格,然后依靠哈希函数来查找各个键值存放在表格中的地址,查找速度与数据多少无关没在没有碰撞和溢出的情况下,一次读取即可完成。
- 哈希法保密性高,事先不知道哈希函数就无法查找到数据。
- 选择哈希函数时,设计原则至少必须符合计算速度快与碰撞频率尽量低两个特点
除留余数法
将数据除以某一个常数后,取余数来当索引
余数最好是质数
平方取中法
先计算数据的平方,之后再取中间的某段数字作为索引
折叠法
将数据转换成一串数字之后,先将这串数字拆分成几个部分,再把他们加起来,就可以计算出键值
例如:有一个数据转成了154684685,可以拆分成154,684,685,再把他们加起来
数字分析法
电话数字类型,取电话的后三位当索引
碰撞和溢出问题的处理
线性探测法
若是碰撞了,直接取到旁边的位置插入数据
import random
INDEXBOX=10 #哈希表最大元素
MAXNUM=7 #最大数据个数
def print_data(data,max_number): #打印数组子程序
print('\t',end='')
for i in range(max_number):
print('[%2d] ' %data[i],end='')
print()
def create_table(num,index): #建立哈希表子程序
tmp=num%INDEXBOX #哈希函数 = 数据%INDEXBOX
while True:
if index[tmp]==-1: #如果数据对应的位置是空的
index[tmp]=num #则直接存入数据
break
else:
tmp=(tmp+1)%INDEXBOX #否则往后找位置存放
#主程序
index=[None]*INDEXBOX
data=[None]*MAXNUM
print('原始数组值:')
for i in range(MAXNUM): #起始数据值
data[i]=random.randint(1,20)
for i in range(INDEXBOX): #清除哈希表
index[i]=-1
print_data(data,MAXNUM) #打印起始数据
print('哈希表的内容:')
for i in range(MAXNUM): #建立哈希表
create_table(data[i],index)
print(' %2d =>' %data[i],end='') #打印单个元素的哈希表位置
print_data(index,INDEXBOX)
print('完成的哈希表:')
print_data(index,INDEXBOX) #打印最后完成的结果
平方探测法
(F(x)+i²)%B
二次哈希法
一次不行就换一种方法,不行就再换