哈希表 (hash table) , 可以實(shí)現(xiàn) 的 read, write, update
相對(duì)應(yīng) python 中的 dict, c語(yǔ)言中的 map
其實(shí)數(shù)組也能實(shí)現(xiàn), 只是數(shù)組用來(lái)索引的關(guān)鍵字是下標(biāo), 是整數(shù).
而哈希表就是將各種關(guān)鍵字映射到數(shù)組下標(biāo)的一種"數(shù)組"
<a id="markdown-1-關(guān)鍵字" name="1-關(guān)鍵字"></a>
1. 關(guān)鍵字
由于關(guān)鍵字是用來(lái)索引數(shù)據(jù)的, 所以要求它不能變動(dòng)(如果變動(dòng),實(shí)際上就是一個(gè)新的關(guān)鍵字插入了), 在python 中表現(xiàn)為 imutable. 常為字符串.
<a id="markdown-2-映射" name="2-映射"></a>
2. 映射
<a id="markdown-21-散列函數(shù)hash" name="21-散列函數(shù)hash"></a>
2.1. 散列函數(shù)(hash)
將關(guān)鍵字 k 進(jìn)行映射, 映射函數(shù) , 映射后的數(shù)組地址
.
<a id="markdown-211-簡(jiǎn)單一致散列" name="211-簡(jiǎn)單一致散列"></a>
2.1.1. 簡(jiǎn)單一致散列
- 簡(jiǎn)單一致假設(shè):元素散列到每個(gè)鏈表的可能性是相同的, 且與其他已被散列的元素獨(dú)立無(wú)關(guān).
- 簡(jiǎn)單一致散列(simple uniform hashing): 滿(mǎn)足簡(jiǎn)單一致假設(shè)的散列
好的散列函數(shù)應(yīng) 滿(mǎn)足簡(jiǎn)單一致假設(shè)
例如
<a id="markdown-212-碰撞collision" name="212-碰撞collision"></a>
2.1.2. 碰撞(collision)
由于關(guān)鍵字值域大于映射后的地址值域, 所以可能出現(xiàn)兩個(gè)關(guān)鍵字有相同的映射地址
<a id="markdown-213-str2int-的方法" name="213-str2int-的方法"></a>
2.1.3. str2int 的方法
可以先用 ascii 值,然后
- 各位相加
- 兩位疊加
- 循環(huán)移位
- ...
<a id="markdown-22-直接尋址法" name="22-直接尋址法"></a>
2.2. 直接尋址法
將關(guān)鍵字直接對(duì)應(yīng)到數(shù)組地址, 即
缺點(diǎn): 如果關(guān)鍵字值域范圍大, 但是數(shù)量小, 就會(huì)浪費(fèi)空間, 有可能還不能儲(chǔ)存這么大的值域范圍.
<a id="markdown-23-鏈接法" name="23-鏈接法"></a>
2.3. 鏈接法
通過(guò)鏈接法來(lái)解決碰撞
記有 m 個(gè)鏈表, n 個(gè)元素 為每個(gè)鏈表的期望元素個(gè)數(shù)(長(zhǎng)度)
則查找成功,或者不成功的時(shí)間復(fù)雜度為
如果 , 則上面的鏈接法滿(mǎn)足
的速度
<a id="markdown-231-全域散列universal-hashing" name="231-全域散列universal-hashing"></a>
2.3.1. 全域散列(universal hashing)
隨機(jī)地選擇散列函數(shù), 使之獨(dú)立于要存儲(chǔ)的關(guān)鍵字
<a id="markdown-2311-定義" name="2311-定義"></a>
2.3.1.1. 定義
設(shè)一組散列函數(shù) , 將 關(guān)鍵字域 U 映射到
, 全域的函數(shù)組, 滿(mǎn)足
即從 H 中任選一個(gè)散列函數(shù), 當(dāng)關(guān)鍵字不相等時(shí), 發(fā)生碰撞的概率不超過(guò)
<a id="markdown-2312-性質(zhì)" name="2312-性質(zhì)"></a>
2.3.1.2. 性質(zhì)
對(duì)于 m 個(gè)槽位的表, 只需 的期望時(shí)間來(lái)處理 n 個(gè)元素的 insert, search, delete,其中 有
個(gè)insert 操作
<a id="markdown-2313-實(shí)現(xiàn)" name="2313-實(shí)現(xiàn)"></a>
2.3.1.3. 實(shí)現(xiàn)
選擇足夠大的 prime p, 記
令
則
<a id="markdown-24-開(kāi)放尋址法" name="24-開(kāi)放尋址法"></a>
2.4. 開(kāi)放尋址法
所有表項(xiàng)都在散列表中, 沒(méi)有鏈表.
且散列表裝載因子
這里散列函數(shù)再接受一個(gè)參數(shù), 作為探測(cè)序號(hào)
逐一試探 ,這要有滿(mǎn)足的,就插入, 不再計(jì)算后面的 hash值
探測(cè)序列一般分有三種
- 線(xiàn)性
存在一次聚集問(wèn)題 - 二次
存在二次聚集問(wèn)題 - 雙重探查
為了能查找整個(gè)表, 即要為模 m 的完系, 則 h_2(k)要與 m 互質(zhì).
如可以取
注意刪除時(shí), 不能直接刪除掉(如果有元素插入在其后插入時(shí)探測(cè)過(guò)此地址,刪除后就不能訪(fǎng)問(wèn)到那個(gè)元素了), 應(yīng)該 只是做個(gè)標(biāo)記為刪除
<a id="markdown-241-不成功查找的探查數(shù)的期望" name="241-不成功查找的探查數(shù)的期望"></a>
2.4.1. 不成功查找的探查數(shù)的期望
對(duì)于開(kāi)放尋址散列表,且 ,一次不成功的查找,是這樣的: 已經(jīng)裝填了 n 個(gè), 總共有m 個(gè),則空槽有 m-n 個(gè).
不成功的探查是這樣的: 一直探查到已經(jīng)裝填的元素(但是不是要找的元素), 直到遇到?jīng)]有裝填的空槽. 所以這服從幾何分布, 即
有
<a id="markdown-2411-插入探查數(shù)的期望" name="2411-插入探查數(shù)的期望"></a>
2.4.1.1. 插入探查數(shù)的期望
所以, 插入一個(gè)關(guān)鍵字, 也最多需要 次, 因?yàn)椴迦脒^(guò)程就是前面都是被占用了的槽, 最后遇到一個(gè)空槽.與探查不成功是一樣的過(guò)程
<a id="markdown-2412-成功查找的探查數(shù)的期望" name="2412-成功查找的探查數(shù)的期望"></a>
2.4.1.2. 成功查找的探查數(shù)的期望
成功查找的探查過(guò)程與插入是一樣的. 所以查找關(guān)鍵字 k 相當(dāng)于 插入它, 設(shè)為第 i+1 個(gè)插入的(前面插入了i個(gè),裝載因子. 那么期望探查數(shù)就是
則成功查找的期望探查數(shù)為
代碼
class item:
def __init__(self,key,val,nextItem=None):
self.key = key
self.val = val
self.next = nextItem
def to(self,it):
self.next = it
def __eq__(self,it):
'''using keyword <in> '''
return self.key == it.key
def __bool__(self):
return self.key is not None
def __str__(self):
li = []
nd = self
while nd:
li.append(f'({nd.key}:{nd.val})')
nd = nd.next
return ' -> '.join(li)
def __repr__(self):
return f'item({self.key},{self.val})'
class hashTable:
def __init__(self,size=100):
self.size = size
self.slots=[item(None,None) for i in range(self.size)]
def __setitem__(self,key,val):
nd = self.slots[self.myhash(key)]
while nd.next:
if nd.key ==key:
if nd.val!=val: nd.val=val
return
nd = nd.next
nd.next = item(key,val)
def myhash(self,key):
if isinstance(key,str):
key = sum(ord(i) for i in key)
if not isinstance(key,int):
key = hash(key)
return key % self.size
def __iter__(self):
'''when using keyword <in>, such as ' if key in dic',
the dic's __iter__ method will be called,(if hasn't, calls __getitem__
then ~iterate~ dic's keys to compare whether one equls to the key
'''
for nd in self.slots:
nd = nd.next
while nd :
yield nd.key
nd = nd.next
def __getitem__(self,key):
nd =self.slots[ self.myhash(key)].next
while nd:
if nd.key==key:
return nd.val
nd = nd.next
raise Exception(f'[KeyError]: {self.__class__.__name__} has no key {key}')
def __delitem__(self,key):
'''note that None item and item(None,None) differ with each other,
which means you should take care of them and correctly cop with None item
especially when deleting items
'''
n = self.myhash(key)
nd = self.slots[n].next
if nd.key == key:
if nd.next is None:
self.slots[n] = item(None,None) # be careful
else:self.slots[n] = nd.next
return
while nd:
if nd.next is None: break # necessary
if nd.next.key ==key:
nd.next = nd.next.next
nd = nd.next
def __str__(self):
li = ['\n\n'+'-'*5+'hashTable'+'-'*5]
for i,nd in enumerate(self.slots):
li.append(f'{i}: '+str(nd.next))
return '\n'.join(li)
