数据结构——哈希

2018-02-12

简单介绍

开辟一个足够大的空间H，数组的元素值作为自变量，通过某一个函数f，将元素值映射到hash空间的index索引处，这样通过f计算出索引，可以快速定位到元素的值，时间复杂度O(1)。基本思想就是用空间换时间。

Hash函数

哈希函数又叫散列函数，输入域可以是非常大的（无限）范围，但输出域是固定范围（所以不同输入可能返回相同输出）。Hash函数非常重要，一个好的Hash函数，能够将数据映射到“杂乱”的位置。

dbj2
sdbm
MurmurHash
MD5
SHA1
dbj2
这个算法是Dan Bernstein在comp.lang.c提出的，这个算法的另一个版本是使用异或的方式：
$hash(i)=hash(i-1)*33^str[i]$
魔数33本身是个合数，但是它的表现比其他很多素数效果都好。这里表现好意思就是经过映射后，数组更为散列。
输入是字符串，输出时整数值。
1
2
3
4
5
def hash(str):
hash=5381
for i in str:
hash=hash*33+ord(i)
return hash

sdbm

dbj2使用的是魔数33，我们也可以用65599，这样就是sdbm算法了。

def hash(str):
    hash=0  # 随机给的初值种子
    for i in str:
        hash=hash*65599+ord(i)
    return hash

这个算法在实际中有很好的分布，这样造成的冲突概率大大降低。

Hash冲突

当两个及以上的键分配到了哈希表同一个索引上时，则称这些键发成了冲突。
处理冲突的方法：

拉链法：冲突后在后面开辟新的空间，不用考虑二次哈希
两次哈希

下面是Python实现采用除余留数法的散列函数hash结构：

class Hash:
    def __init__(self,size):
        self.elem=[None]*size
        self.count=size
    def hash(self,value):
        return value%self.count
    def insert_hash(self,key):
        address=self.hash(key)
        while self.elem[address]!=None:
            address=(address+1)%self.count
        self.elem[address]=key
    def search_hash(self,key):
        star=address=self.hash(key)
        while self.elem[address]!=key:
            address=(address+1)%self.count
            if not self.elem[address] or address == star:  # 说明没找到或者循环到了开始的位置
                return False
        return True
 
 
if __name__ == '__main__':
    list_a = [0, 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    hash_table = Hash(len(list_a))
    for i in list_a:
        hash_table.insert_hash(i)
 
    for i in hash_table.elem:
        print((i, hash_table.elem.index(i)))
    print(hash_table.search_hash(15))
    print(hash_table.search_hash(33))