抽象数据类型 “映射” ：ADT Map

字典，通过保存key-data键值对的数据类型。 ADT Map的结构是键值关联的无序集合。其中关键码key具有唯一性，通过关键码可以唯一确定一个数据值。 通过散列表构造Map。

class HashTable:
    def __init__(self):
        self.size=11  #可以任意设置，但为了便于求解，应该设为素数
        self.slots=[None]*self.size
        self.data=[None]*self.size
        
    #定义散列函数
    def hashfunction(self,key):
        return key%self.size
    #定义冲突解决方法，简单线性加一
    def rehash(self,oldhash):
        return (oldhash+1)%self.size
    
    def put(self,key,data):
        hashvalue=self.hashfunction(key)
        #key不存在
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        #key已存在
        else:
            #未发生冲突
            if self.slots[hashvalue] == key:
                self.data[hashvalue] == data
            else:  #发生散列冲突
                nextslot=self.rehash(hashvalue)
                while self.slots[nextslot] !=None and self.slots[nextslot] !=key:
                    nextslot=self.rehash(nextslot)
                if self.slots[nextslot] == None:
                    self.slots[nextslot]=key
                    self.data[nextslot]=data
                else:
                    self.data[nextslot]=data

    def get(self,key):
        startslot=self.hashfunction(key)
        pos=startslot
        #空槽时则表示找不到key
        while self.slots[pos]!=None:
            if self.slots[pos]==key: #找到key
                return self.data[pos]
            else:
                pos=self.rehash(pos) #没找到key，找下一个
                if pos==startslot: #回到起点表示没找到key
                    return None
        return None
    #通过设置__getitem__和__setitem__就可以实现形如H[key]的取值和赋值
    def __getitem__(self,key):
        return self.get(key)
    def __setitem__(self,key,data):
        self.put(key,data)
        
if __name__==__main__:
    H=HashTable()    
    H[1]=cat
    H[5]=piajun
    print(H[1])
    print(H[5])
    print(H[2])

输出

cat piajun None

散列在最好的情况下（无冲突），可以提供O(1)时间复杂度的查找性能。 评估散列冲突的最重要信息为负载因子λ，负载因子表示散列表的空间使用程度，一般来说：λ越小，散列冲突概率越小，数据项通常能够保存在自己所属的散列槽中；λ越大，冲突概率会越大，需要通过更多的比较来找到空槽；如果采用数据链，则意味着每条数据链上的数据项增多。

如果采用线性探测（依次往后找空槽）的开放定址法来解决冲突，则λ在0~1之间，

成功的查找，平均比对次数为 1 2 ( 1 + 1 1 − λ ) frac{1}{2}(1+frac{1}{1-lambda}) 21(1+1−λ1) 不成功的查找，平均比对次数为 1 2 ( 1 + ( 1 1 − λ ) 2 ) frac{1}{2}(1+(frac{1}{1-lambda})^2) 21(1+(1−λ1)2)

如果采用数据链来解决冲突（λ可大于1），

成功的查找，平均比对次数为 1 + λ 2 1+frac{lambda}{2} 1+2λ 不成功的查找，平均比对次数为λ