python-哈希查找-时间复杂度O(1)

我就是我 2022-05-15 08:28 251阅读 0赞

哈希查找是通过计算数据元素的存储地址进行查找的一种方法。

比如”5“是一个要保存的数，然后我丢给哈希函数，哈希函数给我返回一个”2”，那么此时的”5“和“2”就建立一种对应关系，这种关系就是所谓的“哈希关系”，在实际应用中也就形成了”2“是key，”5“是value。

哈希必须要遵守两点原则：
①: key尽可能的分散，也就是我丢一个“6”和“5”给你，你都返回一个“2”，那么这样的哈希函数不尽完美。
②：哈希函数尽可能的简单，也就是说丢一个“6”给你，你哈希函数要搞1小时才能给我，这样也是不好的。

常用的哈希函数构造方法：

直接定址法：很容易理解，key=Value+C；这个“C”是常量。Value+C其实就是一个简单的哈希函数。
除法取余法：很容易理解， key=value%C;解释同上。
数字分析法：这种蛮有意思，比如有一组value1=112233，value2=112633，value3=119033，针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。
平方取中法。此处忽略，见名识意。
折叠法：这种蛮有意思,比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160，然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相关，来做到“散列地址”尽可能分散的目地。

·

当两个不同的数据元素的哈希值相同时，就会发生冲突。解决冲突常用的手法有2种：

开放地址法：如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。
链接法：将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。

代码

#coding=utf-8
__author__ = 'a359680405'
#除法取余法实现的哈希函数
def myHash(data,hashLength,):
    return data % hashLength
#哈希表检索数据
def searchHash(hash,hashLength,data):
    hashAddress=myHash(data,hashLength)
   #指定hashAddress存在，但并非关键值，则用开放寻址法解决
    while hash.get(hashAddress) and hash[hashAddress]!=data:
        hashAddress+=1
        hashAddress=hashAddress%hashLength
    if hash.get(hashAddress)==None:
        return None
    return hashAddress
#数据插入哈希表
def insertHash(hash,hashLength,data):
    hashAddress=myHash(data,hashLength)
    #如果key存在说明应经被别人占用， 需要解决冲突
    while(hash.get(hashAddress)):
        #用开放寻执法
        hashAddress+=1
        hashAddress=myHash(hashAddress,hashLength)
    hash[hashAddress]=data
if __name__ == '__main__':
    hashLength=20
    L=[13, 29, 27, 28, 26, 30, 38 ]
    hash={}
    for i in L:
        insertHash(hash,hashLength,i)
    result=searchHash(hash,hashLength,38)
    if result:
        print("数据已找到，索引位置在",result)
        print(hash[result])
    else:
        print("没有找到数据")
   1 
   2 
   3 
   4 
   5 
   6 
   7 
   8 
   9 
   10 
   11 
   12 
   13 
   14 
   15 
   16 
   17 
   18 
   19 
   20 
   21 
   22 
   23 
   24 
   25 
   26 
   27 
   28 
   29 
   30 
   31 
   32 
   33 
   34 
   35 
   36 
   37 
   38 
   39