散列表的實現常常叫做散列(hashing)。散列僅支持INSERT,SEARCH和DELETE操作，都是在常數平均時間執行的。需要元素間任何排序信息的操作將不會得到有效的支持。
散列表是普通數組概念的推廣。如果空間允許，可以提供一個數組，為每個可能的關鍵字保留一個位置，就可以運用直接尋址技術。
當實際存儲的關鍵字比可能的關鍵字總數較小時，采用散列表就比較直接尋址更為有效。在散列表中，不是直接把關鍵字用作數組下標，而是根據關鍵字計算出下標，這種
關鍵字與下標之間的映射就叫做散列函數。
一個好的散列函數應滿足簡單移植散列的假設：每個關鍵字都等可能的散列到m個槽位的任何一個中去，并與其它的關鍵字已被散列到哪個槽位無關。
1.1 通常散列表的關鍵字都是自然數。
1.11 除法散列法
通過關鍵字k除以槽位m的余數來映射到某個槽位中。
hash(k)=k mod m
應用除法散列時，應注意m的選擇，m不應該是2的冪，通常選擇與2的冪不太接近的質數。
1.12 乘法散列法
乘法方法包含兩個步驟，第一步用關鍵字k乘上常數A(0<A<1),并取出小數部分，然后用m乘以這個值，再取結果的底(floor)。
hash(k)=floor(m(kA mod 1))
乘法的一個優點是對m的選擇沒有什么特別的要求，一般選擇它為2的某個冪。
一般取A=(√5-1)/2=0.618比較理想。
1.13 全域散列
隨機的選擇散列函數，使之獨立于要存儲的關鍵字。在執行開始時，就從一族仔細設計的函數中，隨機的選擇一個作為散列函數，隨機化保證了
沒有哪一種輸入會始終導致最壞情況發生。
1.2 如果關鍵字是字符串，散列函數需要仔細的選擇
1.2.1 將字符串中字符的ASCII碼值相加
def _hash(key,m): hashVal=0 for _ in key: hashVal+=ord(_) return hashVal%m
由于ascii碼最大127，當表很大時，函數不會很好的分配關鍵字。
1.2.2 取關鍵字的前三個字符。
值27表示英文字母表的字母個數加上一個空格。
hash(k)=k[0]+27*k[1]+729*k[2]
1.2.3 用霍納法則把所有字符擴展到n次多項式。
用32代替27，可以用于位運算。
def _hash(key,m): hashval=0 for _ in key: hashval=(hashval<<5)+ord(_) return hashval%m
散列表會面臨一個問題，當兩個關鍵字散列到同一個值的時候，稱之為沖突或者碰撞(collision)。解決沖突的第一種方法通常叫做分離鏈接法(separate chaining)。
其做法是將散列到同一個值的所有元素保留到一個鏈表中，槽中保留一個指向鏈表頭的指針。
為執行FIND，使用散列函數來確定要考察哪個表，遍歷該表并返回關鍵字所在的位置。
為執行INSERT，首先確定該元素是否在表中。如果是新元素，插入表的前端或末尾。
為執行DELETE，找到該元素執行鏈表刪除即可。
散列表中元素個數與散列表大小的比值稱之為裝填因子(load factor)λ。
執行一次不成功的查找，遍歷的鏈接數平均為λ，成功的查找則花費1+(λ/2)。
分離鏈接散列的一般做法是使得λ盡量接近于1。
代碼：
class _ListNode(object): def __init__(self,key): self.key=key self.next=Noneclass HashMap(object): def __init__(self,tableSize): self._table=[None]*tableSize self._n=0 #number of nodes in the map def __len__(self): return self._n def _hash(self,key): return abs(hash(key))%len(self._table) def __getitem__(self,key): j=self._hash(key) node=self._table[j] while node is not None and node.key!=key : node=node.next if node is None: raise KeyError,'KeyError'+rePR(key) return node def insert(self,key): try: self[key] except KeyError: j=self._hash(key) node=self._table[j] self._table[j]=_ListNode(key) self._table[j].next=node self._n+=1 def __delitem__(self,key): j=self._hash(key) node=self._table[j] if node is not None: if node.key==key: self._table[j]=node.next self._-=1 else: while node.next!=None: pre=node node=node.next if node.key==key: pre.next=node.next self._n-=1 break
在開放定址散列算法中，如果有沖突發生，那么就要嘗試選擇另外的單元，直到找出空的單元為止。
h(k，i)=(h'(k)+f(i)) mod m，i=0,1,...,m-1 ,其中f(0)=0
3.1 線性探測法
函數f(i)是i的線性函數
h(k，i)=(h'(k)+i) mod m
相當于逐個探測每個單元
線性探測會存在一個問題，稱之為一次群集。隨著被占用槽的增加，平均查找時間也會不斷增加。當一個空槽前有i個滿的槽時，該空槽為下一個將被占用
槽的概率是(i+1)/m。連續被占用槽的序列會越來越長，平均查找時間也會隨之增加。
如果表有一半多被填滿的話，線性探測不是個好辦法。
3.2 平法探測
平方探測可以取消線性探測中的一次群集問題。
h(k，i)=(h'(k)+c1i+c2i2) mod m
平方探測中，如果表的一半為空，并且表的大小是質數，保證能夠插入一個新的元素。
平方探測會引起二次群集的問題。
3.3 雙散列
雙散列是用于開放定址法的最好方法之一。
h(k，i)=(h1(k)+ih2(k)) mod m
為能查找整個散列表，值h2(k)要與m互質。確保這個條件成立的一種方法是取m為2的冪，并設計一個總產生奇數的h2。另一種方法是取m為質數，并設計一個總是產生
較m小的正整數的h2。
例如取：
h1(k)=k mod m，h2(k)=1+(k mod m'),m'為略小于m的整數。
給定一個裝填因子λ的開放定址散列表，插入一個元素至多需要1/(1-λ)次探查。
給定一個裝填因子λ<1的開放定址散列表，一次成功查找中的期望探查數至多為(1/λ)ln(1/1-λ)。
如果表的元素填得太滿，那么操作的運行時間將開始消耗過長。一種解決方法是當表到達某個裝填因子時，建立一個大約兩倍大的表，而且使用一個相關的新散列函數，
掃描整個原始散列表，計算每個元素的新散列值并將其插入到新表中。
為避免開放定址散列查找錯誤，刪除操作要采用懶惰刪除。
代碼
class HashEntry(object): def __init__(self,key,value): self.key=key self.value=valueclass HashTable(object): _DELETED=HashEntry(None,None) #用于刪除 def __init__(self,tablesize): self._table=tablesize*[None] self._n=0 def __len__(self): return self._n def __getitem__(self,key): found,j=self._findSlot(key) if not found: raise KeyError return self._table[j].value def __setitem__(self,key,value): found,j=self._findSlot(key) if not found: self._table[j]=HashEntry(key,value) self._n+=1 if self._n>len(self._table)//2: self._rehash() else: self._table[j].value=value def __delitem__(self,key): found,j=self._findSlot(key) if found: self._table[j]=HashTable._DELETED # 懶惰刪除 def _rehash(self): oldList=self._table newsize=2*len(self._table)+1 self._table=newsize*[None] self._n=0 for entry in oldList: if entry is not None and entry is not HashTable._DELETED: self[entry.key]=entry.value self._n+=1 def _findSlot(self,key): slot=self._hash1(key) step=self._hash2(key) firstSlot=None while True: if self._table[slot] is None: if firstSlot is None: firstSlot=slot return (False,firstSlot) elif self._table[slot] is HashTable._DELETED: firstSlot=slot elif self._table[slot].key==key: return (True,slot) slot=(slot+step)%len(self._table) def _hash1(self,key): return abs(hash(key))%len(self._table) def _hash2(self,key): return 1+abs(hash(key))%(len(self._table)-2)
新聞熱點
疑難解答
