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

我就是我 2022-05-15 08:28 147阅读 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

时间复杂度O(1)

转载地址[http://blog.csdn.net/a359680405/article/details/51152084][http_blog.csdn.net_a359680405_article_details_51152084]

[http_blog.csdn.net_a359680405_article_details_51152084]: http://blog.csdn.net/a359680405/article/details/51152084