注：本文如涉及到代碼，均經(jīng)過Python 3.7實(shí)際運(yùn)行檢驗(yàn)，保證其嚴(yán)謹(jǐn)性。
本文閱讀時間約為6分鐘。
映射抽象數(shù)據(jù)類型及Python實(shí)現(xiàn)
在Python字典中，我們可以通過“鍵”訪問對應(yīng)的“值”。字典這種鍵值關(guān)聯(lián)的方法稱為映射（map）。
字典就是這樣一種抽象數(shù)據(jù)類型映射（ADT Map）結(jié)構(gòu)。ADT Map結(jié)構(gòu)是鍵-值關(guān)聯(lián)的集合。在這個集合中，關(guān)鍵碼具有唯一性，我們可以通過關(guān)鍵碼唯一確定一個數(shù)據(jù)值。
抽象數(shù)據(jù)類型映射（ADT Map）定義的操作如下：
- Map()——創(chuàng)建一個空映射，返回空映射對象。
- put(key, val)——將key-val關(guān)聯(lián)對加入到映射中。若映射中key已存在，則val將替換key的舊關(guān)聯(lián)值。
- get(key)——給定key，返回關(guān)聯(lián)的數(shù)據(jù)值。如key不存在，則返回None.
- del——通過del map[key]的語句形式刪除key-val關(guān)聯(lián)。
- len()——返回映射中key-val關(guān)聯(lián)的數(shù)目。
- in——通過key in map的語句形式，返回key是否存在于關(guān)聯(lián)中，布爾值。
字典的優(yōu)勢在于，給定關(guān)鍵碼key，能夠很快找到關(guān)聯(lián)的數(shù)據(jù)值data。
為了達(dá)到快速查找的目標(biāo)，需要一個支持高效查找的ADT（Abstract Data Type，抽象數(shù)據(jù)類型）實(shí)現(xiàn)——可以采用列表數(shù)據(jù)結(jié)構(gòu)加順序查找或者二分查找，當(dāng)然，更為合適的是，使用散列表來實(shí)現(xiàn)，因可以達(dá)到最快O(1)的性能。
實(shí)現(xiàn)抽象數(shù)據(jù)類型映射
下面，我們用一個Hash Table類來實(shí)現(xiàn)ADT Map，該類包含了兩個列表作為成員：一個是slot列表，用于保存key；另一個是平行的data列表，用于保存數(shù)據(jù)項(xiàng)。
在slot列表查找到一個key的位置以后，在data列表對應(yīng)的相對位置的數(shù)據(jù)項(xiàng)即為關(guān)聯(lián)數(shù)據(jù)。
保存key的列表就作為散列表來處理，這樣可以迅速查找指定的key。
注意散列表的大小，雖然可以是任意數(shù)，但考慮到要讓沖突解決算法能有效工作，應(yīng)該選擇為素?cái)?shù)。
hashfunction方法采用了簡單求余方法來實(shí)現(xiàn)散列函數(shù)，而沖突解決則采用線性探測“加1”再散列函數(shù)。
綜上所述，ADT Map的put、get等方法的實(shí)現(xiàn)的完全代碼如下：
# 實(shí)現(xiàn)抽象數(shù)據(jù)類型映射的實(shí)現(xiàn)。
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
# ADT Map的put方法。
def put(self, key, data):
hashvalue = self.hashfunction(key)
if self.slots[hashvalue] == None: # key不存在的情況。
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key: # key存在的情況。
self.data[hashvalue] = data # 替換。
else:
nextslot = self.rehash(hashvalue)
# 散列沖突，再散列，直到找到空槽或者key。
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 hashfunction(self, key):
return key % self.size
def rehash(self, oldhash):
return (oldhash + 1) % self.size
# ADT Map的get方法。
def get(self, key):
startslot = self.hashfunction(key) # 標(biāo)記散列值為查找起點(diǎn)。
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not found and not stop:
# 找到key，直到空槽或者回到起點(diǎn)。
if self.slots[position] == key:
found = True
data = self.data[position]
else: #未找到key，再散列繼續(xù)找。
position = self.rehash(position)
if position == startslot:
stop = True # 沒找到key，回到起點(diǎn)，停下來了。
return data
# 通過特殊方法實(shí)現(xiàn)[]訪問。
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)
H = HashTable()
H[54]="cat"
H[26]="dog"
H[93]="lion"
H[17]="tiger"
H[77]="bird"
H[31]="cow"
H[44]="goat"
H[55]="pig"
H[20]="chicken"
print(H.slots)
print(H.data)
print(H[20])
<<<
[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
chicken
<<<
散列的算法分析
散列在最好的情況下，可以提供O(1)即常數(shù)級的時間復(fù)雜度的查找性能。當(dāng)然，因?yàn)閷?shí)際情況中不免有散列沖突的存在，所以查找比較次數(shù)就沒這么簡單。
評估散列沖突的最重要信息就是負(fù)載因子λ，一般來說：
- 如果λ較小，散列沖突的幾率就小，數(shù)據(jù)項(xiàng)通常會保存在其所屬的散列槽中；
- 如果λ較大，意味著散列表填充較滿，沖突會越來越多，沖突解決也越來越復(fù)雜，也就需要更多的比較來找到空槽；如果采用數(shù)據(jù)項(xiàng)鏈的方式，則意味著每條鏈上的數(shù)據(jù)項(xiàng)增多。
如果采用線性探測的開放定址法來解決沖突問題（λ在0~1之間），則：
- 成功的查找，平均需要比對次數(shù)為：(1+1/(1-λ))/2。
- 不成功的查找，平均比對次數(shù)為：(1+(1/(1-λ))^2)/2。
如果采用數(shù)據(jù)項(xiàng)鏈法來解決沖突問題（λ可大于1），則：
- 成功的查找，平均需要比對次數(shù)為：1+λ/2。
- 不成功的查找，平均比對次數(shù)為：λ。
To be continued.
