【Python】(十四)Python中的哈希

哈希表

哈希查找是一种以O(1)时间复杂为目标的查找方式,效率极高。Python中的内置的字典结构dictionary,其key值的查找就是采用了哈希查找的方式,因而查询操作能够达到O(1)的时间复杂度。
【Python】(四)Python中的字典
哈希表的构造原则可以总结为一下几点:

  • 哈希表中项的个数最好为质数,这有利于冲突后的重新散列。
  • 散列函数应最大限度的减少“冲突”发生。
  • 在以开放寻址的方式解决冲突问题的同时,也应尽量避免“堆积”问题。
  • 当冲突大量发生时,开放寻址的时间成本将越来越高。此时更适合使用链接解决冲突。

(最近看文章的人越来越多了,不知道概念和原理部分讲的这么少到底行不行……)

用哈希表实现字典

下面我们尝试基于哈希表使用python来实现简单的“字典”结构:

  1. 我们将哈希表的长度设定为素数13。
  2. 哈希函数选择平方取中法和余数法相结合的方式,具体为:将key作为字符串看待,将每个字符的ASCII值相加再平方,所得的结果取中间三位数,最后再将其除以13,所得的余数即为哈希值。
  3. 重新散列函数采用向前间隔为3的线性探测。

具体实现代码如下:

class MyDictionary(object):
    # 字典类的初始化
    def __init__(self):
        self.table_size = 13 # 哈希表的大小
        self.key_list = [None]*self.table_size #用以存储key的列表
        self.value_list = [None]*self.table_size #用以存储value的列表

    # 散列函数,返回散列值
    # key为需要计算的key
    def hashfuction(self, key):
        count_char = 0
        key_string = str(key)
        for key_char in key_string: # 计算key所有字符的ASCII值的和
            count_char += ord(key_char) # ord()函数用于求ASCII值
        length = len(str(count_char))
        if length > 3 : # 当和的位数大于3时,使用平方取中法,保留中间3位
            mid_int = 100*int((str(count_char)[length//2-1])) 
                    + 10*int((str(count_char)[length//2])) 
                    + 1*int((str(count_char)[length//2+1]))
        else: # 当和的位数小于等于3时,全部保留
            mid_int = count_char

        return mid_int%self.table_size # 取余数作为散列值返回

    # 重新散列函数,返回新的散列值
    # hash_value为旧的散列值
    def rehash(self, hash_value):
        return (hash_value+3)%self.table_size #向前间隔为3的线性探测

    # 存放键值对
    def __setitem__(self, key, value):
        hash_value = self.hashfuction(key) #计算哈希值
        if None == self.key_list[hash_value]: #哈希值处为空位,则可以放置键值对
            pass
        elif key == self.key_list[hash_value]: #哈希值处不为空,旧键值对与新键值对的key值相同,则作为更新,可以放置键值对
            pass
        else: #哈希值处不为空,key值也不同,即发生了“冲突”,则利用重新散列函数继续探测,直到找到空位
            hash_value = self.rehash(hash_value) # 重新散列
            while (None != self.key_list[hash_value]) and (key != self.key_list[hash_value]): #依然不能插入键值对,重新散列
                hash_value = self.rehash(hash_value) # 重新散列
        #放置键值对        
        self.key_list[hash_value] = key
        self.value_list[hash_value] = value

    # 根据key取得value
    def __getitem__(self, key):
        hash_value = self.hashfuction(key) #计算哈希值
        first_hash = hash_value #记录最初的哈希值,作为重新散列探测的停止条件
        if None == self.key_list[hash_value]: #哈希值处为空位,则不存在该键值对
            return None
        elif key == self.key_list[hash_value]: #哈希值处不为空,key值与寻找中的key值相同,则返回相应的value值
            return self.value_list[hash_value]
        else: #哈希值处不为空,key值也不同,即发生了“冲突”,则利用重新散列函数继续探测,直到找到空位或相同的key值
            hash_value = self.rehash(hash_value) # 重新散列
            while (None != self.key_list[hash_value]) and (key != self.key_list[hash_value]): #依然没有找到,重新散列
                hash_value = self.rehash(hash_value) # 重新散列
                if hash_value == first_hash: #哈希值探测重回起点,判断为无法找到了
                    return None
            #结束了while循环,意味着找到了空位或相同的key值
            if None == self.key_list[hash_value]: #哈希值处为空位,则不存在该键值对
                return None
            else: #哈希值处不为空,key值与寻找中的key值相同,则返回相应的value值
                return self.value_list[hash_value]

    # 删除键值对
    def __delitem__(self, key):
        hash_value = self.hashfuction(key) #计算哈希值
        first_hash = hash_value #记录最初的哈希值,作为重新散列探测的停止条件
        if None == self.key_list[hash_value]: #哈希值处为空位,则不存在该键值对,无需删除
            return
        elif key == self.key_list[hash_value]: #哈希值处不为空,key值与寻找中的key值相同,则删除
            self.key_list[hash_value] = None
            self.value_list[hash_value] = None
            return
        else: #哈希值处不为空,key值也不同,即发生了“冲突”,则利用重新散列函数继续探测,直到找到空位或相同的key值
            hash_value = self.rehash(hash_value) # 重新散列
            while (None != self.key_list[hash_value]) and (key != self.key_list[hash_value]): #依然没有找到,重新散列
                hash_value = self.rehash(hash_value) # 重新散列
                if hash_value == first_hash: #哈希值探测重回起点,判断为无法找到了
                    return
            #结束了while循环,意味着找到了空位或相同的key值
            if None == self.key_list[hash_value]: #哈希值处为空位,则不存在该键值对
                return
            else: #哈希值处不为空,key值与寻找中的key值相同,则删除
                self.key_list[hash_value] = None
                self.value_list[hash_value] = None
                return

    # 返回字典的长度
    def __len__(self):
        count = 0
        for key in self.key_list:
            if key != None:
                count += 1
        return count

def main():
    H = MyDictionary()
    H["kcat"]="cat"
    H["kdog"]="dog"
    H["klion"]="lion"
    H["ktiger"]="tiger"
    H["kbird"]="bird"
    H["kcow"]="cow"
    H["kgoat"]="goat"
    H["pig"]="pig"
    H["chicken"]="chicken"
    print("字典的长度为%d"%len(H))
    print("键 %s 的值为为 %s"%("kcow",H["kcow"]))
    print("字典的长度为%d"%len(H))
    print("键 %s 的值为为 %s"%("kmonkey",H["kmonkey"]))
    print("字典的长度为%d"%len(H))
    del H["klion"]
    print("字典的长度为%d"%len(H))
    print(H.key_list)
    print(H.value_list)

if __name__ == "__main__":
    main()

运行结果如下:

字典的长度为9
键 kcow 的值为为 cow
字典的长度为9
键 kmonkey 的值为为 None
字典的长度为9
字典的长度为8
[None, 'kgoat', None, 'kcat', 'kbird', 'kdog', None, 'kcow', None, 'ktiger', 'chicken', 'pig', None]
[None, 'goat', None, 'cat', 'bird', 'dog', None, 'cow', None, 'tiger', 'chicken', 'pig', None]

结果是正确的。

IT文库 » 【Python】(十四)Python中的哈希
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址