代码编织梦想

顺序查找

#以随机数生成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)+)%B

二次哈希法

一次不行就换一种方法,不行就再换

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_51614272/article/details/123337979

python一日一练17----哈希查找-爱代码爱编程

介绍 哈希查找是通过计算数据元素的存储地址进行查找的一种方法。 比如”5“是一个要保存的数,然后我丢给哈希函数,哈希函数给我返回一个”2”,那么此时的”5“和“2”就建立一种对应关系,这种关系就是所谓的“哈希关系”,在实

python哈希查找,构建简单哈希表-爱代码爱编程

说实话上学期学完数据结构与算法这门课,接触到了挺多的算法,有难的有简单的,但是当时只是为了交作业硬生生把所有的算法全部都看完背下来,而没有去理解算法的深意以及它的用武之地,正巧这段时间都在看scrapy+redis,过程中了

hash算法(含python实现)__yucen的博客-爱代码爱编程_python hash

1. 简介 哈希(hash)也翻译作散列。Hash算法,是将一个不定长的输入,通过散列函数变换成一个定长的输出,即散列值。 这种散列变换是一种单向运算,具有不可逆性即不能根据散列值还原出输入信息,因此严格意义上讲Hash算法是一种消息摘要算法,不是一种加密算法。常见的hash算法有:SM3、MD5、SHA-1等 。 2. 应用 Hash主要应用在数

hash查找的基本原理及实现_bupt-wt的博客-爱代码爱编程_哈希查找原理

理论: 很多查找算法是通过利用关于项在集合中相对余彼此存储的位置的信息,改进搜索算法 建立一个可以在O(1)时间内被搜索的数据结构--> Hash查找 哈希表是以一种容易找到它们的方式存储项的集合,哈希表的每个位置,通常称为一个槽,可以容纳一个项,并且由从0开始的整数值命名,例如有名为0的槽,名为1的槽......,最初,哈希表不包含项,因此每

python基础--查找与哈希法_freequant00的博客-爱代码爱编程

Python基础–查找与哈希法 查找是指从数据文件之中找出满足条件的记录。通常判断一个查找的好坏是比较次数和查找所需的时间来判断,哈希法又被称之为散列法,任何通过哈希查找的数据都不需要经过事先的排序,也就是说这种查找可以直

Python数据结构和算法(六):哈希算法(hash)的六大应用以及哈希一致性的介绍和实现-爱代码爱编程

文章目录 前文哈希算法定义和特征哈希算法应用安全加密散列函数唯一标识数据校验负载均衡数据分片统计关键词次数快速找出图片是否存在图库哈希一致性哈希一致性的定义和使用哈希一致性来定义分布式存储MySQL表哈希一致性的实现总结 前文   说到哈希算法大家应该都不陌生,但系数它的应用范围,大多数人只能答出少部分,比如用于加密,比如用于散列表,比如My

python--数据结构--哈希查找-爱代码爱编程

代码实现: # search_hash_table.py from collections import deque import math class Record: def __init__(self, key): self.key = key self.other_info = None class

【数据结构与算法python】哈希查找算法的python实现-爱代码爱编程

1、Hashing 在文章《【数据结构与算法python】顺序查找算法的python实现(无序表)》与《【数据结构与算法python】顺序查找算法的python实现(有序表)中,我们利用数据集中关于数据项之间排列关系的知识, 来将查找算法进行了提升,如果数据项之间是按照大小排好序的话,就可以利用二分查找来降低算法复杂度。 为了进一步降低算法的复杂度,构造

python实现hash查找-爱代码爱编程

思维导图 Hash表的python实现 class HashTable: def __init__(self): self.size = 11 #最好为质数 self.slots = [None] * self.size #槽 self.data = [None] * self.size #项

python解决哈希查找_python数据结构与算法 29-1 哈希查找-爱代码爱编程

前面的章节中,我们利用数据集中元素的相对位置信息来提高查找算法的性能。 比方知道列表是有序的,能够使用二分查找。本节我们走得更远一些,创建一个数据结构,使得查找性能提高到O(1)。称为哈希查找。 要做到这种性能,我们要知道元素的可能位置。假设每一个元素就在他应该在的位置上,那么要查找的时候仅仅须要一次比較得到有没有的答案,但以下将会看到。不是这么回

Python常见的查找算法(顺序查找、二分查找和哈希查找)-爱代码爱编程

目录 1. 顺序查找2. 二分查找1. 普通实现2.递归实现3.哈希查找 1. 顺序查找 顺序查找也叫线性查找,顺序查找是所有查找方法中最基础也最简单的一种,一般用于对线性表的查找。它是按照数据在查找表中原有的顺序进行遍历查询的算法。由于需要遍历整个查找表,所以顺序查找的时间复杂度为 O(n)。其实现如下: def seq_search(l